十一月 21, 2024
摘要：在本教程中，您将了解内存排序的成本估算。
目录
排序
归并连接算法处理两个按合并键排序的数据集，并返回有序的输出。输入数据集可以通过索引扫描进行预排序，也可以明确地排序。
如果其中一个数据集（或两个数据集）未按连接键排序，则必须在合并之前对其进行排序。这种必要的排序是在执行计划的 Sort 节点中进行的。
让我们开始设置一个小的测试用例：
CREATE TABLE test1 (id integer, val varchar);
CREATE TABLE test2 (id integer, val varchar);
INSERT INTO test1 (id, val)
SELECT i, 'PG00' || i % 1000
FROM generate_series(1, 1000) AS s(i);
INSERT INTO test2 (id, val)
SELECT i, 'PG00' || i % 1000
FROM generate_series(1, 1000000) AS s(i);
下面是一个归并连接的示例。请注意计划中的 Sort 节点。
EXPLAIN (costs off)
SELECT * FROM test1 a
JOIN test2 b ON a.val = b.val
ORDER BY b.val;
QUERY PLAN
-----------------------------------------------
Merge Join
Merge Cond: ((a.val)::text = (b.val)::text)
-> Sort
Sort Key: a.val
-> Seq Scan on test1 a
-> Materialize
-> Sort
Sort Key: b.val
-> Seq Scan on test2 b
(9 rows)
排序算法本身是通用的。它可以由ORDER BY子句来调用，也可以在窗口函数中调用：
EXPLAIN (costs off)
SELECT val,
row_number() OVER (PARTITION BY id ORDER BY val)
FROM test1 a;
QUERY PLAN
---------------------------------
WindowAgg
-> Sort
Sort Key: id, val
-> Seq Scan on test1 a
(4 rows)
在这里，在由 Sort 节点对数据集预先排序后，WindowAgg 节点会在数据集上计算窗口函数。
规划器有一系列的排序模式可供选择。下面的示例展示了其中的两个（Sort Method）。与往常一样，您可以使用EXPLAIN ANALYZE深入了解更多详细信息：
EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM test1 a
JOIN test2 b ON a.val = b.val
ORDER BY b.val;
QUERY PLAN
---------------------------------------------------------------------
Merge Join (actual rows=1000000 loops=1)
Merge Cond: ((a.val)::text = (b.val)::text)
-> Sort (actual rows=1000 loops=1)
Sort Key: a.val
Sort Method: quicksort Memory: 71kB
-> Seq Scan on test1 a (actual rows=1000 loops=1)
-> Materialize (actual rows=1000000 loops=1)
-> Sort (actual rows=1000000 loops=1)
Sort Key: b.val
Sort Method: external merge Disk: 19456kB
-> Seq Scan on test2 b (actual rows=1000000 loops=1)
(11 rows)
快速排序
如果要排序的数据能完全放入到允许的内存中（work_mem），则使用旧的快速排序算法。您可以在任何计算机科学教科书的前几页找到它的描述，因此就不在这里重复它了。
对于实现，排序由特定组件完成，该组件会为任务选择最合适的算法。
成本估算。让我们看看该算法如何对小表进行排序：
EXPLAIN SELECT * FROM test1 ORDER BY val;
QUERY PLAN
----------------------------------------------------------------
Sort (cost=63.83..66.33 rows=1000 width=11)
Sort Key: val
-> Seq Scan on test1 (cost=0.00..14.00 rows=1000 width=11)
(3 rows)
对 n 个值进行排序的复杂度为 O(n log2n) 。一次比较操作的成本是 cpu_operator_cost 的两倍。你需要对整个数据集进行扫描和排序，才能得到结果，所以排序的启动成本会同时包括比较操作成本和子节点的总成本。
除此之外，排序的总成本还会包括 Sort 节点输出的每一行的处理成本，每行估计为 cpu_operator_cost（而不是默认的 cpu_tuple_cost，因为它的成本很低）。
因此，上述示例的排序成本可按以下方式来计算：
WITH costs(startup) AS (
SELECT 14.00 + round((
current_setting('cpu_operator_cost')::real * 2
* 1000 * log(2, 1000)
)::numeric, 2)
)
SELECT startup,
startup + round((
current_setting('cpu_operator_cost')::real * 1000
)::numeric, 2) AS total
FROM costs;
startup | total
---------+-------
63.83 | 66.33
(1 row)
Top-N 堆排序
当您只想对集合排序出一部分的结果（直到某个LIMIT），而不是完整的结果时，您可以执行 Top-N 堆排序操作。更准确地说，当LIMIT会过滤掉至少一半的输入行，或者当输入的数据集不能放入内存，但输出的数据集可以放入内存时，会使用此算法。
EXPLAIN (analyze, timing off, summary off)
SELECT * FROM test2
ORDER BY val
LIMIT 100;
QUERY PLAN
----------------------------------------------------------------------------------------------------------
Limit (cost=51692.28..51692.53 rows=100 width=11) (actual rows=100 loops=1)
-> Sort (cost=51692.28..54192.28 rows=1000000 width=11) (actual rows=100 loops=1)
Sort Key: val
Sort Method: top-N heapsort Memory: 33kB
-> Seq Scan on test2 (cost=0.00..13473.00 rows=1000000 width=11) (actual rows=1000000 loops=1)
(5 rows)
为了从 n 行中找到 k 个最高（最低）值，该算法首先创建一个称为堆的数据结构，并在其中添加前 k 个行。然后，它继续逐行向堆中添加行，但在每行加入之后，它会从堆中取出一个最低（最高）的值。当新行都添加完后，堆中会留下 k 个最高值或最低值。
这里的术语 heap 指的是堆数据结构，不要将它与数据库表混淆，后者通常具有相同的名称。
成本估算。算法复杂度为 O(n log2k) ，但与快速排序相比，每次操作的成本更高，因此成本计算公式使用 n log22k 作为估计值。
WITH costs(startup) AS (
SELECT 13473.00 + round((
current_setting('cpu_operator_cost')::real * 2
* 1000000 * log(2, 2 * 100)
)::numeric, 2)
)
SELECT startup,
startup + round((
current_setting('cpu_operator_cost')::real * 100
)::numeric, 2) AS total
FROM costs;
startup | total
----------+----------
51692.28 | 51692.53
(1 row)