嘉兴网站建设多少钱,wordpress网站搬,163邮箱入口,浙江舟山建设厅网站一阶段哈希连接#xff08;One-Pass Hash Joins#xff09;
散列连接使用预构建的散列表搜索匹配的行。下面是一个使用这种连接的计划的例子#xff1a; 在第一阶段#xff0c;哈希连接节点1调用哈希节点2#xff0c;哈希节点2从其子节点提取整个内部行集#xff0c;并将…一阶段哈希连接One-Pass Hash Joins
散列连接使用预构建的散列表搜索匹配的行。下面是一个使用这种连接的计划的例子 在第一阶段哈希连接节点1调用哈希节点2哈希节点2从其子节点提取整个内部行集并将其放入哈希表中。
哈希表存储哈希键和值对可以通过键快速访问值搜索时间不依赖于哈希表的大小因为哈希键或多或少均匀地分布在有限数量的桶之间。一个给定的键所在的桶是由该哈希键的哈希函数决定的由于桶的数量始终是2的幂因此取计算值的所需位数就足够了。
就像buffer cache一样这个实现使用一个动态可扩展的哈希表通过链接chaining来解决哈希冲突。
在连接操作的第一阶段扫描内部集合并为它的每一行计算散列函数。在连接条件(Hash Cond)中引用的列用作哈希键而哈希表本身存储内部集合的所有查询字段。
如果整个哈希表可以容纳在内存中那么哈希连接是最有效的因为在这种情况下执行器将管理一次处理数据。为此目的分配的内存块的大小受到work_mem × hash_mem_multiplier值的限制。 让我们运行EXPLAIN ANALYZE查看一下查询的内存使用统计数据 嵌套循环连接对内部集和外部集的处理方式不同而散列连接可以交换它们。较小的集合通常用作内部集合因为它会产生较小的哈希表。
在本例中整个表放入分配的缓存中大约占用143MB (Memory Usage)包含4M 2的22次方 个内存桶。因此连接在一次传递(batch)中执行。
但是如果查询只引用了一列那么哈希表将填充111MB 这是避免在查询中引用多余字段的另一个原因(举个例子如果使用星号可能会出现这种情况)。
所选择的桶数应该保证当哈希表完全填满数据时每个桶平均只保存一行。更高的密度会增加哈希冲突率使搜索效率降低而不太紧凑的哈希表会占用太多内存。 桶的估计数量增加到最接近的2的幂。
如果估计的哈希表大小超过基于单行平均宽度的内存限制则将应用两遍散列two-pass hashing。
在哈希表完全构建完成之前哈希连接不能开始返回结果。
在第二阶段 (此时已经构建了哈希表)hash Join节点调用其第二个子节点以获取外部行集。对于扫描的每一行将在散列表中搜索匹配项。它需要计算连接条件中包含的外部集合的列的散列键。 找到的匹配项返回到父节点。
成本预估
我们已经讨论了基数估计;因为它不依赖于连接方法所以我现在将重点放在成本估计上。
Hash节点的成本由其子节点的总成本表示。这是一个虚拟数字只是填补了计划中的空缺。所有实际的估计都包含在Hash Join节点的成本中。 连接的启动成本主要反映了创建哈希表的成本包括以下部分
获取构建哈希表所需的内部集合的总成本计算连接键中包含的所有列的哈希函数的成本对于内部集合的每一行(估计为cpu_operator_cost 每个操作)将所有内部行插入哈希表的成本(估计为cpu_tuple_cost每插入一行)获取外部行集的启动成本这是启动连接操作所必需的
总成本包括启动成本和连接本身的成本即
对于外部集合的每一行计算连接键中包含的所有列的哈希函数的成本(cpu_operator_cost)重新检查连接条件的成本这是解决可能的哈希冲突所必需的(估计为每个检查的操作符的cpu_operator_cost)每个结果行的处理成本(cpu_tuple_cost)
所需复核的次数是最难估计的。它是通过将外部集合的行数乘以内部集合(存储在哈希表中)的某个分数来计算的。为了估计这个分数计划者必须考虑到数据分布可能不均匀。
因此我们的查询成本估计如下 这是依赖关系图
双阶段哈希连接Two-Pass Hash Joins
如果规划器的估计显示哈希表将超过分配的内存则将内部的行集分成若干批分别进行处理。批的数量(就像桶的数量)总是2的幂要使用的批处理由哈希键的相应位数决定。
任意两个匹配的行属于同一个批处理放置在不同批处理中的行不能具有相同的哈希码。
所有批都持有相同数量的哈希键。如果数据均匀分布批大小也将大致相同。计划器可以通过选择适当数量的批来控制内存消耗。
在第一阶段执行程序扫描内部行集以构建散列表。如果扫描的行属于第一批则将其添加到哈希表中并保存在内存中。否则它将被写入临时文件(每个批处理都有一个单独的文件)。
会话可以存储在磁盘上的临时文件的总量是由temp_file_limit参数限制的(临时表不包括在这个限制中)。一旦会话达到这个值查询就会终止。 在第二阶段扫描外部集合。如果该行属于第一批它将与包含内部集合的第一批行的哈希表进行匹配(无论如何在其他批中不可能有匹配)。
如果该行属于不同的批处理则将其存储在临时文件中该文件将为每个批处理单独创建。因此N批可以使用2(N−1)个文件(如果某些批为空则可以使用更少)。
一旦第二阶段完成为哈希表分配的内存将被释放。此时我们已经有了其中一个批次的连接结果。 对于保存在磁盘上的每批数据都要重复这两个阶段:内部数据集的行从临时文件转移到哈希表;然后从另一个临时文件中读取与同一批处理相关的外部集的行并与此哈希表进行匹配。一旦处理临时文件将被删除。 与One-pass连接的类似输出不同two-pass连接的EXPLAIN命令的输出包含多个批处理。如果使用BUFFERS选项该命令还显示磁盘访问的统计信息 我已经用增加的work_mem设置展示了上面的查询。默认值4MB对于整个哈希表来说太小了无法容纳内存;在这个例子中数据被分成64个批次哈希表使用64K (2的16次方)个桶。在构建哈希表(Hash节点)时数据被写入临时文件(temp written);在连接阶段(Hash Join节点)读取和写入临时文件(temp read,written)。
要收集更多关于临时文件的统计信息可以将log_temp_files参数设置为零。然后服务器日志将列出所有临时文件及其大小(在删除时显示的大小)。
动态调整
两个问题可能打乱计划的事件进程不准确的统计和不均匀的数据分布。
如果连接键列中值的分布不均匀则不同批次将具有不同的大小。
如果某个批处理(第一个批处理除外)太大则必须将其所有行都写入磁盘然后再从磁盘读取。最麻烦的是外部集合因为它通常更大。因此如果外部集的mcv上有常规的非多元统计信息(即外部集由表表示连接由单列执行)则具有与mcv对应的哈希码的行被认为是第一批的一部分。这种技术(称为倾斜优化)可以在一定程度上减少两次连接的I/O开销。
由于这两个因素一些(或全部)批的大小可能超过估计。然后相应的哈希表将不适合分配的内存块并将超过定义的限制。
因此如果构建的哈希表太大批处理的数量就会增加(翻倍)。每个批处理实际上被分成两个新的批处理:大约一半的行(假设分布是均匀的)留在哈希表中而另一半保存到一个新的临时文件中。
即使最初计划了一次连接也可能发生这种分离。事实上一次和两次连接使用由相同代码实现的相同算法;我在这里单独列出它们只是为了更流畅地叙述。
批次数量不能减少。如果计划器高估了数据大小则不会将批合并在一起。
在不均匀分布的情况下增加批次数量可能没有帮助。例如如果键列在其所有行中包含一个相同的值则它们将被放入同一个批处理中因为散列函数将一次又一次地返回相同的值。不幸的是在这种情况下无论施加了什么限制哈希表都将继续增长。
为了演示批数量的动态增长我们首先必须执行一些操作 结果我们得到一个名为bookings_copy的新表。它是booking表的精确副本但是计划器将其中的行数低估了10倍。如果为另一个连接操作生成的一组行生成散列表则可能出现类似的情况因此没有可靠的统计信息可用。
这个错误的计算使计划器认为8个桶足够了但是当执行连接时这个数字增长到32 成本预估
我已经使用这个示例来演示单次连接的成本估计但是现在我要将可用内存的大小减少到最小因此计划器将不得不使用两个批处理。它增加了连接的成本 第二次传递的代价是将行溢出到临时文件中并从这些文件中读取它们。
两遍连接的启动成本是基于单遍连接的启动成本这是由于写入尽可能多的页面以存储内部集所有行的所有必要字段的估计成本而增加的。虽然在构建哈希表时没有将第一批数据写入磁盘但估计没有考虑到这一点因此不依赖于批的数量。
反过来总成本包括一次连接的总成本和读取先前存储在磁盘上的内部集的行以及读取和写入外部集的行的估计成本。
由于假定I/O操作是顺序的因此写入和读取都以seq_page_cost 每个页面来估计。
在这个特殊的情况下内部集合所需的页面数估计为7而外部集合的数据预计适合2309页。将这些估计值添加到上面计算的一次连接成本中我们得到与查询计划中显示的相同的数字 因此如果没有足够的内存连接将分两次执行并且效率会降低。因此重要的是要注意以下几点:
查询必须以一种从哈希表中排除冗余字段的方式组成。在构建哈希表时规划器必须选择两组行中较小的那一组。
Parallel One-Pass Hash Joins
尽管常规散列连接在并行计划中非常有效(特别是对于小型内部集并行处理对其没有多大意义)但是使用特殊的并行散列连接算法可以更好地处理较大的数据集。
该算法的并行版本的一个重要区别是哈希表是在共享内存中创建的共享内存是动态分配的可以由参与连接操作的所有并行进程访问。不是几个单独的哈希表而是构建一个公共的哈希表它使用专用于所有参与进程的总内存量。它增加了一次通过完成连接的机会。
在第一阶段(在计划中由Parallel Hash节点表示)所有并行进程构建一个公共哈希表利用对内部集的并行访问。 要从这里继续每个并行进程必须完成其第一阶段处理的份额。
在第二阶段(Parallel Hash Join节点)进程再次并行运行将外部集合的行份额与此时已经构建的散列表进行匹配。 下面是这样一个计划的例子 这与我在前一节中展示的查询是相同的但是并行散列连接当时是由enable_parallel_hash参数关闭的。
尽管与之前演示的常规散列连接相比可用内存减少了一半但该操作仍然在一次传递中完成因为它使用了为所有并行进程分配的内存(memory Usage)。哈希表变大了一点但由于它是我们现在唯一的哈希表所以总内存使用量减少了。
Parallel Two-Pass Hash Joins
所有并行进程的合并内存可能仍然不足以容纳整个哈希表。它可以在计划阶段或之后的查询执行期间变得清晰。在这种情况下应用的两步算法与我们到目前为止看到的完全不同。
该算法的关键区别在于它创建了几个较小的哈希表而不是一个大的哈希表。每个进程都有自己的表并独立处理自己的批。(但是由于单独的哈希表仍然位于共享内存中因此任何进程都可以访问这些表中的任何一个。)如果计划显示需要多个批处理则立即为每个进程构建单独的哈希表。如果在执行阶段做出决策则重新构建哈希表。
因此在第一阶段进程并行扫描内部数据集将其分批写入临时文件。由于每个进程只读取它自己的内部集因此它们都不会为任何批(甚至第一个批)构建完整的哈希表。任何批处理的全部行集仅在所有并行进程以同步方式写入的文件中累积。因此与算法的非并行和单遍并行版本不同并行两遍散列连接将所有批数据写入磁盘包括第一个批数据。 一旦所有进程都完成了内部集合的散列第二阶段就开始了。
如果使用该算法的非并行版本则外部集合中属于第一批的行将立即与哈希表进行匹配。但是在并行版本的情况下内存还不包含哈希表因此工作进程独立处理批次。因此第二阶段首先对外部数据集进行并行扫描将其行分批分发并将每个批写入单独的临时文件中。扫描的行不会插入到哈希表中(就像在第一阶段那样)因此批处理的数量永远不会增加。
一旦所有进程都完成了外部集的扫描我们在磁盘上得到2N个临时文件;它们包含了内部集和外部集的批次。 然后每个进程选择一个批次并执行连接它将内部的行集加载到内存中的哈希表中扫描外部集的行并将它们与哈希表进行匹配。批处理连接完成后进程选择尚未处理的下一个批处理。 如果没有未处理的批已完成其批的进程开始处理当前正在由另一个进程处理的批这种并发处理是可能的因为所有哈希表都位于共享内存中。 这种方法比为所有进程使用单个大哈希表更有效:更容易设置并行处理并且同步成本更低。
修正
散列连接算法支持任何类型的连接:除了内部连接它还可以处理左连接、右连接和完全外部连接以及半连接和反连接。但是正如我已经提到的连接条件仅限于相等运算符。
在处理嵌套循环连接时我们已经观察到了其中的一些操作。下面是一个右外连接的例子 注意SQL查询中指定的逻辑左连接在执行计划中被转换为右连接的物理操作。
在逻辑级别上booking是外部表(构成连接操作的左侧)而tickets表是内部表。因此没有tickets的booking也必须包含在连接结果中。
在物理层内部集和外部集是根据连接的成本而不是它们在查询文本中的位置分配的。这通常意味着具有较小哈希表的集合将被用作内部哈希表。这正是这里发生的事情:预订表被用作内部集左连接被更改为右连接。
反之亦然如果查询指定了右外连接(以显示与任何预订无关的票据)则执行计划使用左连接: 为了完成这个图我将提供一个具有完整外部连接的查询计划示例: 并行哈希连接目前不支持右连接和全连接。
请注意下一个示例使用预订表作为外部集但是如果支持右连接计划器将更倾向于使用右连接
