public inbox for [email protected]
help / color / mirror / Atom feed[PATCH v13 01/18] Allow CREATE INDEX CONCURRENTLY on partitioned table
3+ messages / 3 participants
[nested] [flat]
* [PATCH v13 01/18] Allow CREATE INDEX CONCURRENTLY on partitioned table
@ 2020-06-06 22:42 Justin Pryzby <[email protected]>
0 siblings, 0 replies; 3+ messages in thread
From: Justin Pryzby @ 2020-06-06 22:42 UTC (permalink / raw)
Note, this effectively reverts 050098b14, so take care to not reintroduce the
bug it fixed.
---
doc/src/sgml/ref/create_index.sgml | 9 --
src/backend/commands/indexcmds.c | 143 ++++++++++++++++++-------
src/test/regress/expected/indexing.out | 60 ++++++++++-
src/test/regress/sql/indexing.sql | 18 +++-
4 files changed, 176 insertions(+), 54 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index a5271a9f8f..6869a18968 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -686,15 +686,6 @@ Indexes:
cannot.
</para>
- <para>
- Concurrent builds for indexes on partitioned tables are currently not
- supported. However, you may concurrently build the index on each
- partition individually and then finally create the partitioned index
- non-concurrently in order to reduce the time where writes to the
- partitioned table will be locked out. In this case, building the
- partitioned index is a metadata only operation.
- </para>
-
</refsect2>
</refsect1>
diff --git a/src/backend/commands/indexcmds.c b/src/backend/commands/indexcmds.c
index 127ba7835d..4ac1dacd7d 100644
--- a/src/backend/commands/indexcmds.c
+++ b/src/backend/commands/indexcmds.c
@@ -68,6 +68,7 @@
/* non-export function prototypes */
+static void reindex_invalid_child_indexes(Oid indexRelationId);
static bool CompareOpclassOptions(Datum *opts1, Datum *opts2, int natts);
static void CheckPredicate(Expr *predicate);
static void ComputeIndexAttrs(IndexInfo *indexInfo,
@@ -680,17 +681,6 @@ DefineIndex(Oid relationId,
partitioned = rel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE;
if (partitioned)
{
- /*
- * Note: we check 'stmt->concurrent' rather than 'concurrent', so that
- * the error is thrown also for temporary tables. Seems better to be
- * consistent, even though we could do it on temporary table because
- * we're not actually doing it concurrently.
- */
- if (stmt->concurrent)
- ereport(ERROR,
- (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
- errmsg("cannot create index on partitioned table \"%s\" concurrently",
- RelationGetRelationName(rel))));
if (stmt->excludeOpNames)
ereport(ERROR,
(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
@@ -1128,6 +1118,11 @@ DefineIndex(Oid relationId,
if (pd->nparts != 0)
flags |= INDEX_CREATE_INVALID;
}
+ else if (concurrent && OidIsValid(parentIndexId))
+ {
+ /* If concurrent, initially build index partitions as "invalid" */
+ flags |= INDEX_CREATE_INVALID;
+ }
if (stmt->deferrable)
constr_flags |= INDEX_CONSTR_CREATE_DEFERRABLE;
@@ -1183,6 +1178,14 @@ DefineIndex(Oid relationId,
partdesc = RelationGetPartitionDesc(rel);
if ((!stmt->relation || stmt->relation->inh) && partdesc->nparts > 0)
{
+ /*
+ * Need to close the relation before recursing into children, so
+ * copy needed data into a longlived context.
+ */
+
+ MemoryContext ind_context = AllocSetContextCreate(PortalContext, "CREATE INDEX",
+ ALLOCSET_DEFAULT_SIZES);
+ MemoryContext oldcontext = MemoryContextSwitchTo(ind_context);
int nparts = partdesc->nparts;
Oid *part_oids = palloc(sizeof(Oid) * nparts);
bool invalidate_parent = false;
@@ -1193,8 +1196,10 @@ DefineIndex(Oid relationId,
nparts);
memcpy(part_oids, partdesc->oids, sizeof(Oid) * nparts);
+ parentDesc = CreateTupleDescCopy(RelationGetDescr(rel));
+ table_close(rel, NoLock);
+ MemoryContextSwitchTo(oldcontext);
- parentDesc = RelationGetDescr(rel);
opfamOids = palloc(sizeof(Oid) * numberOfKeyAttributes);
for (i = 0; i < numberOfKeyAttributes; i++)
opfamOids[i] = get_opclass_family(classObjectId[i]);
@@ -1237,10 +1242,12 @@ DefineIndex(Oid relationId,
continue;
}
+ oldcontext = MemoryContextSwitchTo(ind_context);
childidxs = RelationGetIndexList(childrel);
attmap =
build_attrmap_by_name(RelationGetDescr(childrel),
parentDesc);
+ MemoryContextSwitchTo(oldcontext);
foreach(cell, childidxs)
{
@@ -1311,10 +1318,14 @@ DefineIndex(Oid relationId,
*/
if (!found)
{
- IndexStmt *childStmt = copyObject(stmt);
+ IndexStmt *childStmt;
bool found_whole_row;
ListCell *lc;
+ oldcontext = MemoryContextSwitchTo(ind_context);
+ childStmt = copyObject(stmt);
+ MemoryContextSwitchTo(oldcontext);
+
/*
* We can't use the same index name for the child index,
* so clear idxname to let the recursive invocation choose
@@ -1366,10 +1377,18 @@ DefineIndex(Oid relationId,
createdConstraintId,
is_alter_table, check_rights, check_not_in_use,
skip_build, quiet);
+ if (concurrent)
+ {
+ PopActiveSnapshot();
+ PushActiveSnapshot(GetTransactionSnapshot());
+ invalidate_parent = true;
+ }
}
- pgstat_progress_update_param(PROGRESS_CREATEIDX_PARTITIONS_DONE,
- i + 1);
+ /* For concurrent build, this is a catalog-only stage */
+ if (!concurrent)
+ pgstat_progress_update_param(PROGRESS_CREATEIDX_PARTITIONS_DONE,
+ i + 1);
free_attrmap(attmap);
}
@@ -1379,41 +1398,33 @@ DefineIndex(Oid relationId,
* invalid, this is incorrect, so update our row to invalid too.
*/
if (invalidate_parent)
- {
- Relation pg_index = table_open(IndexRelationId, RowExclusiveLock);
- HeapTuple tup,
- newtup;
-
- tup = SearchSysCache1(INDEXRELID,
- ObjectIdGetDatum(indexRelationId));
- if (!HeapTupleIsValid(tup))
- elog(ERROR, "cache lookup failed for index %u",
- indexRelationId);
- newtup = heap_copytuple(tup);
- ((Form_pg_index) GETSTRUCT(newtup))->indisvalid = false;
- CatalogTupleUpdate(pg_index, &tup->t_self, newtup);
- ReleaseSysCache(tup);
- table_close(pg_index, RowExclusiveLock);
- heap_freetuple(newtup);
- }
- }
+ index_set_state_flags(indexRelationId, INDEX_DROP_CLEAR_VALID);
+ } else
+ table_close(rel, NoLock);
/*
* Indexes on partitioned tables are not themselves built, so we're
* done here.
*/
- table_close(rel, NoLock);
if (!OidIsValid(parentIndexId))
+ {
+ if (concurrent)
+ reindex_invalid_child_indexes(indexRelationId);
+
pgstat_progress_end_command();
+ }
+
return address;
}
- if (!concurrent)
+ if (!concurrent || OidIsValid(parentIndexId))
{
- /* Close the heap and we're done, in the non-concurrent case */
- table_close(rel, NoLock);
+ /*
+ * We're done if this is the top-level index,
+ * or the catalog-only phase of a partition built concurrently
+ */
- /* If this is the top-level index, we're done. */
+ table_close(rel, NoLock);
if (!OidIsValid(parentIndexId))
pgstat_progress_end_command();
@@ -1617,6 +1628,62 @@ DefineIndex(Oid relationId,
return address;
}
+/* Reindex invalid child indexes created earlier */
+static void
+reindex_invalid_child_indexes(Oid indexRelationId)
+{
+ ListCell *lc;
+ int npart = 0;
+ ReindexParams params = {
+ .options = REINDEXOPT_CONCURRENTLY
+ };
+
+ MemoryContext ind_context = AllocSetContextCreate(PortalContext, "CREATE INDEX",
+ ALLOCSET_DEFAULT_SIZES);
+ MemoryContext oldcontext;
+ List *childs = find_inheritance_children(indexRelationId, ShareLock);
+ List *partitions = NIL;
+
+ PreventInTransactionBlock(true, "REINDEX INDEX");
+
+ foreach (lc, childs)
+ {
+ Oid partoid = lfirst_oid(lc);
+
+ /* XXX: need to retrofit progress reporting into it */
+ // pgstat_progress_update_param(PROGRESS_CREATEIDX_PARTITIONS_DONE,
+ // npart++);
+
+ if (get_index_isvalid(partoid) ||
+ !RELKIND_HAS_STORAGE(get_rel_relkind(partoid)))
+ continue;
+
+ /* Save partition OID */
+ oldcontext = MemoryContextSwitchTo(ind_context);
+ partitions = lappend_oid(partitions, partoid);
+ MemoryContextSwitchTo(oldcontext);
+ }
+
+ /*
+ * Process each partition listed in a separate transaction. Note that
+ * this commits and then starts a new transaction immediately.
+ * XXX: since this is done in 2*N transactions, it could just as well
+ * call ReindexRelationConcurrently directly
+ */
+ ReindexMultipleInternal(partitions, ¶ms);
+
+ /*
+ * CIC needs to mark a partitioned index as VALID, which itself
+ * requires setting READY, which is unset for CIC (even though
+ * it's meaningless for an index without storage).
+ * This must be done only while holding a lock which precludes adding
+ * partitions.
+ * See also: validatePartitionedIndex().
+ */
+ index_set_state_flags(indexRelationId, INDEX_CREATE_SET_READY);
+ CommandCounterIncrement();
+ index_set_state_flags(indexRelationId, INDEX_CREATE_SET_VALID);
+}
/*
* CheckMutability
diff --git a/src/test/regress/expected/indexing.out b/src/test/regress/expected/indexing.out
index c93f4470c9..f04abc6897 100644
--- a/src/test/regress/expected/indexing.out
+++ b/src/test/regress/expected/indexing.out
@@ -50,11 +50,63 @@ select relname, relkind, relhassubclass, inhparent::regclass
(8 rows)
drop table idxpart;
--- Some unsupported features
+-- CIC on partitioned table
create table idxpart (a int, b int, c text) partition by range (a);
-create table idxpart1 partition of idxpart for values from (0) to (10);
-create index concurrently on idxpart (a);
-ERROR: cannot create index on partitioned table "idxpart" concurrently
+create table idxpart1 partition of idxpart for values from (0) to (10) partition by range(a);
+create table idxpart11 partition of idxpart1 for values from (0) to (10) partition by range(a);
+create table idxpart111 partition of idxpart11 default partition by range(a);
+create table idxpart1111 partition of idxpart111 default partition by range(a);
+create table idxpart2 partition of idxpart for values from (10) to (20);
+insert into idxpart2 values(10),(10); -- not unique
+create index concurrently on idxpart (a); -- partitioned
+create index concurrently on idxpart1 (a); -- partitioned and partition
+create index concurrently on idxpart11 (a); -- partitioned and partition, with no leaves
+create index concurrently on idxpart2 (a); -- leaf
+create unique index concurrently on idxpart (a); -- partitioned, unique failure
+ERROR: could not create unique index "idxpart2_a_idx2_ccnew"
+DETAIL: Key (a)=(10) is duplicated.
+\d idxpart
+ Partitioned table "public.idxpart"
+ Column | Type | Collation | Nullable | Default
+--------+---------+-----------+----------+---------
+ a | integer | | |
+ b | integer | | |
+ c | text | | |
+Partition key: RANGE (a)
+Indexes:
+ "idxpart_a_idx" btree (a)
+ "idxpart_a_idx1" UNIQUE, btree (a) INVALID
+Number of partitions: 2 (Use \d+ to list them.)
+
+\d idxpart1
+ Partitioned table "public.idxpart1"
+ Column | Type | Collation | Nullable | Default
+--------+---------+-----------+----------+---------
+ a | integer | | |
+ b | integer | | |
+ c | text | | |
+Partition of: idxpart FOR VALUES FROM (0) TO (10)
+Partition key: RANGE (a)
+Indexes:
+ "idxpart1_a_idx" btree (a) INVALID
+ "idxpart1_a_idx1" btree (a)
+ "idxpart1_a_idx2" UNIQUE, btree (a) INVALID
+Number of partitions: 1 (Use \d+ to list them.)
+
+\d idxpart2
+ Table "public.idxpart2"
+ Column | Type | Collation | Nullable | Default
+--------+---------+-----------+----------+---------
+ a | integer | | |
+ b | integer | | |
+ c | text | | |
+Partition of: idxpart FOR VALUES FROM (10) TO (20)
+Indexes:
+ "idxpart2_a_idx" btree (a)
+ "idxpart2_a_idx1" btree (a)
+ "idxpart2_a_idx2" UNIQUE, btree (a) INVALID
+ "idxpart2_a_idx2_ccnew" UNIQUE, btree (a) INVALID
+
drop table idxpart;
-- Verify bugfix with query on indexed partitioned table with no partitions
-- https://postgr.es/m/[email protected]
diff --git a/src/test/regress/sql/indexing.sql b/src/test/regress/sql/indexing.sql
index 42f398b67c..3d4b6e9bc9 100644
--- a/src/test/regress/sql/indexing.sql
+++ b/src/test/regress/sql/indexing.sql
@@ -29,10 +29,22 @@ select relname, relkind, relhassubclass, inhparent::regclass
where relname like 'idxpart%' order by relname;
drop table idxpart;
--- Some unsupported features
+-- CIC on partitioned table
create table idxpart (a int, b int, c text) partition by range (a);
-create table idxpart1 partition of idxpart for values from (0) to (10);
-create index concurrently on idxpart (a);
+create table idxpart1 partition of idxpart for values from (0) to (10) partition by range(a);
+create table idxpart11 partition of idxpart1 for values from (0) to (10) partition by range(a);
+create table idxpart111 partition of idxpart11 default partition by range(a);
+create table idxpart1111 partition of idxpart111 default partition by range(a);
+create table idxpart2 partition of idxpart for values from (10) to (20);
+insert into idxpart2 values(10),(10); -- not unique
+create index concurrently on idxpart (a); -- partitioned
+create index concurrently on idxpart1 (a); -- partitioned and partition
+create index concurrently on idxpart11 (a); -- partitioned and partition, with no leaves
+create index concurrently on idxpart2 (a); -- leaf
+create unique index concurrently on idxpart (a); -- partitioned, unique failure
+\d idxpart
+\d idxpart1
+\d idxpart2
drop table idxpart;
-- Verify bugfix with query on indexed partitioned table with no partitions
--
2.17.0
--QTprm0S8XgL7H0Dt
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
filename="v13-0002-f-progress-reporting.patch"
^ permalink raw reply [nested|flat] 3+ messages in thread
* An implementation of multi-key sort
@ 2024-05-22 12:48 Wang Yao <[email protected]>
2024-05-22 15:29 ` Re: An implementation of multi-key sort Heikki Linnakangas <[email protected]>
0 siblings, 1 reply; 3+ messages in thread
From: Wang Yao @ 2024-05-22 12:48 UTC (permalink / raw)
To: pgsql-hackers; +Cc: [email protected] <[email protected]>
Hi hackers,
I'd submit an implementation of multi-key sort for review. Please see the
code as attachment. Thanks for your reponse in advance.
Overview
--------
MKsort (multi-key sort) is an alternative of standard qsort algorithm,
which has better performance for particular sort scenarios, i.e. the data
set has multiple keys to be sorted.
The implementation is based on the paper:
Jon L. Bentley and Robert Sedgewick, "Fast Algorithms for Sorting and
Searching Strings", Jan 1997 [1]
MKsort is applied only for tuple sort by the patch. Theoretically it can
be applied for general-purpose sort scenario when there are multiple sort
keys available, but it is relatively difficult in practice because kind of
unique interface is needed to manipulate the keys. So I limit the usage of
mksort to sort SortTuple.
Comparing to classic quick sort, it can get significant performance
improvement once multiple keys are available. A rough test shows it got
~129% improvement than qsort for ORDER BY on 6 keys, and ~52% for CREATE
INDEX on the same data set. (See more details in section "Performance
Test")
Author: Yao Wang <[email protected]>
Co-author: Hongxu Ma <[email protected]>
Scope
-----
The interface of mksort is pretty simple: in tuplesort_sort_memtuples(),
mksort_tuple() is invoked instead of qsort_tuple() if mksort is applicable.
The major logic in mksort_tuple() is to apply mksort algorithm on
SortTuple, and kind of callback mechanism is used to handle
sort-variant-specific issue, e.g. comparing different datums, like
qsort_tuple() does. It also handles the complexity of "abbreviated keys".
A small difference from classic mksort algorithm is: for IndexTuple, when
all the columns are equal, an additional comparing based on ItemPointer
is performed to determine the order. It is to make the result consistent
to existing qsort.
I did consider about implementing mksort by the approach of kind of
template mechanism like qsort (see sort_template.h), but it seems
unnecessary because all concrete tuple types need to be handled are
derived from SortTuple. Use callback to isolate type specific features
is good enough.
Note that not all tuple types are supported by mksort. Please see the
comments inside tuplesort_sort_memtuples().
Test Cases
----------
The changes of test cases include:
* Generally, mksort should generate result exactly same to qsort. However
some test cases don't. The reason is that SQL doesn't specify order on
all possible columns, e.g. "select c1, c2 from t1 order by c1" will
generate different results between mksort/qsort when c1 values are equal,
and the solution is to order c2 as well ("select c1, c2 from t1 order by
c1, c2"). (e.g. geometry)
* Some cases need to be updated to display the new sort method "multi-key
sort" in explain result. (e.g. incremental_sort)
* regress/tuplesort was updated with new cases to cover some scenarios of
mksort.
Performance Test
----------------
The script I used to configure the build:
CFLAGS="-O3 -fargument-noalias-global -fno-omit-frame-pointer -g"
./configure --prefix=$PGHOME --with-pgport=5432 --with-perl --with-openssl
--with-python --with-pam --with-blocksize=16 --with-wal-blocksize=16
--with-perl --enable-tap-tests --with-gssapi --with-ldap
I used the script for a rough test for ORDER BY:
\timing on
create table t1 (c1 int, c2 int, c3 int, c4 int, c5 int, c6 varchar(100));
insert into t1 values (generate_series(1,499999), 0, 0, 0, 0,
'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb');
update t1 set c2 = c1 % 100, c3 = c1 % 50, c4 = c1 % 10, c5 = c1 % 3;
update t1 set c6 = 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb'
|| (c1 % 5)::text;
-- Use a large work mem to ensure the entire sort happens in memory
set work_mem='1GB';
-- switch between qsort/mksort
set enable_mk_sort=off;
explain analyze select c1 from t1 order by c6, c5, c4, c3, c2, c1;
Results:
mksort:
1341.283 ms (00:01.341)
1379.098 ms (00:01.379)
1369.868 ms (00:01.370)
qsort:
3137.277 ms (00:03.137)
3147.771 ms (00:03.148)
3131.887 ms (00:03.132)
The perf improvement is ~129%.
Another perf test for CREATE INDEX:
create index idx_t1_mk on t3 (c6, c5, c4, c3, c2, c1);
Results:
mksort:
1147.207 ms (00:01.147)
1200.501 ms (00:01.201)
1235.657 ms (00:01.236)
Qsort:
1852.957 ms (00:01.853)
1824.209 ms (00:01.824)
1808.781 ms (00:01.809)
The perf improvement is ~52%.
Another test is to use one of queries of TPC-H:
set work_mem='1GB';
-- query rewritten from TPCH-Q1, and there are 6001215 rows in lineitem
explain analyze select
l_returnflag,l_linestatus,l_quantity,l_shipmode
from
lineitem
where
l_shipdate <= date'1998-12-01' - interval '65 days'
order by
l_returnflag,l_linestatus,l_quantity,l_shipmode;
Result:
Qsort:
14582.626 ms
14524.188 ms
14524.111 ms
mksort:
11390.891 ms
11647.065 ms
11546.791 ms
The perf improvement is ~25.8%.
[1] https://www.cs.tufts.edu/~nr/cs257/archive/bob-sedgewick/fast-strings.pdf
[2] https://www.tpc.org/tpch/
Thanks,
Yao Wang
Attachments:
[application/octet-stream] 0001-Implement-multi-key-sort.patch (75.1K, ../../PH7P220MB1533DA211DF219996760CBB7D9EB2@PH7P220MB1533.NAMP220.PROD.OUTLOOK.COM/2-0001-Implement-multi-key-sort.patch)
download | inline diff:
From 1d583dec54ecd47912a5d68038bc9a07c2339c45 Mon Sep 17 00:00:00 2001
From: Yao Wang <[email protected]>
Date: Tue, 7 May 2024 08:11:13 +0000
Subject: [PATCH] Implement multi-key sort
MKsort (multi-key sort) is an alternative of standard qsort algorithm,
which has better performance for particular sort scenarios, i.e. the data
set has multiple keys to be sorted. Comparing to classic quick sort, it
can get significant performance improvement once multiple keys are
available.
Author: Yao Wang <[email protected]>
Co-author: Hongxu Ma <[email protected]>
---
src/backend/utils/misc/guc_tables.c | 11 +
src/backend/utils/sort/mksort_tuple.c | 358 +++++++++++++++++
src/backend/utils/sort/tuplesort.c | 44 ++
src/backend/utils/sort/tuplesortvariants.c | 300 +++++++++++++-
src/include/c.h | 4 +
src/include/utils/tuplesort.h | 34 +-
src/test/regress/expected/geometry.out | 4 +-
.../regress/expected/incremental_sort.out | 12 +-
src/test/regress/expected/tuplesort.out | 375 ++++++++++++++++++
src/test/regress/expected/window.out | 58 +--
src/test/regress/sql/geometry.sql | 2 +-
src/test/regress/sql/tuplesort.sql | 59 +++
src/test/regress/sql/window.sql | 22 +-
13 files changed, 1215 insertions(+), 68 deletions(-)
create mode 100644 src/backend/utils/sort/mksort_tuple.c
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 3fd0b14dd8..b8fe447d68 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -103,6 +103,7 @@ extern char *default_tablespace;
extern char *temp_tablespaces;
extern bool ignore_checksum_failure;
extern bool ignore_invalid_pages;
+extern bool enable_mk_sort;
#ifdef TRACE_SYNCSCAN
extern bool trace_syncscan;
@@ -839,6 +840,16 @@ struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_mk_sort", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables multi-key"),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &enable_mk_sort,
+ true,
+ NULL, NULL, NULL
+ },
{
{"enable_hashagg", PGC_USERSET, QUERY_TUNING_METHOD,
gettext_noop("Enables the planner's use of hashed aggregation plans."),
diff --git a/src/backend/utils/sort/mksort_tuple.c b/src/backend/utils/sort/mksort_tuple.c
new file mode 100644
index 0000000000..949e9bbf8d
--- /dev/null
+++ b/src/backend/utils/sort/mksort_tuple.c
@@ -0,0 +1,358 @@
+/*
+ * MKsort (multiple-key sort) is an alternative of standard qsort algorithm,
+ * which has better performance for particular sort scenarios, i.e. the
+ * data set has multiple keys to be sorted.
+ *
+ * The sorting algorithm blends Quicksort and radix sort; Like regular
+ * Quicksort, it partitions its input into sets less than and greater than a
+ * given value; like radix sort, it moves on to the next field once the current
+ * input is known to be equal in the given field.
+ *
+ * The implementation is based on the paper:
+ * Jon L. Bentley and Robert Sedgewick, "Fast Algorithms for Sorting and
+ * Searching Strings", Jan 1997
+ *
+ * Some improvements which is related to additional handling for equal tuples
+ * have been adapted to keep consistency with the implementations of postgres
+ * qsort.
+ *
+ * For now, mksort_tuple() is called in tuplesort_sort_memtuples() as a
+ * replacement of qsort_tuple() when specific conditions are satisfied.
+ */
+
+/* Swap two tuples in sort tuple array */
+static inline void
+mksort_swap(int a,
+ int b,
+ SortTuple *x)
+{
+ SortTuple t;
+
+ if (a == b)
+ return;
+ t = x[a];
+ x[a] = x[b];
+ x[b] = t;
+}
+
+/* Swap tuples by batch in sort tuple array */
+static inline void
+mksort_vec_swap(int a,
+ int b,
+ int size,
+ SortTuple *x)
+{
+ while (size-- > 0)
+ {
+ mksort_swap(a, b, x);
+ a++;
+ b++;
+ }
+}
+
+/*
+ * Check whether current datum (at specified tuple and depth) is null
+ * Note that the input x means a specified tuple provided by caller but not
+ * a tuple array, so tupleIndex is unnecessary
+ */
+static inline bool
+check_datum_null(SortTuple *x,
+ int depth,
+ Tuplesortstate *state)
+{
+ Datum datum;
+ bool isNull;
+
+ /* Since we have a specified tuple, the tupleIndex is always 0 */
+ state->base.mksortGetDatumFunc(x, 0, depth, state, &datum, &isNull, false);
+
+ /*
+ * Note: for "abbreviated key", we don't need to handle more here because
+ * if "abbreviated key" of a datum is null, the "full" datum must be null.
+ */
+
+ return isNull;
+}
+
+/*
+ * Compare two tuples at specified depth
+ *
+ * If "abbreviated key" is disabled:
+ * get specified datums and compare them by ApplySortComparator().
+ * If "abbreviated key" is enabled:
+ * Only first datum may be abbr key according to the design (see the comments
+ * of struct SortTuple), so different operations are needed for different
+ * datum.
+ * For first datum (depth == 0): get first datums ("abbr key" version) and
+ * compare them by ApplySortComparator(). If they are equal, get "full"
+ * version and compare again by ApplySortAbbrevFullComparator().
+ * For other datums: get specified datums and compare them by
+ * ApplySortComparator() as regular routine does.
+ *
+ * See comparetup_heap() for details.
+ */
+static inline int
+mksort_compare_datum(SortTuple *tuple1,
+ SortTuple *tuple2,
+ int depth,
+ Tuplesortstate *state)
+{
+ Datum datum1, datum2;
+ bool isNull1, isNull2;
+ SortSupport sortKey;
+ int ret = 0;
+
+ Assert(state->mksortGetDatumFunc);
+
+ sortKey = state->base.sortKeys + depth;
+ state->base.mksortGetDatumFunc(tuple1, 0, depth, state,
+ &datum1, &isNull1, false);
+ state->base.mksortGetDatumFunc(tuple2, 0, depth, state,
+ &datum2, &isNull2, false);
+
+ ret = ApplySortComparator(datum1,
+ isNull1,
+ datum2,
+ isNull2,
+ sortKey);
+
+ /*
+ * If "abbreviated key" is enabled, and we are in the first depth, it means
+ * only "abbreviated keys" are compared. If the two datums are determined to
+ * be equal by ApplySortComparator(), we need to perform an extra "full"
+ * comparing by ApplySortAbbrevFullComparator().
+ */
+ if (sortKey->abbrev_converter &&
+ depth == 0 &&
+ ret == 0)
+ {
+ /* Fetch "full" datum by setting useFullKey = true */
+ state->base.mksortGetDatumFunc(tuple1, 0, depth, state,
+ &datum1, &isNull1, true);
+ state->base.mksortGetDatumFunc(tuple2, 0, depth, state,
+ &datum2, &isNull2, true);
+
+ ret = ApplySortAbbrevFullComparator(datum1,
+ isNull1,
+ datum2,
+ isNull2,
+ sortKey);
+ }
+
+ return ret;
+}
+
+#ifdef USE_ASSERT_CHECKING
+/*
+ * Verify whether the SortTuple list is ordered or not at specified depth
+ */
+static void
+mksort_verify(SortTuple *x,
+ int n,
+ int depth,
+ Tuplesortstate *state)
+{
+ int ret;
+
+ for (int i = 0;i < n - 1;i++)
+ {
+ ret = mksort_compare_datum(x + i,
+ x + i + 1,
+ depth,
+ state);
+ Assert(ret <= 0);
+ }
+}
+#endif
+
+/*
+ * Major of multi-key sort
+ *
+ * seenNull indicates whether we have seen NULL in any datum we checked
+ */
+static void
+mksort_tuple(SortTuple *x,
+ size_t n,
+ int depth,
+ Tuplesortstate *state,
+ bool seenNull)
+{
+ /*
+ * In the process, the tuple array consists of five parts:
+ * left equal, less, not-processed, greater, right equal
+ *
+ * lessStart indicates the first position of less part
+ * lessEnd indicates the next position after less part
+ * greaterStart indicates the prior position before greater part
+ * greaterEnd indicates the latest position of greater part
+ * the range between lessEnd and greaterStart (inclusive) is not-processed
+ */
+ int lessStart, lessEnd, greaterStart, greaterEnd, tupCount;
+ int32 dist;
+ SortTuple *pivot;
+ bool isDatumNull;
+
+ Assert(depth <= state->base.nKeys);
+ Assert(state->base.sortKeys);
+ Assert(state->base.mksortGetDatumFunc);
+
+ if (n <= 1)
+ return;
+
+ /* If we have exceeded the max depth, return immediately */
+ if (depth == state->base.nKeys)
+ return;
+
+ CHECK_FOR_INTERRUPTS();
+
+ /* Select pivot by random and move it to the first position */
+ lessStart = pg_prng_int64p(&pg_global_prng_state) % n;
+ mksort_swap(0, lessStart, x);
+ pivot = x;
+
+ lessStart = 1;
+ lessEnd = 1;
+ greaterStart = n - 1;
+ greaterEnd = n - 1;
+
+ /* Sort the array to three parts: lesser, equal, greater */
+ while (true)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ /* Compare the left end of the array */
+ while (lessEnd <= greaterStart)
+ {
+ /* Compare lessEnd and pivot at current depth */
+ dist = mksort_compare_datum(x + lessEnd,
+ pivot,
+ depth,
+ state);
+
+ if (dist > 0)
+ break;
+
+ /* If lessEnd is equal to pivot, move it to lessStart */
+ if (dist == 0)
+ {
+ mksort_swap(lessEnd, lessStart, x);
+ lessStart++;
+ }
+ lessEnd++;
+ }
+
+ /* Compare the right end of the array */
+ while (lessEnd <= greaterStart)
+ {
+ /* Compare greaterStart and pivot at current depth */
+ dist = mksort_compare_datum(x + greaterStart,
+ pivot,
+ depth,
+ state);
+
+ if (dist < 0)
+ break;
+
+ /* If greaterStart is equal to pivot, move it to greaterEnd */
+ if (dist == 0)
+ {
+ mksort_swap(greaterStart, greaterEnd, x);
+ greaterEnd--;
+ }
+ greaterStart--;
+ }
+
+ if (lessEnd > greaterStart)
+ break;
+ mksort_swap(lessEnd, greaterStart, x);
+ lessEnd++;
+ greaterStart--;
+ }
+
+ /*
+ * Now the array has four parts:
+ * left equal, lesser, greater, right equal
+ * Note greaterStart is less than lessEnd now
+ */
+
+ /* Move the left equal part to middle */
+ dist = Min(lessStart, lessEnd - lessStart);
+ mksort_vec_swap(0, lessEnd - dist, dist, x);
+
+ /* Move the right equal part to middle */
+ dist = Min(greaterEnd - greaterStart, n - greaterEnd - 1);
+ mksort_vec_swap(lessEnd, n - dist, dist, x);
+
+ /*
+ * Now the array has three parts:
+ * lesser, equal, greater
+ * Note that one or two parts may have no element at all.
+ */
+
+ /* Recursively sort the lesser part */
+
+ /* dist means the size of less part */
+ dist = lessEnd - lessStart;
+ mksort_tuple(x,
+ dist,
+ depth,
+ state,
+ seenNull);
+
+ /* Recursively sort the equal part */
+
+ /*
+ * (x + dist) means the first tuple in the equal part
+ * Since all tuples have equal datums at current depth, we just check any one
+ * of them to determine whether we have seen null datum.
+ */
+ isDatumNull = check_datum_null(x + dist, depth, state);
+
+ /* (lessStart + n - greaterEnd - 1) means the size of equal part */
+ tupCount = lessStart + n - greaterEnd - 1;
+
+ if (depth < state->base.nKeys - 1)
+ {
+ mksort_tuple(x + dist,
+ tupCount,
+ depth + 1,
+ state,
+ seenNull || isDatumNull);
+ } else {
+ /*
+ * We have reach the max depth: Call mksortHandleDupFunc to handle duplicated
+ * tuples if necessary, e.g. checking uniqueness or extra comparing
+ */
+
+ /*
+ * Call mksortHandleDupFunc if:
+ * 1. mksortHandleDupFunc is filled
+ * 2. the size of equal part > 1
+ */
+ if (state->base.mksortHandleDupFunc &&
+ (tupCount > 1))
+ {
+ state->base.mksortHandleDupFunc(x + dist,
+ tupCount,
+ seenNull || isDatumNull,
+ state);
+ }
+ }
+
+ /* Recursively sort the greater part */
+
+ /* dist means the size of greater part */
+ dist = greaterEnd - greaterStart;
+ mksort_tuple(x + n - dist,
+ dist,
+ depth,
+ state,
+ seenNull);
+
+#ifdef USE_ASSERT_CHECKING
+ mksort_verify(x,
+ n,
+ depth,
+ state);
+#endif
+}
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 7c4d6dc106..c865772a7a 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -108,6 +108,7 @@
#include "utils/memutils.h"
#include "utils/pg_rusage.h"
#include "utils/tuplesort.h"
+#include "common/pg_prng.h"
/*
* Initial size of memtuples array. We're trying to select this size so that
@@ -128,6 +129,7 @@ bool trace_sort = false;
bool optimize_bounded_sort = true;
#endif
+bool enable_mk_sort = true;
/*
* During merge, we use a pre-allocated set of fixed-size slots to hold
@@ -337,6 +339,9 @@ struct Tuplesortstate
#ifdef TRACE_SORT
PGRUsage ru_start;
#endif
+
+ /* Whether multi-key sort is used */
+ bool mksortUsed;
};
/*
@@ -622,6 +627,8 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
#define ST_DEFINE
#include "lib/sort_template.h"
+#include "mksort_tuple.c"
+
/*
* tuplesort_begin_xxx
*
@@ -690,6 +697,7 @@ tuplesort_begin_common(int workMem, SortCoordinate coordinate, int sortopt)
state->base.sortopt = sortopt;
state->base.tuples = true;
state->abbrevNext = 10;
+ state->mksortUsed = false;
/*
* workMem is forced to be at least 64KB, the current minimum valid value
@@ -2559,6 +2567,8 @@ tuplesort_get_stats(Tuplesortstate *state,
case TSS_SORTEDINMEM:
if (state->boundUsed)
stats->sortMethod = SORT_TYPE_TOP_N_HEAPSORT;
+ else if (state->mksortUsed)
+ stats->sortMethod = SORT_TYPE_MKSORT;
else
stats->sortMethod = SORT_TYPE_QUICKSORT;
break;
@@ -2592,6 +2602,8 @@ tuplesort_method_name(TuplesortMethod m)
return "external sort";
case SORT_TYPE_EXTERNAL_MERGE:
return "external merge";
+ case SORT_TYPE_MKSORT:
+ return "multi-key sort";
}
return "unknown";
@@ -2717,6 +2729,38 @@ tuplesort_sort_memtuples(Tuplesortstate *state)
if (state->memtupcount > 1)
{
+ /*
+ * Apply multi-key sort when:
+ * 1. enable_mk_sort is set
+ * 2. There are multiple keys available
+ * 3. mksortGetDatumFunc is filled, which implies that current tuple
+ * type is supported by mksort. (By now only Heap tuple and Btree
+ * Index tuple are supported, and more types may be supported in
+ * future.)
+ *
+ * A summary of tuple types supported by mksort:
+ *
+ * HeapTuple: supported
+ * IndexTuple(btree): supported
+ * IndexTuple(hash): not supported because there is only one key
+ * DatumTuple: not supported because there is only one key
+ * HeapTuple(for cluster): not supported yet
+ * IndexTuple(gist): not supported yet
+ * IndexTuple(brin): not supported yet
+ */
+ if (enable_mk_sort &&
+ state->base.nKeys > 1 &&
+ state->base.mksortGetDatumFunc != NULL)
+ {
+ state->mksortUsed = true;
+ mksort_tuple(state->memtuples,
+ state->memtupcount,
+ 0,
+ state,
+ false);
+ return;
+ }
+
/*
* Do we have the leading column's value or abbreviation in datum1,
* and is there a specialization for its comparator?
diff --git a/src/backend/utils/sort/tuplesortvariants.c b/src/backend/utils/sort/tuplesortvariants.c
index 05a853caa3..1ae7947cc5 100644
--- a/src/backend/utils/sort/tuplesortvariants.c
+++ b/src/backend/utils/sort/tuplesortvariants.c
@@ -30,6 +30,7 @@
#include "utils/guc.h"
#include "utils/lsyscache.h"
#include "utils/tuplesort.h"
+#include "miscadmin.h"
/* sort-type codes for sort__start probes */
@@ -92,6 +93,41 @@ static void readtup_datum(Tuplesortstate *state, SortTuple *stup,
LogicalTape *tape, unsigned int len);
static void freestate_cluster(Tuplesortstate *state);
+static Datum mksort_get_datum_heap(SortTuple *x,
+ const int tupleIndex,
+ const int depth,
+ Tuplesortstate *state,
+ Datum *datum,
+ bool *isNull,
+ bool useFullKey);
+
+static Datum mksort_get_datum_index_btree(SortTuple *x,
+ const int tupleIndex,
+ const int depth,
+ Tuplesortstate *state,
+ Datum *datum,
+ bool *isNull,
+ bool useFullKey);
+
+static void
+mksort_handle_dup_index_btree(SortTuple *x,
+ const int tupleCount,
+ const bool seenNull,
+ Tuplesortstate *state);
+
+static int
+mksort_compare_equal_index_btree(const SortTuple *a,
+ const SortTuple *b,
+ Tuplesortstate *state);
+
+static inline int
+tuplesort_compare_by_item_pointer(const IndexTuple tuple1,
+ const IndexTuple tuple2);
+
+static void
+raise_error_of_dup_index(IndexTuple x,
+ Tuplesortstate *state);
+
/*
* Data structure pointed by "TuplesortPublic.arg" for the CLUSTER case. Set by
* the tuplesort_begin_cluster.
@@ -163,6 +199,14 @@ typedef struct BrinSortTuple
/* Size of the BrinSortTuple, given length of the BrinTuple. */
#define BRINSORTTUPLE_SIZE(len) (offsetof(BrinSortTuple, tuple) + (len))
+#define ST_SORT qsort_tuple_by_itempointer
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE(a, b, state) mksort_compare_equal_index_btree(a, b, state)
+#define ST_COMPARE_ARG_TYPE Tuplesortstate
+#define ST_CHECK_FOR_INTERRUPTS
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
Tuplesortstate *
tuplesort_begin_heap(TupleDesc tupDesc,
@@ -200,6 +244,7 @@ tuplesort_begin_heap(TupleDesc tupDesc,
base->removeabbrev = removeabbrev_heap;
base->comparetup = comparetup_heap;
base->comparetup_tiebreak = comparetup_heap_tiebreak;
+ base->mksortGetDatumFunc = mksort_get_datum_heap;
base->writetup = writetup_heap;
base->readtup = readtup_heap;
base->haveDatum1 = true;
@@ -388,6 +433,8 @@ tuplesort_begin_index_btree(Relation heapRel,
base->removeabbrev = removeabbrev_index;
base->comparetup = comparetup_index_btree;
base->comparetup_tiebreak = comparetup_index_btree_tiebreak;
+ base->mksortGetDatumFunc = mksort_get_datum_index_btree;
+ base->mksortHandleDupFunc = mksort_handle_dup_index_btree;
base->writetup = writetup_index;
base->readtup = readtup_index;
base->haveDatum1 = true;
@@ -1563,25 +1610,7 @@ comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b,
* attribute in order to ensure that all keys in the index are physically
* unique.
*/
- {
- BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
- BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
-
- if (blk1 != blk2)
- return (blk1 < blk2) ? -1 : 1;
- }
- {
- OffsetNumber pos1 = ItemPointerGetOffsetNumber(&tuple1->t_tid);
- OffsetNumber pos2 = ItemPointerGetOffsetNumber(&tuple2->t_tid);
-
- if (pos1 != pos2)
- return (pos1 < pos2) ? -1 : 1;
- }
-
- /* ItemPointer values should never be equal */
- Assert(false);
-
- return 0;
+ return tuplesort_compare_by_item_pointer(tuple1, tuple2);
}
static int
@@ -1888,3 +1917,236 @@ readtup_datum(Tuplesortstate *state, SortTuple *stup,
if (base->sortopt & TUPLESORT_RANDOMACCESS) /* need trailing length word? */
LogicalTapeReadExact(tape, &tuplen, sizeof(tuplen));
}
+
+/*
+ * Get specified datum from SortTuple (HeapTuple) list
+ *
+ * If the first datum is requested (depth == 0), sortTuple->datum1/isnull1
+ * will be returned. For other datums, relevant datum will be extracted from
+ * sortTuple->tuple.
+ *
+ * The parameter "useFullKey" is used for scenario of "abbreviated key":
+ * false - get sortTuple->datum1/isnull1 (abbreviated key)
+ * true - get the "full" datum
+ * If "abbreviated key" is disabled, useFullKey will be ignored.
+ *
+ * See comparetup_heap() for details.
+ */
+static Datum
+mksort_get_datum_heap(SortTuple *x,
+ int tupleIndex,
+ int depth,
+ Tuplesortstate *state,
+ Datum *datum,
+ bool *isNull,
+ bool useFullKey)
+{
+ TupleDesc tupDesc = NULL;
+ HeapTupleData heapTuple;
+ AttrNumber attno;
+ SortTuple *sortTuple = x + tupleIndex;
+ TuplesortPublic *base = TuplesortstateGetPublic(state);
+ SortSupport sortKey = base->sortKeys + depth;;
+
+ Assert(state);
+ Assert(depth < state->nKeys);
+
+ /*
+ * useFullKey is valid only when depth == 0, because only the first datum
+ * may be involved to "abbreviated key", so only the first datum need to
+ * be checked with "full" version.
+ */
+ AssertImply(useFullKey, depth == 0);
+
+ tupDesc = (TupleDesc)base->arg;
+
+ /*
+ * When useFullKey is false, and the first datum is requested, return the
+ * leading datum
+ */
+ if (depth == 0 && !useFullKey)
+ {
+ *datum = sortTuple->datum1;
+ *isNull = sortTuple->isnull1;
+ return *datum;
+ }
+
+ /* For any datums which depth > 0, extract it from sortTuple->tuple */
+ heapTuple.t_len = ((MinimalTuple) sortTuple->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
+ heapTuple.t_data = (HeapTupleHeader) ((char *) sortTuple->tuple - MINIMAL_TUPLE_OFFSET);
+ attno = sortKey->ssup_attno;
+ *datum = heap_getattr(&heapTuple, attno, tupDesc, isNull);
+
+ return *datum;
+}
+
+/*
+ * Get specified datum from SortTuple (IndexTuple for btree index) list
+ *
+ * If the first datum is requested (depth == 0), sortTuple->datum1/isnull1
+ * will be returned. For other datums, relevant datum will be extracted from
+ * sortTuple->tuple.
+ *
+ * The parameter "useFullKey" is used for scenario of "abbreviated key":
+ * false - get sortTuple->datum1/isnull1 (abbreviated key)
+ * true - get the "full" datum
+ * If "abbreviated key" is disabled, useFullKey will be ignored.
+ *
+ * See comparetup_index_btree() for details.
+ */
+static Datum
+mksort_get_datum_index_btree(SortTuple *x,
+ const int tupleIndex,
+ const int depth,
+ Tuplesortstate *state,
+ Datum *datum,
+ bool *isNull,
+ bool useFullKey)
+{
+ TupleDesc tupDesc;
+ IndexTuple indexTuple;
+ SortTuple *sortTuple = x + tupleIndex;
+ TuplesortPublic *base = TuplesortstateGetPublic(state);
+ TuplesortIndexBTreeArg *arg = (TuplesortIndexBTreeArg *) base->arg;
+
+ Assert(state);
+ Assert(depth < state->nKeys);
+
+ /*
+ * useFullKey is valid only when depth == 0, because only the first datum
+ * may be involved to "abbreviated key", so only the first datum need to
+ * be checked with "full" version.
+ */
+ AssertImply(useFullKey, depth == 0);
+
+ /*
+ * When useFullKey is false, and the first datum is requested, return the
+ * leading datum
+ */
+ if (depth == 0 && !useFullKey)
+ {
+ *isNull = sortTuple->isnull1;
+ *datum = sortTuple->datum1;
+ return *datum;
+ }
+
+ indexTuple = (IndexTuple) sortTuple->tuple;
+ tupDesc = RelationGetDescr(arg->index.indexRel);
+
+ /*
+ * Set parameter attnum = depth + 1 because attnum starts from 1 but depth
+ * starts from 0
+ */
+ *datum = index_getattr(indexTuple, depth + 1, tupDesc, isNull);
+
+ return *datum;
+}
+
+/*
+ * Handle duplicated SortTuples (IndexTuple for btree index during mksort)
+ * x: the duplicated tuple list
+ * tupleCount: count of the tuples
+ */
+static void
+mksort_handle_dup_index_btree(SortTuple *x,
+ const int tupleCount,
+ const bool seenNull,
+ Tuplesortstate *state)
+{
+ TuplesortPublic *base = TuplesortstateGetPublic(state);
+ TuplesortIndexBTreeArg *arg = (TuplesortIndexBTreeArg *) base->arg;
+
+ /* If enforceUnique is enabled and we never saw NULL, raise error */
+ if (arg->enforceUnique && !(!arg->uniqueNullsNotDistinct && seenNull))
+ {
+ Assert(state->comparetup == comparetup_index_btree);
+
+ /*
+ * x means the first tuple of duplicated tuple list
+ * Since they are duplicated, simply pick up the first one
+ * to raise error
+ */
+ raise_error_of_dup_index((IndexTuple)(x->tuple), state);
+ }
+
+ /*
+ * If key values are equal, we sort on ItemPointer. This is required for
+ * btree indexes, since heap TID is treated as an implicit last key
+ * attribute in order to ensure that all keys in the index are physically
+ * unique.
+ */
+ qsort_tuple_by_itempointer(x,
+ tupleCount,
+ state);
+}
+
+/*
+ * Compare two btree index tuples by ItemPointer
+ * It is a callback function for qsort_tuple() called by
+ * mksort_handle_dup_index_btree()
+ */
+static int
+mksort_compare_equal_index_btree(const SortTuple *a,
+ const SortTuple *b,
+ Tuplesortstate *state)
+{
+ IndexTuple tuple1;
+ IndexTuple tuple2;
+
+ tuple1 = (IndexTuple) a->tuple;
+ tuple2 = (IndexTuple) b->tuple;
+
+ return tuplesort_compare_by_item_pointer(tuple1, tuple2);
+}
+
+/* Compare two index tuples by ItemPointer */
+static inline int
+tuplesort_compare_by_item_pointer(const IndexTuple tuple1,
+ const IndexTuple tuple2)
+{
+ {
+ BlockNumber blk1 = ItemPointerGetBlockNumber(&tuple1->t_tid);
+ BlockNumber blk2 = ItemPointerGetBlockNumber(&tuple2->t_tid);
+
+ if (blk1 != blk2)
+ return (blk1 < blk2) ? -1 : 1;
+ }
+ {
+ OffsetNumber pos1 = ItemPointerGetOffsetNumber(&tuple1->t_tid);
+ OffsetNumber pos2 = ItemPointerGetOffsetNumber(&tuple2->t_tid);
+
+ if (pos1 != pos2)
+ return (pos1 < pos2) ? -1 : 1;
+ }
+
+ /* ItemPointer values should never be equal */
+ Assert(false);
+
+ return 0;
+}
+
+/* Raise error for duplicated tuple when creating unique index */
+static void
+raise_error_of_dup_index(IndexTuple x,
+ Tuplesortstate *state)
+{
+ Datum values[INDEX_MAX_KEYS];
+ bool isnull[INDEX_MAX_KEYS];
+ TupleDesc tupDesc;
+ char *key_desc;
+ TuplesortPublic *base = TuplesortstateGetPublic(state);
+ TuplesortIndexBTreeArg *arg = (TuplesortIndexBTreeArg *) base->arg;
+
+ tupDesc = RelationGetDescr(arg->index.indexRel);
+ index_deform_tuple((IndexTuple)x, tupDesc, values, isnull);
+ key_desc = BuildIndexValueDescription(arg->index.indexRel, values, isnull);
+
+ ereport(ERROR,
+ (errcode(ERRCODE_UNIQUE_VIOLATION),
+ errmsg("could not create unique index \"%s\"",
+ RelationGetRelationName(arg->index.indexRel)),
+ key_desc ? errdetail("Key %s is duplicated.", key_desc) :
+ errdetail("Duplicate keys exist."),
+ errtableconstraint(arg->index.heapRel,
+ RelationGetRelationName(arg->index.indexRel))));
+}
diff --git a/src/include/c.h b/src/include/c.h
index dc1841346c..f7c368cd16 100644
--- a/src/include/c.h
+++ b/src/include/c.h
@@ -857,12 +857,14 @@ typedef NameData *Name;
#define Assert(condition) ((void)true)
#define AssertMacro(condition) ((void)true)
+#define AssertImply(condition1, condition2) ((void)true)
#elif defined(FRONTEND)
#include <assert.h>
#define Assert(p) assert(p)
#define AssertMacro(p) ((void) assert(p))
+#define AssertImply(cond1, cond2) Assert(!(cond1) || (cond2))
#else /* USE_ASSERT_CHECKING && !FRONTEND */
@@ -886,6 +888,8 @@ typedef NameData *Name;
((void) ((condition) || \
(ExceptionalCondition(#condition, __FILE__, __LINE__), 0)))
+#define AssertImply(cond1, cond2) Assert(!(cond1) || (cond2))
+
#endif /* USE_ASSERT_CHECKING && !FRONTEND */
/*
diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h
index e7941a1f09..d3f27b49dc 100644
--- a/src/include/utils/tuplesort.h
+++ b/src/include/utils/tuplesort.h
@@ -29,7 +29,6 @@
#include "utils/relcache.h"
#include "utils/sortsupport.h"
-
/*
* Tuplesortstate and Sharedsort are opaque types whose details are not
* known outside tuplesort.c.
@@ -79,9 +78,10 @@ typedef enum
SORT_TYPE_QUICKSORT = 1 << 1,
SORT_TYPE_EXTERNAL_SORT = 1 << 2,
SORT_TYPE_EXTERNAL_MERGE = 1 << 3,
+ SORT_TYPE_MKSORT = 1 << 4,
} TuplesortMethod;
-#define NUM_TUPLESORTMETHODS 4
+#define NUM_TUPLESORTMETHODS 5
typedef enum
{
@@ -155,6 +155,21 @@ typedef struct
typedef int (*SortTupleComparator) (const SortTuple *a, const SortTuple *b,
Tuplesortstate *state);
+typedef Datum
+(*MksortGetDatumFunc) (SortTuple *x,
+ const int tupleIndex,
+ const int depth,
+ Tuplesortstate *state,
+ Datum *datum,
+ bool *isNull,
+ bool useFullKey);
+
+typedef void
+(*MksortHandleDupFunc) (SortTuple *x,
+ const int tupleCount,
+ const bool seenNull,
+ Tuplesortstate *state);
+
/*
* The public part of a Tuple sort operation state. This data structure
* contains the definition of sort-variant-specific interface methods and
@@ -249,6 +264,21 @@ typedef struct
bool tuples; /* Can SortTuple.tuple ever be set? */
void *arg; /* Specific information for the sort variant */
+
+ /*
+ * Function pointer, referencing a function to get specified datum from
+ * SortTuple list with multi-key.
+ * Used by mksort_tuple().
+ */
+ MksortGetDatumFunc mksortGetDatumFunc;
+
+ /*
+ * Function pointer, referencing a function to handle duplicated tuple
+ * from SortTuple list with multi-key.
+ * Used by mksort_tuple().
+ * For now, the function pointer is filled for only btree index tuple.
+ */
+ MksortHandleDupFunc mksortHandleDupFunc;
} TuplesortPublic;
/* Sort parallel code from state for sort__start probes */
diff --git a/src/test/regress/expected/geometry.out b/src/test/regress/expected/geometry.out
index 8be694f46b..094d22861c 100644
--- a/src/test/regress/expected/geometry.out
+++ b/src/test/regress/expected/geometry.out
@@ -4273,7 +4273,7 @@ SELECT circle(f1)
SELECT c1.f1 AS circle, p1.f1 AS point, (p1.f1 <-> c1.f1) AS distance
FROM CIRCLE_TBL c1, POINT_TBL p1
WHERE (p1.f1 <-> c1.f1) > 0
- ORDER BY distance, area(c1.f1), p1.f1[0];
+ ORDER BY distance, area(c1.f1), p1.f1[0], c1.f1::text;
circle | point | distance
----------------+-------------------+---------------
<(1,2),3> | (-3,4) | 1.472135955
@@ -4310,8 +4310,8 @@ SELECT c1.f1 AS circle, p1.f1 AS point, (p1.f1 <-> c1.f1) AS distance
<(3,5),0> | (Infinity,1e+300) | Infinity
<(1,2),3> | (1e+300,Infinity) | Infinity
<(5,1),3> | (1e+300,Infinity) | Infinity
- <(5,1),3> | (Infinity,1e+300) | Infinity
<(1,2),3> | (Infinity,1e+300) | Infinity
+ <(5,1),3> | (Infinity,1e+300) | Infinity
<(1,3),5> | (1e+300,Infinity) | Infinity
<(1,3),5> | (Infinity,1e+300) | Infinity
<(100,200),10> | (1e+300,Infinity) | Infinity
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 5fd54a10b1..e8dba83389 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -520,13 +520,13 @@ select * from (select * from t order by a) s order by a, b limit 55;
-- Test EXPLAIN ANALYZE with only a fullsort group.
select explain_analyze_without_memory('select * from (select * from t order by a) s order by a, b limit 55');
- explain_analyze_without_memory
----------------------------------------------------------------------------------------------------------------
+ explain_analyze_without_memory
+--------------------------------------------------------------------------------------------------------------------
Limit (actual rows=55 loops=1)
-> Incremental Sort (actual rows=55 loops=1)
Sort Key: t.a, t.b
Presorted Key: t.a
- Full-sort Groups: 2 Sort Methods: top-N heapsort, quicksort Average Memory: NNkB Peak Memory: NNkB
+ Full-sort Groups: 2 Sort Methods: top-N heapsort, multi-key sort Average Memory: NNkB Peak Memory: NNkB
-> Sort (actual rows=101 loops=1)
Sort Key: t.a
Sort Method: quicksort Memory: NNkB
@@ -554,7 +554,7 @@ select jsonb_pretty(explain_analyze_inc_sort_nodes_without_memory('select * from
"Group Count": 2, +
"Sort Methods Used": [ +
"top-N heapsort", +
- "quicksort" +
+ "multi-key sort" +
], +
"Sort Space Memory": { +
"Peak Sort Space Used": "NN", +
@@ -728,7 +728,7 @@ select explain_analyze_without_memory('select * from (select * from t order by a
-> Incremental Sort (actual rows=70 loops=1)
Sort Key: t.a, t.b
Presorted Key: t.a
- Full-sort Groups: 1 Sort Method: quicksort Average Memory: NNkB Peak Memory: NNkB
+ Full-sort Groups: 1 Sort Method: multi-key sort Average Memory: NNkB Peak Memory: NNkB
Pre-sorted Groups: 5 Sort Methods: top-N heapsort, quicksort Average Memory: NNkB Peak Memory: NNkB
-> Sort (actual rows=1000 loops=1)
Sort Key: t.a
@@ -756,7 +756,7 @@ select jsonb_pretty(explain_analyze_inc_sort_nodes_without_memory('select * from
"Full-sort Groups": { +
"Group Count": 1, +
"Sort Methods Used": [ +
- "quicksort" +
+ "multi-key sort" +
], +
"Sort Space Memory": { +
"Peak Sort Space Used": "NN", +
diff --git a/src/test/regress/expected/tuplesort.out b/src/test/regress/expected/tuplesort.out
index 6dd97e7427..cd08ce8b3c 100644
--- a/src/test/regress/expected/tuplesort.out
+++ b/src/test/regress/expected/tuplesort.out
@@ -703,3 +703,378 @@ EXPLAIN (COSTS OFF) :qry;
(10 rows)
COMMIT;
+-- Test cases for multi-key sort
+set work_mem='100MB';
+-- test simple sorting
+create table mksort_simple_tbl(a int, b int, c varchar);
+insert into mksort_simple_tbl
+ select g % 10, g % 15, left(md5(g::text), 4)
+ from generate_series(1, 50) g;
+select * from mksort_simple_tbl order by a, b, c;
+ a | b | c
+---+----+------
+ 0 | 0 | 3417
+ 0 | 5 | 98f1
+ 0 | 5 | c0c7
+ 0 | 10 | d3d9
+ 0 | 10 | d645
+ 1 | 1 | c16a
+ 1 | 1 | c4ca
+ 1 | 6 | 3c59
+ 1 | 11 | 3416
+ 1 | 11 | 6512
+ 2 | 2 | 6364
+ 2 | 2 | c81e
+ 2 | 7 | b6d7
+ 2 | 12 | a1d0
+ 2 | 12 | c20a
+ 3 | 3 | 182b
+ 3 | 3 | eccb
+ 3 | 8 | 3769
+ 3 | 13 | 17e6
+ 3 | 13 | c51c
+ 4 | 4 | a87f
+ 4 | 4 | e369
+ 4 | 9 | 1ff1
+ 4 | 14 | aab3
+ 4 | 14 | f717
+ 5 | 0 | 6c83
+ 5 | 0 | 9bf3
+ 5 | 5 | 1c38
+ 5 | 5 | e4da
+ 5 | 10 | 8e29
+ 6 | 1 | c74d
+ 6 | 1 | d9d4
+ 6 | 6 | 1679
+ 6 | 6 | 19ca
+ 6 | 11 | 4e73
+ 7 | 2 | 67c6
+ 7 | 2 | 70ef
+ 7 | 7 | 8f14
+ 7 | 7 | a5bf
+ 7 | 12 | 02e7
+ 8 | 3 | 642e
+ 8 | 3 | 6f49
+ 8 | 8 | a577
+ 8 | 8 | c9f0
+ 8 | 13 | 33e7
+ 9 | 4 | 1f0e
+ 9 | 4 | f457
+ 9 | 9 | 45c4
+ 9 | 9 | d67d
+ 9 | 14 | 6ea9
+(50 rows)
+
+drop table mksort_simple_tbl;
+-- test table with abbr keys
+create table abbr_tbl (a int, b varchar(100), c uuid);
+-- insert data with abbr keys (uuid)
+-- abbr keys of uuid are generated from the first `sizeof(Datum)` bytes of uuid data
+--(see uuid_abbrev_convert()), so two uuids with only different tailed values should
+-- have same abbr keys but different "full" datum.
+insert into abbr_tbl values (generate_series(1,50), 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb');
+update abbr_tbl set b = 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb' || (a % 7)::text;
+update abbr_tbl set c = ('fffffffffffffffffffffffffffffff' || (a % 5)::text)::uuid where a % 4 = 0;
+update abbr_tbl set c = ('0000000000000000000000000000000' || (a % 5)::text)::uuid where a % 4 = 1;
+update abbr_tbl set c = ('1111111111111111111111111111111' || (a % 5)::text)::uuid where a % 4 = 2;
+update abbr_tbl set c = null where a % 4 = 3;
+select c, b, a from abbr_tbl order by c, b, a;
+ c | b | a
+--------------------------------------+---------------------------------------------------------+----
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 45
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 25
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 5
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 21
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 1
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 41
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 37
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 17
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 33
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 13
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 49
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 29
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 9
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 50
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 30
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 10
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 46
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 26
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 6
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 42
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 22
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 2
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 38
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 18
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 14
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 34
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 40
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 20
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 36
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 16
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 32
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 12
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 28
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 8
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 48
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 44
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 24
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 4
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 7
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 35
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 15
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 43
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 23
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 3
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 31
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 11
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 39
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 19
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 47
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 27
+(50 rows)
+
+select c, b, a from abbr_tbl order by c desc, b, a;
+ c | b | a
+--------------------------------------+---------------------------------------------------------+----
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 7
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 35
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 15
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 43
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 23
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 3
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 31
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 11
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 39
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 19
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 47
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 27
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 44
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 24
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 4
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 28
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 8
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 48
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 32
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 12
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 36
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 16
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 40
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 20
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 14
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 34
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 38
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 18
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 42
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 22
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 2
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 46
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 26
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 6
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 50
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 30
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 10
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 49
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 29
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 9
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 33
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 13
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 37
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 17
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 21
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 1
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 41
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 45
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 25
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 5
+(50 rows)
+
+select c, b, a from abbr_tbl order by c, b desc, a;
+ c | b | a
+--------------------------------------+---------------------------------------------------------+----
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 5
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 25
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 45
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 41
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 1
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 21
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 17
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 37
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 13
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 33
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 9
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 29
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 49
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 10
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 30
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 50
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 6
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 26
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 46
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 2
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 22
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 42
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 18
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 38
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 34
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 14
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 20
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 40
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 16
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 36
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 12
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 32
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 48
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 8
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 28
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 4
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 24
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 44
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 27
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 19
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 47
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 11
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 39
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 3
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 31
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 23
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 15
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 43
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 7
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 35
+(50 rows)
+
+select c, b, a from abbr_tbl order by c nulls first, b desc, a;
+ c | b | a
+--------------------------------------+---------------------------------------------------------+----
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 27
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 19
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 47
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 11
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 39
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 3
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 31
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 23
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 15
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 43
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 7
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 35
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 5
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 25
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 45
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 41
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 1
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 21
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 17
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 37
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 13
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 33
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 9
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 29
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 49
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 10
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 30
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 50
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 6
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 26
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 46
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 2
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 22
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 42
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 18
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 38
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 34
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 14
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 20
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 40
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 16
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 36
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 12
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 32
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 48
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 8
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 28
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 4
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 24
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 44
+(50 rows)
+
+select c, b, a from abbr_tbl order by c nulls last, b desc, a;
+ c | b | a
+--------------------------------------+---------------------------------------------------------+----
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 5
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 25
+ 00000000-0000-0000-0000-000000000000 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 45
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 41
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 1
+ 00000000-0000-0000-0000-000000000001 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 21
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 17
+ 00000000-0000-0000-0000-000000000002 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 37
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 13
+ 00000000-0000-0000-0000-000000000003 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 33
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 9
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 29
+ 00000000-0000-0000-0000-000000000004 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 49
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 10
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 30
+ 11111111-1111-1111-1111-111111111110 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 50
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 6
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 26
+ 11111111-1111-1111-1111-111111111111 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 46
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 2
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 22
+ 11111111-1111-1111-1111-111111111112 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 42
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 18
+ 11111111-1111-1111-1111-111111111113 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 38
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 34
+ 11111111-1111-1111-1111-111111111114 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 14
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 20
+ ffffffff-ffff-ffff-ffff-fffffffffff0 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 40
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 16
+ ffffffff-ffff-ffff-ffff-fffffffffff1 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 36
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 12
+ ffffffff-ffff-ffff-ffff-fffffffffff2 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 32
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 48
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 8
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 28
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 4
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 24
+ ffffffff-ffff-ffff-ffff-fffffffffff4 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 44
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb6 | 27
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 19
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb5 | 47
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 11
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb4 | 39
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 3
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3 | 31
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb2 | 23
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 15
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 43
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 7
+ | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb0 | 35
+(50 rows)
+
+-- CREATE INDEX will cover the scenario of sort IndexTuple
+drop index if exists idx_abbr_tbl;
+NOTICE: index "idx_abbr_tbl" does not exist, skipping
+create index idx_abbr_tbl on abbr_tbl(c desc, b, a);
+analyze abbr_tbl;
+select c, b, a from abbr_tbl where c = 'ffffffff-ffff-ffff-ffff-fffffffffff3' and b = 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1' and a = 8;
+ c | b | a
+--------------------------------------+---------------------------------------------------------+---
+ ffffffff-ffff-ffff-ffff-fffffffffff3 | aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1 | 8
+(1 row)
+
+-- Uniqueness check of CREATE INDEX
+drop index if exists idx_abbr_tbl;
+-- insert a duplicated row with null
+insert into abbr_tbl (a, b, c) values (3, 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3', null);
+-- should succeed because uniquess check is not applicable for rows with null
+create unique index idx_abbr_tbl on abbr_tbl(c desc, b, a);
+drop index if exists idx_abbr_tbl;
+-- insert a duplicated row without null
+insert into abbr_tbl (a, b, c) values (1, 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1', '00000000-0000-0000-0000-000000000001');
+-- should fail because of duplicated rows
+create unique index idx_abbr_tbl on abbr_tbl(c desc, b, a);
+ERROR: could not create unique index "idx_abbr_tbl"
+DETAIL: Key (c, b, a)=(00000000-0000-0000-0000-000000000001, aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1, 1) is duplicated.
+drop table abbr_tbl;
diff --git a/src/test/regress/expected/window.out b/src/test/regress/expected/window.out
index ae4e8851f8..2de20ca1d0 100644
--- a/src/test/regress/expected/window.out
+++ b/src/test/regress/expected/window.out
@@ -18,13 +18,13 @@ INSERT INTO empsalary VALUES
('sales', 3, 4800, '2007-08-01'),
('develop', 8, 6000, '2006-10-01'),
('develop', 11, 5200, '2007-08-15');
-SELECT depname, empno, salary, sum(salary) OVER (PARTITION BY depname) FROM empsalary ORDER BY depname, salary;
+SELECT depname, empno, salary, sum(salary) OVER (PARTITION BY depname) FROM empsalary ORDER BY depname, salary, empno;
depname | empno | salary | sum
-----------+-------+--------+-------
develop | 7 | 4200 | 25100
develop | 9 | 4500 | 25100
- develop | 11 | 5200 | 25100
develop | 10 | 5200 | 25100
+ develop | 11 | 5200 | 25100
develop | 8 | 6000 | 25100
personnel | 5 | 3500 | 7400
personnel | 2 | 3900 | 7400
@@ -33,13 +33,13 @@ SELECT depname, empno, salary, sum(salary) OVER (PARTITION BY depname) FROM emps
sales | 1 | 5000 | 14600
(10 rows)
-SELECT depname, empno, salary, rank() OVER (PARTITION BY depname ORDER BY salary) FROM empsalary;
+SELECT depname, empno, salary, rank() OVER (PARTITION BY depname ORDER BY salary) FROM empsalary ORDER BY depname, salary, empno;
depname | empno | salary | rank
-----------+-------+--------+------
develop | 7 | 4200 | 1
develop | 9 | 4500 | 2
- develop | 11 | 5200 | 3
develop | 10 | 5200 | 3
+ develop | 11 | 5200 | 3
develop | 8 | 6000 | 5
personnel | 5 | 3500 | 1
personnel | 2 | 3900 | 2
@@ -90,18 +90,18 @@ SELECT depname, empno, salary, sum(salary) OVER w FROM empsalary WINDOW w AS (PA
sales | 4 | 4800 | 14600
(10 rows)
-SELECT depname, empno, salary, rank() OVER w FROM empsalary WINDOW w AS (PARTITION BY depname ORDER BY salary) ORDER BY rank() OVER w;
+SELECT depname, empno, salary, rank() OVER w FROM empsalary WINDOW w AS (PARTITION BY depname ORDER BY salary) ORDER BY rank() OVER w, empno;
depname | empno | salary | rank
-----------+-------+--------+------
- develop | 7 | 4200 | 1
- personnel | 5 | 3500 | 1
sales | 3 | 4800 | 1
sales | 4 | 4800 | 1
+ personnel | 5 | 3500 | 1
+ develop | 7 | 4200 | 1
personnel | 2 | 3900 | 2
develop | 9 | 4500 | 2
sales | 1 | 5000 | 3
- develop | 11 | 5200 | 3
develop | 10 | 5200 | 3
+ develop | 11 | 5200 | 3
develop | 8 | 6000 | 5
(10 rows)
@@ -3749,23 +3749,24 @@ SELECT
empno,
depname,
row_number() OVER (PARTITION BY depname ORDER BY enroll_date) rn,
- rank() OVER (PARTITION BY depname ORDER BY enroll_date ROWS BETWEEN
+ rank() OVER (PARTITION BY depname ORDER BY enroll_date, empno ROWS BETWEEN
UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) rnk,
- count(*) OVER (PARTITION BY depname ORDER BY enroll_date RANGE BETWEEN
+ count(*) OVER (PARTITION BY depname ORDER BY enroll_date, empno RANGE BETWEEN
CURRENT ROW AND CURRENT ROW) cnt
-FROM empsalary;
+FROM empsalary
+ORDER BY empno, depname, rn;
empno | depname | rn | rnk | cnt
-------+-----------+----+-----+-----
- 8 | develop | 1 | 1 | 1
- 10 | develop | 2 | 2 | 1
- 11 | develop | 3 | 3 | 1
- 9 | develop | 4 | 4 | 2
- 7 | develop | 5 | 4 | 2
- 2 | personnel | 1 | 1 | 1
- 5 | personnel | 2 | 2 | 1
1 | sales | 1 | 1 | 1
+ 2 | personnel | 1 | 1 | 1
3 | sales | 2 | 2 | 1
4 | sales | 3 | 3 | 1
+ 5 | personnel | 2 | 2 | 1
+ 7 | develop | 4 | 4 | 1
+ 8 | develop | 1 | 1 | 1
+ 9 | develop | 5 | 5 | 1
+ 10 | develop | 2 | 2 | 1
+ 11 | develop | 3 | 3 | 1
(10 rows)
-- Test pushdown of quals into a subquery containing window functions
@@ -4106,17 +4107,17 @@ SELECT * FROM
salary,
count(empno) OVER (PARTITION BY depname ORDER BY salary DESC) c
FROM empsalary) emp
-WHERE c <= 3;
+WHERE c <= 3 ORDER BY empno, depname, salary, c;
empno | depname | salary | c
-------+-----------+--------+---
+ 1 | sales | 5000 | 1
+ 2 | personnel | 3900 | 1
+ 3 | sales | 4800 | 3
+ 4 | sales | 4800 | 3
+ 5 | personnel | 3500 | 2
8 | develop | 6000 | 1
10 | develop | 5200 | 3
11 | develop | 5200 | 3
- 2 | personnel | 3900 | 1
- 5 | personnel | 3500 | 2
- 1 | sales | 5000 | 1
- 4 | sales | 4800 | 3
- 3 | sales | 4800 | 3
(8 rows)
-- Ensure we get the correct run condition when the window function is both
@@ -4468,14 +4469,15 @@ SELECT * FROM
empno,
salary,
enroll_date,
- row_number() OVER (PARTITION BY depname ORDER BY enroll_date) AS first_emp,
- row_number() OVER (PARTITION BY depname ORDER BY enroll_date DESC) AS last_emp
+ row_number() OVER (PARTITION BY depname ORDER BY enroll_date, empno) AS first_emp,
+ row_number() OVER (PARTITION BY depname ORDER BY enroll_date DESC, empno) AS last_emp
FROM empsalary) emp
-WHERE first_emp = 1 OR last_emp = 1;
+WHERE first_emp = 1 OR last_emp = 1
+ORDER BY depname, empno, salary, enroll_date, first_emp, last_emp;
depname | empno | salary | enroll_date | first_emp | last_emp
-----------+-------+--------+-------------+-----------+----------
+ develop | 7 | 4200 | 01-01-2008 | 4 | 1
develop | 8 | 6000 | 10-01-2006 | 1 | 5
- develop | 7 | 4200 | 01-01-2008 | 5 | 1
personnel | 2 | 3900 | 12-23-2006 | 1 | 2
personnel | 5 | 3500 | 12-10-2007 | 2 | 1
sales | 1 | 5000 | 10-01-2006 | 1 | 3
diff --git a/src/test/regress/sql/geometry.sql b/src/test/regress/sql/geometry.sql
index c3ea368da5..1f47f07f31 100644
--- a/src/test/regress/sql/geometry.sql
+++ b/src/test/regress/sql/geometry.sql
@@ -403,7 +403,7 @@ SELECT circle(f1)
SELECT c1.f1 AS circle, p1.f1 AS point, (p1.f1 <-> c1.f1) AS distance
FROM CIRCLE_TBL c1, POINT_TBL p1
WHERE (p1.f1 <-> c1.f1) > 0
- ORDER BY distance, area(c1.f1), p1.f1[0];
+ ORDER BY distance, area(c1.f1), p1.f1[0], c1.f1::text;
-- To polygon
SELECT f1, f1::polygon FROM CIRCLE_TBL WHERE f1 >= '<(0,0),1>';
diff --git a/src/test/regress/sql/tuplesort.sql b/src/test/regress/sql/tuplesort.sql
index 8476e594e6..65ecbbd5c9 100644
--- a/src/test/regress/sql/tuplesort.sql
+++ b/src/test/regress/sql/tuplesort.sql
@@ -305,3 +305,62 @@ EXPLAIN (COSTS OFF) :qry;
:qry;
COMMIT;
+
+-- Test cases for multi-key sort
+
+set work_mem='100MB';
+
+-- test simple sorting
+create table mksort_simple_tbl(a int, b int, c varchar);
+
+insert into mksort_simple_tbl
+ select g % 10, g % 15, left(md5(g::text), 4)
+ from generate_series(1, 50) g;
+select * from mksort_simple_tbl order by a, b, c;
+
+drop table mksort_simple_tbl;
+
+-- test table with abbr keys
+
+create table abbr_tbl (a int, b varchar(100), c uuid);
+
+-- insert data with abbr keys (uuid)
+-- abbr keys of uuid are generated from the first `sizeof(Datum)` bytes of uuid data
+--(see uuid_abbrev_convert()), so two uuids with only different tailed values should
+-- have same abbr keys but different "full" datum.
+insert into abbr_tbl values (generate_series(1,50), 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb');
+update abbr_tbl set b = 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb' || (a % 7)::text;
+update abbr_tbl set c = ('fffffffffffffffffffffffffffffff' || (a % 5)::text)::uuid where a % 4 = 0;
+update abbr_tbl set c = ('0000000000000000000000000000000' || (a % 5)::text)::uuid where a % 4 = 1;
+update abbr_tbl set c = ('1111111111111111111111111111111' || (a % 5)::text)::uuid where a % 4 = 2;
+update abbr_tbl set c = null where a % 4 = 3;
+
+select c, b, a from abbr_tbl order by c, b, a;
+select c, b, a from abbr_tbl order by c desc, b, a;
+select c, b, a from abbr_tbl order by c, b desc, a;
+select c, b, a from abbr_tbl order by c nulls first, b desc, a;
+select c, b, a from abbr_tbl order by c nulls last, b desc, a;
+
+-- CREATE INDEX will cover the scenario of sort IndexTuple
+drop index if exists idx_abbr_tbl;
+create index idx_abbr_tbl on abbr_tbl(c desc, b, a);
+analyze abbr_tbl;
+select c, b, a from abbr_tbl where c = 'ffffffff-ffff-ffff-ffff-fffffffffff3' and b = 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1' and a = 8;
+
+-- Uniqueness check of CREATE INDEX
+
+drop index if exists idx_abbr_tbl;
+
+-- insert a duplicated row with null
+insert into abbr_tbl (a, b, c) values (3, 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb3', null);
+-- should succeed because uniquess check is not applicable for rows with null
+create unique index idx_abbr_tbl on abbr_tbl(c desc, b, a);
+
+drop index if exists idx_abbr_tbl;
+
+-- insert a duplicated row without null
+insert into abbr_tbl (a, b, c) values (1, 'aaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb1', '00000000-0000-0000-0000-000000000001');
+-- should fail because of duplicated rows
+create unique index idx_abbr_tbl on abbr_tbl(c desc, b, a);
+
+drop table abbr_tbl;
\ No newline at end of file
diff --git a/src/test/regress/sql/window.sql b/src/test/regress/sql/window.sql
index 6de5493b05..46359cb796 100644
--- a/src/test/regress/sql/window.sql
+++ b/src/test/regress/sql/window.sql
@@ -21,9 +21,9 @@ INSERT INTO empsalary VALUES
('develop', 8, 6000, '2006-10-01'),
('develop', 11, 5200, '2007-08-15');
-SELECT depname, empno, salary, sum(salary) OVER (PARTITION BY depname) FROM empsalary ORDER BY depname, salary;
+SELECT depname, empno, salary, sum(salary) OVER (PARTITION BY depname) FROM empsalary ORDER BY depname, salary, empno;
-SELECT depname, empno, salary, rank() OVER (PARTITION BY depname ORDER BY salary) FROM empsalary;
+SELECT depname, empno, salary, rank() OVER (PARTITION BY depname ORDER BY salary) FROM empsalary ORDER BY depname, salary, empno;
-- with GROUP BY
SELECT four, ten, SUM(SUM(four)) OVER (PARTITION BY four), AVG(ten) FROM tenk1
@@ -31,7 +31,7 @@ GROUP BY four, ten ORDER BY four, ten;
SELECT depname, empno, salary, sum(salary) OVER w FROM empsalary WINDOW w AS (PARTITION BY depname);
-SELECT depname, empno, salary, rank() OVER w FROM empsalary WINDOW w AS (PARTITION BY depname ORDER BY salary) ORDER BY rank() OVER w;
+SELECT depname, empno, salary, rank() OVER w FROM empsalary WINDOW w AS (PARTITION BY depname ORDER BY salary) ORDER BY rank() OVER w, empno;
-- empty window specification
SELECT COUNT(*) OVER () FROM tenk1 WHERE unique2 < 10;
@@ -1146,11 +1146,12 @@ SELECT
empno,
depname,
row_number() OVER (PARTITION BY depname ORDER BY enroll_date) rn,
- rank() OVER (PARTITION BY depname ORDER BY enroll_date ROWS BETWEEN
+ rank() OVER (PARTITION BY depname ORDER BY enroll_date, empno ROWS BETWEEN
UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) rnk,
- count(*) OVER (PARTITION BY depname ORDER BY enroll_date RANGE BETWEEN
+ count(*) OVER (PARTITION BY depname ORDER BY enroll_date, empno RANGE BETWEEN
CURRENT ROW AND CURRENT ROW) cnt
-FROM empsalary;
+FROM empsalary
+ORDER BY empno, depname, rn;
-- Test pushdown of quals into a subquery containing window functions
@@ -1332,7 +1333,7 @@ SELECT * FROM
salary,
count(empno) OVER (PARTITION BY depname ORDER BY salary DESC) c
FROM empsalary) emp
-WHERE c <= 3;
+WHERE c <= 3 ORDER BY empno, depname, salary, c;
-- Ensure we get the correct run condition when the window function is both
-- monotonically increasing and decreasing.
@@ -1510,10 +1511,11 @@ SELECT * FROM
empno,
salary,
enroll_date,
- row_number() OVER (PARTITION BY depname ORDER BY enroll_date) AS first_emp,
- row_number() OVER (PARTITION BY depname ORDER BY enroll_date DESC) AS last_emp
+ row_number() OVER (PARTITION BY depname ORDER BY enroll_date, empno) AS first_emp,
+ row_number() OVER (PARTITION BY depname ORDER BY enroll_date DESC, empno) AS last_emp
FROM empsalary) emp
-WHERE first_emp = 1 OR last_emp = 1;
+WHERE first_emp = 1 OR last_emp = 1
+ORDER BY depname, empno, salary, enroll_date, first_emp, last_emp;
-- cleanup
DROP TABLE empsalary;
--
2.25.1
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: An implementation of multi-key sort
2024-05-22 12:48 An implementation of multi-key sort Wang Yao <[email protected]>
@ 2024-05-22 15:29 ` Heikki Linnakangas <[email protected]>
0 siblings, 0 replies; 3+ messages in thread
From: Heikki Linnakangas @ 2024-05-22 15:29 UTC (permalink / raw)
To: Wang Yao <[email protected]>; pgsql-hackers; +Cc: [email protected] <[email protected]>
On 22/05/2024 15:48, Wang Yao wrote:
> Comparing to classic quick sort, it can get significant performance
> improvement once multiple keys are available. A rough test shows it got
> ~129% improvement than qsort for ORDER BY on 6 keys, and ~52% for CREATE
> INDEX on the same data set. (See more details in section "Performance
> Test")
Impressive. Did you test the performance of the cases where MK-sort
doesn't help, to check if there is a performance regression?
--
Heikki Linnakangas
Neon (https://neon.tech)
^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2024-05-22 15:29 UTC | newest]
Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2020-06-06 22:42 [PATCH v13 01/18] Allow CREATE INDEX CONCURRENTLY on partitioned table Justin Pryzby <[email protected]>
2024-05-22 12:48 An implementation of multi-key sort Wang Yao <[email protected]>
2024-05-22 15:29 ` Re: An implementation of multi-key sort Heikki Linnakangas <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox