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

供一些帮助，在编写过程 中，仍会参考官方文档，但绝不是简单的翻译，甚至有些内容会与官方文档不一致。 编者提醒，升级版本极其重要，4 版本早该淘汰了，5 版本和 6 版本都带来了极大 的性能和稳定性的提升。 声明 本文档的版权归[陈淼]个人所有，未经许可和授权不得抄袭和引用。 本文档中的绝大部分内容都经过编者重新考量和实测验证，有些观点与官方手册有 出入，仅代表编者 协议。这是经过改善的 UDP 协议，在 UDP 协 议的基础上增强了数据包校验，其可靠性与 TCP 协议相似，但其性能和扩展性远好于 TCP 协议。当集群规模较小，同时，网络的稳定性较差的时候，如果 UDPIFC 协议不 稳定，可以考虑使用 TCP 协议，例如只有几十台主机时。通常，还是强烈建议配备稳 定的网络环境，使用 UDPIFC 协议。 冗余与故障切换 GP 提供了避免单点故障的部署选项。本节讲述 确保计算节点机器的资源不会被耗尽，否则，都应该尽最大可能避免 Master 和 Standby 设置到 Instance 主机上，因为，这种模式下，一旦系统在处理负载很高的 任务，Master 将很难获得足够的资源，其响应会变慢，稳定性会下降。从两一个角度 来说，如果可以确保集群是非常良性的运转，不会有任务造成 Master 很大的压力， 可以适当配置计算能力稍差的机器。 网络层冗余 网络层关系到 Instance

Greenplum 功能设计的方方 面面： 外部表数据加载是并行的、 查询计划执行是并行的、索 引的建立和使用是并行的， 统计信息收集是并行的、表 关联（包括其中的重分布或 广播及关联计算）是并行的，排序和分组聚合都是并行的，备份恢复 也是并行的，甚而数据库启停和元数据检查等维护工具也按照并行方 式来设计。得益于这种无所不在的并行，Greenplum 在数据加载和数 据计算中表现出强悍的性能，某行业客户对此深有体会 SQL-On-Hadoop 不擅长于交互式（interactive）的 Ad-hoc 查询， 大多通过预关联的方式来规避这个问题；另外，在并发处理方面的能 力较弱。高并发场景下，需要控制计算请求的并发度，避免资源过载 导致的稳定性问题和性能下降问题。 3) 架构灵活性的对比 前面提到，为保证数据的高性能计算，MPP 数据库节点和数据之 间是紧耦合的，相反，Hadoop 的节点和数据是没有耦合关系的。 这就决定了 Hadoop 在短短的两年半时间里，该客户已经选择了多个厂商的 PC 服务器用 于部署 Greenplum，包括 DELL、HP、IBM 等等，且在单个集群混合 了不同厂商不同型号的服务器。Greenplum 数据库在这些硬件上的表 现都很稳定。 开放性的特性给客户带来的好处，不只是硬件厂商和型号的选择范围， 也包含工程实施过程的便利性。2014 年，该客户大数据平台需要进行 数据搬迁，Greenplum 采用了旧环境数据备份、传输、新环境恢复的

发起一个请求时，每个Instance都将FORK子进 程并行工作； • 对于并发请求高、面向于复杂的灵活查询的系 统，建议每个Segment配置4个或以下Instance， 这样来保证每个Instance所需资源，保证系统 系统运行稳定性，例如，减少OOM发生的概率； • 对于以批处理、串行工作为主的系统，可以配 置到8个Instance，这样可以尽可能的发挥每个 CPU的处理性能。 Master query plan  GPDB内部的对象：所有的表（包括分区表）、索引、视图等都称为对象  GPDB最佳实践所推荐的对象管理要求是：一个数据库内对象不要超过10 0000个  最佳实践是出于对系统性能和稳定性因素建议对pg_class 所维护的对象数进行约束  减少对象数的方法： – 提高分区粒度 – 避免大范围使用列存储  pg_class对象数如果不进行约束，可能会产生以下问题： gr.sql 临时空间的监控和管理  GPDB 支持的Join算法主要有： – Hash Join – Nestloop join（非等值关联） – Merge join（排序关联）  大多数关联都是Hash关联，关联是小表被Hash到内存中，如果涉及数据表规模较大，内存不足时， GPDB将会生成临时文件，这些档会放在segment的实例目录下pgsql_tmp目录下，GPDB建议保留

支持完善，几乎所有 PostgreSQL支持的SQL， gp都支持。 支持有限的SQL，查询 支持子查询，但不支持 窗口函数。大部分dml都 不支持，只支持append。 稳定性 有较多的bug。 比较稳定。 Greenplum架构图 Segment Host Segment Host Segment Host Segment Host 高 速 以 太 网 交 换 联起来的，外部用户不需要访问这个内部网络的。 Segment 与Segment之间是有网络连接的，所以 Segment之间可以直接交互数据的。 Greenplum默认使用UDP协议，不过我们发现UDP有 时不稳定，我们一般都使用TCP协议。使用TCP协议， greenplum最多1000个segment。 Greenplum中的高可用方案 Segment的mirror 当配置了segment mirror，当segment 式的执行 计划分发到各个segment上，然后segment执行它自己 的特定数据集的本地数据库业务。 所有的数据库操作，如表扫描、表连接（joins)、聚集 （ aggregations），排序，这些操作都会在所有的 segment上并行执行。每个segment执行这些操作时都 不依赖其它的segment。 除了上面这引起典型的数据库操作，Greenplum的 数据库有一个额外的操作类型，称为的motion。

卓越的OLAP特性 列式存储 分区、压缩 高级特性 递归查询、窗口函数 集成分析 多格式、多语言 Madlib: 机器学习 数据库内并行模型训练和预测、分类 ORCA 复杂查询优化器 成熟稳定 完备生态、支撑核心生产系统 13 Pivotal Confidential–Internal Use Only 列式存储 表‘SALES’ 表‘SALES’ ■ 更适合压缩 ■ 查询部分列时速度快 16 Pivotal Confidential–Internal Use Only 窗口函数 表‘SALES’ 表‘SALES’ ■ 计算移动平均值或各种时间 间隔的总和 ■ 分组内重置聚合和排序 SELECT last_name, salary, department, rank() OVER w FROM employees WINDOW group rg1 (cpu_rate_limit=20, memory_limit=10, concurrency=5) 资源管理：CPU使用受限和超限 资源管理：CPU，短查询延迟 ■ 更稳定延迟，CPUSET特性：create resource group rg1 (cpu_set=’4,5’, memory_limit=10, concurrency=5) 资源管理：内存 ■ 隔离

HTAP 特性，具备良好性能、可靠性和稳定性，使得 Greenplum 不仅可以作为全能的分析化平台，也能满足交易型业 务场景，能够处理多种并发混合工作负载，专为满足在多结构数据环境中进行实时分析的需求而设计。 欧拉开源操作系统是一款面向数字基础设施的操作系统，支持服务器、云计算、边缘计算、嵌入式等应用场景，支持多 样性计算，致力于提供安全、稳定、易用的操作系统。 Greenplum 欧拉开源操作系统 欧拉开源操作系统（openEuler, 简称“欧拉”）从服务器操作系统正式升级为面向数字基础设施的操作系统，支持服务 器、云计算、边缘计算、嵌入式等应用场景，支持多样性计算，致力于提供安全、稳定、易用的操作系统。通过为应用 提供确定性保障能力，支持 OT 领域应用及 OT 与 ICT 的融合。 欧拉开源社区通过开放的社区形式与全球的开发者共同构建一个开放、多元和架构包容的软件生态体系，孵化支持多种 处理器架构、覆盖数字设施全场景，推动企业数字基础设施软硬件、应用生态繁荣发展。 openEuler 作为一个操作系统发行版平台，每两年推出一个 LTS 版本。该版本为企业级用户提供一个安全稳定可靠的 操作系统。 openEuler 也是一个技术孵化器。通过每半年发布一次的创新版，快速集成 openEuler 以及其他社区的最新技术成 果，将社区验证成熟的特性逐步回合到发行

续发布和质量内建。2017 年 Greenplum 发布了 10 个版本，以前发布一个版本需要 1 个 月左右，现在只需要十几个小时。 ● 具备企业级稳定性的平台：Greenplum 经过十多年发展，有大量活跃客户，大量数百节点 集群为全球 2000 强企业生产系统提供服务，稳定性非常高。 ● 具备成熟生态系统的平台：Greenplum 生态非常完善，有大量的合作伙伴。 发展历程 Greenplum ，通过使用站立会议、 回顾会议、结对编程、持续集成、测试驱动、单周迭代等敏捷方法建立了高效的快速反馈系统， 大大提高了产品的质量和客户的满意度。Greenplum 5.0 是开源之后发布的第一个稳定版本，大 约保持 1 个半月一个版本的发布速度。Greenplum 主干分支（master）开发非常活跃，众多社区 期待的特性稳健推进中，包括内核升级、新课题，处于业界领先地位。 Greenplum

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

ApsaraDB for GP的定位 ApsaraDB for GP = 简单、高效解决大数据分析需求 MPP + 列存压缩 复杂SQL + 查询优化器 本地高效存储 +高速网络 +预置稳定资源 = = 2016Postgres中国用户大会 GP vs. RDS? Select count(*) from customer group by city Return Hash ApsaraDB for GP的定位 ApsaraDB for GP = 简单、高效解决大数据分析需求 MPP + 列存压缩 复杂SQL + 查询优化器 本地高效存储 +高速网络 +预置稳定资源 = = 2016Postgres中国用户大会 ApsaraDB for GP的内核优化 2016Postgres中国用户大会 ApsaraDB for GP架构 ApsaraDB