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

概念，这样理解起来可能会容易一些。 GP 系统中所有的业务表都是分散的(复制表除外)，这意味着数据被拆分成无重叠 的记录集合。每部分数据存储在一个 Instance 中。数据通过复杂的 HASH 算法分布 到所有 Instance。HASH KEY(一个或者多个)由管理员在定义 Table 时指定。 GP 从底层上来说，通过一系列相关的独立 Database 实现，由一个 Master 和数 GP 使用 MD5 算法对库内存储的 ROLE 的密码进行加密存储，所有 Greenplum Database 管理员指南 V6.2.1 版权所有：Esena(陈淼 +86 18616691889) 编写：陈淼 - 30 - 具有权限查看 pg_authid 系统表的用户都可以看到加密后的密码，不过这些密码都是 经过 MD5 加密后的字符串，由于 MD5 加密算法的不可逆性，查看者无法看到真实的原 密码除了使用 MD5 进行加密，还可以使用 SHA-256 算法进行加密，该算法生成一 个 64 字节的十六进制字符串，前缀为 sha256 字符。MD5 算法生成的加密密码前缀为 md5 字符。pg_authid 系统表中存储的加密密码，是通过对密码拼接用户名之后的字 符串执行相应的加密算法得到的，同时以加密时的加密算法名作为前缀。例如： =# CREATE ROLE name1

引类型等等非常方便，只要按照 API 接口开发，无需对 PG 重新编译。 PG 中 contrib 目录下的各个第三方模块，在 GP 中的 postgis 空间 数据库、R、Madlib、pgcrypto 各类加密算法、gptext 全文检索都 是通过这种方式实现功能扩展的。 4) 在诸如 ACID 事物处理、数据强一致性保证、数据类型支持、独特 的 MVCC 带来高效数据更新能力等还有很多方面，Postgresql Greenplum 功能设计的方方 面面： 外部表数据加载是并行的、 查询计划执行是并行的、索 引的建立和使用是并行的， 统计信息收集是并行的、表 关联（包括其中的重分布或 广播及关联计算）是并行的，排序和分组聚合都是并行的，备份恢复 也是并行的，甚而数据库启停和元数据检查等维护工具也按照并行方 式来设计。得益于这种无所不在的并行，Greenplum 在数据加载和数 据计算中表现出强悍的性能，某行业客户对此深有体会 能和方便性；例如我们在某客户实现的数据转码、数据脱敏等，只需 要简单的改写原有代码后部署到 GP 中，通过并行计算获得数十倍性 能提高。 另外，GPTEXT（lucent 全文检索）、Apache Madlib（开源挖掘算法）、 SAS algorithm、R 都是通过 UDF 方式实现在 Greenplum 集群中分布 式部署，从而获得库内计算的并行能力。这里可以分享的是，SAS 曾 经做过测试，对 1 亿条记录做逻辑回归，采用一台小型机耗时约

um 5 支持适用于数据挖掘和数据科学工作的最全面、 最先进的分析程序包和扩展。 Greenplum 5 还针对最受欢迎的 Python 和 R 语言算法库提供简单易用的安装程序。 • Greenplum 5 中支持的 Python 语言算法库和程序包有：Tensorflow、NumPy、SciPy、scikit-learn、Pandas、 NLTK、Pattern-en、Statsmode PostgreSQL 规划器的衍 生产品。PostgreSQL 规划器最初是为单节点 PostgreSQL 设计的，更适用于 OLTP 查询，而不是分析数据平台中长时间运 行的查询。尽管具有精心设计的连接排序之类的功能，但架构和设计选项导致维护和添加新功能变得越来越难。1 2010 年底，Greenplum 开始在内部开发一款新型查询优化器，并在 Greenplum 4.3.5 版中首次推出，名为 GPORCA。

/share/postgresql/contrib/gp_workfile_mgr.sql 临时空间的监控和管理  GPDB 支持的Join算法主要有： – Hash Join – Nestloop join（非等值关联） – Merge join（排序关联）  大多数关联都是Hash关联，关联是小表被Hash到内存中，如果涉及数据表规模较大，内存不足时， 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 st_makepoint() 计算给定经纬 度方圆2KM的范围 GPText.search() 函数可 以知道是否一个人在 Pivotal工作 Greenplum MADlib BFS 算法可以 知道两个之间是否有直接联系 Greenplum模糊字符串匹 配函数Soundex() 可以 知道姓名是否发音是 ‘Pavan’或‘Peter’ Greenplum Time 函数计算24

mirror可以在建库时建，也可以在建完greenplum后再 添加。 理解greenplum分布式数据库 理解GP分布式数据库 理解GP的数据分布策略 Hash分布：按分布键对数据时行hash分布，这个hash 分布算法没有公布，只有greenplum内部知道数据是如 何hash分布的。 随机分布：数据随机分布在数据库，每次查询都会查询 所有的 segment。 GP的SQL支持程度 基本上绝大多数PostgreSQL支持的SQL，在 式的执行 计划分发到各个segment上，然后segment执行它自己 的特定数据集的本地数据库业务。 所有的数据库操作，如表扫描、表连接（joins)、聚集 （ aggregations），排序，这些操作都会在所有的 segment上并行执行。每个segment执行这些操作时都 不依赖其它的segment。 除了上面这引起典型的数据库操作，Greenplum的 数据库有一个额外的操作类型，称为的motion。

为了尽可能的并⾏处理数据，需要选择能够最⼤化地将数据均匀分布到所有计算节点的策略，⽐如选择 primary key；分布式处理中将会存在本地和分布式协作的操作，当不同的表使⽤相 同的分布键的时候，⼤部分的排序、连接关联操作⼯作将会在本地完成，本地操作往往⽐分布式操作快很多，采⽤随机分布的策略⽆法享受到这个优势。 开发指南 Greenplum数据仓库 UDW Copyright © 2012-2021 87/206 UDW 压缩表必须是追加表。UDW ⽀持两种级别的压缩：表级别和字段级别。⾏式表和列式表对压缩的⽀持也不⼀样。 ⾏式表⽀持表级别的压缩，⽀持的压缩算法有 ZLIB。 列式表⽀持表级别和字段级别的压缩，⽀持的压缩算法有 RLE_TYPE，ZLIB。 RLE_TYPE 的压缩级别 compresslevel 取值从1到4，级别越⾼压缩⽐越⾼。RLE_TYPE适合于有⼤量重复的数据记录。 加。 4. 创建选择率⾼的 B-树索引，对于选择率较低的列，使⽤ Bitmap 索引。 5. 对参与连接操作的列创建索引：对经常⽤于连接的列（例如：外键列）创建索引，可以让查询优化器使⽤更多的连接算法，进⽽提⾼连接效率。 6. 对经常出现在 WHERE 条件中的列创建索引。 7. 避免创建冗余的索引：如果索引开头⼏列重复出现在多个索引中，这些索引就是冗余的。 � 8. 在⼤量数据加载时，删除

7 白皮书 | 7 1. 引领内核创新 云原生调度增强：针对云场景在线和离线业务混合部署场景，创新 CPU 调度算法保障在线业务对 CPU 的实时抢占及抖 动抑制，创新业务优先级 00M 内存回收算法保障在线业务安全可靠运行。 • 新文件系统 EulerFS：面向非易失性内存的新文件系统，采用软更新、目录双视图等技术减少文件元数据同步 时间，提升文件读写性能。 两阶段提交（2PC）。 集群在线扩容 Greenplum 6 实现了不停库在线增加新节点, 期间不会中断正在运行的所有查询；另外采用了 Jump Consistent Hash 的一致性哈希算法, 在数据重分布期间，每个旧节点仅移动出需要移动的数据到新节点上, 得益于创新的分布式死锁检测， 对于大量小表做并行重分布性能提升非常明显。 Greenplum VACUUM 提升 将在 支持适用于数据挖掘和数据科学工作的最 全面、最先进的分析程序包和扩展。Greenplum 还针对最受欢迎的 Python 和 R 语言算法库提供简单易用的安装程 序，包括 Tensorflow、NumPy、SciPy、XGBoost、BeautifulSoup、lxml、Keras 和 PyMC3 等 Python 语言算法 库和程序包和 BH、DBI、MASS、MCMCpack、Matrix、R2jags、R6、RColo

com Greenplum: 机器学习工具集 2017.thegiac.com • PL/X：各种语言实现自定义函数（存储过程） • MADLib: 数据挖掘、统计分析、图（Graph）等算法 • GPText：文本检索和分析 • GeoSpatial：地理信息数据分析 • Image: 图像数据分析 Greenplum 机器器学习⼯工具集 2017.thegiac.com Nearest Neighbors • k-Nearest Neighbors 成熟的数据科学学习库 2017.thegiac.com • 更好的并行度 • 算法充分利用 MPP 架构实现并行 • 更好的可扩展性 • 算法随着数据扩充而线性扩展 • 更高的预测精准度 • 适用更多数据，而不是抽样 • 顶级 ASF 开源项目 • 社区驱动开发模式 MADlib (1M s) 可扩展性 – PageRank 性能 2017.thegiac.com MADlib vs. Spark: 不不同的产品，侧重点不不同 MADlib Spark 算法库 易用性 需要编程 查询优化 成熟度稍差 内存和流处理 通过 Gemfire SQL 语法支持 需要提升 磁盘数据 不是核心焦点 并发性能 不是核心焦点 大数据关联