Skip to content

Commit 8b304b8

Browse files
robertmhaasrobertmhaas
committed
Remove replacement selection sort.
At the time replacement_sort_tuples was introduced, there were still cases where replacement selection sort noticeably outperformed using quicksort even for the first run. However, those cases seem to have evaporated as a result of further improvements made since that time (and perhaps also advances in CPU technology). So remove replacement selection and the controlling GUC entirely. This makes tuplesort.c noticeably simpler and probably paves the way for further optimizations someone might want to do later. Peter Geoghegan, with review and testing by Tomas Vondra and me. Discussion: https://postgr.es/m/CAH2-WzmmNjG_K0R9nqYwMq3zjyJJK+hCbiZYNGhAy-Zyjs64GQ@mail.gmail.com
1 parent d2773f9 commit 8b304b8

File tree

9 files changed

+52
-448
lines changed

9 files changed

+52
-448
lines changed

‎doc/src/sgml/config.sgml

Lines changed: 0 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -1505,45 +1505,6 @@ include_dir 'conf.d'
15051505
</listitem>
15061506
</varlistentry>
15071507

1508-
<varlistentry id="guc-replacement-sort-tuples" xreflabel="replacement_sort_tuples">
1509-
<term><varname>replacement_sort_tuples</varname> (<type>integer</type>)
1510-
<indexterm>
1511-
<primary><varname>replacement_sort_tuples</> configuration parameter</primary>
1512-
</indexterm>
1513-
</term>
1514-
<listitem>
1515-
<para>
1516-
When the number of tuples to be sorted is smaller than this number,
1517-
a sort will produce its first output run using replacement selection
1518-
rather than quicksort. This may be useful in memory-constrained
1519-
environments where tuples that are input into larger sort operations
1520-
have a strong physical-to-logical correlation. Note that this does
1521-
not include input tuples with an <emphasis>inverse</emphasis>
1522-
correlation. It is possible for the replacement selection algorithm
1523-
to generate one long run that requires no merging, where use of the
1524-
default strategy would result in many runs that must be merged
1525-
to produce a final sorted output. This may allow sort
1526-
operations to complete sooner.
1527-
</para>
1528-
<para>
1529-
The default is 150,000 tuples. Note that higher values are typically
1530-
not much more effective, and may be counter-productive, since the
1531-
priority queue is sensitive to the size of available CPU cache, whereas
1532-
the default strategy sorts runs using a <firstterm>cache
1533-
oblivious</firstterm> algorithm. This property allows the default sort
1534-
strategy to automatically and transparently make effective use
1535-
of available CPU cache.
1536-
</para>
1537-
<para>
1538-
Setting <varname>maintenance_work_mem</varname> to its default
1539-
value usually prevents utility command external sorts (e.g.,
1540-
sorts used by <command>CREATE INDEX</> to build B-Tree
1541-
indexes) from ever using replacement selection sort, unless the
1542-
input tuples are quite wide.
1543-
</para>
1544-
</listitem>
1545-
</varlistentry>
1546-
15471508
<varlistentry id="guc-autovacuum-work-mem" xreflabel="autovacuum_work_mem">
15481509
<term><varname>autovacuum_work_mem</varname> (<type>integer</type>)
15491510
<indexterm>

‎doc/src/sgml/release-9.6.sgml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5140,7 +5140,7 @@ and many others in the same vein
51405140
The new approach makes better use of the <acronym>CPU</> cache
51415141
for typical cache sizes and data volumes. Where necessary,
51425142
the behavior can be adjusted via the new configuration parameter
5143-
<xref linkend="guc-replacement-sort-tuples">.
5143+
<literal>replacement_sort_tuples</literal>.
51445144
</para>
51455145
</listitem>
51465146

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

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -112,7 +112,6 @@ bool enableFsync = true;
112112
bool allowSystemTableMods = false;
113113
int work_mem = 1024;
114114
int maintenance_work_mem = 16384;
115-
int replacement_sort_tuples = 150000;
116115

117116
/*
118117
* Primary determinants of sizes of shared-memory structures.

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

Lines changed: 0 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1933,16 +1933,6 @@ static struct config_int ConfigureNamesInt[] =
19331933
NULL, NULL, NULL
19341934
},
19351935

1936-
{
1937-
{"replacement_sort_tuples", PGC_USERSET, RESOURCES_MEM,
1938-
gettext_noop("Sets the maximum number of tuples to be sorted using replacement selection."),
1939-
gettext_noop("When more tuples than this are present, quicksort will be used.")
1940-
},
1941-
&replacement_sort_tuples,
1942-
150000, 0, INT_MAX,
1943-
NULL, NULL, NULL
1944-
},
1945-
19461936
/*
19471937
* We use the hopefully-safely-small value of 100kB as the compiled-in
19481938
* default for max_stack_depth. InitializeGUCOptions will increase it if

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

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -121,7 +121,6 @@
121121
# you actively intend to use prepared transactions.
122122
#work_mem = 4MB # min 64kB
123123
#maintenance_work_mem = 64MB # min 1MB
124-
#replacement_sort_tuples = 150000 # limits use of replacement selection sort
125124
#autovacuum_work_mem = -1 # min 1MB, or -1 to use maintenance_work_mem
126125
#max_stack_depth = 2MB # min 100kB
127126
#dynamic_shared_memory_type = posix # the default is the first option

0 commit comments

Comments
 (0)