Skip to content

Commit d2d8a22

Browse files
tvondratvondra
committed
Implement Incremental Sort
Incremental Sort is an optimized variant of multikey sort for cases when the input is already sorted by a prefix of the requested sort keys. For example when the relation is already sorted by (key1, key2) and we need to sort it by (key1, key2, key3) we can simply split the input rows into groups having equal values in (key1, key2), and only sort/compare the remaining column key3. This has a number of benefits: - Reduced memory consumption, because only a single group (determined by values in the sorted prefix) needs to be kept in memory. This may also eliminate the need to spill to disk. - Lower startup cost, because Incremental Sort produce results after each prefix group, which is beneficial for plans where startup cost matters (like for example queries with LIMIT clause). We consider both Sort and Incremental Sort, and decide based on costing. The implemented algorithm operates in two different modes: - Fetching a minimum number of tuples without check of equality on the prefix keys, and sorting on all columns when safe. - Fetching all tuples for a single prefix group and then sorting by comparing only the remaining (non-prefix) keys. We always start in the first mode, and employ a heuristic to switch into the second mode if we believe it's beneficial - the goal is to minimize the number of unnecessary comparions while keeping memory consumption below work_mem. This is a very old patch series. The idea was originally proposed by Alexander Korotkov back in 2013, and then revived in 2017. In 2018 the patch was taken over by James Coleman, who wrote and rewrote most of the current code. There were many reviewers/contributors since 2013 - I've done my best to pick the most active ones, and listed them in this commit message. Author: James Coleman, Alexander Korotkov Reviewed-by: Tomas Vondra, Andreas Karlsson, Marti Raudsepp, Peter Geoghegan, Robert Haas, Thomas Munro, Antonin Houska, Andres Freund, Alexander Kuzmenkov Discussion: https://postgr.es/m/CAPpHfdscOX5an71nHd8WSUH6GNOCf=V7wgDaTXdDd9=goN-gfA@mail.gmail.com Discussion: https://postgr.es/m/CAPpHfds1waRZ=NOmueYq0sx1ZSCnt+5QJvizT8ndT2=etZEeAQ@mail.gmail.com
1 parent 3c85535 commit d2d8a22

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

41 files changed

+4239
-155
lines changed

‎doc/src/sgml/config.sgml

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4573,6 +4573,20 @@ ANY <replaceable class="parameter">num_sync</replaceable> ( <replaceable class="
45734573
</listitem>
45744574
</varlistentry>
45754575

4576+
<varlistentry id="guc-enable-incrementalsort" xreflabel="enable_incrementalsort">
4577+
<term><varname>enable_incrementalsort</varname> (<type>boolean</type>)
4578+
<indexterm>
4579+
<primary><varname>enable_incrementalsort</varname> configuration parameter</primary>
4580+
</indexterm>
4581+
</term>
4582+
<listitem>
4583+
<para>
4584+
Enables or disables the query planner's use of incremental sort steps.
4585+
The default is <literal>on</literal>.
4586+
</para>
4587+
</listitem>
4588+
</varlistentry>
4589+
45764590
<varlistentry id="guc-enable-indexscan" xreflabel="enable_indexscan">
45774591
<term><varname>enable_indexscan</varname> (<type>boolean</type>)
45784592
<indexterm>

‎doc/src/sgml/perform.sgml

Lines changed: 41 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -291,7 +291,47 @@ EXPLAIN SELECT * FROM tenk1 WHERE unique1 = 42;
291291
often see this plan type for queries that fetch just a single row. It's
292292
also often used for queries that have an <literal>ORDER BY</literal> condition
293293
that matches the index order, because then no extra sorting step is needed
294-
to satisfy the <literal>ORDER BY</literal>.
294+
to satisfy the <literal>ORDER BY</literal>. In this example, adding
295+
<literal>ORDER BY unique1</literal> would use the same plan because the
296+
index already implicitly provides the requested ordering.
297+
</para>
298+
299+
<para>
300+
The planner may implement an <literal>ORDER BY</literal> clause in several
301+
ways. The above example shows that such an ordering clause may be
302+
implemented implicitly. The planner may also add an explicit
303+
<literal>sort</literal> step:
304+
305+
<screen>
306+
EXPLAIN SELECT * FROM tenk1 ORDER BY unique1;
307+
QUERY PLAN
308+
-------------------------------------------------------------------
309+
Sort (cost=1109.39..1134.39 rows=10000 width=244)
310+
Sort Key: unique1
311+
-> Seq Scan on tenk1 (cost=0.00..445.00 rows=10000 width=244)
312+
</screen>
313+
314+
If the a part of the plan guarantess an ordering on a prefix of the
315+
required sort keys, then the planner may instead decide to use an
316+
<literal>incremental sort</literal> step:
317+
318+
<screen>
319+
EXPLAIN SELECT * FROM tenk1 ORDER BY four, ten LIMIT 100;
320+
QUERY PLAN
321+
------------------------------------------------------------------------------------------------------
322+
Limit (cost=521.06..538.05 rows=100 width=244)
323+
-> Incremental Sort (cost=521.06..2220.95 rows=10000 width=244)
324+
Sort Key: four, ten
325+
Presorted Key: four
326+
-> Index Scan using index_tenk1_on_four on tenk1 (cost=0.29..1510.08 rows=10000 width=244)
327+
</screen>
328+
329+
Compared to regular sorts, sorting incrementally allows returning tuples
330+
before the entire result set has been sorted, which particularly enables
331+
optimizations with <literal>LIMIT</literal> queries. It may also reduce
332+
memory usage and the likelihood of spilling sorts to disk, but it comes at
333+
the cost of the increased overhead of splitting the result set into multiple
334+
sorting batches.
295335
</para>
296336

297337
<para>

0 commit comments

Comments
 (0)