在postgres中使用top-N堆排序理解顺序

Question

在没有索引的理论场景中，带有限制的order必须扫描所有数据，然后应用order，然后应用限制，因为我们只有在排序后才能得到前10行(例如)。

但是postgres在这里并不聪明，下面的计划给出了这个故事。

有限制的命令

learning=# explain (analyze,buffers) select * from temp order by userid limit 10;
                                                          QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=81745.51..81745.54 rows=10 width=41) (actual time=2064.275..2064.278 rows=10 loops=1)
   Buffers: shared hit=13 read=18644
   ->  Sort  (cost=81745.51..86735.41 rows=1995958 width=41) (actual time=2064.273..2064.274 rows=10 loops=1)
         Sort Key: userid
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: shared hit=13 read=18644
         ->  Seq Scan on temp  (cost=0.00..38613.58 rows=1995958 width=41) (actual time=35.053..1652.660 rows=1995958 loops=1)
               Buffers: shared hit=10 read=18644
 Planning time: 0.167 ms
 Execution time: 2064.335 ms
(10 rows)

无限制的命令

learning=# explain (analyze,buffers) select * from temp order by userid;
                                                      QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
 Sort  (cost=308877.61..313867.51 rows=1995958 width=41) (actual time=2685.680..3293.698 rows=1995958 loops=1)
   Sort Key: userid
   Sort Method: external merge  Disk: 99504kB
   Buffers: shared hit=42 read=18612, temp read=12440 written=12440
   ->  Seq Scan on temp  (cost=0.00..38613.58 rows=1995958 width=41) (actual time=0.069..286.556 rows=1995958 loops=1)
         Buffers: shared hit=42 read=18612
 Planning time: 0.066 ms
 Execution time: 3540.545 ms
(8 rows)

我的假设是postgres使用了一种名为堆排序(非常有名)的算法，并在获得第一个N(极限)行时停止。

通过这可视化，我无法理解这是如何工作的？有人能为理解this.Is我以上的假设提供一点启示吗？

Answer 1

我还没有深入阅读源代码，但据我所知，它保持了一个有限度大小的堆。

它按顺序使用输入值。当它将堆填充到元组的目标数量之后，它将开始检查每个新值，看看它是否大于所有当前值、小于所有当前值，还是适合堆中的值。

如果它大于所有当前值(假设ASC排序)，它就会被丢弃，因为我们已经有足够低的值了。

如果它小于所有当前值或某些当前值，则在堆中的适当点插入它，所有东西都会被移动一个，并且它会将最后一个条目从堆中移出。

参见src/backend/utils/sort/tuplesort.c行一六一八 (以git )，case TSS_BOUNDED:在puttuple_common中。

Answer 2

PostgreSQL为此使用了一个"top-N排序堆“。在对这样的查询执行“解释分析”时，您可以看到这一点。没有索引，就无法避免全表扫描。但是，top-N堆排序避免为所有行分配内存，因为您只关心前10行。

例如，我有一个600万个条目表，并通过一个未编入索引的列请求前10行。有了第10条限制，它告诉我：

      Sort Method: top-N heapsort  Memory: 25kB
      Without:
      Sort Method: quicksort  Memory: (some value)kB

因此，如果Postgres必须存储所有已排序的600万行，那么它将需要那么多MB的工作内存。如果(请参阅显示work_mem)低于此，将导致它将大量临时文件写入磁盘：

      Sort Method: external merge  Disk: 99504kB

为了使用快速内存扫描，必须增加work_mem参数

Answer 3

链接到的可视化只是一个执行堆排序。堆数据结构是一棵(二进制)树，其属性是每个节点中的值大于(或小于)其子节点中的值。堆可以存储在数组中，这就是可视化所显示的。

堆可以用作有效的优先级队列。因为它只是部分排序，所以作为优先级队列使用比排序列表或类似的更便宜。这可能就是Postgres所做的事情:如果从表中选择N个最大的值，Postgres将保留一个优先级队列(由堆实现)，该队列将保持到目前为止所看到的N个最大值的优先级队列，其中最小值优先(即堆的顶部)。如果新值甚至小于优先级队列的第一项，则可以丢弃新值。如果它更大，则从优先级队列中删除第一个值并插入新值。