v20240609-0001-patch-2024-06-07.patch
text/x-patch
Filename: v20240609-0001-patch-2024-06-07.patch
Type: text/x-patch
Part: 0
Patch
Format: format-patch
Series: patch v20240609-0001
Subject: patch 2024/06/07
| File | + | − |
|---|---|---|
| src/backend/utils/misc/guc_tables.c | 11 | 0 |
| src/backend/utils/sort/mk_qsort_tuple.c | 388 | 0 |
| src/backend/utils/sort/tuplesort.c | 44 | 0 |
| src/backend/utils/sort/tuplesortvariants.c | 278 | 35 |
| src/include/c.h | 4 | 0 |
| src/include/utils/tuplesort.h | 34 | 2 |
| src/test/regress/expected/geometry.out | 2 | 2 |
| src/test/regress/expected/incremental_sort.out | 6 | 6 |
| src/test/regress/expected/sysviews.out | 2 | 1 |
| src/test/regress/expected/tuplesort.out | 376 | 0 |
| src/test/regress/expected/window.out | 30 | 28 |
| src/test/regress/sql/geometry.sql | 1 | 1 |
| src/test/regress/sql/tuplesort.sql | 66 | 0 |
| src/test/regress/sql/window.sql | 12 | 10 |
From 592500255df863baaf2afade60c6801411ab8eca Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tv@fuzzy.cz>
Date: Sun, 9 Jun 2024 13:26:15 +0200
Subject: [PATCH v20240609 1/4] patch 2024/06/07
---
src/backend/utils/misc/guc_tables.c | 11 +
src/backend/utils/sort/mk_qsort_tuple.c | 388 ++++++++++++++++++
src/backend/utils/sort/tuplesort.c | 44 ++
src/backend/utils/sort/tuplesortvariants.c | 313 ++++++++++++--
src/include/c.h | 4 +
src/include/utils/tuplesort.h | 36 +-
src/test/regress/expected/geometry.out | 4 +-
.../regress/expected/incremental_sort.out | 12 +-
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/expected/tuplesort.out | 376 +++++++++++++++++
src/test/regress/expected/window.out | 58 +--
src/test/regress/sql/geometry.sql | 2 +-
src/test/regress/sql/tuplesort.sql | 66 +++
src/test/regress/sql/window.sql | 22 +-
14 files changed, 1254 insertions(+), 85 deletions(-)
create mode 100644 src/backend/utils/sort/mk_qsort_tuple.c
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 46c258be282..a5f8b3798cc 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 sort"),
+ 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/mk_qsort_tuple.c b/src/backend/utils/sort/mk_qsort_tuple.c
new file mode 100644
index 00000000000..9c5715380aa
--- /dev/null
+++ b/src/backend/utils/sort/mk_qsort_tuple.c
@@ -0,0 +1,388 @@
+/*
+ * MK qsort (multi-key quick 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, mk_qsort_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
+mkqs_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
+mkqs_vec_swap(int a,
+ int b,
+ int size,
+ SortTuple *x)
+{
+ while (size-- > 0)
+ {
+ mkqs_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;
+
+ Assert(depth < state->base.nKeys);
+
+ /* Since we have a specified tuple, the tupleIndex is always 0 */
+ state->base.mkqsGetDatumFunc(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
+mkqs_compare_datum(SortTuple *tuple1,
+ SortTuple *tuple2,
+ int depth,
+ Tuplesortstate *state)
+{
+ Datum datum1, datum2;
+ bool isNull1, isNull2;
+ SortSupport sortKey;
+ int ret = 0;
+
+ Assert(state->base.mkqsGetDatumFunc);
+ Assert(depth < state->base.nKeys);
+
+ sortKey = state->base.sortKeys + depth;
+ state->base.mkqsGetDatumFunc(tuple1, 0, depth, state,
+ &datum1, &isNull1, false);
+ state->base.mkqsGetDatumFunc(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.mkqsGetDatumFunc(tuple1, 0, depth, state,
+ &datum1, &isNull1, true);
+ state->base.mkqsGetDatumFunc(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
+mkqs_verify(SortTuple *x,
+ int n,
+ int depth,
+ Tuplesortstate *state)
+{
+ int ret;
+
+ for (int i = 0;i < n - 1;i++)
+ {
+ ret = mkqs_compare_datum(x + i,
+ x + i + 1,
+ depth,
+ state);
+ Assert(ret <= 0);
+ }
+}
+#endif
+
+/*
+ * Major of multi-key quick sort
+ *
+ * seenNull indicates whether we have seen NULL in any datum we checked
+ */
+static void
+mk_qsort_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;
+ bool strictOrdered = true;
+
+ Assert(depth <= state->base.nKeys);
+ Assert(state->base.sortKeys);
+ Assert(state->base.mkqsGetDatumFunc);
+
+ if (n <= 1)
+ return;
+
+ /* If we have exceeded the max depth, return immediately */
+ if (depth == state->base.nKeys)
+ return;
+
+ CHECK_FOR_INTERRUPTS();
+
+ /*
+ * Check if the array is ordered already. If yes, return immediately.
+ * Different from qsort_tuple(), the array must be strict ordered (no
+ * equal datums). If there are equal datums, we must continue the mk
+ * qsort process to check datums on lower depth.
+ */
+ for (int i = 0;i < n - 1;i++)
+ {
+ int ret;
+
+ CHECK_FOR_INTERRUPTS();
+ ret = mkqs_compare_datum(x + i,
+ x + i + 1,
+ depth,
+ state);
+ if (ret >= 0)
+ {
+ strictOrdered = false;
+ break;
+ }
+ }
+
+ if (strictOrdered)
+ return;
+
+ /* Select pivot by random and move it to the first position */
+ lessStart = n / 2;
+ mkqs_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 = mkqs_compare_datum(x + lessEnd,
+ pivot,
+ depth,
+ state);
+
+ if (dist > 0)
+ break;
+
+ /* If lessEnd is equal to pivot, move it to lessStart */
+ if (dist == 0)
+ {
+ mkqs_swap(lessEnd, lessStart, x);
+ lessStart++;
+ }
+ lessEnd++;
+ }
+
+ /* Compare the right end of the array */
+ while (lessEnd <= greaterStart)
+ {
+ /* Compare greaterStart and pivot at current depth */
+ dist = mkqs_compare_datum(x + greaterStart,
+ pivot,
+ depth,
+ state);
+
+ if (dist < 0)
+ break;
+
+ /* If greaterStart is equal to pivot, move it to greaterEnd */
+ if (dist == 0)
+ {
+ mkqs_swap(greaterStart, greaterEnd, x);
+ greaterEnd--;
+ }
+ greaterStart--;
+ }
+
+ if (lessEnd > greaterStart)
+ break;
+ mkqs_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);
+ mkqs_vec_swap(0, lessEnd - dist, dist, x);
+
+ /* Move the right equal part to middle */
+ dist = Min(greaterEnd - greaterStart, n - greaterEnd - 1);
+ mkqs_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;
+ mk_qsort_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)
+ {
+ mk_qsort_tuple(x + dist,
+ tupCount,
+ depth + 1,
+ state,
+ seenNull || isDatumNull);
+ } else {
+ /*
+ * We have reach the max depth: Call mkqsHandleDupFunc to handle
+ * duplicated tuples if necessary, e.g. checking uniqueness or extra
+ * comparing
+ */
+
+ /*
+ * Call mkqsHandleDupFunc if:
+ * 1. mkqsHandleDupFunc is filled
+ * 2. the size of equal part > 1
+ */
+ if (state->base.mkqsHandleDupFunc &&
+ (tupCount > 1))
+ {
+ state->base.mkqsHandleDupFunc(x + dist,
+ tupCount,
+ seenNull || isDatumNull,
+ state);
+ }
+ }
+
+ /* Recursively sort the greater part */
+
+ /* dist means the size of greater part */
+ dist = greaterEnd - greaterStart;
+ mk_qsort_tuple(x + n - dist,
+ dist,
+ depth,
+ state,
+ seenNull);
+
+#ifdef USE_ASSERT_CHECKING
+ mkqs_verify(x,
+ n,
+ depth,
+ state);
+#endif
+}
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 7c4d6dc106b..5718911eb9b 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -128,6 +128,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 +338,9 @@ struct Tuplesortstate
#ifdef TRACE_SORT
PGRUsage ru_start;
#endif
+
+ /* Whether multi-key quick sort is used */
+ bool mkqsUsed;
};
/*
@@ -622,6 +626,8 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
#define ST_DEFINE
#include "lib/sort_template.h"
+#include "mk_qsort_tuple.c"
+
/*
* tuplesort_begin_xxx
*
@@ -690,6 +696,7 @@ tuplesort_begin_common(int workMem, SortCoordinate coordinate, int sortopt)
state->base.sortopt = sortopt;
state->base.tuples = true;
state->abbrevNext = 10;
+ state->mkqsUsed = false;
/*
* workMem is forced to be at least 64KB, the current minimum valid value
@@ -2559,6 +2566,8 @@ tuplesort_get_stats(Tuplesortstate *state,
case TSS_SORTEDINMEM:
if (state->boundUsed)
stats->sortMethod = SORT_TYPE_TOP_N_HEAPSORT;
+ else if (state->mkqsUsed)
+ stats->sortMethod = SORT_TYPE_MK_QSORT;
else
stats->sortMethod = SORT_TYPE_QUICKSORT;
break;
@@ -2592,6 +2601,8 @@ tuplesort_method_name(TuplesortMethod m)
return "external sort";
case SORT_TYPE_EXTERNAL_MERGE:
return "external merge";
+ case SORT_TYPE_MK_QSORT:
+ return "multi-key quick sort";
}
return "unknown";
@@ -2717,6 +2728,39 @@ tuplesort_sort_memtuples(Tuplesortstate *state)
if (state->memtupcount > 1)
{
+ /*
+ * Apply multi-key quick sort when:
+ * 1. enable_mk_sort is set
+ * 2. There are multiple keys available
+ * 3. mkqsGetDatumFunc is filled, which implies that current tuple
+ * type is supported by mk qsort. (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 mk qsort:
+ *
+ * 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.mkqsGetDatumFunc != NULL)
+ {
+ state->mkqsUsed = true;
+ mk_qsort_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 05a853caa36..ddcffa5094d 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 mkqs_get_datum_heap(SortTuple *x,
+ const int tupleIndex,
+ const int depth,
+ Tuplesortstate *state,
+ Datum *datum,
+ bool *isNull,
+ bool useFullKey);
+
+static Datum mkqs_get_datum_index_btree(SortTuple *x,
+ const int tupleIndex,
+ const int depth,
+ Tuplesortstate *state,
+ Datum *datum,
+ bool *isNull,
+ bool useFullKey);
+
+static void
+mkqs_handle_dup_index_btree(SortTuple *x,
+ const int tupleCount,
+ const bool seenNull,
+ Tuplesortstate *state);
+
+static int
+mkqs_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 inline 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) mkqs_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->mkqsGetDatumFunc = mkqs_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->mkqsGetDatumFunc = mkqs_get_datum_index_btree;
+ base->mkqsHandleDupFunc = mkqs_handle_dup_index_btree;
base->writetup = writetup_index;
base->readtup = readtup_index;
base->haveDatum1 = true;
@@ -1531,10 +1578,6 @@ comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b,
*/
if (arg->enforceUnique && !(!arg->uniqueNullsNotDistinct && equal_hasnull))
{
- Datum values[INDEX_MAX_KEYS];
- bool isnull[INDEX_MAX_KEYS];
- char *key_desc;
-
/*
* Some rather brain-dead implementations of qsort (such as the one in
* QNX 4) will sometimes call the comparison routine to compare a
@@ -1543,18 +1586,7 @@ comparetup_index_btree_tiebreak(const SortTuple *a, const SortTuple *b,
*/
Assert(tuple1 != tuple2);
- index_deform_tuple(tuple1, tupDes, 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))));
+ raise_error_of_dup_index(tuple1, state);
}
/*
@@ -1563,25 +1595,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 +1902,232 @@ 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
+mkqs_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);
+
+ /*
+ * 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
+mkqs_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);
+
+ /*
+ * 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 mk qsort)
+ * x: the duplicated tuple list
+ * tupleCount: count of the tuples
+ */
+static void
+mkqs_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))
+ {
+ /*
+ * 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
+ * mkqs_handle_dup_index_btree()
+ */
+static int
+mkqs_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 inline 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 dc1841346cd..f7c368cd162 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 e7941a1f09f..74a6a5ae5ce 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_MK_QSORT = 1 << 4,
} TuplesortMethod;
-#define NUM_TUPLESORTMETHODS 4
+#define NUM_TUPLESORTMETHODS 5
typedef enum
{
@@ -155,6 +155,23 @@ typedef struct
typedef int (*SortTupleComparator) (const SortTuple *a, const SortTuple *b,
Tuplesortstate *state);
+/* Multi-key quick sort */
+
+typedef Datum
+(*MkqsGetDatumFunc) (SortTuple *x,
+ const int tupleIndex,
+ const int depth,
+ Tuplesortstate *state,
+ Datum *datum,
+ bool *isNull,
+ bool useFullKey);
+
+typedef void
+(*MkqsHandleDupFunc) (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 +266,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 mk_qsort_tuple().
+ */
+ MkqsGetDatumFunc mkqsGetDatumFunc;
+
+ /*
+ * Function pointer, referencing a function to handle duplicated tuple
+ * from SortTuple list with multi-key.
+ * Used by mk_qsort_tuple().
+ * For now, the function pointer is filled for only btree index tuple.
+ */
+ MkqsHandleDupFunc mkqsHandleDupFunc;
} 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 8be694f46be..094d22861c1 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 5fd54a10b1a..a26f8f100a5 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 quick 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 quick 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 quick 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 quick sort" +
], +
"Sort Space Memory": { +
"Peak Sort Space Used": "NN", +
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index dbfd0c13d46..edd2cbfffd5 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -146,6 +146,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_material | on
enable_memoize | on
enable_mergejoin | on
+ enable_mk_sort | on
enable_nestloop | on
enable_parallel_append | on
enable_parallel_hash | on
@@ -156,7 +157,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(22 rows)
+(23 rows)
-- There are always wait event descriptions for various types.
select type, count(*) > 0 as ok FROM pg_wait_events
diff --git a/src/test/regress/expected/tuplesort.out b/src/test/regress/expected/tuplesort.out
index 6dd97e7427a..ad9e56c2548 100644
--- a/src/test/regress/expected/tuplesort.out
+++ b/src/test/regress/expected/tuplesort.out
@@ -703,3 +703,379 @@ EXPLAIN (COSTS OFF) :qry;
(10 rows)
COMMIT;
+-- Test cases for multi-key quick 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, 20) g;
+select * from mksort_simple_tbl order by a, b, c;
+ a | b | c
+---+----+------
+ 0 | 5 | 98f1
+ 0 | 10 | d3d9
+ 1 | 1 | c4ca
+ 1 | 11 | 6512
+ 2 | 2 | c81e
+ 2 | 12 | c20a
+ 3 | 3 | eccb
+ 3 | 13 | c51c
+ 4 | 4 | a87f
+ 4 | 14 | aab3
+ 5 | 0 | 9bf3
+ 5 | 5 | e4da
+ 6 | 1 | c74d
+ 6 | 6 | 1679
+ 7 | 2 | 70ef
+ 7 | 7 | 8f14
+ 8 | 3 | 6f49
+ 8 | 8 | c9f0
+ 9 | 4 | 1f0e
+ 9 | 9 | 45c4
+(20 rows)
+
+-- test sorting on distinct values, in which mk qsort is supposed to be
+-- not affective, but still can generate correct result
+truncate table mksort_simple_tbl;
+insert into mksort_simple_tbl
+ select 20 - g, g, g::text
+ from generate_series(1, 20) g;
+select * from mksort_simple_tbl order by a, b, c;
+ a | b | c
+----+----+----
+ 0 | 20 | 20
+ 1 | 19 | 19
+ 2 | 18 | 18
+ 3 | 17 | 17
+ 4 | 16 | 16
+ 5 | 15 | 15
+ 6 | 14 | 14
+ 7 | 13 | 13
+ 8 | 12 | 12
+ 9 | 11 | 11
+ 10 | 10 | 10
+ 11 | 9 | 9
+ 12 | 8 | 8
+ 13 | 7 | 7
+ 14 | 6 | 6
+ 15 | 5 | 5
+ 16 | 4 | 4
+ 17 | 3 | 3
+ 18 | 2 | 2
+ 19 | 1 | 1
+(20 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 ae4e8851f8a..2de20ca1d0c 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 c3ea368da5e..1f47f07f311 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 8476e594e6c..a7d11a146f3 100644
--- a/src/test/regress/sql/tuplesort.sql
+++ b/src/test/regress/sql/tuplesort.sql
@@ -305,3 +305,69 @@ EXPLAIN (COSTS OFF) :qry;
:qry;
COMMIT;
+
+-- Test cases for multi-key quick 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, 20) g;
+select * from mksort_simple_tbl order by a, b, c;
+
+-- test sorting on distinct values, in which mk qsort is supposed to be
+-- not affective, but still can generate correct result
+truncate table mksort_simple_tbl;
+insert into mksort_simple_tbl
+ select 20 - g, g, g::text
+ from generate_series(1, 20) 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;
diff --git a/src/test/regress/sql/window.sql b/src/test/regress/sql/window.sql
index 6de5493b05b..46359cb7968 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.45.1