注册了域名之后怎么做网站,文汇网站建设,百度搜索引擎下载,网站建设制作设计JOIN 一直是数据库性能优化的老大难问题#xff0c;本来挺快的查询#xff0c;一旦涉及了几个 JOIN#xff0c;性能就会陡降。而且#xff0c;参与 JOIN 的表越大越多#xff0c;性能就越难提上来。
其实#xff0c;让 JOIN 跑得快的关键是要对 JOIN 分类#xff0c;分…JOIN 一直是数据库性能优化的老大难问题本来挺快的查询一旦涉及了几个 JOIN性能就会陡降。而且参与 JOIN 的表越大越多性能就越难提上来。
其实让 JOIN 跑得快的关键是要对 JOIN 分类分类之后就能利用各种类型 JOIN 的特征来做性能优化了。
JOIN 分类
有 SQL 开发经验的同学都知道绝大多数 JOIN 都是等值 JOIN也就是关联条件为等式的 JOIN。非等值 JOIN 要少见得多而且多数情况也可以转换成等值 JOIN 来处理所以我们可以只讨论等值 JOIN。
等值 JOIN 主要又可以分为两大类外键关联和主键关联。
外键关联是指用一个表的非主键字段去关联另一个表的主键前者称为事实表后者为维表。比如下图中订单表是事实表客户表、产品表、雇员表是维表。 外键表是多对一关系而且是不对称的事实表和维表的位置不能互换。需要说明的是这里说的主键是指逻辑上的主键也就是在表中取值唯一、可以用于唯一确定某条记录的字段或字段组不一定在数据库表上建立过主键。
主键关联是指用一个表的主键关联另一个表的主键或部分主键。比如下图中客户和 VIP 客户、订单表和订单明细表的关联。 客户和 VIP 客户按照主键关联这两个表互为同维表。订单则是用主键去关联明细的部分主键我们称订单表是主表明细表是子表。
同维表是一对一关系。且同维表之间是对称的两个表的地位相同。主子表则是一对多关系而且是不对称的有明确的方向。
仔细观察会发现这两类 JOIN 都涉及到主键了。而不涉及主键的 JOIN 会导致多对多关系大多数情况都没有业务意义。换句话说上述这两大类 JOIN 涵盖了几乎全部有业务意义的 JOIN。如果我们能利用 JOIN 总会涉及主键这个特征做性能优化能解决掉这两大类 JOIN其实也就意味着解决了大部分 JOIN 性能问题。
但是SQL 对 JOIN 的定义并不涉及主键只是两个表做笛卡尔积后再按某种条件过滤。这个定义很简单也很宽泛几乎可以描述一切。但是如果严格按这个定义去实现 JOIN也就没办法在性能优化时利用主键的特征了。
SPL 改变了 JOIN 的定义专门针对这两大类 JOIN 分别处理利用了主键的特征减少运算量从而实现性能优化的目标。
下面我们来看看 SPL 具体是怎么做的。
外键关联
如果事实表和维表都不太大可以全部装入内存SPL 提供了外键地址化方法先把事实表中的外键字段值转换为对应维表记录的地址之后引用维表字段时就可以用地址直接取出了。
以前面的订单表、雇员表为例假定这两个表已经被读入内存。外键地址化的工作机制是这样的对于订单表某记录 r 的 eid 字段到雇员表中找到这个 eid 字段值对应的记录得到其内存地址 a再将 r 的 eid 字段值替换成 a。对订单表的所有记录都做好这样的转换就完成了外键地址化。这时候订单表记录 r 要引用雇员表字段时直接用 eid 字段存储的地址 a 取出雇员表记录和字段就可以了相当于常数时间内就能取得雇员表的字段不需要再到雇员表做查找。
可以在系统启动时把事实表和维表读入内存并一次性做好外键地址化即预关联。这样在后续关联计算时就能直接用事实表外键字段中的地址去取维表记录完成高性能的 JOIN 计算。
外键地址化和预关联的详细原理请参考【性能优化】6.1 [外键关联] 外键地址化
SQL 通常使用 HASH 算法来做内存连接需要计算 HASH 值和比对性能会比直接用地址读取差很多。
SPL 之所以能实现外键地址化是利用了维表的关联字段是主键这一特征。上面例子中关联字段 eid 是雇员表的主键具有唯一性。订单表中的每个 eid 只会唯一对应一条雇员记录所以才能把每个 eid 转换成它唯一对应的那条雇员记录的地址。
而 SQL 对 JOIN 的定义中没有主键的约定就不能认定与事实表中外键关联的维表记录有唯一性有可能发生与多条记录关联的情况。对于订单表的记录来讲eid 值没有办法唯一对应一条雇员记录就无法做到外键地址化了。而且 SQL 也没有记录地址这种数据类型结果会导致每次关联时还是要计算 HASH 值并比对。
只是两个表 JOIN 时外键地址化和 HASH 关联的差别还不是非常明显。这是因为 JOIN 并不是最终目的JOIN 之后还会有其它很多运算JOIN 本身运算消耗时间的占比相对不大。但事实表常常会有多个维表甚至维表还会有很多层。比如订单关联产品产品关联供应商供应商关联城市城市关联国家等等。在关联表很多时外键地址化的性能优势会更明显。
下面的测试在关联表个数不同的情况下对比 SPL 与 Oracle 的性能差异可以看出在表很多时外键地址化的优势相当明显 测试的详细情况请参考性能优化技巧预关联。
对于只有维表能装入内存而事实表很大需要外存的情况SPL 提供了外键序号化方法预先将事实表中的外键字段值转换为维表对应记录的序号。关联计算时分批读入新事实表记录再用序号取出对应维表记录。
以上述订单表、产品表为例假定产品表已经装入内存订单表存储在外存中。外键序号化的过程是这样先读入一批订单数据设其中某记录 r 中的 pid 对应的是内存中产品表的第 i 条记录。我们要将 r 中的 pid 字段值转换为 i。对这批订单记录都完成这样的转换后再做关联计算时从外存中分批读入订单数据。对于其中的记录 r就可以直接根据 pid 值去内存中的产品表里用位置取出相应的记录也避免了查找动作。
外键序号化原理更详细的介绍参考【性能优化】6.3 [外键关联] 外键序号化。
数据库通常会把小表读入内存再分批读入大表数据用哈希算法做内存连接需要计算哈希值和比对。而 SPL 使用序号定位是直接读取不需要进行任何比对性能优势比较明显。虽然预先把事实表的外键字段转换成序号需要一定成本但这个预计算只需要做一次而且可以在多次外键关联中得到复用。
SPL 外键序号化同样利用了维表关联字段是主键的特征。如前所述SQL 对 JOIN 的定义没有主键的约定无法利用这一特征做到外键序号化。另外SQL 使用无序集合的概念即使我们事先把外键序号化了数据库也无法利用这个特点不能在无序集合上使用序号快速定位的机制最快也就是用索引查找。而且数据库并不知道外键被序号化了仍然会去计算 HASH 值和比对。
下面这个测试在不同并行数情况下对比 SPL 和 Oracle 完成大事实表、小维表关联计算的速度SPL 跑的比 Oracle 快 3 到 8 倍。测试结果见下图 这个测试更详细的信息请参考性能优化技巧外键序号化。
如果维表很大也需要外存而事实表较小能装入内存SPL 则提供了大维表查找机制。如果维表和事实表都很大SPL 则使用单边分堆算法。对于维表过滤后再关联的情况SPL 提供了索引复用方法及对位序列等方法。
数据量大到需要分布式计算时如果维表较小SPL 采用复写维表机制将维表在集群节点上复制多份如果维表很大则采用集群维表方法以保证随机访问。这两种方法都可以有效的避免 Shuffle 动作。相比而言SQL 体系下不能区分出维表HASH 拆分方法要将两个表都做 Shuffle 动作网络传输量要大得多。
主键关联
主键关联涉及的表一般都比较大需要存储在外存中。SPL 为此提供了有序归并方法预先将外存表按照主键有序存储关联时顺序取出数据做归并计算。
以客户和 VIP 客户两个表做内连接为例假设已经预先将两个表按照主键 cid 有序存储在外存中。关联时从两个表的游标中读取记录逐条比较 cid 值。如果 cid 相等则将两表的记录合并成结果游标的一条记录返回。如果不相等则 cid 小的那个游标再读取记录继续判断。重复这些动作直到任何一个表的数据被取完返回的游标就是 JOIN 的结果。
对于两个大表关联数据库通常使用哈希分堆算法复杂度是乘法级的。而有序归并算法复杂度是加法级性能会好很多。而且数据库做大数据的外存运算时哈希分堆会产生缓存文件的读写动作。有序归并算法则只需要对两个表依次遍历不必借助外存缓存可以大幅降低 IO 量有巨大的性能优势。
预先按照主键排序的成本虽高但是一次性做好即可以后就总能使用归并算法实现 JOIN性能可以提高很多。同时SPL 也提供了在有追加数据时仍然保持数据整体有序的方案。
这类 JOIN 的特征在于关联字段是主键或部分主键有序归并算法正是根据这个特征来设计的。因为不管是同维表还是主子表关联字段都不会是主键之外的其他字段所以我们将关联表按照主键有序这一种方式排序存储就可以了不会出现冗余。而外键关联就不具备这个特征不能使用有序归并。具体来说是因为事实表的关联字段不是主键会存在多个要参与关联的外键字段我们不可能让同一个事实表同时按多个字段都有序。
SQL 对 JOIN 的定义不区分 JOIN 类型不假定某些 JOIN 总是针对主键的就没办法从算法层面上利用主键关联的特征。而且前面说过 SQL 基于无序集合概念数据库不会刻意保证数据的物理有序性很难实施有序归并算法。
有序归并算法的优势还在于易于分段并行。以订单和订单明细按 oid 关联为例假如将两表都按照记录数大致平均分为 4 段订单第 2 段的 oid 有可能会出现在明细第 3 段类似的错位会导致错误的计算结果。SPL 再次利用主键 oid 的有序性提供同步分段机制解决了这个问题先将有序的订单表分为 4 段再找到每一段起止记录的 oid 值形成 4 个区间将明细表也分成同步的 4 段。这样在并行计算时两表对应分段就不会出现错位了。由于明细表也对 oid 有序可以迅速地按照起止 oid 定位不会降低有序归并的性能。
有序归并和同步分段并行的原理详见SPL 有序归并关联。
传统的 HASH 分堆技术实现并行就比较困难了多线程做 HASH 分堆时需要同时向某个分堆写出数据造成共享资源冲突而下一步实现某组分堆关联时又会消费大量内存无法实施较大的并行数量。
实际测试证明在相同情况下我们对两个大表做主键关联测试详情参见性能优化技巧有序归并结果是 SPL 比 Oracle 快了近 3 倍 除了有序归并SPL 还提供了很多高性能算法全面提高主键关联 JOIN 的计算速度。包括附表机制可以将多表一体化存储减少存储数据量的同时还相当于预先完成了关联不需要再比对了关联定位算法实现先过滤再关联可以避免全表遍历获得更好的性能等等。
当数据量继续增加需要多台服务器集群时SPL 提供复组表机制将需要关联的大表按照主键分布到集群节点上。相同主键的数据在同一节点避免分机之间的数据传输也不会出现 Shuffle 动作。
回顾与总结
回顾上面两大类、各场景 JOIN采用 SPL 分情况提供的高性能算法可以利用不同类型 JOIN 的特征提速让 JOIN 跑得更快。SQL 对上述这么多种 JOIN 场景笼统的处理就没办法针对不同 JOIN 的特征来实施这些高性能算法。比如事实表和维表都装入内存时SQL 只能按照键值计算 HASH 和比对无法利用地址直接对应SQL 数据表无序在大表按照主键关联时无法做到有序归并只能使用 HASH 分堆有可能会出现多次缓存的现象性能有一定的不可控性。
并行计算方面SQL 单表计算时还容易做到分段并行多表关联运算时一般就只能事先做好固定分段很难做到同步动态分段这就难以根据机器的负载临时决定并行数量。
对于集群运算也是这样SQL 在理论上不区分维表和事实表要实现大表 JOIN 就会不可避免地产生占用大量网络资源的 HASH Shuffle 动作在集群节点数太多时网络传输造成的延迟会超过节点多带来的好处。
SPL 设计并应用了新的运算和存储模型可以在原理和实现上解决 SQL 的这些问题。对于 JOIN 的不同分类和场景程序员有针对性的采取上述高性能算法就能获得更快的计算速度让 JOIN 跑得更快。
SPL资料
SPL官网SPL下载SPL源代码
欢迎对SPL有兴趣的加小助手VX号SPL-helper进SPL技术交流群
