PostgreSQL中的查询:Hashing
到目前为止,我们已经讨论了查询执行阶段、统计、顺序和索引扫描,并继续讨论联接。
上一篇文章主要讨论嵌套循环连接,在这篇文章中,我将解释哈希连接。我还将简要提及分组方式和区分方式。
一次传递散列连接
哈希连接使用哈希表查找匹配对,该哈希表必须事先准备好。下面是一个带有哈希连接的计划示例:
EXPLAIN (costs off) SELECT *
FROM tickets t
JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Join
Hash Cond: (tf.ticket_no = t.ticket_no)
−> Seq Scan on ticket_flights tf
−> Hash
−> Seq Scan on tickets t (5 rows)
首先,哈希连接节点调用哈希节点。哈希节点从其子节点获取所有内部集合行,并将它们排列到哈希表中。
哈希表将数据存储为哈希键和值对。这使得键值搜索时间恒定,不受哈希表大小的影响。散列函数将散列密钥随机均匀地分布在有限数量的桶中。桶的总数始终是N的二次幂,给定哈希键的桶数是其哈希函数结果的最后N位。
因此,在第一阶段,散列连接从扫描所有内部集合行开始。通过将哈希函数应用于连接属性(hash Cond)来计算每行的哈希值,查询所需的行中的所有字段都存储在哈希表中。
理想情况下,散列联接希望在一次传递中读取所有数据,但它需要足够的内存来同时容纳整个哈希表。为哈希表分配的内存量为work_mem×hash_memm_multiplier(后者默认为1.0)。
让我们使用解释分析并查看内存利用率:
SET work_mem = '256MB';
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT *
FROM bookings b
JOIN tickets t ON b.book_ref = t.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Join (actual rows=2949857 loops=1)
Hash Cond: (t.book_ref = b.book_ref)
−> Seq Scan on tickets t (actual rows=2949857 loops=1)
−> Hash (actual rows=2111110 loops=1)
Buckets: 4194304 Batches: 1 Memory Usage: 145986kB
−> Seq Scan on bookings b (actual rows=2111110 loops=1)
(6 rows)
与嵌套循环联接不同,嵌套循环联接对内部集合和外部集合进行不同的处理,哈希联接可以轻松地交换集合。较小的集合通常被选择为内部集合,因为这样哈希表将更小。
在这种情况下,分配的内存足够了:哈希表占用了大约143MB(内存使用),有400万(222)个桶。这允许联接在一个过程(批处理)中执行。
我们可以修改查询以选择单个列。这将使哈希表大小减小到111MB:
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT b.book_ref
FROM bookings b
JOIN tickets t ON b.book_ref = t.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Join (actual rows=2949857 loops=1)
Hash Cond: (t.book_ref = b.book_ref)
−> Index Only Scan using tickets_book_ref_idx on tickets t
(actual rows=2949857 loops=1)
Heap Fetches: 0
−> Hash (actual rows=2111110 loops=1)
Buckets: 4194304 Batches: 1 Memory Usage: 113172kB
−> Seq Scan on bookings b (actual rows=2111110 loops=1)
(8 rows)
还有一个原因是要针对您的查询,尽量避免使用SELECT*命令。
哈希表存储桶的数量被选择为平均每个存储桶只有一行。更紧凑的分布会增加散列冲突的机会,而更松散的分布会占用不必要的内存。最小计算的桶数增加到最接近的二次幂。
(如果行足够宽,具有适当数量存储桶的哈希表的预期大小可能会超过分配的内存。每当发生这种情况时,算法会将内部集拆分为多个批,并切换到双通道模式。)
在第一阶段完成之前,不能返回任何输出。
在第二阶段(构建哈希表之后),哈希连接节点调用其第二个子节点并获取外部集。对于每个提取的行,将在哈希表中查找匹配的行,并为连接属性计算哈希值(使用与之前相同的哈希函数)。
并返回到哈希连接节点。
现在,让我们尝试使用两个哈希连接的更多分支计划。此查询返回所有乘客的姓名及其预订的航班:
EXPLAIN (costs off)
SELECT t.passenger_name, f.flight_no
FROM tickets t
JOIN ticket_flights tf ON tf.ticket_no = t.ticket_no
JOIN flights f ON f.flight_id = tf.flight_id;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Join
Hash Cond: (tf.flight_id = f.flight_id)
−> Hash Join
Hash Cond: (tf.ticket_no = t.ticket_no)
−> Seq Scan on ticket_flights tf
−> Hash
−> Seq Scan on tickets t
−> Hash
−> Seq Scan on flights f
(9 rows)
首先,将票与ticket_flights连接,并为票构建哈希表。然后,将结果集与航班连接,并为航班构建哈希表。
成本估算。我在上一篇文章中解释了连接基数。计算方法是不可知的,所以我不再重复。然而,成本估算是不同的。
哈希节点成本被认为等于其子节点成本。这是仅在计划输出中使用的虚拟值。所有实际估计都包含在哈希连接成本中。
考虑这个例子:
EXPLAIN (analyze, timing off, summary off)
SELECT *
FROM flights f
JOIN seats s ON s.aircraft_code = f.aircraft_code;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Join (cost=38.13..278507.28 rows=16518865 width=78)
(actual rows=16518865 loops=1)
Hash Cond: (f.aircraft_code = s.aircraft_code)
−> Seq Scan on flights f (cost=0.00..4772.67 rows=214867 widt...
(actual rows=214867 loops=1)
−> Hash (cost=21.39..21.39 rows=1339 width=15)
(actual rows=1339 loops=1)
Buckets: 2048 Batches: 1 Memory Usage: 79kB
−> Seq Scan on seats s (cost=0.00..21.39 rows=1339 width=15)
(actual rows=1339 loops=1)
(10 rows)
启动成本主要是哈希表构建成本。它包括:
-
完整的内部集合获取成本(我们需要它来构建表)。
-
对于每个内部集合行,每个联接字段的哈希值计算成本(以每次操作的cpu_operator_cost估计)。
-
每个内部集合行的哈希表插入成本(估计为每行的cpu_operator_cost)。
-
启动外部集获取成本(这样我们就可以加入一些东西)。
-
然后,总成本加上实际连接成本:
对于每个外部集合行,每个联接字段的哈希值计算成本(以每次操作的cpu_operator_cost估计)。
连接条件重新检查成本(避免哈希冲突所必需的,估计为每个运算符的cpu_operator_cost)。
输出处理成本(每行的cpu_operator_cost)。
这里有趣的部分是确定完成连接所需的复查次数。该数字估计为外部行数乘以内部行数(位于哈希表中)的某个分数。计算比这更复杂,还取决于数据的均匀性。对于我们的具体示例,分数等于0.150122,我不会对计算的确切细节感到厌烦。
考虑到所有这些,我们可以计算总成本估算:
WITH cost(startup) AS (
SELECT round((
21.39 +
current_setting('cpu_operator_cost')::real * 1339 +
current_setting('cpu_tuple_cost')::real * 1339 +
0.00
)::numeric, 2)
)
SELECT startup,
startup + round((
4772.67 +
current_setting('cpu_operator_cost')::real * 214867 +
current_setting('cpu_operator_cost')::real * 214867 * 1339 *
0.150112 +
current_setting('cpu_tuple_cost')::real * 16518865
)::numeric, 2) AS total
FROM cost;
startup | total
−−−−−−−−−+−−−−−−−−−−−
38.13 | 278507.26
(1 row)
两遍散列连接
如果规划器估计哈希表不适合分配的内存,它会将内部集拆分为多个批,并分别进行处理。批的总数总是2的幂,批的ID由其散列值的最后位确定。
任何两个匹配的行都属于同一个桶,因为来自不同桶的行不能具有相同的哈希值。
每个批具有相同数量的与之相关联的哈希值。如果数据分布均匀,所有桶的大小将非常接近。规划器可以通过选择一定数量的存储桶来控制内存消耗,以使每个存储桶都适合可用内存。
在第一阶段,算法扫描内部集合并构建哈希表。如果扫描的内部集合行属于第一批,则算法将其放入哈希表,因此它保留在内存中。否则,如果该行属于任何其他批,它将存储在一个临时文件中(每个bucket有一个)。
可以使用temp_file_limit参数限制每个会话创建的临时文件的大小(临时表不受影响)。当会话超过限制时,它将终止。
在第二阶段,算法扫描外部集合。如果扫描的外部行属于第一批,它将与哈希表匹配,哈希表存储内部集的第一批(无论如何,其他批中可能没有匹配)。
否则,如果该行属于另一个批,则将其存储在临时文件中(每个批也是单独的)。因此,对于总共N个批次,临时文件的数量将为2(N−1) 如果任何批次为空,则减少。
当扫描外部集并匹配第一批时,将清除哈希表。
此时,这两个集合将被分批排序并存储在临时文件中。从这里开始,该算法从其临时文件中获取一个内部集批处理,并构建其哈希表,然后从临时文件中提取相应的外部集批处理并与该表进行匹配。完成批处理后,该算法将擦除临时文件和哈希表,然后对下一批重复该过程,直到完成。
请注意,两遍联接的解释输出中的批数大于1。此外,此处使用“缓冲区”选项来显示磁盘使用统计信息。
EXPLAIN (analyze, buffers, costs off, timing off, summary off)
SELECT *
FROM bookings b
JOIN tickets t ON b.book_ref = t.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Join (actual rows=2949857 loops=1)
Hash Cond: (t.book_ref = b.book_ref)
Buffers: shared hit=7205 read=55657, temp read=55126
written=55126
−> Seq Scan on tickets t (actual rows=2949857 loops=1)
Buffers: shared read=49415
−> Hash (actual rows=2111110 loops=1)
Buckets: 65536 Batches: 64 Memory Usage: 2277kB
Buffers: shared hit=7205 read=6242, temp written=10858
−> Seq Scan on bookings b (actual rows=2111110 loops=1)
Buffers: shared hit=7205 read=6242
(11 rows)
这与前面的示例相同,但这次使用了默认的work_mem值。由于只有4MB可用,哈希表无法放入内存,因此算法决定将其分成64个批次,总共64K个桶。在哈希节点处构建哈希表时,数据将写入临时文件(临时写入)。在连接阶段(散列连接节点),文件被读取和写入(临时读取,临时写入)。
如果需要有关临时文件的更多信息,可以将log_temp_files参数设置为零。这将迫使服务器在删除时记录每个文件及其大小的记录。
动态计划调整
有两个可能的问题会打乱计划。第一种是非均匀分布。
如果联接键列中的值分布不均匀,则不同批次的行数将不同。
如果最大的批是除第一批以外的任何其他批,则必须先将所有行写入磁盘,然后再从磁盘读取。这对于外部集合尤其重要,因为它通常是较大的集合。因此,如果我们为外部集合构建了最常见的值统计信息(换句话说,如果外部集合是一个表,并且连接在一列上进行,没有多变量MCV列表),则具有与MCV列表匹配的哈希代码的行被视为属于第一批。这称为歪斜优化,它有助于减少两遍连接期间的输入/输出开销。
第二个可能的问题是过时的统计数据。
这两个问题都可能导致某些(或所有)批的大小大于预期,因此哈希表可能超过分配的内存。
该算法可以在表构建阶段发现这一点,并在运行中将批数增加一倍,以避免溢出。基本上,它将每个批次分成两部分。每个批的一半行(假设分布均匀)保留在内存中,另一半存储在磁盘上的新临时文件中。
这也可能发生在单通道连接期间。事实上,单遍联接和双遍联接都由同一代码管理。我只是用不同的方式称呼他们以避免混淆。
批次的数量永远不会减少。如果规划人员高估了批次大小,则不会将较小的批次合并在一起。
当非均匀分布起作用时,分批可能仍然是低效的。例如,联接键列可以在每行中存储相同的值。这将把所有行放在同一批中,因为哈希函数总是返回相同的值。在这种特定情况下,除了看着哈希表增长之外,别无选择,尽管存在所有限制参数。理论上,这可以通过一次检查一部分批次的多遍联接来解决,但这尚未实现。
为了演示动态批次数量的增加,我们必须做一些事情来欺骗规划者:
CREATE TABLE bookings_copy (LIKE bookings INCLUDING INDEXES)
WITH (autovacuum_enabled = off);
INSERT INTO bookings_copy SELECT * FROM bookings;
INSERT 0 2111110
DELETE FROM bookings_copy WHERE random() < 0.9;
DELETE 1899931
ANALYZE bookings_copy;
INSERT INTO bookings_copy SELECT * FROM bookings
ON CONFLICT DO NOTHING;
INSERT 0 1899931
SELECT reltuples FROM pg_class WHERE relname = 'bookings_copy';
reltuples
−−−−−−−−−−−
211179
(1 row)
我们刚刚创建了一个表bookings_copy。这是一个相同的预订副本,但规划者认为它的行数比实际的少十倍。在现实生活中可能会出现类似的情况,例如,我们为一组行构建一个哈希表,而这些行本身是另一个联接的结果,没有精确的统计数据。
我们成功地欺骗了规划者,使其认为只有8个批次就足够了,而在表格构建阶段,数量将增长到32:
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT *
FROM bookings_copy b
JOIN tickets t ON b.book_ref = t.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Join (actual rows=2949857 loops=1)
Hash Cond: (t.book_ref = b.book_ref)
−> Seq Scan on tickets t (actual rows=2949857 loops=1)
−> Hash (actual rows=2111110 loops=1)
Buckets: 65536 (originally 65536) Batches: 32 (originally 8)
Memory Usage: 4040kB
−> Seq Scan on bookings_copy b (actual rows=2111110 loops=1)
(7 rows)
成本估算。这是一次连接部分的相同示例,但现在我设置了极低的内存限制,迫使规划器使用两个批。这增加了成本:
SET work_mem = '64kB';
EXPLAIN (analyze, timing off, summary off)
SELECT *
FROM flights f
JOIN seats s ON s.aircraft_code = f.aircraft_code;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Join (cost=45.13..283139.28 rows=16518865 width=78)
(actual rows=16518865 loops=1)
Hash Cond: (f.aircraft_code = s.aircraft_code)
−> Seq Scan on flights f (cost=0.00..4772.67 rows=214867 widt...
(actual rows=214867 loops=1)
−> Hash (cost=21.39..21.39 rows=1339 width=15)
(actual rows=1339 loops=1)
Buckets: 2048 Batches: 2 Memory Usage: 55kB
−> Seq Scan on seats s (cost=0.00..21.39 rows=1339 width=15)
(actual rows=1339 loops=1)
(10 rows)
RESET work_mem;
连接成本本身由于临时文件写入和读取成本而增加。
启动成本将增加写入足以存储所有内部集合行中所需字段的页数的估计成本。在构建哈希表时,第一批数据不会写入磁盘,但估计没有考虑到这一点,因此它不取决于批的数量。
总成本增加了从磁盘读取存储的内部集合行,然后写入和读取外部集合行的成本估计。
假设读和写都是顺序的,并且使用seq_page_cost参数估计一行的读和写成本。
在本例中,内部集合的页面数估计为7,外部集合的页面数量估计为2309。通过将这些成本与之前的一次通过估计相加,我们得到了规划者最终得到的相同估计:
SELECT 38.13 + -- one-pass startup cost
current_setting('seq_page_cost')::real * 7
AS startup,
279232.27 + -- one-pass total cost
current_setting('seq_page_cost')::real * 2 * (7 + 2309)
AS total;
startup | total
−−−−−−−−−+−−−−−−−−−−−
45.13 | 283864.27
(1 row)
这说明,当可用内存不足时,单遍联接算法会变成双遍联接算法,效率会受到影响。为了避免效率低下,请确保:
-
哈希表仅包括真正必要的字段(程序员的责任)。
-
哈希表是为较小的集合构建的(由规划人员负责)。
并行计划中的哈希连接
哈希连接可以在类似于我上面描述的并行计划中工作。每个并行进程将首先从内部集合构建自己的哈希表副本,然后使用它并行访问外部集合。这里的好处是每个进程只扫描外部集合的一小部分。
下面是一个具有常规(在本例中为一次传递)哈希连接的计划示例:
SET work_mem = '128MB';
SET enable_parallel_hash = off;
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT count(*)
FROM bookings b
JOIN tickets t ON t.book_ref = b.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Finalize Aggregate (actual rows=1 loops=1)
−> Gather (actual rows=3 loops=1)
Workers Planned: 2
Workers Launched: 2
−> Partial Aggregate (actual rows=1 loops=3)
−> Hash Join (actual rows=983286 loops=3)
Hash Cond: (t.book_ref = b.book_ref)
−> Parallel Index Only Scan using tickets_book_ref...
Heap Fetches: 0
−> Hash (actual rows=2111110 loops=3)
Buckets: 4194304 Batches: 1 Memory Usage:
113172kB
−> Seq Scan on bookings b (actual rows=2111110...
(13 rows)
RESET enable_parallel_hash;
每个进程首先为预订创建一个哈希表。然后,进程以仅并行索引扫描模式扫描票据,并将其行集与哈希表匹配。
哈希表大小限制分别适用于每个并行进程,因此分配的总内存(在本例中)将是计划中在内存使用情况下所述的三倍。
一次并行散列连接
虽然常规散列连接可以从并行运行中受益(特别是内部集足够小,不需要考虑并行化),但在PostgreSQL 11中引入的专用并行散列连接算法中,较大的集性能更好。
新算法的一个显著优点是它能够在共享、动态分配的内存中构建哈希表,这使得所有参与的并行进程都可以访问哈希表。
这允许所有进程将其个人内存分配给构建共享表,而不是每个进程构建相同的个人表。更大的内存池可以容纳更大的表,从而增加了整个表适合的机会,并且可以在一次传递中完成连接。
在第一阶段,在并行哈希节点下,所有并行进程并行扫描内部集,并构建共享哈希表。
每个过程都必须在算法前进之前完成其部分。
在第二阶段(并行哈希连接节点),每个进程将其外部集的一部分与共享哈希表并行匹配。
这是一个工作中的例子:
SET work_mem = '64MB';
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT count(*)
FROM bookings b
JOIN tickets t ON t.book_ref = b.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Finalize Aggregate (actual rows=1 loops=1)
−> Gather (actual rows=3 loops=1)
Workers Planned: 2
Workers Launched: 2
−> Partial Aggregate (actual rows=1 loops=3)
−> Parallel Hash Join (actual rows=983286 loops=3)
Hash Cond: (t.book_ref = b.book_ref)
−> Parallel Index Only Scan using tickets_book_ref...
Heap Fetches: 0
−> Parallel Hash (actual rows=703703 loops=3)
Buckets: 4194304 Batches: 1 Memory Usage: 115424kB
−> Parallel Seq Scan on bookings b (actual row...
(13 rows)
RESET work_mem;
这与我们在上一节中运行的查询相同,但我在那里使用了参数enable_parallel_hash来显式限制这种类型的执行。
尽管与上一个示例相比,哈希表的内存减少了一半,但由于共享内存特性(内存使用),此哈希表在一次传递中执行。这里的哈希表稍大一些,但我们不需要任何其他哈希表,因此总内存使用量已经减少。
并行两遍散列连接
对于足够大的哈希表,即使所有进程的共享内存也可能不足以一次存储所有哈希表。这一事实可能会在规划期间出现,或在稍后的执行阶段出现。当这种情况发生时,另一个两遍算法会出现,其中一个与之前的所有算法非常不同。
主要区别在于,它为每个工作进程使用单独的较小哈希表,而不是单个大哈希表,并且每个工作进程独立于其他进程处理批次。较小的表仍然驻留在共享内存中,其他工作人员可以访问。如果算法在规划阶段发现连接操作不是一个单批作业,它将立即为每个工作人员构建表。如果在执行阶段发现不足,则将大表重建为小表。
算法的第一阶段让进程并行扫描内部集,将其拆分为批,并将其写入临时文件。由于每个进程只扫描其内部集的一部分,因此没有一个进程会为任何批(包括第一批)构建完整的哈希表。批处理的整组行被编译成一个专用文件,所有进程在同步时都会写入该文件。这就是为什么这里不同于非并行和并行单通道变体,每个批都存储在磁盘上。
当所有的过程都用散列完成时,第二阶段开始。这里,非并行算法将开始将第一批的外部集合行与哈希表进行匹配。然而,并行表还没有一个完整的表,并且具有独立处理的批。首先,该算法并行扫描外部集,将其拆分为批,并将批存储在磁盘上的单独临时文件中。在这个阶段,扫描的行不需要为它们构建哈希表,因此批处理的数量永远不会增加。
当进程完成扫描时,该算法最终得到2N个临时文件,存储内部和外部集合批。
现在,每个进程获取一个批并执行实际的连接。它将内部集合从磁盘拉入哈希表,扫描外部集合行,并将它们与哈希表行进行匹配。处理完批次后,流程将选择另一个可用批次,依此类推。
如果没有剩余的未处理批次,该流程将与另一个流程协作,以帮助其完成批次。他们可以这样做,因为所有哈希表都驻留在共享内存中。
这种方法优于使用单个大型共享表的算法,因为进程之间的协作更容易,同步开销更小。
修改
散列连接算法并不排斥内部连接;任何其他类型的联接,无论是左联接、右联接、全联接、外联接、半联接还是反联接,都可以利用它。然而,限制是联接条件必须是等式运算符。
我以前演示过嵌套循环连接示例中的一些操作。这是一个右外连接示例:
EXPLAIN (costs off) SELECT *
FROM bookings b
LEFT OUTER JOIN tickets t ON t.book_ref = b.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Right Join
Hash Cond: (t.book_ref = b.book_ref)
−> Seq Scan on tickets t
−> Hash
−> Seq Scan on bookings b
(5 rows)
请注意,查询中的逻辑左连接操作将转换为计划中的物理右连接操作。
在逻辑层面上,bookings表将是外部表(在等式运算符的左侧),tickets表将是内部表(在运算符的右侧)。如果这样连接,生成的表将包括所有预订,而不包括任何门票。
在物理层上,规划器不是通过它们在查询中的位置,而是通过相对联接成本来确定哪个集合是内部集合,哪个集合是外部集合。这通常会导致较小哈希表占据内部位置的集合,就像这里的预订一样。因此,连接类型在平面中从左到右切换。
反过来也是如此。如果指定想要右外部联接(以获取所有没有关联预订的票证),则计划将使用左联接:
EXPLAIN (costs off) SELECT *
FROM bookings b
RIGHT OUTER JOIN tickets t ON t.book_ref = b.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Left Join
Hash Cond: (t.book_ref = b.book_ref)
−> Seq Scan on tickets t
−> Hash
−> Seq Scan on bookings b
(5 rows)
一个完整的连接,最重要的是:
EXPLAIN (costs off) SELECT *
FROM bookings b
FULL OUTER JOIN tickets t ON t.book_ref = b.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Hash Full Join
Hash Cond: (t.book_ref = b.book_ref)
−> Seq Scan on tickets t
−> Hash
−> Seq Scan on bookings b
(5 rows)
右侧和左侧联接当前不支持并行哈希联接(但正在处理)。请注意,在下一个示例中,如何将bookings表用作外部集。如果支持外部联接,则会选择它作为内部集合。
EXPLAIN (costs off) SELECT sum(b.total_amount)
FROM bookings b
LEFT OUTER JOIN tickets t ON t.book_ref = b.book_ref;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Finalize Aggregate
−> Gather
Workers Planned: 2
−> Partial Aggregate
−> Parallel Hash Left Join
Hash Cond: (b.book_ref = t.book_ref)
−> Parallel Seq Scan on bookings b
−> Parallel Hash
−> Parallel Index Only Scan using tickets_book...
(9 rows)
分组和不同值
可以通过与联接算法类似的算法来对聚合值进行分组和删除重复值。其中一种方法是为所需字段构建哈希表。只有在表中没有这样的值时,才会将每个值放入表中。这将导致一个仅包含不同值的哈希表。
EXPLAIN (costs off) SELECT fare_conditions, count(*)
FROM seats
GROUP BY fare_conditions;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
HashAggregate
Group Key: fare_conditions
−> Seq Scan on seats
(3 rows)
类别列表(DISTINCT):
EXPLAIN (costs off) SELECT DISTINCT fare_conditions
FROM seats;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
HashAggregate
Group Key: fare_conditions
−> Seq Scan on seats
(3 rows)
票价等级加上另一个值(UNION):
EXPLAIN (costs off) SELECT fare_conditions
FROM seats
UNION
SELECT NULL;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
HashAggregate
Group Key: seats.fare_conditions
−> Append
−> Seq Scan on seats
−> Result
(5 rows)
Append节点是合并行集的地方,但它不会删除任何重复值,这是UNION操作所需要的。这是在HashAggregate节点单独完成的。
与哈希连接一样,哈希表的可用内存量不能超过work_mem×hash_memm_multiplier。
如果哈希表匹配,则聚合在一个批中完成,如下例所示:
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT DISTINCT amount
FROM ticket_flights;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
HashAggregate (actual rows=338 loops=1)
Group Key: amount
Batches: 1 Memory Usage: 61kB
−> Seq Scan on ticket_flights (actual rows=8391852 loops=1)
(4 rows)
没有太多不同的值,因此哈希表只占用61KB(内存使用)。
一旦表不再适合内存,多余的值就开始溢出到磁盘,并根据散列值的特定位分成几个分区。分区的数量始终是2的幂,并且以允许每个分区的哈希表适合内存的方式进行选择。该估计值容易出现统计不准确,因此得到的所需分区数乘以1.5以获得良好的度量,进一步减小了每个分区的大小,并增加了在单个批次中处理该分区的可能性。
扫描数据集后,节点立即返回哈希表中值的聚合结果。
然后,清除哈希表,从临时文件中扫描下一个分区,并像常规行集一样进行处理。在某些情况下,分区的哈希表可能再次溢出。如果发生这种情况,“额外”行将再次拆分为分区并存储在磁盘上。
正如您所记得的,两遍哈希连接算法将所有最常见的值移动到第一批中,以节省一些I/O时间。聚合不需要这样做,因为它只存储磁盘上溢出的行,而不是所有行。最常见的值可能会很早出现在集合中,并在哈希表中占有一席之地。
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT DISTINCT flight_id
FROM ticket_flights;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
HashAggregate (actual rows=150588 loops=1)
Group Key: flight_id
Batches: 5 Memory Usage: 4145kB Disk Usage: 98184kB
−> Seq Scan on ticket_flights (actual rows=8391852 loops=1)
(4 rows)
在本例中,不同值的数量足够高,使得哈希表无法适应内存限制。数据分5批处理:一批用于初始集,四批用于存储在磁盘上的四个分区。
原文标题:Queries in PostgreSQL:6.Hashing
原文作者:Egor Rogov
原文链接:https://postgrespro.com/blog/pgsql/5969673
免责声明:
1、本站资源由自动抓取工具收集整理于网络。
2、本站不承担由于内容的合法性及真实性所引起的一切争议和法律责任。
3、电子书、小说等仅供网友预览使用,书籍版权归作者或出版社所有。
4、如作者、出版社认为资源涉及侵权,请联系本站,本站将在收到通知书后尽快删除您认为侵权的作品。
5、如果您喜欢本资源,请您支持作者,购买正版内容。
6、资源失效,请下方留言,欢迎分享资源链接
文章评论