Понимание порядка с использованием top-N heapsort в postgres

Question

В теоретическом сценарии при отсутствии индексов порядок с ограничением должен проверять все данные, а затем применять порядок, а затем применять только предел, поскольку мы можем получить верхние 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 визуализации, я не могу понять, как это работает? Может кто-нибудь пролить свет на понимание этого. Правильно ли это мое предположение?

Answer 1

Я не читал источник в глубину, но, насколько я могу судить, он поддерживает кучу с ограниченным размером.

Он потребляет входные значения в последовательности. После того, как он заполняет кучу до целевого количества кортежей, он начинает изучать каждое новое значение, чтобы увидеть, больше ли оно всех текущих значений, меньше всех текущих значений или помещается внутри кучи.

Если он больше всех текущих значений (при условии сортировки по ASC), он отбрасывается, так как мы уже имеем более низкие значения.

Если он меньше, чем все текущие значения или некоторые текущие значения, он вставлен в соответствующую точку кучи, все сдвигается на один, и он ударяет последний вход из кучи.

См. src/backend/utils/sort/tuplesort.c вокруг линии 1618 (в git master), case TSS_BOUNDED: в puttuple_common.

Answer 2

Визуализацию, на которую вы ссылаетесь, - это всего лишь исполнение, выполняемое с помощью heapsort. Структура данных кучи представляет собой (двоичное) дерево с тем свойством, что значение в каждом узле больше (или меньше), чем значения в его дочерних элементах. Куча может храниться в массиве, что и демонстрирует визуализация.

Куча может использоваться как эффективная очередь приоритетов. Поскольку он только частично отсортирован, дешевле использовать в качестве очереди приоритетов, чем отсортированный список или что-то подобное. Вероятно, это то, что делает Postgres: если вы выберете N наибольших значений из таблицы, Postgres сохранит приоритетную очередь (реализуемую кучей) из N наибольших значений, которые были обнаружены до сих пор, с наименьшим значением вначале (то есть в верхней части куча). Если новое значение еще меньше этого первого элемента очереди приоритетов, новое значение может быть отброшено. Если он больше, удалите первое значение из очереди приоритетов и вставьте новое значение.