Skip to content

Commit f9aefcb

Browse files
tglsfdctglsfdc
committed
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
1 parent 3501f71 commit f9aefcb

File tree

11 files changed

+351
-92
lines changed

11 files changed

+351
-92
lines changed

‎src/backend/nodes/outfuncs.c

+1
Original file line numberDiff line numberDiff line change
@@ -2129,6 +2129,7 @@ _outIndexOptInfo(StringInfo str, const IndexOptInfo *node)
21292129
/* indexprs is redundant since we print indextlist */
21302130
WRITE_NODE_FIELD(indpred);
21312131
WRITE_NODE_FIELD(indextlist);
2132+
WRITE_NODE_FIELD(indrestrictinfo);
21322133
WRITE_BOOL_FIELD(predOK);
21332134
WRITE_BOOL_FIELD(unique);
21342135
WRITE_BOOL_FIELD(immediate);

‎src/backend/optimizer/path/allpaths.c

+2-2
Original file line numberDiff line numberDiff line change
@@ -474,7 +474,7 @@ set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
474474
* Test any partial indexes of rel for applicability. We must do this
475475
* first since partial unique indexes can affect size estimates.
476476
*/
477-
check_partial_indexes(root, rel);
477+
check_index_predicates(root, rel);
478478

479479
/* Mark rel with estimated output rows, width, etc */
480480
set_baserel_size_estimates(root, rel);
@@ -716,7 +716,7 @@ set_tablesample_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
716716
* Test any partial indexes of rel for applicability. We must do this
717717
* first since partial unique indexes can affect size estimates.
718718
*/
719-
check_partial_indexes(root, rel);
719+
check_index_predicates(root, rel);
720720

721721
/*
722722
* Call the sampling method's estimation function to estimate the number

‎src/backend/optimizer/path/costsize.c

+13-10
Original file line numberDiff line numberDiff line change
@@ -433,23 +433,26 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count)
433433

434434
/*
435435
* Mark the path with the correct row estimate, and identify which quals
436-
* will need to be enforced as qpquals.
436+
* will need to be enforced as qpquals. We need not check any quals that
437+
* are implied by the index's predicate, so we can use indrestrictinfo not
438+
* baserestrictinfo as the list of relevant restriction clauses for the
439+
* rel.
437440
*/
438441
if (path->path.param_info)
439442
{
440443
path->path.rows = path->path.param_info->ppi_rows;
441444
/* qpquals come from the rel's restriction clauses and ppi_clauses */
442445
qpquals = list_concat(
443-
extract_nonindex_conditions(baserel->baserestrictinfo,
444-
path->indexquals),
446+
extract_nonindex_conditions(path->indexinfo->indrestrictinfo,
447+
path->indexquals),
445448
extract_nonindex_conditions(path->path.param_info->ppi_clauses,
446449
path->indexquals));
447450
}
448451
else
449452
{
450453
path->path.rows = baserel->rows;
451454
/* qpquals come from just the rel's restriction clauses */
452-
qpquals = extract_nonindex_conditions(baserel->baserestrictinfo,
455+
qpquals = extract_nonindex_conditions(path->indexinfo->indrestrictinfo,
453456
path->indexquals);
454457
}
455458

@@ -631,11 +634,11 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count)
631634
* final plan. So we approximate it as quals that don't appear directly in
632635
* indexquals and also are not redundant children of the same EquivalenceClass
633636
* as some indexqual. This method neglects some infrequently-relevant
634-
* considerations such as clauses that needn't be checked because they are
635-
* implied by a partial index's predicate. It does not seem worth the cycles
636-
* to try to factor those things in at this stage, even though createplan.c
637-
* will take pains to remove such unnecessary clauses from the qpquals list if
638-
* this path is selected for use.
637+
* considerations, specifically clauses that needn't be checked because they
638+
* are implied by an indexqual. It does not seem worth the cycles to try to
639+
* factor that in at this stage, even though createplan.c will take pains to
640+
* remove such unnecessary clauses from the qpquals list if this path is
641+
* selected for use.
639642
*/
640643
static List *
641644
extract_nonindex_conditions(List *qual_clauses, List *indexquals)
@@ -654,7 +657,7 @@ extract_nonindex_conditions(List *qual_clauses, List *indexquals)
654657
continue; /* simple duplicate */
655658
if (is_redundant_derived_clause(rinfo, indexquals))
656659
continue; /* derived from same EquivalenceClass */
657-
/* ... skip the predicate proof attempts createplan.c will try ... */
660+
/* ... skip the predicate proof attempt createplan.c will try ... */
658661
result = lappend(result, rinfo);
659662
}
660663
return result;

‎src/backend/optimizer/path/indxpath.c

+86-37
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,7 @@
3030
#include "optimizer/pathnode.h"
3131
#include "optimizer/paths.h"
3232
#include "optimizer/predtest.h"
33+
#include "optimizer/prep.h"
3334
#include "optimizer/restrictinfo.h"
3435
#include "optimizer/var.h"
3536
#include "utils/builtins.h"
@@ -216,7 +217,7 @@ static Const *string_to_const(const char *str, Oid datatype);
216217
*
217218
* 'rel' is the relation for which we want to generate index paths
218219
*
219-
* Note: check_partial_indexes() must have been run previously for this rel.
220+
* Note: check_index_predicates() must have been run previously for this rel.
220221
*
221222
* Note: in cases involving LATERAL references in the relation's tlist, it's
222223
* possible that rel->lateral_relids is nonempty. Currently, we include
@@ -1800,25 +1801,27 @@ check_index_only(RelOptInfo *rel, IndexOptInfo *index)
18001801
/*
18011802
* Check that all needed attributes of the relation are available from the
18021803
* index.
1803-
*
1804-
* XXX this is overly conservative for partial indexes, since we will
1805-
* consider attributes involved in the index predicate as required even
1806-
* though the predicate won't need to be checked at runtime. (The same is
1807-
* true for attributes used only in index quals, if we are certain that
1808-
* the index is not lossy.) However, it would be quite expensive to
1809-
* determine that accurately at this point, so for now we take the easy
1810-
* way out.
18111804
*/
18121805

18131806
/*
1814-
* Add all the attributes needed for joins or final output. Note: we must
1815-
* look at rel's targetlist, not the attr_needed data, because attr_needed
1816-
* isn't computed for inheritance child rels.
1807+
* First, identify all the attributes needed for joins or final output.
1808+
* Note: we must look at rel's targetlist, not the attr_needed data,
1809+
* because attr_needed isn't computed for inheritance child rels.
18171810
*/
18181811
pull_varattnos((Node *) rel->reltarget->exprs, rel->relid, &attrs_used);
18191812

1820-
/* Add all the attributes used by restriction clauses. */
1821-
foreach(lc, rel->baserestrictinfo)
1813+
/*
1814+
* Add all the attributes used by restriction clauses; but consider only
1815+
* those clauses not implied by the index predicate, since ones that are
1816+
* so implied don't need to be checked explicitly in the plan.
1817+
*
1818+
* Note: attributes used only in index quals would not be needed at
1819+
* runtime either, if we are certain that the index is not lossy. However
1820+
* it'd be complicated to account for that accurately, and it doesn't
1821+
* matter in most cases, since we'd conclude that such attributes are
1822+
* available from the index anyway.
1823+
*/
1824+
foreach(lc, index->indrestrictinfo)
18221825
{
18231826
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
18241827

@@ -2023,7 +2026,8 @@ static void
20232026
match_restriction_clauses_to_index(RelOptInfo *rel, IndexOptInfo *index,
20242027
IndexClauseSet *clauseset)
20252028
{
2026-
match_clauses_to_index(index, rel->baserestrictinfo, clauseset);
2029+
/* We can ignore clauses that are implied by the index predicate */
2030+
match_clauses_to_index(index, index->indrestrictinfo, clauseset);
20272031
}
20282032

20292033
/*
@@ -2664,39 +2668,48 @@ match_clause_to_ordering_op(IndexOptInfo *index,
26642668
****************************************************************************/
26652669

26662670
/*
2667-
* check_partial_indexes
2668-
* Check each partial index of the relation, and mark it predOK if
2669-
* the index's predicate is satisfied for this query.
2671+
* check_index_predicates
2672+
* Set the predicate-derived IndexOptInfo fields for each index
2673+
* of the specified relation.
2674+
*
2675+
* predOK is set true if the index is partial and its predicate is satisfied
2676+
* for this query, ie the query's WHERE clauses imply the predicate.
26702677
*
2671-
* Note: it is possible for this to get re-run after adding more restrictions
2672-
* to the rel; so we might be able to prove more indexes OK. We assume that
2673-
* adding more restrictions can't make an index not OK.
2678+
* indrestrictinfo is set to the relation's baserestrictinfo list less any
2679+
* conditions that are implied by the index's predicate. (Obviously, for a
2680+
* non-partial index, this is the same as baserestrictinfo.) Such conditions
2681+
* can be dropped from the plan when using the index, in certain cases.
2682+
*
2683+
* At one time it was possible for this to get re-run after adding more
2684+
* restrictions to the rel, thus possibly letting us prove more indexes OK.
2685+
* That doesn't happen any more (at least not in the core code's usage),
2686+
* but this code still supports it in case extensions want to mess with the
2687+
* baserestrictinfo list. We assume that adding more restrictions can't make
2688+
* an index not predOK. We must recompute indrestrictinfo each time, though,
2689+
* to make sure any newly-added restrictions get into it if needed.
26742690
*/
26752691
void
2676-
check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
2692+
check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
26772693
{
26782694
List *clauselist;
26792695
bool have_partial;
2696+
bool is_target_rel;
26802697
Relids otherrels;
26812698
ListCell *lc;
26822699

26832700
/*
2684-
* Frequently, there will be no partial indexes, so first check to make
2685-
* sure there's something useful to do here.
2701+
* Initialize the indrestrictinfo lists to be identical to
2702+
* baserestrictinfo, and check whether there are any partial indexes. If
2703+
* not, this is all we need to do.
26862704
*/
26872705
have_partial = false;
26882706
foreach(lc, rel->indexlist)
26892707
{
26902708
IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
26912709

2692-
if (index->indpred == NIL)
2693-
continue; /* ignore non-partial indexes */
2694-
2695-
if (index->predOK)
2696-
continue; /* don't repeat work if already proven OK */
2697-
2698-
have_partial = true;
2699-
break;
2710+
index->indrestrictinfo = rel->baserestrictinfo;
2711+
if (index->indpred)
2712+
have_partial = true;
27002713
}
27012714
if (!have_partial)
27022715
return;
@@ -2743,18 +2756,54 @@ check_partial_indexes(PlannerInfo *root, RelOptInfo *rel)
27432756
otherrels,
27442757
rel));
27452758

2746-
/* Now try to prove each index predicate true */
2759+
/*
2760+
* Normally we remove quals that are implied by a partial index's
2761+
* predicate from indrestrictinfo, indicating that they need not be
2762+
* checked explicitly by an indexscan plan using this index. However, if
2763+
* the rel is a target relation of UPDATE/DELETE/SELECT FOR UPDATE, we
2764+
* cannot remove such quals from the plan, because they need to be in the
2765+
* plan so that they will be properly rechecked by EvalPlanQual testing.
2766+
* Some day we might want to remove such quals from the main plan anyway
2767+
* and pass them through to EvalPlanQual via a side channel; but for now,
2768+
* we just don't remove implied quals at all for target relations.
2769+
*/
2770+
is_target_rel = (rel->relid == root->parse->resultRelation ||
2771+
get_plan_rowmark(root->rowMarks, rel->relid) != NULL);
2772+
2773+
/*
2774+
* Now try to prove each index predicate true, and compute the
2775+
* indrestrictinfo lists for partial indexes. Note that we compute the
2776+
* indrestrictinfo list even for non-predOK indexes; this might seem
2777+
* wasteful, but we may be able to use such indexes in OR clauses, cf
2778+
* generate_bitmap_or_paths().
2779+
*/
27472780
foreach(lc, rel->indexlist)
27482781
{
27492782
IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
2783+
ListCell *lcr;
27502784

27512785
if (index->indpred == NIL)
2752-
continue; /* ignore non-partial indexes */
2786+
continue; /* ignore non-partial indexes here */
27532787

2754-
if (index->predOK)
2755-
continue; /* don't repeat work if already proven OK */
2788+
if (!index->predOK) /* don't repeat work if already proven OK */
2789+
index->predOK = predicate_implied_by(index->indpred, clauselist);
27562790

2757-
index->predOK = predicate_implied_by(index->indpred, clauselist);
2791+
/* If rel is an update target, leave indrestrictinfo as set above */
2792+
if (is_target_rel)
2793+
continue;
2794+
2795+
/* Else compute indrestrictinfo as the non-implied quals */
2796+
index->indrestrictinfo = NIL;
2797+
foreach(lcr, rel->baserestrictinfo)
2798+
{
2799+
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lcr);
2800+
2801+
/* predicate_implied_by() assumes first arg is immutable */
2802+
if (contain_mutable_functions((Node *) rinfo->clause) ||
2803+
!predicate_implied_by(list_make1(rinfo->clause),
2804+
index->indpred))
2805+
index->indrestrictinfo = lappend(index->indrestrictinfo, rinfo);
2806+
}
27582807
}
27592808
}
27602809

‎src/backend/optimizer/plan/createplan.c

+30-34
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,6 @@
3535
#include "optimizer/planmain.h"
3636
#include "optimizer/planner.h"
3737
#include "optimizer/predtest.h"
38-
#include "optimizer/prep.h"
3938
#include "optimizer/restrictinfo.h"
4039
#include "optimizer/subselect.h"
4140
#include "optimizer/tlist.h"
@@ -494,8 +493,25 @@ create_scan_plan(PlannerInfo *root, Path *best_path, int flags)
494493
* Extract the relevant restriction clauses from the parent relation. The
495494
* executor must apply all these restrictions during the scan, except for
496495
* pseudoconstants which we'll take care of below.
496+
*
497+
* If this is a plain indexscan or index-only scan, we need not consider
498+
* restriction clauses that are implied by the index's predicate, so use
499+
* indrestrictinfo not baserestrictinfo. Note that we can't do that for
500+
* bitmap indexscans, since there's not necessarily a single index
501+
* involved; but it doesn't matter since create_bitmap_scan_plan() will be
502+
* able to get rid of such clauses anyway via predicate proof.
497503
*/
498-
scan_clauses = rel->baserestrictinfo;
504+
switch (best_path->pathtype)
505+
{
506+
case T_IndexScan:
507+
case T_IndexOnlyScan:
508+
Assert(IsA(best_path, IndexPath));
509+
scan_clauses = ((IndexPath *) best_path)->indexinfo->indrestrictinfo;
510+
break;
511+
default:
512+
scan_clauses = rel->baserestrictinfo;
513+
break;
514+
}
499515

500516
/*
501517
* If this is a parameterized scan, we also need to enforce all the join
@@ -2385,11 +2401,6 @@ create_indexscan_plan(PlannerInfo *root,
23852401
* first input contains only immutable functions, so we have to check
23862402
* that.)
23872403
*
2388-
* We can also discard quals that are implied by a partial index's
2389-
* predicate, but only in a plain SELECT; when scanning a target relation
2390-
* of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the
2391-
* plan so that they'll be properly rechecked by EvalPlanQual testing.
2392-
*
23932404
* Note: if you change this bit of code you should also look at
23942405
* extract_nonindex_conditions() in costsize.c.
23952406
*/
@@ -2405,21 +2416,9 @@ create_indexscan_plan(PlannerInfo *root,
24052416
continue; /* simple duplicate */
24062417
if (is_redundant_derived_clause(rinfo, indexquals))
24072418
continue; /* derived from same EquivalenceClass */
2408-
if (!contain_mutable_functions((Node *) rinfo->clause))
2409-
{
2410-
List *clausel = list_make1(rinfo->clause);
2411-
2412-
if (predicate_implied_by(clausel, indexquals))
2413-
continue; /* provably implied by indexquals */
2414-
if (best_path->indexinfo->indpred)
2415-
{
2416-
if (baserelid != root->parse->resultRelation &&
2417-
get_plan_rowmark(root->rowMarks, baserelid) == NULL)
2418-
if (predicate_implied_by(clausel,
2419-
best_path->indexinfo->indpred))
2420-
continue; /* implied by index predicate */
2421-
}
2422-
}
2419+
if (!contain_mutable_functions((Node *) rinfo->clause) &&
2420+
predicate_implied_by(list_make1(rinfo->clause), indexquals))
2421+
continue; /* provably implied by indexquals */
24232422
qpqual = lappend(qpqual, rinfo);
24242423
}
24252424

@@ -2556,11 +2555,12 @@ create_bitmap_scan_plan(PlannerInfo *root,
25562555
* redundant with any top-level indexqual by virtue of being generated
25572556
* from the same EC. After that, try predicate_implied_by().
25582557
*
2559-
* Unlike create_indexscan_plan(), we need take no special thought here
2560-
* for partial index predicates; this is because the predicate conditions
2561-
* are already listed in bitmapqualorig and indexquals. Bitmap scans have
2562-
* to do it that way because predicate conditions need to be rechecked if
2563-
* the scan becomes lossy, so they have to be included in bitmapqualorig.
2558+
* Unlike create_indexscan_plan(), the predicate_implied_by() test here is
2559+
* useful for getting rid of qpquals that are implied by index predicates,
2560+
* because the predicate conditions are included in the "indexquals"
2561+
* returned by create_bitmap_subplan(). Bitmap scans have to do it that
2562+
* way because predicate conditions need to be rechecked if the scan
2563+
* becomes lossy, so they have to be included in bitmapqualorig.
25642564
*/
25652565
qpqual = NIL;
25662566
foreach(l, scan_clauses)
@@ -2575,13 +2575,9 @@ create_bitmap_scan_plan(PlannerInfo *root,
25752575
continue; /* simple duplicate */
25762576
if (rinfo->parent_ec && list_member_ptr(indexECs, rinfo->parent_ec))
25772577
continue; /* derived from same EquivalenceClass */
2578-
if (!contain_mutable_functions(clause))
2579-
{
2580-
List *clausel = list_make1(clause);
2581-
2582-
if (predicate_implied_by(clausel, indexquals))
2583-
continue; /* provably implied by indexquals */
2584-
}
2578+
if (!contain_mutable_functions(clause) &&
2579+
predicate_implied_by(list_make1(clause), indexquals))
2580+
continue; /* provably implied by indexquals */
25852581
qpqual = lappend(qpqual, rinfo);
25862582
}
25872583

‎src/backend/optimizer/util/plancat.c

+2-1
Original file line numberDiff line numberDiff line change
@@ -339,7 +339,8 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
339339
/* Build targetlist using the completed indexprs data */
340340
info->indextlist = build_index_tlist(root, info, relation);
341341

342-
info->predOK = false; /* set later in indxpath.c */
342+
info->indrestrictinfo = NIL; /* set later, in indxpath.c */
343+
info->predOK = false; /* set later, in indxpath.c */
343344
info->unique = index->indisunique;
344345
info->immediate = index->indimmediate;
345346
info->hypothetical = false;

0 commit comments

Comments
 (0)