Greenplum内核揭秘之排序算法 5 ● 内排序算法 ● 外排序算法 ● Greenplum TupleSort ● 排序在Greenplum中的应用 Outline 6 ● 冒泡排序 ● 插入排序 ● 快速排序 ● 堆排序 ● 基数排序 内排序算法 7 快速排序是最常用的排序算法，由Tony Hoare在1959年发明。 快速排序算法的三个步骤： ● 挑选基 挑选基准值：从数列中挑选出一个基准元素，称为pivot ● 分割：重新排序数组，所有比基准元素小的元素排放到基准元素之前；所有比基 准元素大的元素排放到基准元素之后。分割完成后，我们完成了对基准元素的 排序，即基准元素在数组中的位置不再改变 ● 递归排序子序列：递归地将小于基准元素的子序列和大于基准元素的子序列分 别进行排序 快速排序 8 ● 快速排序算法每次选取一个基准元素，将比基准元素小的排到基准元素左边， 比基准元素大的排到基准元素的右边，从而将待排序数组分成两个子集。 快速排序 6 8 3 2 7 1 7 9 8 7 7 9 6 3 2 1 分治法 9 快速排序 ● 快速排序算法： 10 堆排序是最常用的排序算法，由J.Williams在1964年发明。 ● 堆是一种近似完全二叉树的结构，最大值堆要求每个子节点的键值总是小于父 节点。最小值堆要求每个子节点的键值总是大于父节点。 堆排序算法 ● 步骤1：建立最大值堆

....................................................................................... - 373 - 数据模型 .................................................................................................. 之间存储数据的，可以参考下图所示的简单 逻辑关系，主键(Primary Key)被使用黑体标记，外键(Foreign Key)关系通过连 线标明。 用数据仓库的术语来说，这种数据模型称为星型模型。在这种数据库模型下，Order 表通常被称为事实表(Fact Table)，其他表(Customer、Vendor、Product)被称 为维表(Dimension Table)。不管是哪张表，虽然对于用户来说，看起来就是一张 可以选择将临时文件或事务文件转移到一个特殊的表空间从而改善 DB的查询性能、 备份性能、数据读写的性能。GP 数据库通过 temp_tablespaces 参数来控制，用于 Hash Agg，Hash Join，排序操作等临时溢出文件的存储位置。这个目录缺省为 /base/pgsql_tmp，这与 6 之前的版本不同，6 之前的版本，这个目录 缺省为：/base/

0 码力 | 416 页 | 6.08 MB | 1 年前

3

Greenplum 功能设计的方方 面面： 外部表数据加载是并行的、 查询计划执行是并行的、索 引的建立和使用是并行的， 统计信息收集是并行的、表 关联（包括其中的重分布或 广播及关联计算）是并行的，排序和分组聚合都是并行的，备份恢复 也是并行的，甚而数据库启停和元数据检查等维护工具也按照并行方 式来设计。得益于这种无所不在的并行，Greenplum 在数据加载和数 据计算中表现出强悍的性能，某行业客户对此深有体会 Append-only 的特性，SQL-On-Hadoop 大多不 支持数据局部更新和删除功能 (update/delete)；例如 Spark 计算时， 需要预先将数据装载到 DataFrames 模型中； 基本上都缺少索引和存储过程等特征 除 HAWQ 外，大多对于 ODBC/JDBC/DBI/OLEDB/.NET 接口的支持 有限，与主流第三方 BI 报表工具的兼容性不如 MPP 数据库 的任务和用于少数次 的访问，而且主要用于 Batch（不需要交互式），对计算性能不是 很敏感，那 Hadoop 也是不错的选择，因为 Hadoop 不需要你花费 较多的精力来模式化你的数据，节省数据模型设计和数据加载设计 方面的投入。这些系统包括：历史数据系统、ETL 临时数据区、数 据交换平台等等。 切记，千万不要为了大数据而大数据（就好像不要为了创新而创新一 个道理），否则，你项目最后的产出与你的最初设想可能

点时间会很长 – 系统表（pg_class,pg_attribute）太大，影响系统工作效率 – 系统元数据检查pg_checkcat等工具运行时间比较长 物理模型经验分享 物理模型对于系统性能有很大影响，因此需要我们特别关注。 以下来自于在某大型银行的使用经验： 行存储和列存储： • 避免过多使用列存储的原因是防止小档数过多。 • 列存储能够提升查询性 户号，这个可以提高关联条件的命中率，减少关联时数据重分布 （主要对大表） • 选用分布键同时考虑数据平均分布（一个例子，日志号不是最好的分布键，大量的空值导致资料倾斜） 物理模型经验分享（续） 分区表使用： • 不建议使用二级分区，二级分区不便于管理，而且Parser效率较低； • 二级分区可以用一级分区+Bitmap方式替代，例如按照“发生日期”做分区，然后在机构字段上将bitmap索引 gr.sql 临时空间的监控和管理  GPDB 支持的Join算法主要有： – Hash Join – Nestloop join（非等值关联） – Merge join（排序关联）  大多数关联都是Hash关联，关联是小表被Hash到内存中，如果涉及数据表规模较大，内存不足时， GPDB将会生成临时文件，这些档会放在segment的实例目录下pgsql_tmp目录下，GPDB建议保留

Confidential–Internal Use Only 卓越的OLAP特性 列式存储 分区、压缩 高级特性 递归查询、窗口函数 集成分析 多格式、多语言 Madlib: 机器学习 数据库内并行模型训练和预测、分类 ORCA 复杂查询优化器 成熟稳定 完备生态、支撑核心生产系统 13 Pivotal Confidential–Internal Use Only 列式存储 表‘SALES’ 16 Pivotal Confidential–Internal Use Only 窗口函数 表‘SALES’ 表‘SALES’ ■ 计算移动平均值或各种时间 间隔的总和 ■ 分组内重置聚合和排序 SELECT last_name, salary, department, rank() OVER w FROM employees WINDOW 优化分布式大数据系统中特别复杂的查询 18 Madlib: 迭代并行模型训练 Master model = init(…) WHILE model not converged model = SELECT model.aggregation(…) FROM data table ENDWHILE 模型存储过程 … 广播 Segment 2 Segment

的表格创建类似于 postgresql，由于 udw 采⽤ mpp 数据，创建表格的时候可以选择不同的数据分布策略，不同的存储⽅式等等。创建表格的时候可以定义下⾯信息： 数据类型 表约束 数据分布策略 表存储模型 分区策略 外部表：udwfile、udwhdfs 下⾯分别根据上⾯的可选信息对表格设计进⾏分析。 4.1 数据类型 数据类型 开发指南 Greenplum数据仓库 UDW Copyright 为了尽可能的并⾏处理数据，需要选择能够最⼤化地将数据均匀分布到所有计算节点的策略，⽐如选择 primary key；分布式处理中将会存在本地和分布式协作的操作，当不同的表使⽤相 同的分布键的时候，⼤部分的排序、连接关联操作⼯作将会在本地完成，本地操作往往⽐分布式操作快很多，采⽤随机分布的策略⽆法享受到这个优势。 开发指南 Greenplum数据仓库 UDW Copyright © 2012-2021 2012-2021 UCloud 优刻得 85/206 备注：更多关于分区策略的的使⽤可以通过命令⾏执⾏\h create table 或者 \h alter table 查看 4.4 表存储模型（ 表存储模型（heap表和 表和appendonly表） 表） UDW ⽀持两种类型的表：堆表（heap table）和追加表（Appendonly table）。默认创建的是堆表。 堆表（heap

集成分析：改进后的全新分析接口 一直以来，客户都能在 Pivotal Greenplum 中做高级分析，无论是提供将应用逻辑向下推送至数据所在位置的方法，执行 分析功能，还是以大规模并行方式构建数据模型，都可以实现。Greenplum 5 支持适用于数据挖掘和数据科学工作的最全面、 最先进的分析程序包和扩展。 Greenplum 5 还针对最受欢迎的 Python 和 R 语言算法库提供简单易用的安装程序。 PostgreSQL 规划器的衍 生产品。PostgreSQL 规划器最初是为单节点 PostgreSQL 设计的，更适用于 OLTP 查询，而不是分析数据平台中长时间运 行的查询。尽管具有精心设计的连接排序之类的功能，但架构和设计选项导致维护和添加新功能变得越来越难。1 2010 年底，Greenplum 开始在内部开发一款新型查询优化器，并在 Greenplum 4.3.5 版中首次推出，名为 GPORCA。

式的执行 计划分发到各个segment上，然后segment执行它自己 的特定数据集的本地数据库业务。 所有的数据库操作，如表扫描、表连接（joins)、聚集 （ aggregations），排序，这些操作都会在所有的 segment上并行执行。每个segment执行这些操作时都 不依赖其它的segment。 除了上面这引起典型的数据库操作，Greenplum的 数据库有一个额外的操作类型，称为的motion。

generate_series(1,30:: bigint) AS ID) foo DISTRIBUTED BY (id); 2017.thegiac.com 2017.thegiac.com • 适合模型应用于数据子集的场景，并行执行效率非常高 • 如果节点间数据通讯，使用 适⽤用场景 2017.thegiac.com MADlib 2017.thegiac.com 强⼤大的分析能⼒力力 2017.thegiac.com ⽤用户案例例 1 Greenplum + MADlib 助⼒力力邮件营销 2017.thegiac.com 问题 ● 邮件⼴广告点击预测 模型不不够精准，需 要更更好的邮件营销 策略略 ● 现有数据分析流程 繁琐，速度慢，有 很多⼿手动步骤，易易 出错 客户 数据科学解决⽅方案 ● 某⼤大型跨国多元 化传媒和娱乐公 逻辑回归 计算 KS 分值 模型验证 ⼿手动预测 1 2 3 4 5 6 7 8 原始⼯工作流程 2017.thegiac.com 数据整理理 特征⽣生成 验证 预测 信息价值 ⽅方差膨胀 因⼦子 成对相关性 逻辑回归 Elastic Net 特征选择 模型 1 2 3 4 5

Confidential │ ©2021 VMware, Inc. Greenplum 分布式执行器 QD/QE/火山模型/Gang Confidential │ ©2021 VMware, Inc. 25 Greenplum，或者说 PostgreSQL 是进程模型，而不是类似于 MySQL 的线程模型。 主进程 postmaster 是整个数据库实例的总控进程，负责启动和关闭数据库实例。当客户端和 Coordinator 发来的计划树，对每一个节点按照拉模型 (火山模型) 进行执行。 QD && QE Confidential │ ©2021 VMware, Inc. 26 QD && QE Confidential │ ©2021 VMware, Inc. 27 火山模型，或者说拉模型，是指从最顶层的输出节点开始，不断从下层节点拉取数据，一种自顶向 下的执行方式。最常见的拉模型是 Tuple-At-A-Ti Greenplum、PostgreSQL、MySQL 以及 Oracle 等主流数据库均采用拉模型。 拉模型的每个算子都实现了从下层节点获取一条元组的 GetNext 函数，每次调用该函数都会从下 层节点返回一条元组或者 EOF 的 NULL 指针。上层节点不断地调用 GetNext 函数从下层节点获 取数据，直至数据全部获取完毕。 火山模型 postgres=# explain select * from t order