Skip to content

Commit 0711803

Browse files
robertmhaasrobertmhaas
committed
Use quicksort, not replacement selection, for external sorting.
We still use replacement selection for the first run of the sort only and only when the number of tuples is relatively small. Otherwise, the first run, and subsequent runs in all cases, are produced using quicksort. This tends to be faster except perhaps for very small amounts of working memory. Peter Geoghegan, reviewed by Tomas Vondra, Jeff Janes, Mithun Cy, Greg Stark, and me.
1 parent 719c84c commit 0711803

File tree

7 files changed

+430
-91
lines changed

7 files changed

+430
-91
lines changed

‎doc/src/sgml/config.sgml

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1472,6 +1472,45 @@ include_dir 'conf.d'
14721472
</listitem>
14731473
</varlistentry>
14741474

1475+
<varlistentry id="guc-replacement-sort-tuples" xreflabel="replacement_sort_tuples">
1476+
<term><varname>replacement_sort_tuples</varname> (<type>integer</type>)
1477+
<indexterm>
1478+
<primary><varname>replacement_sort_tuples</> configuration parameter</primary>
1479+
</indexterm>
1480+
</term>
1481+
<listitem>
1482+
<para>
1483+
When the number of tuples to be sorted is smaller than this number,
1484+
a sort will produce its first output run using replacement selection
1485+
rather than quicksort. This may be useful in memory-constrained
1486+
environments where tuples that are input into larger sort operations
1487+
have a strong physical-to-logical correlation. Note that this does
1488+
not include input tuples with an <emphasis>inverse</emphasis>
1489+
correlation. It is possible for the replacement selection algorithm
1490+
to generate one long run that requires no merging, where use of the
1491+
default strategy would result in many runs that must be merged
1492+
to produce a final sorted output. This may allow sort
1493+
operations to complete sooner.
1494+
</para>
1495+
<para>
1496+
The default is 150,000 tuples. Note that higher values are typically
1497+
not much more effective, and may be counter-productive, since the
1498+
priority queue is sensitive to the size of available CPU cache, whereas
1499+
the default strategy sorts runs using a <firstterm>cache
1500+
oblivious</firstterm> algorithm. This property allows the default sort
1501+
strategy to automatically and transparently make effective use
1502+
of available CPU cache.
1503+
</para>
1504+
<para>
1505+
Setting <varname>maintenance_work_mem</varname> to its default
1506+
value usually prevents utility command external sorts (e.g.,
1507+
sorts used by <command>CREATE INDEX</> to build B-Tree
1508+
indexes) from ever using replacement selection sort, unless the
1509+
input tuples are quite wide.
1510+
</para>
1511+
</listitem>
1512+
</varlistentry>
1513+
14751514
<varlistentry id="guc-autovacuum-work-mem" xreflabel="autovacuum_work_mem">
14761515
<term><varname>autovacuum_work_mem</varname> (<type>integer</type>)
14771516
<indexterm>

‎src/backend/optimizer/path/costsize.c

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1432,8 +1432,8 @@ cost_recursive_union(Path *runion, Path *nrterm, Path *rterm)
14321432
* total, but we will also need to write and read each tuple once per
14331433
* merge pass. We expect about ceil(logM(r)) merge passes where r is the
14341434
* number of initial runs formed and M is the merge order used by tuplesort.c.
1435-
* Since the average initial run should be about twice sort_mem, we have
1436-
* disk traffic = 2 * relsize * ceil(logM(p / (2*sort_mem)))
1435+
* Since the average initial run should be about sort_mem, we have
1436+
* disk traffic = 2 * relsize * ceil(logM(p / sort_mem))
14371437
* cpu = comparison_cost * t * log2(t)
14381438
*
14391439
* If the sort is bounded (i.e., only the first k result tuples are needed)
@@ -1509,7 +1509,7 @@ cost_sort(Path *path, PlannerInfo *root,
15091509
* We'll have to use a disk-based sort of all the tuples
15101510
*/
15111511
double npages = ceil(input_bytes / BLCKSZ);
1512-
double nruns = (input_bytes / sort_mem_bytes) * 0.5;
1512+
double nruns = input_bytes / sort_mem_bytes;
15131513
double mergeorder = tuplesort_merge_order(sort_mem_bytes);
15141514
double log_runs;
15151515
double npageaccesses;

‎src/backend/utils/init/globals.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,7 @@ bool enableFsync = true;
109109
bool allowSystemTableMods = false;
110110
int work_mem = 1024;
111111
int maintenance_work_mem = 16384;
112+
int replacement_sort_tuples = 150000;
112113

113114
/*
114115
* Primary determinants of sizes of shared-memory structures.

‎src/backend/utils/misc/guc.c

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1928,6 +1928,16 @@ static struct config_int ConfigureNamesInt[] =
19281928
NULL, NULL, NULL
19291929
},
19301930

1931+
{
1932+
{"replacement_sort_tuples", PGC_USERSET, RESOURCES_MEM,
1933+
gettext_noop("Sets the maximum number of tuples to be sorted using replacement selection."),
1934+
gettext_noop("When more tuples than this are present, quicksort will be used.")
1935+
},
1936+
&replacement_sort_tuples,
1937+
150000, 0, INT_MAX,
1938+
NULL, NULL, NULL
1939+
},
1940+
19311941
/*
19321942
* We use the hopefully-safely-small value of 100kB as the compiled-in
19331943
* default for max_stack_depth. InitializeGUCOptions will increase it if

‎src/backend/utils/misc/postgresql.conf.sample

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -125,6 +125,7 @@
125125
# actively intend to use prepared transactions.
126126
#work_mem = 4MB # min 64kB
127127
#maintenance_work_mem = 64MB # min 1MB
128+
#replacement_sort_tuples = 150000 # limits use of replacement selection sort
128129
#autovacuum_work_mem = -1 # min 1MB, or -1 to use maintenance_work_mem
129130
#max_stack_depth = 2MB # min 100kB
130131
#dynamic_shared_memory_type = posix # the default is the first option

0 commit comments

Comments
 (0)