Fix incorrect step generation in HASH partition pruning

get_steps_using_prefix_recurse() incorrectly assumed that it could stop
recursive processing of the 'prefix' list when cur_keyno was one before
the step_lastkeyno.  Since hash partition pruning can prune using IS
NULL quals, and these IS NULL quals are not present in the 'prefix'
list, then that logic could cause more levels of recursion than what is
needed and lead to there being no more items in the 'prefix' list to
process.  This would manifest itself as a crash in some code that
expected the 'start' ListCell not to be NULL.

Here we adjust the logic so that instead of stopping recursion at 1 key
before the step_lastkeyno, we just look at the llast(prefix) item and
ensure we only recursively process up until just before whichever the last
key is.  This effectively allows keys to be missing in the 'prefix' list.

This change does mean that step_lastkeyno is no longer needed, so we
remove that from the static functions.  I also spent quite some time
reading this code and testing it to try to convince myself that there
are no other issues.  That resulted in the irresistible temptation of
rewriting some comments, many of which were just not true or inconcise.

Reported-by: Sergei Glukhov
Reviewed-by: Sergei Glukhov, tender wang
Discussion: https://postgr.es/m/2f09ce72-315e-2a33-589a-8519ada8df61@postgrespro.ru
Backpatch-through: 11, where partition pruning was introduced.

2 files changed, 256 insertions, 18 deletions

diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 2abf7593858..6452a3b5f5c 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -4016,20 +4016,217 @@ explain (costs off) select * from rp_prefix_test3 where a >= 1 and b >= 1 and b
    Filter: ((a >= 1) AND (b >= 1) AND (d >= 0) AND (b = 2) AND (c = 2))
 (2 rows)
 
-create table hp_prefix_test (a int, b int, c int, d int) partition by hash (a part_test_int4_ops, b part_test_int4_ops, c part_test_int4_ops, d part_test_int4_ops);
-create table hp_prefix_test_p1 partition of hp_prefix_test for values with (modulus 2, remainder 0);
-create table hp_prefix_test_p2 partition of hp_prefix_test for values with (modulus 2, remainder 1);
--- Test that get_steps_using_prefix() handles non-NULL step_nullkeys
-explain (costs off) select * from hp_prefix_test where a = 1 and b is null and c = 1 and d = 1;
-                         QUERY PLAN                          
--------------------------------------------------------------
- Seq Scan on hp_prefix_test_p1 hp_prefix_test
-   Filter: ((b IS NULL) AND (a = 1) AND (c = 1) AND (d = 1))
-(2 rows)
-
 drop table rp_prefix_test1;
 drop table rp_prefix_test2;
 drop table rp_prefix_test3;
+--
+-- Test that get_steps_using_prefix() handles IS NULL clauses correctly
+--
+create table hp_prefix_test (a int, b int, c int, d int)
+  partition by hash (a part_test_int4_ops, b part_test_int4_ops, c part_test_int4_ops, d part_test_int4_ops);
+-- create 8 partitions
+select 'create table hp_prefix_test_p' || x::text || ' partition of hp_prefix_test for values with (modulus 8, remainder ' || x::text || ');'
+from generate_Series(0,7) x;
+                                               ?column?                                               
+------------------------------------------------------------------------------------------------------
+ create table hp_prefix_test_p0 partition of hp_prefix_test for values with (modulus 8, remainder 0);
+ create table hp_prefix_test_p1 partition of hp_prefix_test for values with (modulus 8, remainder 1);
+ create table hp_prefix_test_p2 partition of hp_prefix_test for values with (modulus 8, remainder 2);
+ create table hp_prefix_test_p3 partition of hp_prefix_test for values with (modulus 8, remainder 3);
+ create table hp_prefix_test_p4 partition of hp_prefix_test for values with (modulus 8, remainder 4);
+ create table hp_prefix_test_p5 partition of hp_prefix_test for values with (modulus 8, remainder 5);
+ create table hp_prefix_test_p6 partition of hp_prefix_test for values with (modulus 8, remainder 6);
+ create table hp_prefix_test_p7 partition of hp_prefix_test for values with (modulus 8, remainder 7);
+(8 rows)
+
+\gexec
+create table hp_prefix_test_p0 partition of hp_prefix_test for values with (modulus 8, remainder 0);
+create table hp_prefix_test_p1 partition of hp_prefix_test for values with (modulus 8, remainder 1);
+create table hp_prefix_test_p2 partition of hp_prefix_test for values with (modulus 8, remainder 2);
+create table hp_prefix_test_p3 partition of hp_prefix_test for values with (modulus 8, remainder 3);
+create table hp_prefix_test_p4 partition of hp_prefix_test for values with (modulus 8, remainder 4);
+create table hp_prefix_test_p5 partition of hp_prefix_test for values with (modulus 8, remainder 5);
+create table hp_prefix_test_p6 partition of hp_prefix_test for values with (modulus 8, remainder 6);
+create table hp_prefix_test_p7 partition of hp_prefix_test for values with (modulus 8, remainder 7);
+-- insert 16 rows, one row for each test to perform.
+insert into hp_prefix_test
+select
+  case a when 0 then null else 1 end,
+  case b when 0 then null else 2 end,
+  case c when 0 then null else 3 end,
+  case d when 0 then null else 4 end
+from
+  generate_series(0,1) a,
+  generate_series(0,1) b,
+  generate_Series(0,1) c,
+  generate_Series(0,1) d;
+-- Ensure partition pruning works correctly for each combination of IS NULL
+-- and equality quals.  This may seem a little excessive, but there have been
+-- a number of bugs in this area over the years.  We make use of row only
+-- output to reduce the size of the expected results.
+\t on
+select
+  'explain (costs off) select tableoid::regclass,* from hp_prefix_test where ' ||
+  string_agg(c.colname || case when g.s & (1 << c.colpos) = 0 then ' is null' else ' = ' || (colpos+1)::text end, ' and ' order by c.colpos)
+from (values('a',0),('b',1),('c',2),('d',3)) c(colname, colpos), generate_Series(0,15) g(s)
+group by g.s
+order by g.s;
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c is null and d is null
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c is null and d is null
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c is null and d is null
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c is null and d is null
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c = 3 and d is null
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c = 3 and d is null
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c = 3 and d is null
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c = 3 and d is null
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c is null and d = 4
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c is null and d = 4
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c is null and d = 4
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c is null and d = 4
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c = 3 and d = 4
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c = 3 and d = 4
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c = 3 and d = 4
+ explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c = 3 and d = 4
+
+\gexec
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c is null and d is null
+ Seq Scan on hp_prefix_test_p0 hp_prefix_test
+   Filter: ((a IS NULL) AND (b IS NULL) AND (c IS NULL) AND (d IS NULL))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c is null and d is null
+ Seq Scan on hp_prefix_test_p1 hp_prefix_test
+   Filter: ((b IS NULL) AND (c IS NULL) AND (d IS NULL) AND (a = 1))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c is null and d is null
+ Seq Scan on hp_prefix_test_p2 hp_prefix_test
+   Filter: ((a IS NULL) AND (c IS NULL) AND (d IS NULL) AND (b = 2))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c is null and d is null
+ Seq Scan on hp_prefix_test_p4 hp_prefix_test
+   Filter: ((c IS NULL) AND (d IS NULL) AND (a = 1) AND (b = 2))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c = 3 and d is null
+ Seq Scan on hp_prefix_test_p3 hp_prefix_test
+   Filter: ((a IS NULL) AND (b IS NULL) AND (d IS NULL) AND (c = 3))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c = 3 and d is null
+ Seq Scan on hp_prefix_test_p7 hp_prefix_test
+   Filter: ((b IS NULL) AND (d IS NULL) AND (a = 1) AND (c = 3))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c = 3 and d is null
+ Seq Scan on hp_prefix_test_p4 hp_prefix_test
+   Filter: ((a IS NULL) AND (d IS NULL) AND (b = 2) AND (c = 3))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c = 3 and d is null
+ Seq Scan on hp_prefix_test_p5 hp_prefix_test
+   Filter: ((d IS NULL) AND (a = 1) AND (b = 2) AND (c = 3))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c is null and d = 4
+ Seq Scan on hp_prefix_test_p4 hp_prefix_test
+   Filter: ((a IS NULL) AND (b IS NULL) AND (c IS NULL) AND (d = 4))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c is null and d = 4
+ Seq Scan on hp_prefix_test_p6 hp_prefix_test
+   Filter: ((b IS NULL) AND (c IS NULL) AND (a = 1) AND (d = 4))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c is null and d = 4
+ Seq Scan on hp_prefix_test_p5 hp_prefix_test
+   Filter: ((a IS NULL) AND (c IS NULL) AND (b = 2) AND (d = 4))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c is null and d = 4
+ Seq Scan on hp_prefix_test_p6 hp_prefix_test
+   Filter: ((c IS NULL) AND (a = 1) AND (b = 2) AND (d = 4))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c = 3 and d = 4
+ Seq Scan on hp_prefix_test_p4 hp_prefix_test
+   Filter: ((a IS NULL) AND (b IS NULL) AND (c = 3) AND (d = 4))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c = 3 and d = 4
+ Seq Scan on hp_prefix_test_p5 hp_prefix_test
+   Filter: ((b IS NULL) AND (a = 1) AND (c = 3) AND (d = 4))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c = 3 and d = 4
+ Seq Scan on hp_prefix_test_p6 hp_prefix_test
+   Filter: ((a IS NULL) AND (b = 2) AND (c = 3) AND (d = 4))
+
+explain (costs off) select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c = 3 and d = 4
+ Seq Scan on hp_prefix_test_p4 hp_prefix_test
+   Filter: ((a = 1) AND (b = 2) AND (c = 3) AND (d = 4))
+
+-- And ensure we get exactly 1 row from each. Again, all 16 possible combinations.
+select
+  'select tableoid::regclass,* from hp_prefix_test where ' ||
+  string_agg(c.colname || case when g.s & (1 << c.colpos) = 0 then ' is null' else ' = ' || (colpos+1)::text end, ' and ' order by c.colpos)
+from (values('a',0),('b',1),('c',2),('d',3)) c(colname, colpos), generate_Series(0,15) g(s)
+group by g.s
+order by g.s;
+ select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c is null and d is null
+ select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c is null and d is null
+ select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c is null and d is null
+ select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c is null and d is null
+ select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c = 3 and d is null
+ select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c = 3 and d is null
+ select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c = 3 and d is null
+ select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c = 3 and d is null
+ select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c is null and d = 4
+ select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c is null and d = 4
+ select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c is null and d = 4
+ select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c is null and d = 4
+ select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c = 3 and d = 4
+ select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c = 3 and d = 4
+ select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c = 3 and d = 4
+ select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c = 3 and d = 4
+
+\gexec
+select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c is null and d is null
+ hp_prefix_test_p0 |   |   |   |  
+
+select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c is null and d is null
+ hp_prefix_test_p1 | 1 |   |   |  
+
+select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c is null and d is null
+ hp_prefix_test_p2 |   | 2 |   |  
+
+select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c is null and d is null
+ hp_prefix_test_p4 | 1 | 2 |   |  
+
+select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c = 3 and d is null
+ hp_prefix_test_p3 |   |   | 3 |  
+
+select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c = 3 and d is null
+ hp_prefix_test_p7 | 1 |   | 3 |  
+
+select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c = 3 and d is null
+ hp_prefix_test_p4 |   | 2 | 3 |  
+
+select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c = 3 and d is null
+ hp_prefix_test_p5 | 1 | 2 | 3 |  
+
+select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c is null and d = 4
+ hp_prefix_test_p4 |   |   |   | 4
+
+select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c is null and d = 4
+ hp_prefix_test_p6 | 1 |   |   | 4
+
+select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c is null and d = 4
+ hp_prefix_test_p5 |   | 2 |   | 4
+
+select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c is null and d = 4
+ hp_prefix_test_p6 | 1 | 2 |   | 4
+
+select tableoid::regclass,* from hp_prefix_test where a is null and b is null and c = 3 and d = 4
+ hp_prefix_test_p4 |   |   | 3 | 4
+
+select tableoid::regclass,* from hp_prefix_test where a = 1 and b is null and c = 3 and d = 4
+ hp_prefix_test_p5 | 1 |   | 3 | 4
+
+select tableoid::regclass,* from hp_prefix_test where a is null and b = 2 and c = 3 and d = 4
+ hp_prefix_test_p6 |   | 2 | 3 | 4
+
+select tableoid::regclass,* from hp_prefix_test where a = 1 and b = 2 and c = 3 and d = 4
+ hp_prefix_test_p4 | 1 | 2 | 3 | 4
+
+\t off
 drop table hp_prefix_test;
 --
 -- Check that gen_partprune_steps() detects self-contradiction from clauses
diff --git a/src/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index d1c60b8fe9d..caf50458be9 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -1182,16 +1182,57 @@ explain (costs off) select * from rp_prefix_test3 where a >= 1 and b >= 1 and b
 -- that the caller arranges clauses in that prefix in the required order)
 explain (costs off) select * from rp_prefix_test3 where a >= 1 and b >= 1 and b = 2 and c = 2 and d >= 0;
 
-create table hp_prefix_test (a int, b int, c int, d int) partition by hash (a part_test_int4_ops, b part_test_int4_ops, c part_test_int4_ops, d part_test_int4_ops);
-create table hp_prefix_test_p1 partition of hp_prefix_test for values with (modulus 2, remainder 0);
-create table hp_prefix_test_p2 partition of hp_prefix_test for values with (modulus 2, remainder 1);
-
--- Test that get_steps_using_prefix() handles non-NULL step_nullkeys
-explain (costs off) select * from hp_prefix_test where a = 1 and b is null and c = 1 and d = 1;
-
 drop table rp_prefix_test1;
 drop table rp_prefix_test2;
 drop table rp_prefix_test3;
+
+--
+-- Test that get_steps_using_prefix() handles IS NULL clauses correctly
+--
+create table hp_prefix_test (a int, b int, c int, d int)
+  partition by hash (a part_test_int4_ops, b part_test_int4_ops, c part_test_int4_ops, d part_test_int4_ops);
+
+-- create 8 partitions
+select 'create table hp_prefix_test_p' || x::text || ' partition of hp_prefix_test for values with (modulus 8, remainder ' || x::text || ');'
+from generate_Series(0,7) x;
+\gexec
+
+-- insert 16 rows, one row for each test to perform.
+insert into hp_prefix_test
+select
+  case a when 0 then null else 1 end,
+  case b when 0 then null else 2 end,
+  case c when 0 then null else 3 end,
+  case d when 0 then null else 4 end
+from
+  generate_series(0,1) a,
+  generate_series(0,1) b,
+  generate_Series(0,1) c,
+  generate_Series(0,1) d;
+
+-- Ensure partition pruning works correctly for each combination of IS NULL
+-- and equality quals.  This may seem a little excessive, but there have been
+-- a number of bugs in this area over the years.  We make use of row only
+-- output to reduce the size of the expected results.
+\t on
+select
+  'explain (costs off) select tableoid::regclass,* from hp_prefix_test where ' ||
+  string_agg(c.colname || case when g.s & (1 << c.colpos) = 0 then ' is null' else ' = ' || (colpos+1)::text end, ' and ' order by c.colpos)
+from (values('a',0),('b',1),('c',2),('d',3)) c(colname, colpos), generate_Series(0,15) g(s)
+group by g.s
+order by g.s;
+\gexec
+
+-- And ensure we get exactly 1 row from each. Again, all 16 possible combinations.
+select
+  'select tableoid::regclass,* from hp_prefix_test where ' ||
+  string_agg(c.colname || case when g.s & (1 << c.colpos) = 0 then ' is null' else ' = ' || (colpos+1)::text end, ' and ' order by c.colpos)
+from (values('a',0),('b',1),('c',2),('d',3)) c(colname, colpos), generate_Series(0,15) g(s)
+group by g.s
+order by g.s;
+\gexec
+\t off
+
 drop table hp_prefix_test;
 
 --