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：建立最大值堆

可以选择将临时文件或事务文件转移到一个特殊的表空间从而改善 DB的查询性能、 备份性能、数据读写的性能。GP 数据库通过 temp_tablespaces 参数来控制，用于 Hash Agg，Hash Join，排序操作等临时溢出文件的存储位置。这个目录缺省为 /base/pgsql_tmp，这与 6 之前的版本不同，6 之前的版本，这个目录 缺省为：/base/排序、聚合等算子， 如果能够在Instance本地完成，其效率将高于需要从其他Instance获取数据的 操作。当不同的Table使用相同的DK时，在DK上的关联或者排序操作将会以最高 效的方式把绝大部分工作在Instance本地完成。若Table使用随机分布策略，将 会出现更多的数据 PARTITION FOR ('2020-01-01'); 注意：在将RANK(1)的分区删除后，其余分区的rank值仍然是从1开始的连续编号。 编号的顺序按照分区字段的值由小到大从1开始排序，不管分区是否连续(所有的 START和END之间没有空缺即为连续)，所以，在真实的项目场景中，要绝对杜绝这种 删除分区的方式，要使用partition name或者value的方式来匹配分区。

Greenplum 功能设计的方方 面面： 外部表数据加载是并行的、 查询计划执行是并行的、索 引的建立和使用是并行的， 统计信息收集是并行的、表 关联（包括其中的重分布或 广播及关联计算）是并行的，排序和分组聚合都是并行的，备份恢复 也是并行的，甚而数据库启停和元数据检查等维护工具也按照并行方 式来设计。得益于这种无所不在的并行，Greenplum 在数据加载和数 据计算中表现出强悍的性能，某行业客户对此深有体会 关联，将一张表按照关联字段 Hash 到内存中，形成 Key-Value 散列，在扫描另外一张表的时候到散列中做匹配。 这种是 Merge 关联，会将关联的两张表先按照关联字段做排序，通常 在内存不吃紧的情况下，排序算法不如 Hash 算法快。 这种是 Nested Loop 关联，等于是两张表做了笛卡尔积复杂度的匹配。 Big Date2.indd 45 16-11-22 下午3:38

gr.sql 临时空间的监控和管理  GPDB 支持的Join算法主要有： – Hash Join – Nestloop join（非等值关联） – Merge join（排序关联）  大多数关联都是Hash关联，关联是小表被Hash到内存中，如果涉及数据表规模较大，内存不足时， GPDB将会生成临时文件，这些档会放在segment的实例目录下pgsql_tmp目录下，GPDB建议保留 ），还是整個系统挂起 – 确定是否有锁等待或资源队列排队导致SQL长时间不能完成 – 确定是否整体性能慢，还是某一个SQL导致（在pg_stat_activity中按照query_start排序，检查时间最长的SQL)  检查硬件和OS状态 – 查看command Centre中系统监控情況 – MegaCli检查磁片和Raid卡状态 – 检查OS是否有硬件错误告警 –

16 Pivotal Confidential–Internal Use Only 窗口函数 表‘SALES’ 表‘SALES’ ■ 计算移动平均值或各种时间 间隔的总和 ■ 分组内重置聚合和排序 SELECT last_name, salary, department, rank() OVER w FROM employees WINDOW

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

PostgreSQL 规划器的衍 生产品。PostgreSQL 规划器最初是为单节点 PostgreSQL 设计的，更适用于 OLTP 查询，而不是分析数据平台中长时间运 行的查询。尽管具有精心设计的连接排序之类的功能，但架构和设计选项导致维护和添加新功能变得越来越难。1 2010 年底，Greenplum 开始在内部开发一款新型查询优化器，并在 Greenplum 4.3.5 版中首次推出，名为 GPORCA。

为了尽可能的并⾏处理数据，需要选择能够最⼤化地将数据均匀分布到所有计算节点的策略，⽐如选择 primary key；分布式处理中将会存在本地和分布式协作的操作，当不同的表使⽤相 同的分布键的时候，⼤部分的排序、连接关联操作⼯作将会在本地完成，本地操作往往⽐分布式操作快很多，采⽤随机分布的策略⽆法享受到这个优势。 开发指南 Greenplum数据仓库 UDW Copyright © 2012-2021