Support using index-only scans with partial indexes in more cases.

Previously, the planner would reject an index-only scan if any restriction
clause for its table used a column not available from the index, even
if that restriction clause would later be dropped from the plan entirely
because it's implied by the index's predicate.  This is a fairly common
situation for partial indexes because predicates using columns not included
in the index are often the most useful kind of predicate, and we have to
duplicate (or at least imply) the predicate in the WHERE clause in order
to get the index to be considered at all.  So index-only scans were
essentially unavailable with such partial indexes.

To fix, we have to do detection of implied-by-predicate clauses much
earlier in the planner.  This patch puts it in check_index_predicates
(nee check_partial_indexes), meaning it gets done for every partial index,
whereas we previously only considered this issue at createplan time,
so that the work was only done for an index actually selected for use.
That could result in a noticeable planning slowdown for queries against
tables with many partial indexes.  However, testing suggested that there
isn't really a significant cost, especially not with reasonable numbers
of partial indexes.  We do get a small additional benefit, which is that
cost_index is more accurate since it correctly discounts the evaluation
cost of clauses that will be removed.  We can also avoid considering such
clauses as potential indexquals, which saves useless matching cycles in
the case where the predicate columns aren't in the index, and prevents
generating bogus plans that double-count the clause's selectivity when
the columns are in the index.

Tomas Vondra and Kyotaro Horiguchi, reviewed by Kevin Grittner and
Konstantin Knizhnik, and whacked around a little by me

3 files changed, 206 insertions, 6 deletions

diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index 601bdb405aa..3ff669140ff 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -780,7 +780,6 @@ explain (costs off)
                  ->  Index Only Scan Backward using minmaxtest2i on minmaxtest2
                        Index Cond: (f1 IS NOT NULL)
                  ->  Index Only Scan using minmaxtest3i on minmaxtest3
-                       Index Cond: (f1 IS NOT NULL)
    InitPlan 2 (returns $1)
      ->  Limit
            ->  Merge Append
@@ -792,8 +791,7 @@ explain (costs off)
                  ->  Index Only Scan using minmaxtest2i on minmaxtest2 minmaxtest2_1
                        Index Cond: (f1 IS NOT NULL)
                  ->  Index Only Scan Backward using minmaxtest3i on minmaxtest3 minmaxtest3_1
-                       Index Cond: (f1 IS NOT NULL)
-(25 rows)
+(23 rows)
 
 select min(f1), max(f1) from minmaxtest;
  min | max 
@@ -818,7 +816,6 @@ explain (costs off)
                  ->  Index Only Scan Backward using minmaxtest2i on minmaxtest2
                        Index Cond: (f1 IS NOT NULL)
                  ->  Index Only Scan using minmaxtest3i on minmaxtest3
-                       Index Cond: (f1 IS NOT NULL)
    InitPlan 2 (returns $1)
      ->  Limit
            ->  Merge Append
@@ -830,11 +827,10 @@ explain (costs off)
                  ->  Index Only Scan using minmaxtest2i on minmaxtest2 minmaxtest2_1
                        Index Cond: (f1 IS NOT NULL)
                  ->  Index Only Scan Backward using minmaxtest3i on minmaxtest3 minmaxtest3_1
-                       Index Cond: (f1 IS NOT NULL)
    ->  Sort
          Sort Key: ($0), ($1)
          ->  Result
-(28 rows)
+(26 rows)
 
 select distinct min(f1), max(f1) from minmaxtest;
  min | max 
diff --git a/src/test/regress/expected/select.out b/src/test/regress/expected/select.out
index c376523bbe3..f84f8ac767d 100644
--- a/src/test/regress/expected/select.out
+++ b/src/test/regress/expected/select.out
@@ -734,6 +734,166 @@ SELECT * FROM foo ORDER BY f1 DESC NULLS LAST;
 (7 rows)
 
 --
+-- Test planning of some cases with partial indexes
+--
+-- partial index is usable
+explain (costs off)
+select * from onek2 where unique2 = 11 and stringu1 = 'ATAAAA';
+               QUERY PLAN                
+-----------------------------------------
+ Index Scan using onek2_u2_prtl on onek2
+   Index Cond: (unique2 = 11)
+   Filter: (stringu1 = 'ATAAAA'::name)
+(3 rows)
+
+select * from onek2 where unique2 = 11 and stringu1 = 'ATAAAA';
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+     494 |      11 |   0 |    2 |   4 |     14 |       4 |       94 |          94 |       494 |      494 |   8 |    9 | ATAAAA   | LAAAAA   | VVVVxx
+(1 row)
+
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 = 'ATAAAA';
+               QUERY PLAN                
+-----------------------------------------
+ Index Scan using onek2_u2_prtl on onek2
+   Index Cond: (unique2 = 11)
+   Filter: (stringu1 = 'ATAAAA'::name)
+(3 rows)
+
+select unique2 from onek2 where unique2 = 11 and stringu1 = 'ATAAAA';
+ unique2 
+---------
+      11
+(1 row)
+
+-- partial index predicate implies clause, so no need for retest
+explain (costs off)
+select * from onek2 where unique2 = 11 and stringu1 < 'B';
+               QUERY PLAN                
+-----------------------------------------
+ Index Scan using onek2_u2_prtl on onek2
+   Index Cond: (unique2 = 11)
+(2 rows)
+
+select * from onek2 where unique2 = 11 and stringu1 < 'B';
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4 
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+     494 |      11 |   0 |    2 |   4 |     14 |       4 |       94 |          94 |       494 |      494 |   8 |    9 | ATAAAA   | LAAAAA   | VVVVxx
+(1 row)
+
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B';
+                  QUERY PLAN                  
+----------------------------------------------
+ Index Only Scan using onek2_u2_prtl on onek2
+   Index Cond: (unique2 = 11)
+(2 rows)
+
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B';
+ unique2 
+---------
+      11
+(1 row)
+
+-- but if it's an update target, must retest anyway
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B' for update;
+                  QUERY PLAN                   
+-----------------------------------------------
+ LockRows
+   ->  Index Scan using onek2_u2_prtl on onek2
+         Index Cond: (unique2 = 11)
+         Filter: (stringu1 < 'B'::name)
+(4 rows)
+
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B' for update;
+ unique2 
+---------
+      11
+(1 row)
+
+-- partial index is not applicable
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'C';
+                      QUERY PLAN                       
+-------------------------------------------------------
+ Seq Scan on onek2
+   Filter: ((stringu1 < 'C'::name) AND (unique2 = 11))
+(2 rows)
+
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'C';
+ unique2 
+---------
+      11
+(1 row)
+
+-- partial index implies clause, but bitmap scan must recheck predicate anyway
+SET enable_indexscan TO off;
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B';
+                         QUERY PLAN                          
+-------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: ((unique2 = 11) AND (stringu1 < 'B'::name))
+   ->  Bitmap Index Scan on onek2_u2_prtl
+         Index Cond: (unique2 = 11)
+(4 rows)
+
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B';
+ unique2 
+---------
+      11
+(1 row)
+
+RESET enable_indexscan;
+-- check multi-index cases too
+explain (costs off)
+select unique1, unique2 from onek2
+  where (unique2 = 11 or unique1 = 0) and stringu1 < 'B';
+                                   QUERY PLAN                                   
+--------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: (((unique2 = 11) AND (stringu1 < 'B'::name)) OR (unique1 = 0))
+   Filter: (stringu1 < 'B'::name)
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_u2_prtl
+               Index Cond: (unique2 = 11)
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 = 0)
+(8 rows)
+
+select unique1, unique2 from onek2
+  where (unique2 = 11 or unique1 = 0) and stringu1 < 'B';
+ unique1 | unique2 
+---------+---------
+     494 |      11
+       0 |     998
+(2 rows)
+
+explain (costs off)
+select unique1, unique2 from onek2
+  where (unique2 = 11 and stringu1 < 'B') or unique1 = 0;
+                                   QUERY PLAN                                   
+--------------------------------------------------------------------------------
+ Bitmap Heap Scan on onek2
+   Recheck Cond: (((unique2 = 11) AND (stringu1 < 'B'::name)) OR (unique1 = 0))
+   ->  BitmapOr
+         ->  Bitmap Index Scan on onek2_u2_prtl
+               Index Cond: (unique2 = 11)
+         ->  Bitmap Index Scan on onek2_u1_prtl
+               Index Cond: (unique1 = 0)
+(7 rows)
+
+select unique1, unique2 from onek2
+  where (unique2 = 11 and stringu1 < 'B') or unique1 = 0;
+ unique1 | unique2 
+---------+---------
+     494 |      11
+       0 |     998
+(2 rows)
+
+--
 -- Test some corner cases that have been known to confuse the planner
 --
 -- ORDER BY on a constant doesn't really need any sorting
diff --git a/src/test/regress/sql/select.sql b/src/test/regress/sql/select.sql
index b99fb13c7d3..abdd785a770 100644
--- a/src/test/regress/sql/select.sql
+++ b/src/test/regress/sql/select.sql
@@ -188,6 +188,50 @@ SELECT * FROM foo ORDER BY f1 DESC;
 SELECT * FROM foo ORDER BY f1 DESC NULLS LAST;
 
 --
+-- Test planning of some cases with partial indexes
+--
+
+-- partial index is usable
+explain (costs off)
+select * from onek2 where unique2 = 11 and stringu1 = 'ATAAAA';
+select * from onek2 where unique2 = 11 and stringu1 = 'ATAAAA';
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 = 'ATAAAA';
+select unique2 from onek2 where unique2 = 11 and stringu1 = 'ATAAAA';
+-- partial index predicate implies clause, so no need for retest
+explain (costs off)
+select * from onek2 where unique2 = 11 and stringu1 < 'B';
+select * from onek2 where unique2 = 11 and stringu1 < 'B';
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B';
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B';
+-- but if it's an update target, must retest anyway
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B' for update;
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B' for update;
+-- partial index is not applicable
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'C';
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'C';
+-- partial index implies clause, but bitmap scan must recheck predicate anyway
+SET enable_indexscan TO off;
+explain (costs off)
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B';
+select unique2 from onek2 where unique2 = 11 and stringu1 < 'B';
+RESET enable_indexscan;
+-- check multi-index cases too
+explain (costs off)
+select unique1, unique2 from onek2
+  where (unique2 = 11 or unique1 = 0) and stringu1 < 'B';
+select unique1, unique2 from onek2
+  where (unique2 = 11 or unique1 = 0) and stringu1 < 'B';
+explain (costs off)
+select unique1, unique2 from onek2
+  where (unique2 = 11 and stringu1 < 'B') or unique1 = 0;
+select unique1, unique2 from onek2
+  where (unique2 = 11 and stringu1 < 'B') or unique1 = 0;
+
+--
 -- Test some corner cases that have been known to confuse the planner
 --