知识卡片

结构图卡

三种连接策略:嵌套循环、排序合并、散列连接

理解等级:未标注

当涉及多表连接(INNER/OUTER/CROSS JOIN,PostgreSQL默认INNER,指定LEFT/RIGHT/FULL会自动转为OUTER)时,计划器要在三种连接策略之间做选择。嵌套循环:对外部表的每一条记录,都去内部表逐条比较,一旦连接条件满足就输出这条结果——它的成本与两张表记录数的乘积成正比,这意味着当两张表都很大时代价会急剧膨胀,适合至少有一张表很小或有索引可用来加速内层查找的场景。排序合并连接:先分别对两个表的数据集按连接键排序,再同步扫描两个已排序的集合,遇到匹配就完成配对——这种策略天然适合两个数据集本来就已经有序(或排序代价不高)的情况。散列连接:只适用于等值连接,先对(通常是)较小的一张表按连接键做散列,构建一张散列表,再对另一张表的每一行做同样的散列运算,去已建好的散列表里查找是否命中——这种策略把”逐个比较”的开销转化成了近乎O(1)的散列查找,代价集中在为较小表建立散列表这一步。这三种策略没有绝对的优劣之分,计划器会结合两张表的大小、是否存在可用索引、连接类型是否为等值连接等因素综合估算成本后自动选择——理解这三种策略的适用条件,有助于判断”为什么同一个连接改了一下过滤条件,执行计划就从嵌套循环变成了散列连接”这类现象背后的原因。

结构图:

flowchart TB
  J["多表连接"]
  J --> N["嵌套循环<br/>成本∝两表行数乘积<br/>适合小表或内层有索引"]
  J --> S["排序合并连接<br/>先排序两个数据集再同步扫描<br/>适合数据本就有序"]
  J --> H["散列连接(仅等值连接)<br/>对较小表建散列表,另一表逐行查找<br/>近似O(1)查找开销"]
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《数据架构师的PostgreSQL修炼:高效设计、开发与维护数据库应用》第7章《SQL调优》之"7.2.3 连接策略"(源文件:_epub-src/OEBPS/text00078.html) - 结论依据:原文说明"嵌套循环的方法……成本与各表中的记录数的乘积成比例……另一个连接策略是先从两个表中排序数据集,然后扫描排序集,当匹配出现时,完成值的匹配并返回记录……第三个选择被称为散列连接,它被用于等值连接……一张表的每一行用散列算法创建一个散列表……然后,其他表的每一行也被散列化", 直接支撑本卡关于三种连接策略及其适用条件的结构图。 - 原始内容:在此方法中,成本与各表中的记录数的乘积成比例。