On Mon, Nov 3, 2025 at 8:24 PM I wrote: > v1 was careful to restore isnull1 to false when diverting to quicksort > for the tiebreak. v2 doesn't bother, since the only tiebreak in core > that looks at isnull1 is comparetup_datum_tiebreak, which is not > reachable by radix sort, requiring a pass-by-value datum that compares > like an integer. This is a bit of a risk, since it's possible a third > party fork could be doing something weird. Seems unlikely, but > something to keep in mind.
I decided I wasn't quite comfortable with the full normalized datum sharing space in SortTuple with isnull1. There's too much of a cognitive burden involved in deciding when we do or don't need to reset isnull1, and there's a non-zero risk of difficult-to-detect bugs. For v4 I've instead used one byte of padding space in SortTuple to store only the byte used for the current pass. That means we must compute the normalized datum on every pass. That's actually better than it sounds, since that one byte can now be used directly during the "deal" step, rather than having to extract the byte from the normalized datum by shifting and masking. That extraction step might add significant cycles in cases where a pass requires multiple iterations through the "deal" loop. It doesn't seem to make much difference in practice, performance-wise, even with the following pessimization: I had to scrap the qsort specialization on the normalized datum for small sorts, since it's no longer stored. It could still be worth it to compute the "next byte of the normalized datum" and perform a qsort on that (falling back to the comparator function in the usual way), but I haven't felt the need to resort to that yet. For v4, I just divert to qsort_tuple in non-assert builds, with a threshold of 40. > - I don't quite like how the NULL partitioning step looks, and it > could be costly when the distribution of NULL is not predictable, so > I'm thinking of turning part of that into a branch-free cyclic > permutation, similar to > https://www.postgresql.org/message-id/CANWCAZbAmaZ7P%2BARjS97sJLXsBB5CPZyzFgqNDiqe-L%2BBqXzug%40mail.gmail.com This is done. Even though the inner loop is mysterious at first glance, it's really quite elegant. I made an attempt at clean-up, but it's still under-commented. The common prefix detection has moved to a separate patch (v4-0004). I've been forcing all eligible sorts to use radix sort in assert builds, even when small enough that qsort would be faster. Since both qsort and in-place radix sort are unstable, it's expected that some regression tests need adjustment (v4-0002). One thing surprised me, however: The pg_upgrade TAP test that runs regression tests on the old cluster showed additional failures that I can't explain. I haven't seen this before, but it's possible I never ran TAP tests when testing new sort algorithms previously. This doesn't happen if you change the current insertion sort threshold, so I haven't been able to reproduce it aside from this patch. For that reason I can't completely rule out an actual bug, although I actually have more confidence in the verification of correct sort order in v4, since isnull1 now never changes, just as in master. I found that changing some tests to have additional sort keys seems to fix it (v4-0003). I did this in a rather quick and haphazard fashion. There's probably a longer conversation to be had about making test output more deterministic while still covering the intended executor paths. Aside from that, this seems like a good place to settle down, so I'm going to create a CF entry for this. I'll start more rigorous performance testing in the near future. -- John Naylor Amazon Web Services
From d816f92e1c290c771bfd323ffba6f33319a4eb72 Mon Sep 17 00:00:00 2001 From: John Naylor <[email protected]> Date: Wed, 12 Nov 2025 14:31:24 +0700 Subject: [PATCH v4 4/4] Detect common prefix to avoid wasted work during radix sort This is particularly useful for integers, since they commonly have some zero upper bytes. --- src/backend/utils/sort/tuplesort.c | 53 +++++++++++++++++++++++++++++- 1 file changed, 52 insertions(+), 1 deletion(-) diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index 3efc22de24e..68fa9c13ca8 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -104,6 +104,7 @@ #include "commands/tablespace.h" #include "miscadmin.h" #include "pg_trace.h" +#include "port/pg_bitutils.h" #include "storage/shmem.h" #include "utils/guc.h" #include "utils/memutils.h" @@ -2980,9 +2981,59 @@ sort_byvalue_datum(Tuplesortstate *state) } else { + int common_prefix; + Datum first_datum = 0; + Datum common_upper_bits = 0; + + /* + * Compute the common prefix to skip unproductive recursion steps + * during radix sort. + */ + for (SortTuple *tup = not_null_start; + tup < not_null_start + not_null_count; + tup++) + { + Datum this_datum = tup->datum1; + + if (tup == not_null_start) + { + /* + * Need to start with some value, may as well be the first + * one. + */ + first_datum = this_datum; + } + else + { + Datum this_common_bits; + + /* The bits in common will be zero */ + this_common_bits = first_datum ^ this_datum; + + /* + * We're really only interested in the case where the + * leftmost one bit is further left, but this branch + * should be predictable enough not to waste cycles trying + * harder. + */ + if (this_common_bits > common_upper_bits) + common_upper_bits = this_common_bits; + } + } + + /* + * The upper bits of common_upper_bits are zero where all values + * have the same bits. The byte position of the leftmost one bit + * is the byte where radix sort should start bucketing. OR-ing in + * the lowest bit guards against undefined behavior without + * changing the result. + */ + common_prefix = sizeof(Datum) - 1 - + (pg_leftmost_one_pos64(common_upper_bits | 1) / BITS_PER_BYTE); + radix_sort_tuple(not_null_start, not_null_count, - 0, + common_prefix, state); } } -- 2.51.1
From 12d0603a3aa94b033b4111d1944f2b054f00628d Mon Sep 17 00:00:00 2001 From: John Naylor <[email protected]> Date: Tue, 11 Nov 2025 17:41:26 +0700 Subject: [PATCH v4 2/4] WIP Adjust regression tests Regression tests don't pass for underspecified queries; this is expected since both qsort and in-place radix sort are unstable sorts. For the query SELECT a, b from mytable ORDER BY a; ...a stable sort would guarantee the relative position of 'b' for each group of 'a', compared to the input. This is separated out since the relative order changes with the qsort threshold, same as it would for qsort and its insertion sort threshold. Assert builds always do radix sort regardless of input size, if the data type allows it. The final commit will have the same threshold for all builds. --- contrib/pg_stat_statements/expected/dml.out | 6 +- .../postgres_fdw/expected/postgres_fdw.out | 8 +- src/backend/utils/sort/tuplesort.c | 1 - src/test/regress/expected/groupingsets.out | 2 +- src/test/regress/expected/inet.out | 4 +- src/test/regress/expected/join.out | 20 +- src/test/regress/expected/plancache.out | 8 +- src/test/regress/expected/sqljson.out | 8 +- src/test/regress/expected/tsrf.out | 38 +- src/test/regress/expected/tuplesort.out | 6 +- src/test/regress/expected/window.out | 500 +++++++++--------- 11 files changed, 300 insertions(+), 301 deletions(-) diff --git a/contrib/pg_stat_statements/expected/dml.out b/contrib/pg_stat_statements/expected/dml.out index 347cb8699e4..aa6e91e1c7f 100644 --- a/contrib/pg_stat_statements/expected/dml.out +++ b/contrib/pg_stat_statements/expected/dml.out @@ -44,12 +44,12 @@ SELECT * SELECT * FROM pgss_dml_tab ORDER BY a; a | b ---+---------------------- - 1 | a 1 | 111 - 2 | b + 1 | a 2 | 222 - 3 | c + 2 | b 3 | 333 + 3 | c 4 | 444 5 | 555 6 | 666 diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out index cd28126049d..95f8fd388e6 100644 --- a/contrib/postgres_fdw/expected/postgres_fdw.out +++ b/contrib/postgres_fdw/expected/postgres_fdw.out @@ -2626,15 +2626,15 @@ SELECT * FROM ft1, ft4, ft5, local_tbl WHERE ft1.c1 = ft4.c1 AND ft1.c1 = ft5.c1 12 | 2 | 00012 | Tue Jan 13 00:00:00 1970 PST | Tue Jan 13 00:00:00 1970 | 2 | 2 | foo | 12 | 13 | AAA012 | 12 | 13 | AAA012 | 2 | 2 | 0002 42 | 2 | 00042 | Thu Feb 12 00:00:00 1970 PST | Thu Feb 12 00:00:00 1970 | 2 | 2 | foo | 42 | 43 | AAA042 | 42 | 43 | AAA042 | 2 | 2 | 0002 72 | 2 | 00072 | Sat Mar 14 00:00:00 1970 PST | Sat Mar 14 00:00:00 1970 | 2 | 2 | foo | 72 | 73 | AAA072 | 72 | 73 | | 2 | 2 | 0002 - 24 | 4 | 00024 | Sun Jan 25 00:00:00 1970 PST | Sun Jan 25 00:00:00 1970 | 4 | 4 | foo | 24 | 25 | AAA024 | 24 | 25 | AAA024 | 4 | 4 | 0004 54 | 4 | 00054 | Tue Feb 24 00:00:00 1970 PST | Tue Feb 24 00:00:00 1970 | 4 | 4 | foo | 54 | 55 | AAA054 | 54 | 55 | | 4 | 4 | 0004 + 24 | 4 | 00024 | Sun Jan 25 00:00:00 1970 PST | Sun Jan 25 00:00:00 1970 | 4 | 4 | foo | 24 | 25 | AAA024 | 24 | 25 | AAA024 | 4 | 4 | 0004 84 | 4 | 00084 | Thu Mar 26 00:00:00 1970 PST | Thu Mar 26 00:00:00 1970 | 4 | 4 | foo | 84 | 85 | AAA084 | 84 | 85 | AAA084 | 4 | 4 | 0004 - 96 | 6 | 00096 | Tue Apr 07 00:00:00 1970 PST | Tue Apr 07 00:00:00 1970 | 6 | 6 | foo | 96 | 97 | AAA096 | 96 | 97 | AAA096 | 6 | 6 | 0006 + 6 | 6 | 00006 | Wed Jan 07 00:00:00 1970 PST | Wed Jan 07 00:00:00 1970 | 6 | 6 | foo | 6 | 7 | AAA006 | 6 | 7 | AAA006 | 6 | 6 | 0006 36 | 6 | 00036 | Fri Feb 06 00:00:00 1970 PST | Fri Feb 06 00:00:00 1970 | 6 | 6 | foo | 36 | 37 | AAA036 | 36 | 37 | | 6 | 6 | 0006 66 | 6 | 00066 | Sun Mar 08 00:00:00 1970 PST | Sun Mar 08 00:00:00 1970 | 6 | 6 | foo | 66 | 67 | AAA066 | 66 | 67 | AAA066 | 6 | 6 | 0006 - 6 | 6 | 00006 | Wed Jan 07 00:00:00 1970 PST | Wed Jan 07 00:00:00 1970 | 6 | 6 | foo | 6 | 7 | AAA006 | 6 | 7 | AAA006 | 6 | 6 | 0006 - 48 | 8 | 00048 | Wed Feb 18 00:00:00 1970 PST | Wed Feb 18 00:00:00 1970 | 8 | 8 | foo | 48 | 49 | AAA048 | 48 | 49 | AAA048 | 8 | 8 | 0008 + 96 | 6 | 00096 | Tue Apr 07 00:00:00 1970 PST | Tue Apr 07 00:00:00 1970 | 6 | 6 | foo | 96 | 97 | AAA096 | 96 | 97 | AAA096 | 6 | 6 | 0006 18 | 8 | 00018 | Mon Jan 19 00:00:00 1970 PST | Mon Jan 19 00:00:00 1970 | 8 | 8 | foo | 18 | 19 | AAA018 | 18 | 19 | | 8 | 8 | 0008 + 48 | 8 | 00048 | Wed Feb 18 00:00:00 1970 PST | Wed Feb 18 00:00:00 1970 | 8 | 8 | foo | 48 | 49 | AAA048 | 48 | 49 | AAA048 | 8 | 8 | 0008 78 | 8 | 00078 | Fri Mar 20 00:00:00 1970 PST | Fri Mar 20 00:00:00 1970 | 8 | 8 | foo | 78 | 79 | AAA078 | 78 | 79 | AAA078 | 8 | 8 | 0008 (13 rows) diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index c2b9625ae88..3efc22de24e 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -104,7 +104,6 @@ #include "commands/tablespace.h" #include "miscadmin.h" #include "pg_trace.h" -#include "port/pg_bitutils.h" #include "storage/shmem.h" #include "utils/guc.h" #include "utils/memutils.h" diff --git a/src/test/regress/expected/groupingsets.out b/src/test/regress/expected/groupingsets.out index 398cf6965e0..02abebdb0d7 100644 --- a/src/test/regress/expected/groupingsets.out +++ b/src/test/regress/expected/groupingsets.out @@ -94,8 +94,8 @@ select a, b, grouping(a,b), sum(v), count(*), max(v) 1 | | 1 | 60 | 5 | 14 1 | 1 | 0 | 21 | 2 | 11 2 | | 1 | 15 | 1 | 15 - 3 | | 1 | 33 | 2 | 17 1 | 2 | 0 | 25 | 2 | 13 + 3 | | 1 | 33 | 2 | 17 1 | 3 | 0 | 14 | 1 | 14 4 | | 1 | 37 | 2 | 19 4 | 1 | 0 | 37 | 2 | 19 diff --git a/src/test/regress/expected/inet.out b/src/test/regress/expected/inet.out index 1705bff4dd3..85a3a6a7de5 100644 --- a/src/test/regress/expected/inet.out +++ b/src/test/regress/expected/inet.out @@ -465,9 +465,9 @@ SELECT * FROM inet_tbl WHERE i < '192.168.1.0/24'::cidr ORDER BY i; c | i -------------+------------- 10.0.0.0/8 | 9.1.2.3/8 - 10.0.0.0/32 | 10.1.2.3/8 10.0.0.0/8 | 10.1.2.3/8 10.0.0.0/8 | 10.1.2.3/8 + 10.0.0.0/32 | 10.1.2.3/8 10.1.0.0/16 | 10.1.2.3/16 10.1.2.0/24 | 10.1.2.3/24 10.1.2.3/32 | 10.1.2.3 @@ -613,9 +613,9 @@ SELECT * FROM inet_tbl WHERE i < '192.168.1.0/24'::cidr ORDER BY i; c | i -------------+------------- 10.0.0.0/8 | 9.1.2.3/8 - 10.0.0.0/32 | 10.1.2.3/8 10.0.0.0/8 | 10.1.2.3/8 10.0.0.0/8 | 10.1.2.3/8 + 10.0.0.0/32 | 10.1.2.3/8 10.1.0.0/16 | 10.1.2.3/16 10.1.2.0/24 | 10.1.2.3/24 10.1.2.3/32 | 10.1.2.3 diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out index 0e82ca1867a..9b6a9f536d3 100644 --- a/src/test/regress/expected/join.out +++ b/src/test/regress/expected/join.out @@ -220,8 +220,8 @@ SELECT t1.a, t2.e ---+---- 0 | 1 | -1 - 2 | 2 2 | 4 + 2 | 2 3 | -3 5 | -5 5 | -5 @@ -1575,8 +1575,8 @@ SELECT * ---+---+-------+---- 0 | | zero | 1 | 4 | one | -1 - 2 | 3 | two | 2 2 | 3 | two | 4 + 2 | 3 | two | 2 3 | 2 | three | -3 5 | 0 | five | -5 5 | 0 | five | -5 @@ -1589,8 +1589,8 @@ SELECT * ---+---+-------+---- 0 | | zero | 1 | 4 | one | -1 - 2 | 3 | two | 2 2 | 3 | two | 4 + 2 | 3 | two | 2 3 | 2 | three | -3 5 | 0 | five | -5 5 | 0 | five | -5 @@ -1683,8 +1683,8 @@ SELECT * ---+---+-------+---- 0 | | zero | 1 | 4 | one | -1 - 2 | 3 | two | 2 2 | 3 | two | 4 + 2 | 3 | two | 2 3 | 2 | three | -3 5 | 0 | five | -5 5 | 0 | five | -5 @@ -1696,8 +1696,8 @@ SELECT * ---+---+-------+---- 0 | | zero | 1 | 4 | one | -1 - 2 | 3 | two | 2 2 | 3 | two | 4 + 2 | 3 | two | 2 3 | 2 | three | -3 5 | 0 | five | -5 5 | 0 | five | -5 @@ -1720,8 +1720,8 @@ SELECT * ---+---+-------+---- 0 | | zero | 1 | 4 | one | -1 - 2 | 3 | two | 2 2 | 3 | two | 4 + 2 | 3 | two | 2 3 | 2 | three | -3 5 | 0 | five | -5 5 | 0 | five | -5 @@ -1736,8 +1736,8 @@ SELECT * ---+---+-------+---+---- 0 | | zero | 0 | 1 | 4 | one | 1 | -1 - 2 | 3 | two | 2 | 2 2 | 3 | two | 2 | 4 + 2 | 3 | two | 2 | 2 3 | 2 | three | 3 | -3 5 | 0 | five | 5 | -5 5 | 0 | five | 5 | -5 @@ -1820,8 +1820,8 @@ SELECT * ---+---+-------+---- 0 | | zero | 1 | 4 | one | -1 - 2 | 3 | two | 2 2 | 3 | two | 4 + 2 | 3 | two | 2 3 | 2 | three | -3 5 | 0 | five | -5 5 | 0 | five | -5 @@ -1835,8 +1835,8 @@ SELECT * ---+---+-------+---- 0 | | zero | 1 | 4 | one | -1 - 2 | 3 | two | 2 2 | 3 | two | 4 + 2 | 3 | two | 2 3 | 2 | three | -3 5 | 0 | five | -5 5 | 0 | five | -5 @@ -2776,8 +2776,8 @@ select * from ---+---+-------+---+---- | | | | 0 | | | | - | 0 | zero | | | | null | | + | 0 | zero | | 8 | 8 | eight | | 7 | 7 | seven | | 6 | 6 | six | | diff --git a/src/test/regress/expected/plancache.out b/src/test/regress/expected/plancache.out index 4e59188196c..41440c10cdd 100644 --- a/src/test/regress/expected/plancache.out +++ b/src/test/regress/expected/plancache.out @@ -38,8 +38,8 @@ EXECUTE prepstmt; 4567890123456789 | -4567890123456789 4567890123456789 | 123 123 | 456 - 123 | 4567890123456789 4567890123456789 | 4567890123456789 + 123 | 4567890123456789 (5 rows) EXECUTE prepstmt2(123); @@ -64,8 +64,8 @@ EXECUTE prepstmt; 4567890123456789 | -4567890123456789 4567890123456789 | 123 123 | 456 - 123 | 4567890123456789 4567890123456789 | 4567890123456789 + 123 | 4567890123456789 (5 rows) EXECUTE prepstmt2(123); @@ -86,8 +86,8 @@ EXECUTE vprep; 4567890123456789 | -4567890123456789 4567890123456789 | 123 123 | 456 - 123 | 4567890123456789 4567890123456789 | 4567890123456789 + 123 | 4567890123456789 (5 rows) CREATE OR REPLACE TEMP VIEW pcacheview AS @@ -98,8 +98,8 @@ EXECUTE vprep; 4567890123456789 | -2283945061728394 4567890123456789 | 61 123 | 228 - 123 | 2283945061728394 4567890123456789 | 2283945061728394 + 123 | 2283945061728394 (5 rows) -- Check basic SPI plan invalidation diff --git a/src/test/regress/expected/sqljson.out b/src/test/regress/expected/sqljson.out index c7b9e575445..13fa4f2262d 100644 --- a/src/test/regress/expected/sqljson.out +++ b/src/test/regress/expected/sqljson.out @@ -870,10 +870,10 @@ FROM 4 | [4, 4] 4 | [4, 4] 2 | [4, 4] - 5 | [5, 3, 5] - 3 | [5, 3, 5] - 1 | [5, 3, 5] - 5 | [5, 3, 5] + 3 | [3, 5, 5] + 1 | [3, 5, 5] + 5 | [3, 5, 5] + 5 | [3, 5, 5] | | | diff --git a/src/test/regress/expected/tsrf.out b/src/test/regress/expected/tsrf.out index c4f7b187f5b..fd3914b0fad 100644 --- a/src/test/regress/expected/tsrf.out +++ b/src/test/regress/expected/tsrf.out @@ -354,18 +354,18 @@ SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(d a | foo | 1 | 1 a | | 1 | 2 b | bar | 1 | 1 - b | | 1 | 1 - | | 1 | 3 | bar | 1 | 2 | foo | 1 | 1 - | foo | 2 | 1 + | | 1 | 3 + b | | 1 | 1 a | bar | 2 | 1 - b | | 2 | 1 a | foo | 2 | 1 - | bar | 2 | 2 a | | 2 | 2 - | | 2 | 3 b | bar | 2 | 1 + | bar | 2 | 2 + | foo | 2 | 1 + b | | 2 | 1 + | | 2 | 3 (16 rows) SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab, g); @@ -433,26 +433,26 @@ SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(d a | foo | 1 | 1 b | bar | 1 | 1 | bar | 1 | 2 - | foo | 1 | 1 + | | 1 | 3 a | | 1 | 2 b | | 1 | 1 - | | 1 | 3 + | foo | 1 | 1 + a | bar | 2 | 1 + a | foo | 2 | 1 + b | bar | 2 | 1 + | bar | 2 | 2 a | | 2 | 2 b | | 2 | 1 - | bar | 2 | 2 | | 2 | 3 | foo | 2 | 1 - a | bar | 2 | 1 - a | foo | 2 | 1 - b | bar | 2 | 1 - a | | | 4 - b | bar | | 2 - b | | | 2 + a | bar | | 2 + | foo | | 2 | | | 6 a | foo | | 2 - a | bar | | 2 + a | | | 4 | bar | | 4 - | foo | | 2 + b | bar | | 2 + b | | | 2 (24 rows) reset enable_hashagg; @@ -600,8 +600,8 @@ FROM (VALUES (3, 2), (3,1), (1,1), (1,4), (5,3), (5,1)) AS t(a, b); a | b | g ---+---+--- 3 | 2 | 1 - 5 | 1 | 2 - 3 | 1 | 3 + 3 | 2 | 2 + 3 | 2 | 3 (3 rows) -- LIMIT / OFFSET is evaluated after SRF evaluation diff --git a/src/test/regress/expected/tuplesort.out b/src/test/regress/expected/tuplesort.out index 6dd97e7427a..fc1321bf443 100644 --- a/src/test/regress/expected/tuplesort.out +++ b/src/test/regress/expected/tuplesort.out @@ -304,9 +304,9 @@ FROM abbrev_abort_uuids ORDER BY ctid DESC LIMIT 5; id | abort_increasing | abort_decreasing | noabort_increasing | noabort_decreasing -------+--------------------------------------+--------------------------------------+--------------------------------------+-------------------------------------- - 0 | | | | 20002 | | | | 20003 | | | | + 0 | | | | 10009 | 00000000-0000-0000-0000-000000010008 | 00000000-0000-0000-0000-000000009992 | 00010008-0000-0000-0000-000000010008 | 00009992-0000-0000-0000-000000009992 10008 | 00000000-0000-0000-0000-000000010007 | 00000000-0000-0000-0000-000000009993 | 00010007-0000-0000-0000-000000010007 | 00009993-0000-0000-0000-000000009993 (5 rows) @@ -335,9 +335,9 @@ FROM abbrev_abort_uuids ORDER BY ctid DESC LIMIT 5; id | abort_increasing | abort_decreasing | noabort_increasing | noabort_decreasing -------+--------------------------------------+--------------------------------------+--------------------------------------+-------------------------------------- - 0 | | | | - 20003 | | | | 20002 | | | | + 20003 | | | | + 0 | | | | 9993 | 00000000-0000-0000-0000-000000009992 | 00000000-0000-0000-0000-000000010008 | 00009992-0000-0000-0000-000000009992 | 00010008-0000-0000-0000-000000010008 9994 | 00000000-0000-0000-0000-000000009993 | 00000000-0000-0000-0000-000000010007 | 00009993-0000-0000-0000-000000009993 | 00010007-0000-0000-0000-000000010007 (5 rows) diff --git a/src/test/regress/expected/window.out b/src/test/regress/expected/window.out index 9e2f53726f5..b3cdeaea4b3 100644 --- a/src/test/regress/expected/window.out +++ b/src/test/regress/expected/window.out @@ -95,13 +95,13 @@ SELECT depname, empno, salary, rank() OVER w FROM empsalary WINDOW w AS (PARTITI -----------+-------+--------+------ develop | 7 | 4200 | 1 personnel | 5 | 3500 | 1 - sales | 3 | 4800 | 1 sales | 4 | 4800 | 1 - personnel | 2 | 3900 | 2 + sales | 3 | 4800 | 1 develop | 9 | 4500 | 2 - sales | 1 | 5000 | 3 + personnel | 2 | 3900 | 2 develop | 11 | 5200 | 3 develop | 10 | 5200 | 3 + sales | 1 | 5000 | 3 develop | 8 | 6000 | 5 (10 rows) @@ -394,12 +394,12 @@ SELECT first_value(ten) OVER (PARTITION BY four ORDER BY ten), ten, four FROM te SELECT last_value(four) OVER (ORDER BY ten), ten, four FROM tenk1 WHERE unique2 < 10; last_value | ten | four ------------+-----+------ - 0 | 0 | 0 - 0 | 0 | 2 - 0 | 0 | 0 - 1 | 1 | 1 + 2 | 0 | 0 + 2 | 0 | 0 + 2 | 0 | 2 1 | 1 | 3 1 | 1 | 1 + 1 | 1 | 1 3 | 3 | 3 0 | 4 | 0 1 | 7 | 1 @@ -821,14 +821,14 @@ SELECT sum(unique1) over (order by four range between current row and unbounded FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 45 | 0 | 0 - 45 | 8 | 0 45 | 4 | 0 - 33 | 5 | 1 - 33 | 9 | 1 + 45 | 8 | 0 + 45 | 0 | 0 33 | 1 | 1 - 18 | 6 | 2 + 33 | 9 | 1 + 33 | 5 | 1 18 | 2 | 2 + 18 | 6 | 2 10 | 3 | 3 10 | 7 | 3 (10 rows) @@ -940,14 +940,14 @@ SELECT first_value(unique1) over (ORDER BY four rows between current row and 2 f FROM tenk1 WHERE unique1 < 10; first_value | unique1 | four -------------+---------+------ - 8 | 0 | 0 - 4 | 8 | 0 - 5 | 4 | 0 - 9 | 5 | 1 - 1 | 9 | 1 - 6 | 1 | 1 - 2 | 6 | 2 - 3 | 2 | 2 + 8 | 4 | 0 + 0 | 8 | 0 + 1 | 0 | 0 + 9 | 1 | 1 + 5 | 9 | 1 + 2 | 5 | 1 + 6 | 2 | 2 + 3 | 6 | 2 7 | 3 | 3 | 7 | 3 (10 rows) @@ -957,14 +957,14 @@ SELECT first_value(unique1) over (ORDER BY four rows between current row and 2 f FROM tenk1 WHERE unique1 < 10; first_value | unique1 | four -------------+---------+------ - | 0 | 0 - 5 | 8 | 0 - 5 | 4 | 0 - | 5 | 1 - 6 | 9 | 1 - 6 | 1 | 1 - 3 | 6 | 2 + | 4 | 0 + 1 | 8 | 0 + 1 | 0 | 0 + | 1 | 1 + 2 | 9 | 1 + 2 | 5 | 1 3 | 2 | 2 + 3 | 6 | 2 | 3 | 3 | 7 | 3 (10 rows) @@ -974,14 +974,14 @@ SELECT first_value(unique1) over (ORDER BY four rows between current row and 2 f FROM tenk1 WHERE unique1 < 10; first_value | unique1 | four -------------+---------+------ - 0 | 0 | 0 - 8 | 8 | 0 4 | 4 | 0 - 5 | 5 | 1 - 9 | 9 | 1 + 8 | 8 | 0 + 0 | 0 | 0 1 | 1 | 1 - 6 | 6 | 2 + 9 | 9 | 1 + 5 | 5 | 1 2 | 2 | 2 + 6 | 6 | 2 3 | 3 | 3 7 | 7 | 3 (10 rows) @@ -991,14 +991,14 @@ SELECT last_value(unique1) over (ORDER BY four rows between current row and 2 fo FROM tenk1 WHERE unique1 < 10; last_value | unique1 | four ------------+---------+------ - 4 | 0 | 0 - 5 | 8 | 0 - 9 | 4 | 0 - 1 | 5 | 1 - 6 | 9 | 1 - 2 | 1 | 1 - 3 | 6 | 2 - 7 | 2 | 2 + 0 | 4 | 0 + 1 | 8 | 0 + 9 | 0 | 0 + 5 | 1 | 1 + 2 | 9 | 1 + 6 | 5 | 1 + 3 | 2 | 2 + 7 | 6 | 2 7 | 3 | 3 | 7 | 3 (10 rows) @@ -1008,14 +1008,14 @@ SELECT last_value(unique1) over (ORDER BY four rows between current row and 2 fo FROM tenk1 WHERE unique1 < 10; last_value | unique1 | four ------------+---------+------ - | 0 | 0 - 5 | 8 | 0 - 9 | 4 | 0 - | 5 | 1 - 6 | 9 | 1 - 2 | 1 | 1 - 3 | 6 | 2 - 7 | 2 | 2 + | 4 | 0 + 1 | 8 | 0 + 9 | 0 | 0 + | 1 | 1 + 2 | 9 | 1 + 6 | 5 | 1 + 3 | 2 | 2 + 7 | 6 | 2 | 3 | 3 | 7 | 3 (10 rows) @@ -1025,14 +1025,14 @@ SELECT last_value(unique1) over (ORDER BY four rows between current row and 2 fo FROM tenk1 WHERE unique1 < 10; last_value | unique1 | four ------------+---------+------ - 0 | 0 | 0 - 5 | 8 | 0 - 9 | 4 | 0 - 5 | 5 | 1 - 6 | 9 | 1 - 2 | 1 | 1 - 3 | 6 | 2 - 7 | 2 | 2 + 4 | 4 | 0 + 1 | 8 | 0 + 9 | 0 | 0 + 1 | 1 | 1 + 2 | 9 | 1 + 6 | 5 | 1 + 3 | 2 | 2 + 7 | 6 | 2 3 | 3 | 3 7 | 7 | 3 (10 rows) @@ -1093,14 +1093,14 @@ SELECT sum(unique1) over (w range between current row and unbounded following), FROM tenk1 WHERE unique1 < 10 WINDOW w AS (order by four); sum | unique1 | four -----+---------+------ - 45 | 0 | 0 - 45 | 8 | 0 45 | 4 | 0 - 33 | 5 | 1 - 33 | 9 | 1 + 45 | 8 | 0 + 45 | 0 | 0 33 | 1 | 1 - 18 | 6 | 2 + 33 | 9 | 1 + 33 | 5 | 1 18 | 2 | 2 + 18 | 6 | 2 10 | 3 | 3 10 | 7 | 3 (10 rows) @@ -1110,14 +1110,14 @@ SELECT sum(unique1) over (w range between unbounded preceding and current row ex FROM tenk1 WHERE unique1 < 10 WINDOW w AS (order by four); sum | unique1 | four -----+---------+------ - 12 | 0 | 0 - 4 | 8 | 0 8 | 4 | 0 - 22 | 5 | 1 - 18 | 9 | 1 + 4 | 8 | 0 + 12 | 0 | 0 26 | 1 | 1 - 29 | 6 | 2 + 18 | 9 | 1 + 22 | 5 | 1 33 | 2 | 2 + 29 | 6 | 2 42 | 3 | 3 38 | 7 | 3 (10 rows) @@ -1127,14 +1127,14 @@ SELECT sum(unique1) over (w range between unbounded preceding and current row ex FROM tenk1 WHERE unique1 < 10 WINDOW w AS (order by four); sum | unique1 | four -----+---------+------ - | 0 | 0 - | 8 | 0 | 4 | 0 - 12 | 5 | 1 - 12 | 9 | 1 + | 8 | 0 + | 0 | 0 12 | 1 | 1 - 27 | 6 | 2 + 12 | 9 | 1 + 12 | 5 | 1 27 | 2 | 2 + 27 | 6 | 2 35 | 3 | 3 35 | 7 | 3 (10 rows) @@ -1144,14 +1144,14 @@ SELECT sum(unique1) over (w range between unbounded preceding and current row ex FROM tenk1 WHERE unique1 < 10 WINDOW w AS (order by four); sum | unique1 | four -----+---------+------ - 0 | 0 | 0 - 8 | 8 | 0 4 | 4 | 0 - 17 | 5 | 1 - 21 | 9 | 1 + 8 | 8 | 0 + 0 | 0 | 0 13 | 1 | 1 - 33 | 6 | 2 + 21 | 9 | 1 + 17 | 5 | 1 29 | 2 | 2 + 33 | 6 | 2 38 | 3 | 3 42 | 7 | 3 (10 rows) @@ -1163,14 +1163,14 @@ FROM tenk1 WHERE unique1 < 10 WINDOW w AS (order by four range between current row and unbounded following); first_value | nth_2 | last_value | unique1 | four -------------+-------+------------+---------+------ - 0 | 8 | 7 | 0 | 0 - 0 | 8 | 7 | 8 | 0 - 0 | 8 | 7 | 4 | 0 - 5 | 9 | 7 | 5 | 1 - 5 | 9 | 7 | 9 | 1 - 5 | 9 | 7 | 1 | 1 - 6 | 2 | 7 | 6 | 2 - 6 | 2 | 7 | 2 | 2 + 4 | 8 | 7 | 4 | 0 + 4 | 8 | 7 | 8 | 0 + 4 | 8 | 7 | 0 | 0 + 1 | 9 | 7 | 1 | 1 + 1 | 9 | 7 | 9 | 1 + 1 | 9 | 7 | 5 | 1 + 2 | 6 | 7 | 2 | 2 + 2 | 6 | 7 | 6 | 2 3 | 7 | 7 | 3 | 3 3 | 7 | 7 | 7 | 3 (10 rows) @@ -1367,14 +1367,14 @@ SELECT sum(unique1) over (order by four range between 2::int8 preceding and 1::i FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - | 0 | 0 - | 8 | 0 | 4 | 0 - 12 | 5 | 1 - 12 | 9 | 1 + | 8 | 0 + | 0 | 0 12 | 1 | 1 - 27 | 6 | 2 + 12 | 9 | 1 + 12 | 5 | 1 27 | 2 | 2 + 27 | 6 | 2 23 | 3 | 3 23 | 7 | 3 (10 rows) @@ -1386,14 +1386,14 @@ FROM tenk1 WHERE unique1 < 10; -----+---------+------ | 3 | 3 | 7 | 3 - 10 | 6 | 2 10 | 2 | 2 + 10 | 6 | 2 18 | 9 | 1 18 | 5 | 1 18 | 1 | 1 - 23 | 0 | 0 - 23 | 8 | 0 23 | 4 | 0 + 23 | 8 | 0 + 23 | 0 | 0 (10 rows) SELECT sum(unique1) over (order by four range between 2::int8 preceding and 1::int2 preceding exclude no others), @@ -1401,14 +1401,14 @@ SELECT sum(unique1) over (order by four range between 2::int8 preceding and 1::i FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - | 0 | 0 - | 8 | 0 | 4 | 0 - 12 | 5 | 1 - 12 | 9 | 1 + | 8 | 0 + | 0 | 0 12 | 1 | 1 - 27 | 6 | 2 + 12 | 9 | 1 + 12 | 5 | 1 27 | 2 | 2 + 27 | 6 | 2 23 | 3 | 3 23 | 7 | 3 (10 rows) @@ -1418,14 +1418,14 @@ SELECT sum(unique1) over (order by four range between 2::int8 preceding and 1::i FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - | 0 | 0 - | 8 | 0 | 4 | 0 - 12 | 5 | 1 - 12 | 9 | 1 + | 8 | 0 + | 0 | 0 12 | 1 | 1 - 27 | 6 | 2 + 12 | 9 | 1 + 12 | 5 | 1 27 | 2 | 2 + 27 | 6 | 2 23 | 3 | 3 23 | 7 | 3 (10 rows) @@ -1435,14 +1435,14 @@ SELECT sum(unique1) over (order by four range between 2::int8 preceding and 1::i FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - | 0 | 0 - | 8 | 0 | 4 | 0 - 12 | 5 | 1 - 12 | 9 | 1 + | 8 | 0 + | 0 | 0 12 | 1 | 1 - 27 | 6 | 2 + 12 | 9 | 1 + 12 | 5 | 1 27 | 2 | 2 + 27 | 6 | 2 23 | 3 | 3 23 | 7 | 3 (10 rows) @@ -1452,14 +1452,14 @@ SELECT sum(unique1) over (order by four range between 2::int8 preceding and 1::i FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - | 0 | 0 - | 8 | 0 | 4 | 0 - 12 | 5 | 1 - 12 | 9 | 1 + | 8 | 0 + | 0 | 0 12 | 1 | 1 - 27 | 6 | 2 + 12 | 9 | 1 + 12 | 5 | 1 27 | 2 | 2 + 27 | 6 | 2 23 | 3 | 3 23 | 7 | 3 (10 rows) @@ -1469,14 +1469,14 @@ SELECT sum(unique1) over (order by four range between 2::int8 preceding and 6::i FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 33 | 0 | 0 - 41 | 8 | 0 37 | 4 | 0 - 35 | 5 | 1 - 39 | 9 | 1 + 41 | 8 | 0 + 33 | 0 | 0 31 | 1 | 1 - 43 | 6 | 2 + 39 | 9 | 1 + 35 | 5 | 1 39 | 2 | 2 + 43 | 6 | 2 26 | 3 | 3 30 | 7 | 3 (10 rows) @@ -1486,14 +1486,14 @@ SELECT sum(unique1) over (order by four range between 2::int8 preceding and 6::i FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 33 | 0 | 0 - 33 | 8 | 0 33 | 4 | 0 - 30 | 5 | 1 - 30 | 9 | 1 + 33 | 8 | 0 + 33 | 0 | 0 30 | 1 | 1 - 37 | 6 | 2 + 30 | 9 | 1 + 30 | 5 | 1 37 | 2 | 2 + 37 | 6 | 2 23 | 3 | 3 23 | 7 | 3 (10 rows) @@ -1539,13 +1539,13 @@ select sum(salary) over (order by enroll_date range between '1 year'::interval p 34900 | 5000 | 10-01-2006 34900 | 6000 | 10-01-2006 38400 | 3900 | 12-23-2006 - 47100 | 4800 | 08-01-2007 47100 | 5200 | 08-01-2007 + 47100 | 4800 | 08-01-2007 47100 | 4800 | 08-08-2007 47100 | 5200 | 08-15-2007 36100 | 3500 | 12-10-2007 - 32200 | 4500 | 01-01-2008 32200 | 4200 | 01-01-2008 + 32200 | 4500 | 01-01-2008 (10 rows) select sum(salary) over (order by enroll_date desc range between '1 year'::interval preceding and '1 year'::interval following), @@ -1557,8 +1557,8 @@ select sum(salary) over (order by enroll_date desc range between '1 year'::inter 36100 | 3500 | 12-10-2007 47100 | 5200 | 08-15-2007 47100 | 4800 | 08-08-2007 - 47100 | 4800 | 08-01-2007 47100 | 5200 | 08-01-2007 + 47100 | 4800 | 08-01-2007 38400 | 3900 | 12-23-2006 34900 | 5000 | 10-01-2006 34900 | 6000 | 10-01-2006 @@ -1573,8 +1573,8 @@ select sum(salary) over (order by enroll_date desc range between '1 year'::inter | 3500 | 12-10-2007 | 5200 | 08-15-2007 | 4800 | 08-08-2007 - | 4800 | 08-01-2007 | 5200 | 08-01-2007 + | 4800 | 08-01-2007 | 3900 | 12-23-2006 | 5000 | 10-01-2006 | 6000 | 10-01-2006 @@ -1587,13 +1587,13 @@ select sum(salary) over (order by enroll_date range between '1 year'::interval p 29900 | 5000 | 10-01-2006 28900 | 6000 | 10-01-2006 34500 | 3900 | 12-23-2006 - 42300 | 4800 | 08-01-2007 41900 | 5200 | 08-01-2007 + 42300 | 4800 | 08-01-2007 42300 | 4800 | 08-08-2007 41900 | 5200 | 08-15-2007 32600 | 3500 | 12-10-2007 - 27700 | 4500 | 01-01-2008 28000 | 4200 | 01-01-2008 + 27700 | 4500 | 01-01-2008 (10 rows) select sum(salary) over (order by enroll_date range between '1 year'::interval preceding and '1 year'::interval following @@ -1603,13 +1603,13 @@ select sum(salary) over (order by enroll_date range between '1 year'::interval p 23900 | 5000 | 10-01-2006 23900 | 6000 | 10-01-2006 34500 | 3900 | 12-23-2006 - 37100 | 4800 | 08-01-2007 37100 | 5200 | 08-01-2007 + 37100 | 4800 | 08-01-2007 42300 | 4800 | 08-08-2007 41900 | 5200 | 08-15-2007 32600 | 3500 | 12-10-2007 - 23500 | 4500 | 01-01-2008 23500 | 4200 | 01-01-2008 + 23500 | 4500 | 01-01-2008 (10 rows) select sum(salary) over (order by enroll_date range between '1 year'::interval preceding and '1 year'::interval following @@ -1619,13 +1619,13 @@ select sum(salary) over (order by enroll_date range between '1 year'::interval p 28900 | 5000 | 10-01-2006 29900 | 6000 | 10-01-2006 38400 | 3900 | 12-23-2006 - 41900 | 4800 | 08-01-2007 42300 | 5200 | 08-01-2007 + 41900 | 4800 | 08-01-2007 47100 | 4800 | 08-08-2007 47100 | 5200 | 08-15-2007 36100 | 3500 | 12-10-2007 - 28000 | 4500 | 01-01-2008 27700 | 4200 | 01-01-2008 + 28000 | 4500 | 01-01-2008 (10 rows) select first_value(salary) over(order by salary range between 1000 preceding and 1000 following), @@ -1710,13 +1710,13 @@ select first_value(salary) over(order by enroll_date range between unbounded pre 5000 | 5200 | 5000 | 10-01-2006 6000 | 5200 | 6000 | 10-01-2006 5000 | 3500 | 3900 | 12-23-2006 - 5000 | 4200 | 4800 | 08-01-2007 - 5000 | 4200 | 5200 | 08-01-2007 - 5000 | 4200 | 4800 | 08-08-2007 - 5000 | 4200 | 5200 | 08-15-2007 - 5000 | 4200 | 3500 | 12-10-2007 - 5000 | 4200 | 4500 | 01-01-2008 - 5000 | 4200 | 4200 | 01-01-2008 + 5000 | 4500 | 5200 | 08-01-2007 + 5000 | 4500 | 4800 | 08-01-2007 + 5000 | 4500 | 4800 | 08-08-2007 + 5000 | 4500 | 5200 | 08-15-2007 + 5000 | 4500 | 3500 | 12-10-2007 + 5000 | 4500 | 4200 | 01-01-2008 + 5000 | 4500 | 4500 | 01-01-2008 (10 rows) select first_value(salary) over(order by enroll_date range between unbounded preceding and '1 year'::interval following @@ -1729,13 +1729,13 @@ select first_value(salary) over(order by enroll_date range between unbounded pre 5000 | 5200 | 5000 | 10-01-2006 6000 | 5200 | 6000 | 10-01-2006 5000 | 3500 | 3900 | 12-23-2006 - 5000 | 4200 | 4800 | 08-01-2007 - 5000 | 4200 | 5200 | 08-01-2007 - 5000 | 4200 | 4800 | 08-08-2007 - 5000 | 4200 | 5200 | 08-15-2007 - 5000 | 4200 | 3500 | 12-10-2007 - 5000 | 4500 | 4500 | 01-01-2008 + 5000 | 4500 | 5200 | 08-01-2007 + 5000 | 4500 | 4800 | 08-01-2007 + 5000 | 4500 | 4800 | 08-08-2007 + 5000 | 4500 | 5200 | 08-15-2007 + 5000 | 4500 | 3500 | 12-10-2007 5000 | 4200 | 4200 | 01-01-2008 + 5000 | 4500 | 4500 | 01-01-2008 (10 rows) select first_value(salary) over(order by enroll_date range between unbounded preceding and '1 year'::interval following @@ -1748,13 +1748,13 @@ select first_value(salary) over(order by enroll_date range between unbounded pre 3900 | 5200 | 5000 | 10-01-2006 3900 | 5200 | 6000 | 10-01-2006 5000 | 3500 | 3900 | 12-23-2006 - 5000 | 4200 | 4800 | 08-01-2007 - 5000 | 4200 | 5200 | 08-01-2007 - 5000 | 4200 | 4800 | 08-08-2007 - 5000 | 4200 | 5200 | 08-15-2007 - 5000 | 4200 | 3500 | 12-10-2007 - 5000 | 3500 | 4500 | 01-01-2008 + 5000 | 4500 | 5200 | 08-01-2007 + 5000 | 4500 | 4800 | 08-01-2007 + 5000 | 4500 | 4800 | 08-08-2007 + 5000 | 4500 | 5200 | 08-15-2007 + 5000 | 4500 | 3500 | 12-10-2007 5000 | 3500 | 4200 | 01-01-2008 + 5000 | 3500 | 4500 | 01-01-2008 (10 rows) select first_value(salary) over(order by enroll_date range between unbounded preceding and '1 year'::interval following @@ -1767,13 +1767,13 @@ select first_value(salary) over(order by enroll_date range between unbounded pre 6000 | 5200 | 5000 | 10-01-2006 5000 | 5200 | 6000 | 10-01-2006 5000 | 3500 | 3900 | 12-23-2006 - 5000 | 4200 | 4800 | 08-01-2007 - 5000 | 4200 | 5200 | 08-01-2007 - 5000 | 4200 | 4800 | 08-08-2007 - 5000 | 4200 | 5200 | 08-15-2007 - 5000 | 4200 | 3500 | 12-10-2007 - 5000 | 4200 | 4500 | 01-01-2008 + 5000 | 4500 | 5200 | 08-01-2007 + 5000 | 4500 | 4800 | 08-01-2007 + 5000 | 4500 | 4800 | 08-08-2007 + 5000 | 4500 | 5200 | 08-15-2007 + 5000 | 4500 | 3500 | 12-10-2007 5000 | 4500 | 4200 | 01-01-2008 + 5000 | 4200 | 4500 | 01-01-2008 (10 rows) -- RANGE offset PRECEDING/FOLLOWING with null values @@ -1828,8 +1828,8 @@ window w as (order by x desc nulls first range between 2 preceding and 2 following); x | y | first_value | last_value ---+----+-------------+------------ - | 43 | 43 | 42 - | 42 | 43 | 42 + | 42 | 42 | 43 + | 43 | 42 | 43 5 | 5 | 5 | 3 4 | 4 | 5 | 2 3 | 3 | 5 | 1 @@ -2751,10 +2751,10 @@ window w as (order by f_timestamptz desc range between 7 | Wed Oct 19 02:23:54 2005 PDT | 8 | 6 6 | Tue Oct 19 02:23:54 2004 PDT | 7 | 5 5 | Sun Oct 19 02:23:54 2003 PDT | 6 | 4 - 4 | Sat Oct 19 02:23:54 2002 PDT | 5 | 2 - 3 | Fri Oct 19 02:23:54 2001 PDT | 4 | 1 + 4 | Sat Oct 19 02:23:54 2002 PDT | 5 | 3 2 | Fri Oct 19 02:23:54 2001 PDT | 4 | 1 - 1 | Thu Oct 19 02:23:54 2000 PDT | 3 | 1 + 3 | Fri Oct 19 02:23:54 2001 PDT | 4 | 1 + 1 | Thu Oct 19 02:23:54 2000 PDT | 2 | 1 0 | -infinity | 0 | 0 (12 rows) @@ -2862,10 +2862,10 @@ window w as (order by f_timestamp desc range between 7 | Wed Oct 19 10:23:54 2005 | 8 | 6 6 | Tue Oct 19 10:23:54 2004 | 7 | 5 5 | Sun Oct 19 10:23:54 2003 | 6 | 4 - 4 | Sat Oct 19 10:23:54 2002 | 5 | 2 - 3 | Fri Oct 19 10:23:54 2001 | 4 | 1 + 4 | Sat Oct 19 10:23:54 2002 | 5 | 3 2 | Fri Oct 19 10:23:54 2001 | 4 | 1 - 1 | Thu Oct 19 10:23:54 2000 | 3 | 1 + 3 | Fri Oct 19 10:23:54 2001 | 4 | 1 + 1 | Thu Oct 19 10:23:54 2000 | 2 | 1 0 | -infinity | 0 | 0 (12 rows) @@ -2983,14 +2983,14 @@ SELECT sum(unique1) over (order by four groups between unbounded preceding and c FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 12 | 0 | 0 - 12 | 8 | 0 12 | 4 | 0 - 27 | 5 | 1 - 27 | 9 | 1 + 12 | 8 | 0 + 12 | 0 | 0 27 | 1 | 1 - 35 | 6 | 2 + 27 | 9 | 1 + 27 | 5 | 1 35 | 2 | 2 + 35 | 6 | 2 45 | 3 | 3 45 | 7 | 3 (10 rows) @@ -3000,14 +3000,14 @@ SELECT sum(unique1) over (order by four groups between unbounded preceding and u FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 45 | 0 | 0 - 45 | 8 | 0 45 | 4 | 0 - 45 | 5 | 1 - 45 | 9 | 1 + 45 | 8 | 0 + 45 | 0 | 0 45 | 1 | 1 - 45 | 6 | 2 + 45 | 9 | 1 + 45 | 5 | 1 45 | 2 | 2 + 45 | 6 | 2 45 | 3 | 3 45 | 7 | 3 (10 rows) @@ -3017,14 +3017,14 @@ SELECT sum(unique1) over (order by four groups between current row and unbounded FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 45 | 0 | 0 - 45 | 8 | 0 45 | 4 | 0 - 33 | 5 | 1 - 33 | 9 | 1 + 45 | 8 | 0 + 45 | 0 | 0 33 | 1 | 1 - 18 | 6 | 2 + 33 | 9 | 1 + 33 | 5 | 1 18 | 2 | 2 + 18 | 6 | 2 10 | 3 | 3 10 | 7 | 3 (10 rows) @@ -3034,14 +3034,14 @@ SELECT sum(unique1) over (order by four groups between 1 preceding and unbounded FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 45 | 0 | 0 - 45 | 8 | 0 45 | 4 | 0 - 45 | 5 | 1 - 45 | 9 | 1 + 45 | 8 | 0 + 45 | 0 | 0 45 | 1 | 1 - 33 | 6 | 2 + 45 | 9 | 1 + 45 | 5 | 1 33 | 2 | 2 + 33 | 6 | 2 18 | 3 | 3 18 | 7 | 3 (10 rows) @@ -3051,14 +3051,14 @@ SELECT sum(unique1) over (order by four groups between 1 following and unbounded FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 33 | 0 | 0 - 33 | 8 | 0 33 | 4 | 0 - 18 | 5 | 1 - 18 | 9 | 1 + 33 | 8 | 0 + 33 | 0 | 0 18 | 1 | 1 - 10 | 6 | 2 + 18 | 9 | 1 + 18 | 5 | 1 10 | 2 | 2 + 10 | 6 | 2 | 3 | 3 | 7 | 3 (10 rows) @@ -3068,14 +3068,14 @@ SELECT sum(unique1) over (order by four groups between unbounded preceding and 2 FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 35 | 0 | 0 - 35 | 8 | 0 35 | 4 | 0 - 45 | 5 | 1 - 45 | 9 | 1 + 35 | 8 | 0 + 35 | 0 | 0 45 | 1 | 1 - 45 | 6 | 2 + 45 | 9 | 1 + 45 | 5 | 1 45 | 2 | 2 + 45 | 6 | 2 45 | 3 | 3 45 | 7 | 3 (10 rows) @@ -3085,14 +3085,14 @@ SELECT sum(unique1) over (order by four groups between 2 preceding and 1 precedi FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - | 0 | 0 - | 8 | 0 | 4 | 0 - 12 | 5 | 1 - 12 | 9 | 1 + | 8 | 0 + | 0 | 0 12 | 1 | 1 - 27 | 6 | 2 + 12 | 9 | 1 + 12 | 5 | 1 27 | 2 | 2 + 27 | 6 | 2 23 | 3 | 3 23 | 7 | 3 (10 rows) @@ -3102,14 +3102,14 @@ SELECT sum(unique1) over (order by four groups between 2 preceding and 1 followi FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 27 | 0 | 0 - 27 | 8 | 0 27 | 4 | 0 - 35 | 5 | 1 - 35 | 9 | 1 + 27 | 8 | 0 + 27 | 0 | 0 35 | 1 | 1 - 45 | 6 | 2 + 35 | 9 | 1 + 35 | 5 | 1 45 | 2 | 2 + 45 | 6 | 2 33 | 3 | 3 33 | 7 | 3 (10 rows) @@ -3119,14 +3119,14 @@ SELECT sum(unique1) over (order by four groups between 0 preceding and 0 followi FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 12 | 0 | 0 - 12 | 8 | 0 12 | 4 | 0 - 15 | 5 | 1 - 15 | 9 | 1 + 12 | 8 | 0 + 12 | 0 | 0 15 | 1 | 1 - 8 | 6 | 2 + 15 | 9 | 1 + 15 | 5 | 1 8 | 2 | 2 + 8 | 6 | 2 10 | 3 | 3 10 | 7 | 3 (10 rows) @@ -3136,14 +3136,14 @@ SELECT sum(unique1) over (order by four groups between 2 preceding and 1 followi FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 27 | 0 | 0 - 19 | 8 | 0 23 | 4 | 0 - 30 | 5 | 1 - 26 | 9 | 1 + 19 | 8 | 0 + 27 | 0 | 0 34 | 1 | 1 - 39 | 6 | 2 + 26 | 9 | 1 + 30 | 5 | 1 43 | 2 | 2 + 39 | 6 | 2 30 | 3 | 3 26 | 7 | 3 (10 rows) @@ -3153,14 +3153,14 @@ SELECT sum(unique1) over (order by four groups between 2 preceding and 1 followi FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 15 | 0 | 0 - 15 | 8 | 0 15 | 4 | 0 - 20 | 5 | 1 - 20 | 9 | 1 + 15 | 8 | 0 + 15 | 0 | 0 20 | 1 | 1 - 37 | 6 | 2 + 20 | 9 | 1 + 20 | 5 | 1 37 | 2 | 2 + 37 | 6 | 2 23 | 3 | 3 23 | 7 | 3 (10 rows) @@ -3170,14 +3170,14 @@ SELECT sum(unique1) over (order by four groups between 2 preceding and 1 followi FROM tenk1 WHERE unique1 < 10; sum | unique1 | four -----+---------+------ - 15 | 0 | 0 - 23 | 8 | 0 19 | 4 | 0 - 25 | 5 | 1 - 29 | 9 | 1 + 23 | 8 | 0 + 15 | 0 | 0 21 | 1 | 1 - 43 | 6 | 2 + 29 | 9 | 1 + 25 | 5 | 1 39 | 2 | 2 + 43 | 6 | 2 26 | 3 | 3 30 | 7 | 3 (10 rows) @@ -3258,14 +3258,14 @@ select first_value(salary) over(order by enroll_date groups between 1 preceding -------------+------+-----------+--------+------------- 5000 | 6000 | 5000 | 5000 | 10-01-2006 5000 | 3900 | 5000 | 6000 | 10-01-2006 - 5000 | 4800 | 5000 | 3900 | 12-23-2006 - 3900 | 5200 | 3900 | 4800 | 08-01-2007 + 5000 | 5200 | 5000 | 3900 | 12-23-2006 3900 | 4800 | 3900 | 5200 | 08-01-2007 - 4800 | 5200 | 4800 | 4800 | 08-08-2007 + 3900 | 4800 | 3900 | 4800 | 08-01-2007 + 5200 | 5200 | 5200 | 4800 | 08-08-2007 4800 | 3500 | 4800 | 5200 | 08-15-2007 - 5200 | 4500 | 5200 | 3500 | 12-10-2007 - 3500 | 4200 | 3500 | 4500 | 01-01-2008 - 3500 | | 3500 | 4200 | 01-01-2008 + 5200 | 4200 | 5200 | 3500 | 12-10-2007 + 3500 | 4500 | 3500 | 4200 | 01-01-2008 + 3500 | | 3500 | 4500 | 01-01-2008 (10 rows) select last_value(salary) over(order by enroll_date groups between 1 preceding and 1 following), @@ -3275,14 +3275,14 @@ select last_value(salary) over(order by enroll_date groups between 1 preceding a ------------+------+--------+------------- 3900 | | 5000 | 10-01-2006 3900 | 5000 | 6000 | 10-01-2006 - 5200 | 6000 | 3900 | 12-23-2006 - 4800 | 3900 | 4800 | 08-01-2007 - 4800 | 4800 | 5200 | 08-01-2007 - 5200 | 5200 | 4800 | 08-08-2007 + 4800 | 6000 | 3900 | 12-23-2006 + 4800 | 3900 | 5200 | 08-01-2007 + 4800 | 5200 | 4800 | 08-01-2007 + 5200 | 4800 | 4800 | 08-08-2007 3500 | 4800 | 5200 | 08-15-2007 - 4200 | 5200 | 3500 | 12-10-2007 - 4200 | 3500 | 4500 | 01-01-2008 - 4200 | 4500 | 4200 | 01-01-2008 + 4500 | 5200 | 3500 | 12-10-2007 + 4500 | 3500 | 4200 | 01-01-2008 + 4500 | 4200 | 4500 | 01-01-2008 (10 rows) select first_value(salary) over(order by enroll_date groups between 1 following and 3 following @@ -3295,14 +3295,14 @@ select first_value(salary) over(order by enroll_date groups between 1 following -------------+------+-----------+--------+------------- 3900 | 6000 | 3900 | 5000 | 10-01-2006 3900 | 3900 | 3900 | 6000 | 10-01-2006 - 4800 | 4800 | 4800 | 3900 | 12-23-2006 - 4800 | 5200 | 4800 | 4800 | 08-01-2007 + 5200 | 5200 | 5200 | 3900 | 12-23-2006 4800 | 4800 | 4800 | 5200 | 08-01-2007 + 4800 | 4800 | 4800 | 4800 | 08-01-2007 5200 | 5200 | 5200 | 4800 | 08-08-2007 3500 | 3500 | 3500 | 5200 | 08-15-2007 - 4500 | 4500 | 4500 | 3500 | 12-10-2007 - | 4200 | | 4500 | 01-01-2008 - | | | 4200 | 01-01-2008 + 4200 | 4200 | 4200 | 3500 | 12-10-2007 + | 4500 | | 4200 | 01-01-2008 + | | | 4500 | 01-01-2008 (10 rows) select last_value(salary) over(order by enroll_date groups between 1 following and 3 following @@ -3314,13 +3314,13 @@ select last_value(salary) over(order by enroll_date groups between 1 following a 4800 | | 5000 | 10-01-2006 4800 | 5000 | 6000 | 10-01-2006 5200 | 6000 | 3900 | 12-23-2006 - 3500 | 3900 | 4800 | 08-01-2007 - 3500 | 4800 | 5200 | 08-01-2007 - 4200 | 5200 | 4800 | 08-08-2007 - 4200 | 4800 | 5200 | 08-15-2007 - 4200 | 5200 | 3500 | 12-10-2007 - | 3500 | 4500 | 01-01-2008 - | 4500 | 4200 | 01-01-2008 + 3500 | 3900 | 5200 | 08-01-2007 + 3500 | 5200 | 4800 | 08-01-2007 + 4500 | 4800 | 4800 | 08-08-2007 + 4500 | 4800 | 5200 | 08-15-2007 + 4500 | 5200 | 3500 | 12-10-2007 + | 3500 | 4200 | 01-01-2008 + | 4200 | 4500 | 01-01-2008 (10 rows) -- Show differences in offset interpretation between ROWS, RANGE, and GROUPS -- 2.51.1
From 0525e6f284779da7f68f35bc415f3da0848ec0df Mon Sep 17 00:00:00 2001 From: John Naylor <[email protected]> Date: Wed, 12 Nov 2025 18:56:29 +0700 Subject: [PATCH v4 3/4] WIP make some regression tests' sort order more deterministic The previous commit still results in failures in the TAP test 002_pg_upgrade.pl, namely that the regression tests fail on the old cluster. XXX it's not clear why only some tests fail this way --- src/test/regress/expected/tsrf.out | 16 +++---- src/test/regress/expected/window.out | 72 ++++++++++++++-------------- src/test/regress/sql/tsrf.sql | 2 +- src/test/regress/sql/window.sql | 20 ++++---- 4 files changed, 55 insertions(+), 55 deletions(-) diff --git a/src/test/regress/expected/tsrf.out b/src/test/regress/expected/tsrf.out index fd3914b0fad..f5647ee561c 100644 --- a/src/test/regress/expected/tsrf.out +++ b/src/test/regress/expected/tsrf.out @@ -397,26 +397,24 @@ SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(d | | 2 | 3 (24 rows) -SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab, g) ORDER BY dataa; +SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab, g) ORDER BY dataa, datab, g; dataa | b | g | count -------+-----+---+------- - a | foo | | 2 - a | | | 4 - a | | 2 | 2 a | bar | 1 | 1 a | bar | 2 | 1 a | bar | | 2 a | foo | 1 | 1 a | foo | 2 | 1 + a | foo | | 2 a | | 1 | 2 + a | | 2 | 2 + a | | | 4 b | bar | 1 | 1 - b | | | 2 - b | | 1 | 1 b | bar | 2 | 1 b | bar | | 2 + b | | 1 | 1 b | | 2 | 1 - | | 2 | 3 - | | | 6 + b | | | 2 | bar | 1 | 2 | bar | 2 | 2 | bar | | 4 @@ -424,6 +422,8 @@ SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(d | foo | 2 | 1 | foo | | 2 | | 1 | 3 + | | 2 | 3 + | | | 6 (24 rows) SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab, g) ORDER BY g; diff --git a/src/test/regress/expected/window.out b/src/test/regress/expected/window.out index b3cdeaea4b3..8a38417e721 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,18 +33,18 @@ 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, empno) FROM empsalary; depname | empno | salary | rank -----------+-------+--------+------ develop | 7 | 4200 | 1 develop | 9 | 4500 | 2 - develop | 11 | 5200 | 3 develop | 10 | 5200 | 3 + develop | 11 | 5200 | 4 develop | 8 | 6000 | 5 personnel | 5 | 3500 | 1 personnel | 2 | 3900 | 2 sales | 3 | 4800 | 1 - sales | 4 | 4800 | 1 + sales | 4 | 4800 | 2 sales | 1 | 5000 | 3 (10 rows) @@ -75,33 +75,33 @@ GROUP BY four, ten ORDER BY four, ten; 3 | 9 | 7500 | 9.0000000000000000 (20 rows) -SELECT depname, empno, salary, sum(salary) OVER w FROM empsalary WINDOW w AS (PARTITION BY depname); +SELECT depname, empno, salary, sum(salary) OVER w FROM empsalary WINDOW w AS (PARTITION BY depname) ORDER BY depname, empno; depname | empno | salary | sum -----------+-------+--------+------- - develop | 11 | 5200 | 25100 develop | 7 | 4200 | 25100 - develop | 9 | 4500 | 25100 develop | 8 | 6000 | 25100 + develop | 9 | 4500 | 25100 develop | 10 | 5200 | 25100 - personnel | 5 | 3500 | 7400 + develop | 11 | 5200 | 25100 personnel | 2 | 3900 | 7400 - sales | 3 | 4800 | 14600 + personnel | 5 | 3500 | 7400 sales | 1 | 5000 | 14600 + sales | 3 | 4800 | 14600 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 | 4 | 4800 | 1 sales | 3 | 4800 | 1 - develop | 9 | 4500 | 2 + sales | 4 | 4800 | 1 + personnel | 5 | 3500 | 1 + develop | 7 | 4200 | 1 personnel | 2 | 3900 | 2 - develop | 11 | 5200 | 3 - develop | 10 | 5200 | 3 + develop | 9 | 4500 | 2 sales | 1 | 5000 | 3 + develop | 10 | 5200 | 3 + develop | 11 | 5200 | 3 develop | 8 | 6000 | 5 (10 rows) @@ -3754,7 +3754,7 @@ FROM empsalary; SELECT empno, depname, - row_number() OVER (PARTITION BY depname ORDER BY enroll_date) rn, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date, empno) rn, rank() OVER (PARTITION BY depname ORDER BY enroll_date ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) rnk, count(*) OVER (PARTITION BY depname ORDER BY enroll_date RANGE BETWEEN @@ -3765,8 +3765,8 @@ FROM empsalary; 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 + 7 | develop | 4 | 4 | 2 + 9 | develop | 5 | 4 | 2 2 | personnel | 1 | 1 | 1 5 | personnel | 2 | 2 | 1 1 | sales | 1 | 1 | 1 @@ -4202,7 +4202,7 @@ SELECT * FROM -- Ensure we correctly filter out all of the run conditions from each window SELECT * FROM - (SELECT *, + (SELECT depname, count(salary) OVER (PARTITION BY depname || '') c1, -- w1 row_number() OVER (PARTITION BY depname) rn, -- w2 count(*) OVER (PARTITION BY depname) c2, -- w2 @@ -4210,10 +4210,10 @@ SELECT * FROM ntile(2) OVER (PARTITION BY depname) nt -- w2 FROM empsalary ) e WHERE rn <= 1 AND c1 <= 3 AND nt < 2; - depname | empno | salary | enroll_date | c1 | rn | c2 | c3 | nt ------------+-------+--------+-------------+----+----+----+----+---- - personnel | 5 | 3500 | 12-10-2007 | 2 | 1 | 2 | 2 | 1 - sales | 3 | 4800 | 08-01-2007 | 3 | 1 | 3 | 3 | 1 + depname | c1 | rn | c2 | c3 | nt +-----------+----+----+----+----+---- + personnel | 2 | 1 | 2 | 2 | 1 + sales | 3 | 1 | 3 | 3 | 1 (2 rows) -- Ensure we remove references to reduced outer joins as nulling rels in run @@ -4498,23 +4498,23 @@ 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; - QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------- + QUERY PLAN +--------------------------------------------------------------------------------------------------------------------------------------------- Subquery Scan on emp Filter: ((emp.first_emp = 1) OR (emp.last_emp = 1)) -> WindowAgg - Window: w2 AS (PARTITION BY empsalary.depname ORDER BY empsalary.enroll_date ROWS UNBOUNDED PRECEDING) + Window: w2 AS (PARTITION BY empsalary.depname ORDER BY empsalary.enroll_date, empsalary.empno ROWS UNBOUNDED PRECEDING) -> Incremental Sort - Sort Key: empsalary.depname, empsalary.enroll_date + Sort Key: empsalary.depname, empsalary.enroll_date, empsalary.empno Presorted Key: empsalary.depname -> WindowAgg - Window: w1 AS (PARTITION BY empsalary.depname ORDER BY empsalary.enroll_date ROWS UNBOUNDED PRECEDING) + Window: w1 AS (PARTITION BY empsalary.depname ORDER BY empsalary.enroll_date, empsalary.empno ROWS UNBOUNDED PRECEDING) -> Sort - Sort Key: empsalary.depname, empsalary.enroll_date DESC + Sort Key: empsalary.depname, empsalary.enroll_date DESC, empsalary.empno -> Seq Scan on empsalary (12 rows) @@ -4523,14 +4523,14 @@ 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; depname | empno | salary | enroll_date | first_emp | last_emp -----------+-------+--------+-------------+-----------+---------- develop | 8 | 6000 | 10-01-2006 | 1 | 5 - develop | 7 | 4200 | 01-01-2008 | 5 | 1 + develop | 7 | 4200 | 01-01-2008 | 4 | 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/tsrf.sql b/src/test/regress/sql/tsrf.sql index 7c22529a0db..af7bd4bdd95 100644 --- a/src/test/regress/sql/tsrf.sql +++ b/src/test/regress/sql/tsrf.sql @@ -96,7 +96,7 @@ SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(d SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab) ORDER BY dataa; SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab) ORDER BY g; SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab, g); -SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab, g) ORDER BY dataa; +SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab, g) ORDER BY dataa, datab, g; SELECT dataa, datab b, generate_series(1,2) g, count(*) FROM few GROUP BY CUBE(dataa, datab, g) ORDER BY g; reset enable_hashagg; diff --git a/src/test/regress/sql/window.sql b/src/test/regress/sql/window.sql index 37d837a2f66..cb28d552fe8 100644 --- a/src/test/regress/sql/window.sql +++ b/src/test/regress/sql/window.sql @@ -21,17 +21,17 @@ 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, empno) FROM empsalary; -- with GROUP BY SELECT four, ten, SUM(SUM(four)) OVER (PARTITION BY four), AVG(ten) FROM tenk1 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, sum(salary) OVER w FROM empsalary WINDOW w AS (PARTITION BY depname) ORDER BY depname, empno; -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; @@ -1145,7 +1145,7 @@ FROM empsalary; SELECT empno, depname, - row_number() OVER (PARTITION BY depname ORDER BY enroll_date) rn, + row_number() OVER (PARTITION BY depname ORDER BY enroll_date, empno) rn, rank() OVER (PARTITION BY depname ORDER BY enroll_date ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) rnk, count(*) OVER (PARTITION BY depname ORDER BY enroll_date RANGE BETWEEN @@ -1366,7 +1366,7 @@ SELECT * FROM -- Ensure we correctly filter out all of the run conditions from each window SELECT * FROM - (SELECT *, + (SELECT depname, count(salary) OVER (PARTITION BY depname || '') c1, -- w1 row_number() OVER (PARTITION BY depname) rn, -- w2 count(*) OVER (PARTITION BY depname) c2, -- w2 @@ -1507,8 +1507,8 @@ 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; @@ -1517,8 +1517,8 @@ 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; -- 2.51.1
From 4564bbf46e40834368975e0cea528d6077437576 Mon Sep 17 00:00:00 2001 From: John Naylor <[email protected]> Date: Fri, 17 Oct 2025 09:57:43 +0700 Subject: [PATCH v4 1/4] Use radix sort when datum1 is an integer type For now this only works for signed and unsigned ints with the usual comparison semantics, the same types for which we previously had separate qsort specializations. Temporary GUC wip_radix_sort for testing --- src/backend/utils/misc/guc_parameters.dat | 7 + src/backend/utils/sort/tuplesort.c | 399 ++++++++++++++++++++-- src/include/utils/guc.h | 1 + src/include/utils/tuplesort.h | 1 + 4 files changed, 389 insertions(+), 19 deletions(-) diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat index 1128167c025..c9167eb4bb4 100644 --- a/src/backend/utils/misc/guc_parameters.dat +++ b/src/backend/utils/misc/guc_parameters.dat @@ -3469,6 +3469,13 @@ max => 'INT_MAX', }, +{ name => 'wip_radix_sort', type => 'bool', context => 'PGC_USERSET', group => 'DEVELOPER_OPTIONS', + short_desc => 'Test radix sort for debugging.', + flags => 'GUC_NOT_IN_SAMPLE', + variable => 'wip_radix_sort', + boot_val => 'true', +}, + { name => 'work_mem', type => 'int', context => 'PGC_USERSET', group => 'RESOURCES_MEM', short_desc => 'Sets the maximum memory to be used for query workspaces.', long_desc => 'This much memory can be used by each internal sort operation and hash table before switching to temporary disk files.', diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index 5d4411dc33f..c2b9625ae88 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -104,6 +104,7 @@ #include "commands/tablespace.h" #include "miscadmin.h" #include "pg_trace.h" +#include "port/pg_bitutils.h" #include "storage/shmem.h" #include "utils/guc.h" #include "utils/memutils.h" @@ -122,6 +123,7 @@ /* GUC variables */ bool trace_sort = false; +bool wip_radix_sort = true; /* FIXME not for commit */ #ifdef DEBUG_BOUNDED_SORT bool optimize_bounded_sort = true; @@ -615,6 +617,25 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state) #define ST_DEFINE #include "lib/sort_template.h" + +#ifdef USE_ASSERT_CHECKING +/* WIP: for now prefer test coverage of radix sort in Assert builds. */ +#define QSORT_THRESHOLD 0 +#else +/* WIP: low because qsort_tuple() is slow -- we could raise this with a new specialization */ +#define QSORT_THRESHOLD 40 +#endif + +typedef struct RadixPartitionInfo +{ + union + { + size_t count; + size_t offset; + }; + size_t next_offset; +} RadixPartitionInfo; + /* * tuplesort_begin_xxx * @@ -2663,10 +2684,334 @@ sort_bounded_heap(Tuplesortstate *state) state->boundUsed = true; } +static inline uint8_t +extract_byte(Datum key, int level) +{ + return (key >> (((SIZEOF_DATUM - 1) - level) * 8)) & 0xFF; +} + +/* + * Normalize datum to work with pure unsigned comparison, + * taking ASC/DESC into account as well. + */ +static inline Datum +normalize_datum(Datum orig, SortSupport ssup) +{ + Datum norm_datum1; + + if (ssup->comparator == ssup_datum_signed_cmp) + { + norm_datum1 = orig + ((uint64) PG_INT64_MAX) + 1; + } + else if (ssup->comparator == ssup_datum_int32_cmp) + { + /* + * First truncate to uint32. Technically, we don't need to do this, + * but it forces the upper bytes to remain the same regardless of + * sign. + */ + uint32 u32 = DatumGetUInt32(orig) + ((uint32) PG_INT32_MAX) + 1; + + norm_datum1 = UInt32GetDatum(u32); + } + else + { + Assert(ssup->comparator == ssup_datum_unsigned_cmp); + norm_datum1 = orig; + } + + if (ssup->ssup_reverse) + norm_datum1 = ~norm_datum1; + + return norm_datum1; +} + +/* + * Based on implementation in https://github.com/skarupke/ska_sort (Boost license), + * with the following noncosmetic change: + * - count sorted partitions in every pass, rather than maintaining a + * list of unsorted partitions + */ +static void +radix_sort_tuple(SortTuple *begin, size_t n_elems, int level, Tuplesortstate *state) +{ + RadixPartitionInfo partitions[256] = {0}; + uint8_t remaining_partitions[256] = {0}; + size_t total = 0; + int num_partitions = 0; + int num_remaining; + SortSupport ssup = &state->base.sortKeys[0]; + size_t start_offset = 0; + SortTuple *partition_begin = begin; + + /* count key chunks */ + for (SortTuple *tup = begin; tup < begin + n_elems; tup++) + { + uint8 current_byte; + + /* extract the byte for this level from the normalized datum */ + current_byte = extract_byte(normalize_datum(tup->datum1, ssup), + level); + + /* save it for the permutation step */ + tup->current_byte = current_byte; + + partitions[current_byte].count++; + } + + /* compute partition offsets */ + for (int i = 0; i < 256; i++) + { + size_t count = partitions[i].count; + + if (count) + { + partitions[i].offset = total; + total += count; + remaining_partitions[num_partitions] = i; + num_partitions++; + } + partitions[i].next_offset = total; + } + + num_remaining = num_partitions; + + /* + * Permute tuples to correct partition. If we started with one partition, + * there is nothing to do. If a permutation from a previous iteration + * results in a single partition that hasn't been marked as sorted, we + * know it's actually sorted. + */ + while (num_remaining > 1) + { + /* + * We can only exit the loop when all partitions are sorted, so must + * reset every iteration + */ + num_remaining = num_partitions; + + for (int i = 0; i < num_partitions; i++) + { + uint8 idx = remaining_partitions[i]; + + RadixPartitionInfo part = partitions[idx]; + + for (SortTuple *st = begin + part.offset; + st < begin + part.next_offset; + st++) + { + size_t offset = partitions[st->current_byte].offset++; + SortTuple tmp; + + /* swap current tuple with destination position */ + Assert(offset < n_elems); + tmp = *st; + *st = begin[offset]; + begin[offset] = tmp; + }; + + if (part.offset == part.next_offset) + { + /* partition is sorted */ + num_remaining--; + } + } + } + + /* recurse */ + for (uint8_t *rp = remaining_partitions; + rp < remaining_partitions + num_partitions; + rp++) + { + size_t end_offset = partitions[*rp].next_offset; + SortTuple *partition_end = begin + end_offset; + ptrdiff_t num_elements = end_offset - start_offset; + + if (num_elements > 1) + { + if (level < SIZEOF_DATUM - 1) + { + if (num_elements < QSORT_THRESHOLD) + { + qsort_tuple(partition_begin, + num_elements, + state->base.comparetup, + state); + } + else + { + radix_sort_tuple(partition_begin, + num_elements, + level + 1, + state); + } + } + else if (state->base.onlyKey == NULL) + { + /* + * We've finished radix sort on all bytes of the pass-by-value + * datum (possibly abbreviated), now qsort with the tiebreak + * comparator. + */ + qsort_tuple(partition_begin, + num_elements, + state->base.comparetup_tiebreak, + state); + } + } + + start_offset = end_offset; + partition_begin = partition_end; + } +} + /* - * Sort all memtuples using specialized qsort() routines. + * Partition tuples by NULL and NOT NULL first sort key. + * Then dispatch to either radix sort or qsort. + */ +static void +sort_byvalue_datum(Tuplesortstate *state) +{ + SortSupportData ssup = state->base.sortKeys[0]; + + bool nulls_first = ssup.ssup_nulls_first; + SortTuple *data = state->memtuples; + SortTuple *null_start; + SortTuple *not_null_start; + size_t d1 = 0, + d2, + null_count, + not_null_count; + + /* + * First, partition by NULL-ness of the leading sort key, since we can + * only radix sort on NOT NULL pass-by-value datums. + */ + + /* + * Find the first NOT NULL tuple if NULLS FIRST, or first NULL element if + * NULLS LAST. This is a quick check for the common case where all tuples + * are NOT NULL in the first sort key. + */ + while (d1 < state->memtupcount && data[d1].isnull1 == nulls_first) + d1++; + + /* + * If we have more than one tuple left after the quick check, partition + * the remainder using branchless cyclic permutation, based on + * https://orlp.net/blog/branchless-lomuto-partitioning/ + */ + if (d1 < state->memtupcount - 1) + { + size_t j = d1; + SortTuple save = data[d1]; /* create gap at front */ + + /* WIP: more comments */ + while (j < state->memtupcount - 1) + { + data[j] = data[d1]; + j += 1; + data[d1] = data[j]; + d1 += (data[d1].isnull1 == nulls_first); + } + + data[j] = data[d1]; + data[d1] = save; + d1 += (data[d1].isnull1 == nulls_first); + } + + /* d1 is now the number of elements in the left partition */ + d2 = state->memtupcount - d1; + + /* set pointers and counts for each partition */ + if (nulls_first) + { + null_start = state->memtuples; + null_count = d1; + not_null_start = state->memtuples + d1; + not_null_count = d2; + } + else + { + not_null_start = state->memtuples; + not_null_count = d1; + null_start = state->memtuples + d1; + null_count = d2; + } + + for (SortTuple *tup = null_start; + tup < null_start + null_count; + tup++) + Assert(tup->isnull1 == true); + for (SortTuple *tup = not_null_start; + tup < not_null_start + not_null_count; + tup++) + Assert(tup->isnull1 == false); + + /* + * Sort the NULL partition using tiebreak comparator, if necessary. XXX + * this will repeat the comparison on isnull1 for abbreviated keys. + */ + if (state->base.onlyKey == NULL && null_count > 1) + { + qsort_tuple(null_start, + null_count, + state->base.comparetup_tiebreak, + state); + } + + /* + * Sort the NOT NULL partition, using radix sort if large enough, + * otherwise fall back to quicksort. + */ + if (not_null_count > 1) + { + if (not_null_count < QSORT_THRESHOLD) + { + /* + * WIP: We could compute the common prefix, save the following + * byte in current_byte, and use a new qsort specialization for + * that. Same for the diversion to qsort while recursing during + * radix sort. + */ + qsort_tuple(not_null_start, + not_null_count, + state->base.comparetup, + state); + } + else + { + radix_sort_tuple(not_null_start, + not_null_count, + 0, + state); + } + } +} + +/* Verify sort using standard comparator. */ +static void +verify_sorted_memtuples(Tuplesortstate *state) +{ +#ifdef USE_ASSERT_CHECKING + for (SortTuple *tup = state->memtuples + 1; + tup < state->memtuples + state->memtupcount; + tup++) + { +#if 0 + Assert(COMPARETUP(state, tup - 1, tup) <= 0); +#else + if (COMPARETUP(state, tup - 1, tup) > 0) + elog(ERROR, "SORT FAILED"); +#endif + } +#endif +} + +/* + * Sort all memtuples using specialized routines. * - * Quicksort is used for small in-memory sorts, and external sort runs. + * Quicksort or radix sort is used for small in-memory sorts, and external sort runs. */ static void tuplesort_sort_memtuples(Tuplesortstate *state) @@ -2681,26 +3026,42 @@ tuplesort_sort_memtuples(Tuplesortstate *state) */ if (state->base.haveDatum1 && state->base.sortKeys) { - if (state->base.sortKeys[0].comparator == ssup_datum_unsigned_cmp) - { - qsort_tuple_unsigned(state->memtuples, - state->memtupcount, - state); - return; - } - else if (state->base.sortKeys[0].comparator == ssup_datum_signed_cmp) + SortSupportData ssup = state->base.sortKeys[0]; + + if (wip_radix_sort) { - qsort_tuple_signed(state->memtuples, - state->memtupcount, - state); - return; + if ((ssup.comparator == ssup_datum_unsigned_cmp || + ssup.comparator == ssup_datum_signed_cmp || + ssup.comparator == ssup_datum_int32_cmp)) + { + sort_byvalue_datum(state); + verify_sorted_memtuples(state); + return; + } } - else if (state->base.sortKeys[0].comparator == ssup_datum_int32_cmp) + else { - qsort_tuple_int32(state->memtuples, - state->memtupcount, - state); - return; + if (state->base.sortKeys[0].comparator == ssup_datum_unsigned_cmp) + { + qsort_tuple_unsigned(state->memtuples, + state->memtupcount, + state); + return; + } + else if (state->base.sortKeys[0].comparator == ssup_datum_signed_cmp) + { + qsort_tuple_signed(state->memtuples, + state->memtupcount, + state); + return; + } + else if (state->base.sortKeys[0].comparator == ssup_datum_int32_cmp) + { + qsort_tuple_int32(state->memtuples, + state->memtupcount, + state); + return; + } } } diff --git a/src/include/utils/guc.h b/src/include/utils/guc.h index f21ec37da89..bc6f7fa60f3 100644 --- a/src/include/utils/guc.h +++ b/src/include/utils/guc.h @@ -324,6 +324,7 @@ extern PGDLLIMPORT int tcp_user_timeout; extern PGDLLIMPORT char *role_string; extern PGDLLIMPORT bool in_hot_standby_guc; extern PGDLLIMPORT bool trace_sort; +extern PGDLLIMPORT bool wip_radix_sort; #ifdef DEBUG_BOUNDED_SORT extern PGDLLIMPORT bool optimize_bounded_sort; diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h index 0bf55902aa1..e40c6e52f81 100644 --- a/src/include/utils/tuplesort.h +++ b/src/include/utils/tuplesort.h @@ -150,6 +150,7 @@ typedef struct void *tuple; /* the tuple itself */ Datum datum1; /* value of first key column */ bool isnull1; /* is first key column NULL? */ + uint8 current_byte; /* chunk of datum1 conditioned for radix sort */ int srctape; /* source tape number */ } SortTuple; -- 2.51.1
