Hi,
I took a stab at this and implemented the trick with the VM - during
index scan, we also extract the filters that only need the indexed
attributes (just like in IOS). And then, during the execution we:
1) scan the index using the scan keys (as before)
2) if the heap page is all-visible, we check the new filters that can
be evaluated on the index tuple
3) fetch the heap tuple and evaluate the filters
This is pretty much exactly the same thing we do for IOS, so I don't see
why this would be incorrect while IOS is correct.
This also adds "Index Filter" to explain output, to show which filters
are executed on the index tuple (at the moment the filters are a subset
of "Filter"), so if the index tuple matches we'll execute them again on
the heap tuple. I guess that could be fixed by having two "filter"
lists, depending on whether we were able to evaluate the index filters.
Most of the patch is pretty mechanical - particularly the planning part
is about identifying filters that can be evaluated on the index tuple,
and that code was mostly shamelessly copied from index-only scan.
The matching of filters to index is done in check_index_filter(), and
it's simpler than match_clause_to_indexcol() as it does not need to
consider operators etc. (I think). But maybe it should be careful about
other things, not sure.
The actual magic happens in IndexNext (nodeIndexscan.c). As mentioned
earlier, the idea is to check VM and evaluate the filters on the index
tuple if possible, similar to index-only scans. Except that we then have
to fetch the heap tuple. Unfortunately, this means the code can't use
index_getnext_slot() anymore. Perhaps we should invent a new variant
that'd allow evaluating the index filters in between.
With the patch applied, the query plan changes from:
QUERY PLAN
-------------------------------------------------------------------
Limit (cost=0.42..10929.89 rows=1 width=12)
(actual time=94.649..94.653 rows=0 loops=1)
Buffers: shared hit=197575 read=661
-> Index Scan using t_a_include_b on t
(cost=0.42..10929.89 rows=1 width=12)
(actual time=94.646..94.647 rows=0 loops=1)
Index Cond: (a > 1000000)
Filter: (b = 4)
Rows Removed by Filter: 197780
Buffers: shared hit=197575 read=661
Planning Time: 0.091 ms
Execution Time: 94.674 ms
(9 rows)
to
QUERY PLAN
-------------------------------------------------------------------
Limit (cost=0.42..3662.15 rows=1 width=12)
(actual time=13.663..13.667 rows=0 loops=1)
Buffers: shared hit=544
-> Index Scan using t_a_include_b on t
(cost=0.42..3662.15 rows=1 width=12)
(actual time=13.659..13.660 rows=0 loops=1)
Index Cond: (a > 1000000)
Index Filter: (b = 4)
Rows Removed by Index Recheck: 197780
Filter: (b = 4)
Buffers: shared hit=544
Planning Time: 0.105 ms
Execution Time: 13.690 ms
(10 rows)
which is much closer to the "best" case:
QUERY PLAN
-------------------------------------------------------------------
Limit (cost=0.42..4155.90 rows=1 width=12)
(actual time=10.152..10.156 rows=0 loops=1)
Buffers: shared read=543
-> Index Scan using t_a_b_idx on t
(cost=0.42..4155.90 rows=1 width=12)
(actual time=10.148..10.150 rows=0 loops=1)
Index Cond: ((a > 1000000) AND (b = 4))
Buffers: shared read=543
Planning Time: 0.089 ms
Execution Time: 10.176 ms
(7 rows)
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL CompanyFrom b372bb44b18038fa0c57ea6289a1e629fa029241 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.von...@postgresql.org>
Date: Sun, 9 Apr 2023 02:08:45 +0200
Subject: [PATCH] evaluate filters on the index tuple (when possible)
Discussion: https://www.postgresql.org/message-id/flat/N1xaIrU29uk5YxLyW55MGk5fz9s6V2FNtj54JRaVlFbPixD5z8sJ07Ite5CvbWwik8ZvDG07oSTN-usENLVMq2UAcizVTEd5b-o16ZGDIIU%3D%40yamlcoder.me
---
src/backend/commands/explain.c | 2 +
src/backend/executor/nodeIndexscan.c | 190 +++++++++++++++++++++++-
src/backend/optimizer/path/costsize.c | 23 +++
src/backend/optimizer/path/indxpath.c | 187 ++++++++++++++++++++---
src/backend/optimizer/plan/createplan.c | 139 +++++++++++++++++
src/backend/optimizer/plan/planner.c | 2 +-
src/backend/optimizer/plan/setrefs.c | 6 +
src/backend/optimizer/util/pathnode.c | 2 +
src/backend/utils/misc/guc_tables.c | 10 ++
src/include/nodes/execnodes.h | 6 +
src/include/nodes/pathnodes.h | 1 +
src/include/nodes/plannodes.h | 2 +
src/include/optimizer/cost.h | 1 +
src/include/optimizer/pathnode.h | 1 +
14 files changed, 547 insertions(+), 25 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 15f9bddcdf3..a77076542e0 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -1778,6 +1778,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
case T_IndexScan:
show_scan_qual(((IndexScan *) plan)->indexqualorig,
"Index Cond", planstate, ancestors, es);
+ show_scan_qual(((IndexScan *) plan)->indexfiltersorig,
+ "Index Filter", planstate, ancestors, es);
if (((IndexScan *) plan)->indexqualorig)
show_instrumentation_count("Rows Removed by Index Recheck", 2,
planstate, es);
diff --git a/src/backend/executor/nodeIndexscan.c b/src/backend/executor/nodeIndexscan.c
index 4540c7781d2..c8385aea4bc 100644
--- a/src/backend/executor/nodeIndexscan.c
+++ b/src/backend/executor/nodeIndexscan.c
@@ -32,6 +32,7 @@
#include "access/nbtree.h"
#include "access/relscan.h"
#include "access/tableam.h"
+#include "access/visibilitymap.h"
#include "catalog/pg_am.h"
#include "executor/execdebug.h"
#include "executor/nodeIndexscan.h"
@@ -70,6 +71,10 @@ static void reorderqueue_push(IndexScanState *node, TupleTableSlot *slot,
static HeapTuple reorderqueue_pop(IndexScanState *node);
+static void StoreIndexTuple(TupleTableSlot *slot, IndexTuple itup,
+ TupleDesc itupdesc);
+
+
/* ----------------------------------------------------------------
* IndexNext
*
@@ -115,6 +120,13 @@ IndexNext(IndexScanState *node)
node->iss_ScanDesc = scandesc;
+ /* Set it up for index-only scan */
+ if (node->indexfilters != NULL)
+ {
+ node->iss_ScanDesc->xs_want_itup = true;
+ node->iss_VMBuffer = InvalidBuffer;
+ }
+
/*
* If no run-time keys to calculate or they are ready, go ahead and
* pass the scankeys to the index AM.
@@ -127,11 +139,138 @@ IndexNext(IndexScanState *node)
/*
* ok, now that we have what we need, fetch the next tuple.
+ *
+ * XXX maybe we should invent something like index_getnext_tid/index_getnext_slot
+ * that would allow doing this in a more readable / coherent way.
*/
- while (index_getnext_slot(scandesc, direction, slot))
+ while (true)
{
+ bool has_index_tuple = false;
+ bool filter_checked;
+ ItemPointer tid;
+
CHECK_FOR_INTERRUPTS();
+ /*
+ * XXX code from index_getnext_slot(), but we need to inject stuff between
+ * the index_getnext_tid() and index_fetch_heap(), so we do it here
+ */
+ for (;;)
+ {
+ filter_checked = false;
+
+ if (!scandesc->xs_heap_continue)
+ {
+ /* Time to fetch the next TID from the index */
+ tid = index_getnext_tid(scandesc, direction);
+
+ /* If we're out of index entries, we're done */
+ if (tid == NULL)
+ break;
+
+ Assert(ItemPointerEquals(tid, &scandesc->xs_heaptid));
+ }
+
+ /*
+ * If there are index clauses, try to evaluate the filter on the index
+ * tuple first, and only when it fails try the index tuple.
+ *
+ * https://www.postgresql.org/message-id/N1xaIrU29uk5YxLyW55MGk5fz9s6V2FNtj54JRaVlFbPixD5z8sJ07Ite5CvbWwik8ZvDG07oSTN-usENLVMq2UAcizVTEd5b-o16ZGDIIU%3D%40yamlcoder.me
+ */
+ if (node->indexfilters != NULL)
+ {
+ /*
+ * XXX see nodeIndexonlyscan.c, but inverse - we only do this when
+ * we can check some filters on the index tuple.
+ */
+ if (VM_ALL_VISIBLE(scandesc->heapRelation,
+ ItemPointerGetBlockNumber(tid),
+ &node->iss_VMBuffer))
+ {
+ /*
+ * Only MVCC snapshots are supported here, so there should be no
+ * need to keep following the HOT chain once a visible entry has
+ * been found. If we did want to allow that, we'd need to keep
+ * more state to remember not to call index_getnext_tid next time.
+ *
+ * XXX Is there a place where we can decide whether to consider
+ * this optimization, based on which type of snapshot we're going
+ * to use? And disable it for non-MVCC ones? That'd mean this
+ * error can't really happen here. Or how can we even get this
+ * error now?
+ */
+ if (scandesc->xs_heap_continue)
+ elog(ERROR, "non-MVCC snapshots are not supported with index filters");
+
+ /*
+ * Fill the scan tuple slot with data from the index. This might be
+ * provided in either HeapTuple or IndexTuple format. Conceivably an
+ * index AM might fill both fields, in which case we prefer the heap
+ * format, since it's probably a bit cheaper to fill a slot from.
+ */
+ if (scandesc->xs_hitup)
+ {
+ /*
+ * We don't take the trouble to verify that the provided tuple has
+ * exactly the slot's format, but it seems worth doing a quick
+ * check on the number of fields.
+ */
+ Assert(slot->tts_tupleDescriptor->natts ==
+ scandesc->xs_hitupdesc->natts);
+ ExecForceStoreHeapTuple(scandesc->xs_hitup, slot, false);
+ }
+ else if (scandesc->xs_itup)
+ StoreIndexTuple(node->iss_IndexSlot, scandesc->xs_itup,
+ scandesc->xs_itupdesc);
+ else
+ elog(ERROR, "no data returned for index-only scan");
+
+ /* run the expressions */
+ econtext->ecxt_scantuple = node->iss_IndexSlot;
+
+ /* check the filters pushed to the index-tuple level */
+ if (!ExecQual(node->indexfilters, econtext))
+ {
+ InstrCountFiltered2(node, 1);
+ continue;
+ }
+
+ /* remember we already checked the filter */
+ filter_checked = true;
+ }
+ }
+
+ /*
+ * Fetch the next (or only) visible heap tuple for this index entry.
+ * If we don't find anything, loop around and grab the next TID from
+ * the index.
+ */
+ Assert(ItemPointerIsValid(&scandesc->xs_heaptid));
+ if (index_fetch_heap(scandesc, slot))
+ {
+ has_index_tuple = true;
+ break;
+ }
+ }
+
+ if (!has_index_tuple)
+ break;
+
+ /*
+ * If we didn't manage to check the filter on the index tuple (because
+ * of the page not being all-visible, etc.), do that now on the heap
+ * tuple.
+ */
+ if (!filter_checked)
+ {
+ econtext->ecxt_scantuple = slot;
+ if (!ExecQual(node->indexfiltersorig, econtext))
+ {
+ InstrCountFiltered2(node, 1);
+ continue;
+ }
+ }
+
/*
* If the index was lossy, we have to recheck the index quals using
* the fetched tuple.
@@ -794,6 +933,16 @@ ExecEndIndexScan(IndexScanState *node)
indexRelationDesc = node->iss_RelationDesc;
indexScanDesc = node->iss_ScanDesc;
+ /* Release VM buffer pin, if any. */
+ if (node->iss_VMBuffer != InvalidBuffer)
+ {
+ ReleaseBuffer(node->iss_VMBuffer);
+ node->iss_VMBuffer = InvalidBuffer;
+ }
+
+ if (node->iss_IndexSlot != NULL)
+ ExecDropSingleTupleTableSlot(node->iss_IndexSlot);
+
/*
* Free the exprcontext(s) ... now dead code, see ExecFreeExprContext
*/
@@ -956,6 +1105,10 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
ExecInitQual(node->scan.plan.qual, (PlanState *) indexstate);
indexstate->indexqualorig =
ExecInitQual(node->indexqualorig, (PlanState *) indexstate);
+ indexstate->indexfilters =
+ ExecInitQual(node->indexfilters, (PlanState *) indexstate);
+ indexstate->indexfiltersorig =
+ ExecInitQual(node->indexfiltersorig, (PlanState *) indexstate);
indexstate->indexorderbyorig =
ExecInitExprList(node->indexorderbyorig, (PlanState *) indexstate);
@@ -971,6 +1124,10 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
lockmode = exec_rt_fetch(node->scan.scanrelid, estate)->rellockmode;
indexstate->iss_RelationDesc = index_open(node->indexid, lockmode);
+ indexstate->iss_IndexSlot
+ = MakeSingleTupleTableSlot(RelationGetDescr(indexstate->iss_RelationDesc),
+ &TTSOpsVirtual);
+
/*
* Initialize index-specific scan state
*/
@@ -992,6 +1149,13 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
NULL, /* no ArrayKeys */
NULL);
+ /*
+ * build the index filter from the index qualification
+ *
+ * XXX We probably don't need to build scan keys for filter clauses. Or
+ * should we have something like ExecIndexBuildScanKeys()?
+ */
+
/*
* any ORDER BY exprs have to be turned into scankeys in the same way
*/
@@ -1744,3 +1908,27 @@ ExecIndexScanInitializeWorker(IndexScanState *node,
node->iss_ScanKeys, node->iss_NumScanKeys,
node->iss_OrderByKeys, node->iss_NumOrderByKeys);
}
+
+/*
+ * StoreIndexTuple
+ * Fill the slot with data from the index tuple.
+ *
+ * At some point this might be generally-useful functionality, but
+ * right now we don't need it elsewhere.
+ */
+static void
+StoreIndexTuple(TupleTableSlot *slot, IndexTuple itup, TupleDesc itupdesc)
+{
+ /*
+ * Note: we must use the tupdesc supplied by the AM in index_deform_tuple,
+ * not the slot's tupdesc, in case the latter has different datatypes
+ * (this happens for btree name_ops in particular). They'd better have
+ * the same number of columns though, as well as being datatype-compatible
+ * which is something we can't so easily check.
+ */
+ Assert(slot->tts_tupleDescriptor->natts == itupdesc->natts);
+
+ ExecClearTuple(slot);
+ index_deform_tuple(itup, itupdesc, slot->tts_values, slot->tts_isnull);
+ ExecStoreVirtualTuple(slot);
+}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index ef475d95a18..ef4be8d6bb3 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -135,6 +135,7 @@ int max_parallel_workers_per_gather = 2;
bool enable_seqscan = true;
bool enable_indexscan = true;
bool enable_indexonlyscan = true;
+bool enable_indexonlyfilter = true;
bool enable_bitmapscan = true;
bool enable_tidscan = true;
bool enable_sort = true;
@@ -607,6 +608,28 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count,
/* estimate number of main-table tuples fetched */
tuples_fetched = clamp_row_est(indexSelectivity * baserel->tuples);
+ /*
+ * If some filters can be evaluated on the index tuple, account for that.
+ * We need to scan all tuples from pages that are not all-visible, and
+ * for the remaining tuples we fetch those not eliminated by the filter.
+ *
+ * XXX Does this need to worry about path->path.param_info?
+ *
+ * XXX All of this seems overly manual / ad-hoc, surely there's a place
+ * where we already do this in a more elegant manner?
+ */
+ if (path->indexfilters != NIL)
+ {
+ Selectivity sel;
+
+ sel = clauselist_selectivity(root, path->indexfilters, baserel->relid,
+ JOIN_INNER, NULL);
+
+ tuples_fetched *= (1.0 - baserel->allvisfrac) + (baserel->allvisfrac) * sel;
+
+ tuples_fetched = clamp_row_est(tuples_fetched);
+ }
+
/* fetch estimated page costs for tablespace containing table */
get_tablespace_page_costs(baserel->reltablespace,
&spc_random_page_cost,
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 1436dbc2f2f..9d0e00122bd 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -101,9 +101,11 @@ static bool eclass_already_used(EquivalenceClass *parent_ec, Relids oldrelids,
List *indexjoinclauses);
static void get_index_paths(PlannerInfo *root, RelOptInfo *rel,
IndexOptInfo *index, IndexClauseSet *clauses,
- List **bitindexpaths);
+ List *filters, List **bitindexpaths);
static List *build_index_paths(PlannerInfo *root, RelOptInfo *rel,
- IndexOptInfo *index, IndexClauseSet *clauses,
+ IndexOptInfo *index,
+ IndexClauseSet *clauses,
+ List *filters,
bool useful_predicate,
ScanTypeControl scantype,
bool *skip_nonnative_saop,
@@ -124,6 +126,7 @@ static PathClauseUsage *classify_index_clause_usage(Path *path,
static void find_indexpath_quals(Path *bitmapqual, List **quals, List **preds);
static int find_list_position(Node *node, List **nodelist);
static bool check_index_only(RelOptInfo *rel, IndexOptInfo *index);
+static bool check_index_filter(RelOptInfo *rel, IndexOptInfo *index, Node *clause);
static double get_loop_count(PlannerInfo *root, Index cur_relid, Relids outer_relids);
static double adjust_rowcount_for_semijoins(PlannerInfo *root,
Index cur_relid,
@@ -132,7 +135,8 @@ static double adjust_rowcount_for_semijoins(PlannerInfo *root,
static double approximate_joinrel_size(PlannerInfo *root, Relids relids);
static void match_restriction_clauses_to_index(PlannerInfo *root,
IndexOptInfo *index,
- IndexClauseSet *clauseset);
+ IndexClauseSet *clauseset,
+ List **filters);
static void match_join_clauses_to_index(PlannerInfo *root,
RelOptInfo *rel, IndexOptInfo *index,
IndexClauseSet *clauseset,
@@ -143,15 +147,20 @@ static void match_eclass_clauses_to_index(PlannerInfo *root,
static void match_clauses_to_index(PlannerInfo *root,
List *clauses,
IndexOptInfo *index,
- IndexClauseSet *clauseset);
+ IndexClauseSet *clauseset,
+ List **filters);
static void match_clause_to_index(PlannerInfo *root,
RestrictInfo *rinfo,
IndexOptInfo *index,
- IndexClauseSet *clauseset);
+ IndexClauseSet *clauseset,
+ List **filters);
static IndexClause *match_clause_to_indexcol(PlannerInfo *root,
RestrictInfo *rinfo,
int indexcol,
IndexOptInfo *index);
+static RestrictInfo *match_filter_to_index(PlannerInfo *root,
+ RestrictInfo *rinfo,
+ IndexOptInfo *index);
static bool IsBooleanOpfamily(Oid opfamily);
static IndexClause *match_boolean_index_clause(PlannerInfo *root,
RestrictInfo *rinfo,
@@ -241,6 +250,7 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
IndexClauseSet rclauseset;
IndexClauseSet jclauseset;
IndexClauseSet eclauseset;
+ List *rfilters;
ListCell *lc;
/* Skip the whole mess if no indexes */
@@ -270,14 +280,15 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
* Identify the restriction clauses that can match the index.
*/
MemSet(&rclauseset, 0, sizeof(rclauseset));
- match_restriction_clauses_to_index(root, index, &rclauseset);
+ rfilters = NIL;
+ match_restriction_clauses_to_index(root, index, &rclauseset, &rfilters);
/*
* Build index paths from the restriction clauses. These will be
* non-parameterized paths. Plain paths go directly to add_path(),
* bitmap paths are added to bitindexpaths to be handled below.
*/
- get_index_paths(root, rel, index, &rclauseset,
+ get_index_paths(root, rel, index, &rclauseset, rfilters,
&bitindexpaths);
/*
@@ -301,6 +312,8 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
/*
* If we found any plain or eclass join clauses, build parameterized
* index paths using them.
+ *
+ * XXX Maybe pass the filters too?
*/
if (jclauseset.nonempty || eclauseset.nonempty)
consider_index_join_clauses(root, rel, index,
@@ -662,7 +675,7 @@ get_join_index_paths(PlannerInfo *root, RelOptInfo *rel,
Assert(clauseset.nonempty);
/* Build index path(s) using the collected set of clauses */
- get_index_paths(root, rel, index, &clauseset, bitindexpaths);
+ get_index_paths(root, rel, index, &clauseset, NULL, bitindexpaths);
/*
* Remember we considered paths for this set of relids.
@@ -712,7 +725,7 @@ eclass_already_used(EquivalenceClass *parent_ec, Relids oldrelids,
static void
get_index_paths(PlannerInfo *root, RelOptInfo *rel,
IndexOptInfo *index, IndexClauseSet *clauses,
- List **bitindexpaths)
+ List *filters, List **bitindexpaths)
{
List *indexpaths;
bool skip_nonnative_saop = false;
@@ -726,7 +739,7 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
* paths if possible).
*/
indexpaths = build_index_paths(root, rel,
- index, clauses,
+ index, clauses, filters,
index->predOK,
ST_ANYSCAN,
&skip_nonnative_saop,
@@ -741,7 +754,7 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
{
indexpaths = list_concat(indexpaths,
build_index_paths(root, rel,
- index, clauses,
+ index, clauses, filters,
index->predOK,
ST_ANYSCAN,
&skip_nonnative_saop,
@@ -781,7 +794,7 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
if (skip_nonnative_saop)
{
indexpaths = build_index_paths(root, rel,
- index, clauses,
+ index, clauses, filters,
false,
ST_BITMAPSCAN,
NULL,
@@ -833,7 +846,9 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
*/
static List *
build_index_paths(PlannerInfo *root, RelOptInfo *rel,
- IndexOptInfo *index, IndexClauseSet *clauses,
+ IndexOptInfo *index,
+ IndexClauseSet *clauses,
+ List *filters,
bool useful_predicate,
ScanTypeControl scantype,
bool *skip_nonnative_saop,
@@ -842,6 +857,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
List *result = NIL;
IndexPath *ipath;
List *index_clauses;
+ List *index_filters;
Relids outer_relids;
double loop_count;
List *orderbyclauses;
@@ -947,6 +963,23 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
return NIL;
}
+ index_filters = NIL;
+
+ if (filters)
+ {
+ ListCell *lc;
+
+ foreach(lc, filters)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+ /* OK to include this clause (as a filter) */
+ index_filters = lappend(index_filters, rinfo);
+ outer_relids = bms_add_members(outer_relids,
+ rinfo->clause_relids);
+ }
+ }
+
/* We do not want the index's rel itself listed in outer_relids */
outer_relids = bms_del_member(outer_relids, rel->relid);
@@ -1009,6 +1042,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
{
ipath = create_index_path(root, index,
index_clauses,
+ index_filters,
orderbyclauses,
orderbyclausecols,
useful_pathkeys,
@@ -1029,6 +1063,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
{
ipath = create_index_path(root, index,
index_clauses,
+ index_filters,
orderbyclauses,
orderbyclausecols,
useful_pathkeys,
@@ -1062,6 +1097,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
{
ipath = create_index_path(root, index,
index_clauses,
+ index_filters,
NIL,
NIL,
useful_pathkeys,
@@ -1079,6 +1115,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
{
ipath = create_index_path(root, index,
index_clauses,
+ index_filters,
NIL,
NIL,
useful_pathkeys,
@@ -1141,6 +1178,7 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
{
IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
IndexClauseSet clauseset;
+ List *filters;
List *indexpaths;
bool useful_predicate;
@@ -1185,11 +1223,14 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
* Identify the restriction clauses that can match the index.
*/
MemSet(&clauseset, 0, sizeof(clauseset));
- match_clauses_to_index(root, clauses, index, &clauseset);
+ filters = NIL;
+ match_clauses_to_index(root, clauses, index, &clauseset, &filters);
/*
* If no matches so far, and the index predicate isn't useful, we
* don't want it.
+ *
+ * XXX Maybe this should check the filterset too?
*/
if (!clauseset.nonempty && !useful_predicate)
continue;
@@ -1197,13 +1238,13 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
/*
* Add "other" restriction clauses to the clauseset.
*/
- match_clauses_to_index(root, other_clauses, index, &clauseset);
+ match_clauses_to_index(root, other_clauses, index, &clauseset, &filters);
/*
* Construct paths if possible.
*/
indexpaths = build_index_paths(root, rel,
- index, &clauseset,
+ index, &clauseset, filters,
useful_predicate,
ST_BITMAPSCAN,
NULL,
@@ -1847,6 +1888,62 @@ check_index_only(RelOptInfo *rel, IndexOptInfo *index)
return result;
}
+/*
+ * check_index_filter
+ * Determine whether a clause can be executed directly on the index tuple.
+ */
+static bool
+check_index_filter(RelOptInfo *rel, IndexOptInfo *index, Node *clause)
+{
+ bool result;
+ Bitmapset *attrs_used = NULL;
+ Bitmapset *index_canreturn_attrs = NULL;
+ int i;
+
+ /* Index-only scans must be enabled */
+ if (!enable_indexonlyfilter)
+ return false;
+
+ /*
+ * Check that all needed attributes of the relation are available from the
+ * index.
+ */
+
+ /*
+ * First, identify all the attributes needed by the clause.
+ */
+ pull_varattnos(clause, rel->relid, &attrs_used);
+
+ /*
+ * Construct a bitmapset of columns that the index can return back in an
+ * index-only scan.
+ */
+ for (i = 0; i < index->ncolumns; i++)
+ {
+ int attno = index->indexkeys[i];
+
+ /*
+ * For the moment, we just ignore index expressions. It might be nice
+ * to do something with them, later.
+ */
+ if (attno == 0)
+ continue;
+
+ if (index->canreturn[i])
+ index_canreturn_attrs =
+ bms_add_member(index_canreturn_attrs,
+ attno - FirstLowInvalidHeapAttributeNumber);
+ }
+
+ /* Do we have all the necessary attributes? */
+ result = bms_is_subset(attrs_used, index_canreturn_attrs);
+
+ bms_free(attrs_used);
+ bms_free(index_canreturn_attrs);
+
+ return result;
+}
+
/*
* get_loop_count
* Choose the loop count estimate to use for costing a parameterized path
@@ -2015,10 +2112,11 @@ approximate_joinrel_size(PlannerInfo *root, Relids relids)
static void
match_restriction_clauses_to_index(PlannerInfo *root,
IndexOptInfo *index,
- IndexClauseSet *clauseset)
+ IndexClauseSet *clauseset,
+ List **filters)
{
/* We can ignore clauses that are implied by the index predicate */
- match_clauses_to_index(root, index->indrestrictinfo, index, clauseset);
+ match_clauses_to_index(root, index->indrestrictinfo, index, clauseset, filters);
}
/*
@@ -2026,6 +2124,8 @@ match_restriction_clauses_to_index(PlannerInfo *root,
* Identify join clauses for the rel that match the index.
* Matching clauses are added to *clauseset.
* Also, add any potentially usable join OR clauses to *joinorclauses.
+ *
+ * FIXME Maybe this should fill the filterset too?
*/
static void
match_join_clauses_to_index(PlannerInfo *root,
@@ -2048,7 +2148,7 @@ match_join_clauses_to_index(PlannerInfo *root,
if (restriction_is_or_clause(rinfo))
*joinorclauses = lappend(*joinorclauses, rinfo);
else
- match_clause_to_index(root, rinfo, index, clauseset);
+ match_clause_to_index(root, rinfo, index, clauseset, NULL);
}
}
@@ -2056,6 +2156,8 @@ match_join_clauses_to_index(PlannerInfo *root,
* match_eclass_clauses_to_index
* Identify EquivalenceClass join clauses for the rel that match the index.
* Matching clauses are added to *clauseset.
+ *
+ * XXX Maybe this should fill the filterset too?
*/
static void
match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index,
@@ -2086,7 +2188,7 @@ match_eclass_clauses_to_index(PlannerInfo *root, IndexOptInfo *index,
* since for non-btree indexes the EC's equality operators might not
* be in the index opclass (cf ec_member_matches_indexcol).
*/
- match_clauses_to_index(root, clauses, index, clauseset);
+ match_clauses_to_index(root, clauses, index, clauseset, NULL);
}
}
@@ -2099,7 +2201,8 @@ static void
match_clauses_to_index(PlannerInfo *root,
List *clauses,
IndexOptInfo *index,
- IndexClauseSet *clauseset)
+ IndexClauseSet *clauseset,
+ List **filters)
{
ListCell *lc;
@@ -2107,7 +2210,7 @@ match_clauses_to_index(PlannerInfo *root,
{
RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
- match_clause_to_index(root, rinfo, index, clauseset);
+ match_clause_to_index(root, rinfo, index, clauseset, filters);
}
}
@@ -2132,7 +2235,8 @@ static void
match_clause_to_index(PlannerInfo *root,
RestrictInfo *rinfo,
IndexOptInfo *index,
- IndexClauseSet *clauseset)
+ IndexClauseSet *clauseset,
+ List **filters)
{
int indexcol;
@@ -2181,6 +2285,20 @@ match_clause_to_index(PlannerInfo *root,
return;
}
}
+
+ /* if filterset is NULL, we're done */
+ if (!filters)
+ return;
+
+ /*
+ * We didn't record the clause as a regular index clause, so see if
+ * we can evaluate it as an index filter.
+ */
+ if ((rinfo = match_filter_to_index(root, rinfo, index)) != NULL)
+ {
+ /* FIXME maybe check/prevent duplicates, like above? */
+ *filters = lappend(*filters, rinfo);
+ }
}
/*
@@ -2316,6 +2434,29 @@ match_clause_to_indexcol(PlannerInfo *root,
return NULL;
}
+static RestrictInfo *
+match_filter_to_index(PlannerInfo *root,
+ RestrictInfo *rinfo,
+ IndexOptInfo *index)
+{
+ Expr *clause = rinfo->clause;
+
+ /*
+ * Historically this code has coped with NULL clauses. That's probably
+ * not possible anymore, but we might as well continue to cope.
+ */
+ if (clause == NULL)
+ return NULL;
+
+ /*
+ * Can the clause be evaluated only using the index tuple?
+ */
+ if (!check_index_filter(index->rel, index, (Node *) rinfo->clause))
+ return NULL;
+
+ return rinfo;
+}
+
/*
* IsBooleanOpfamily
* Detect whether an opfamily supports boolean equality as an operator.
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 4bb38160b33..e8fe0a4f39a 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -166,10 +166,16 @@ static Node *replace_nestloop_params_mutator(Node *node, PlannerInfo *root);
static void fix_indexqual_references(PlannerInfo *root, IndexPath *index_path,
List **stripped_indexquals_p,
List **fixed_indexquals_p);
+static void fix_indexfilter_references(PlannerInfo *root, IndexPath *index_path,
+ List **stripped_indexfilters_p,
+ List **fixed_indexfilters_p);
static List *fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path);
static Node *fix_indexqual_clause(PlannerInfo *root,
IndexOptInfo *index, int indexcol,
Node *clause, List *indexcolnos);
+static Node *fix_indexfilter_clause(PlannerInfo *root,
+ IndexOptInfo *index,
+ Node *clause);
static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol);
static List *get_switched_clauses(List *clauses, Relids outerrelids);
static List *order_qual_clauses(PlannerInfo *root, List *clauses);
@@ -182,6 +188,7 @@ static SampleScan *make_samplescan(List *qptlist, List *qpqual, Index scanrelid,
TableSampleClause *tsc);
static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
Oid indexid, List *indexqual, List *indexqualorig,
+ List *indexfilters, List *indexfiltersorig,
List *indexorderby, List *indexorderbyorig,
List *indexorderbyops,
ScanDirection indexscandir);
@@ -2993,13 +3000,16 @@ create_indexscan_plan(PlannerInfo *root,
{
Scan *scan_plan;
List *indexclauses = best_path->indexclauses;
+// List *indexfilters = best_path->indexfilters;
List *indexorderbys = best_path->indexorderbys;
Index baserelid = best_path->path.parent->relid;
IndexOptInfo *indexinfo = best_path->indexinfo;
Oid indexoid = indexinfo->indexoid;
List *qpqual;
List *stripped_indexquals;
+ List *stripped_indexfilters;
List *fixed_indexquals;
+ List *fixed_indexfilters;
List *fixed_indexorderbys;
List *indexorderbyops = NIL;
ListCell *l;
@@ -3021,6 +3031,16 @@ create_indexscan_plan(PlannerInfo *root,
&stripped_indexquals,
&fixed_indexquals);
+ /*
+ * Extract the index qual expressions (stripped of RestrictInfos) from the
+ * IndexClauses list, and prepare a copy with index Vars substituted for
+ * table Vars. (This step also does replace_nestloop_params on the
+ * fixed_indexquals.)
+ */
+ fix_indexfilter_references(root, best_path,
+ &stripped_indexfilters,
+ &fixed_indexfilters);
+
/*
* Likewise fix up index attr references in the ORDER BY expressions.
*/
@@ -3063,6 +3083,8 @@ create_indexscan_plan(PlannerInfo *root,
continue; /* we may drop pseudoconstants here */
if (is_redundant_with_indexclauses(rinfo, indexclauses))
continue; /* dup or derived from same EquivalenceClass */
+// if (is_redundant_with_indexclauses(rinfo, indexfilters))
+// continue; /* dup or derived from same EquivalenceClass */
if (!contain_mutable_functions((Node *) rinfo->clause) &&
predicate_implied_by(list_make1(rinfo->clause), stripped_indexquals,
false))
@@ -3089,6 +3111,8 @@ create_indexscan_plan(PlannerInfo *root,
{
stripped_indexquals = (List *)
replace_nestloop_params(root, (Node *) stripped_indexquals);
+ stripped_indexfilters = (List *)
+ replace_nestloop_params(root, (Node *) stripped_indexfilters);
qpqual = (List *)
replace_nestloop_params(root, (Node *) qpqual);
indexorderbys = (List *)
@@ -3165,6 +3189,8 @@ create_indexscan_plan(PlannerInfo *root,
indexoid,
fixed_indexquals,
stripped_indexquals,
+ fixed_indexfilters,
+ stripped_indexfilters,
fixed_indexorderbys,
indexorderbys,
indexorderbyops,
@@ -5009,6 +5035,31 @@ fix_indexqual_references(PlannerInfo *root, IndexPath *index_path,
*fixed_indexquals_p = fixed_indexquals;
}
+static void
+fix_indexfilter_references(PlannerInfo *root, IndexPath *index_path,
+ List **stripped_indexfilters_p, List **fixed_indexfilters_p)
+{
+ IndexOptInfo *index = index_path->indexinfo;
+ List *stripped_indexfilters;
+ List *fixed_indexfilters;
+ ListCell *lc;
+
+ stripped_indexfilters = fixed_indexfilters = NIL;
+
+ foreach(lc, index_path->indexfilters)
+ {
+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
+ Node *clause = (Node *) rinfo->clause;
+
+ stripped_indexfilters = lappend(stripped_indexfilters, clause);
+ clause = fix_indexfilter_clause(root, index, clause);
+ fixed_indexfilters = lappend(fixed_indexfilters, clause);
+ }
+
+ *stripped_indexfilters_p = stripped_indexfilters;
+ *fixed_indexfilters_p = fixed_indexfilters;
+}
+
/*
* fix_indexorderby_references
* Adjust indexorderby clauses to the form the executor's index
@@ -5107,6 +5158,90 @@ fix_indexqual_clause(PlannerInfo *root, IndexOptInfo *index, int indexcol,
return clause;
}
+typedef struct
+{
+ PlannerInfo *root;
+ IndexOptInfo *index;
+} fix_indexfilter_context;
+
+static Node *
+fix_indexfilter_mutator(Node *node, fix_indexfilter_context *context)
+{
+ IndexOptInfo *index = context->index;
+
+ if (node == NULL)
+ return NULL;
+
+ /*
+ * Remove any binary-compatible relabeling of the indexkey
+ */
+ if (IsA(node, RelabelType))
+ node = (Node *) ((RelabelType *) node)->arg;
+
+ /* It's a simple index column */
+ if (IsA(node, Var) &&
+ ((Var *) node)->varno == index->rel->relid)
+ {
+ Var *result;
+ Var *var = (Var *) node;
+ AttrNumber attnum = InvalidAttrNumber;
+
+ for (int i = 0; i < index->ncolumns; i++)
+ {
+ if (index->indexkeys[i] == var->varattno)
+ {
+ attnum = (i + 1);
+ break;
+ }
+ }
+
+ Assert(attnum != InvalidAttrNumber);
+
+ result = (Var *) copyObject(node);
+ result->varno = INDEX_VAR;
+ result->varattno = attnum;
+
+ return (Node *) result;
+ }
+
+ return expression_tree_mutator(node, fix_indexfilter_mutator,
+ (void *) context);
+}
+
+/*
+ * fix_indexfilter_clause
+ * Convert a single indexqual clause to the form needed by the executor.
+ *
+ * We replace nestloop params here, and replace the index key variables
+ * or expressions by index Var nodes.
+ *
+ * XXX I'm not sure why this is done this early in createplan.c and not later
+ * in setrefs.c, which is where these things generally happen.
+ *
+ * XXX I'm also not sure why fix_indexqual_operand() doesn't use tree walker,
+ * but instead does all this manually. Is there a reason, or was this just
+ * simpler, considering how restricted the regular index clauses are? Or
+ * did it just precede the walker infrastructure, perhaps?
+ */
+static Node *
+fix_indexfilter_clause(PlannerInfo *root, IndexOptInfo *index, Node *clause)
+{
+ fix_indexfilter_context context;
+
+ /*
+ * Replace any outer-relation variables with nestloop params.
+ *
+ * This also makes a copy of the clause, so it's safe to modify it
+ * in-place below.
+ */
+ clause = replace_nestloop_params(root, clause);
+
+ context.root = root;
+ context.index = index;
+
+ return fix_indexfilter_mutator(clause, &context);
+}
+
/*
* fix_indexqual_operand
* Convert an indexqual expression to a Var referencing the index column.
@@ -5505,6 +5640,8 @@ make_indexscan(List *qptlist,
Oid indexid,
List *indexqual,
List *indexqualorig,
+ List *indexfilters,
+ List *indexfiltersorig,
List *indexorderby,
List *indexorderbyorig,
List *indexorderbyops,
@@ -5521,6 +5658,8 @@ make_indexscan(List *qptlist,
node->indexid = indexid;
node->indexqual = indexqual;
node->indexqualorig = indexqualorig;
+ node->indexfilters = indexfilters;
+ node->indexfiltersorig = indexfiltersorig;
node->indexorderby = indexorderby;
node->indexorderbyorig = indexorderbyorig;
node->indexorderbyops = indexorderbyops;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 1e4dd27dbaf..e53034f761e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -6604,7 +6604,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid)
/* Estimate the cost of index scan */
indexScanPath = create_index_path(root, indexInfo,
- NIL, NIL, NIL, NIL,
+ NIL, NIL, NIL, NIL, NIL,
ForwardScanDirection, false,
NULL, 1.0, false);
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c
index 1ca26baa259..e223f8b1ddb 100644
--- a/src/backend/optimizer/plan/setrefs.c
+++ b/src/backend/optimizer/plan/setrefs.c
@@ -666,6 +666,12 @@ set_plan_refs(PlannerInfo *root, Plan *plan, int rtoffset)
splan->indexqualorig =
fix_scan_list(root, splan->indexqualorig,
rtoffset, NUM_EXEC_QUAL(plan));
+ splan->indexfilters =
+ fix_scan_list(root, splan->indexfilters,
+ rtoffset, 1);
+ splan->indexfiltersorig =
+ fix_scan_list(root, splan->indexfiltersorig,
+ rtoffset, NUM_EXEC_QUAL(plan));
splan->indexorderby =
fix_scan_list(root, splan->indexorderby,
rtoffset, 1);
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 5f5596841c8..fa0e7567160 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -995,6 +995,7 @@ IndexPath *
create_index_path(PlannerInfo *root,
IndexOptInfo *index,
List *indexclauses,
+ List *indexfilters,
List *indexorderbys,
List *indexorderbycols,
List *pathkeys,
@@ -1019,6 +1020,7 @@ create_index_path(PlannerInfo *root,
pathnode->indexinfo = index;
pathnode->indexclauses = indexclauses;
+ pathnode->indexfilters = indexfilters;
pathnode->indexorderbys = indexorderbys;
pathnode->indexorderbycols = indexorderbycols;
pathnode->indexscandir = indexscandir;
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 4665b0a35c3..48b9372ea8c 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -833,6 +833,16 @@ struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_indexonlyfilter", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables the planner's use of index to evaluate filters."),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &enable_indexonlyfilter,
+ true,
+ NULL, NULL, NULL
+ },
{
{"enable_bitmapscan", PGC_USERSET, QUERY_TUNING_METHOD,
gettext_noop("Enables the planner's use of bitmap-scan plans."),
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index cb714f4a196..eb995ffcebd 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1572,6 +1572,12 @@ typedef struct IndexScanState
Relation iss_RelationDesc;
struct IndexScanDescData *iss_ScanDesc;
+ ExprState *indexfilters;
+ ExprState *indexfiltersorig;
+ // List *iss_FilterClauses;
+ Buffer iss_VMBuffer;
+ TupleTableSlot *iss_IndexSlot;
+
/* These are needed for re-checking ORDER BY expr ordering */
pairingheap *iss_ReorderQueue;
bool iss_ReachedEnd;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index c17b53f7adb..5c856b41efb 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1677,6 +1677,7 @@ typedef struct IndexPath
Path path;
IndexOptInfo *indexinfo;
List *indexclauses;
+ List *indexfilters;
List *indexorderbys;
List *indexorderbycols;
ScanDirection indexscandir;
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 1b787fe0318..cf02b939b23 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -450,6 +450,8 @@ typedef struct IndexScan
Oid indexid; /* OID of index to scan */
List *indexqual; /* list of index quals (usually OpExprs) */
List *indexqualorig; /* the same in original form */
+ List *indexfilters; /* quals for included columns */
+ List *indexfiltersorig; /* the same in original form */
List *indexorderby; /* list of index ORDER BY exprs */
List *indexorderbyorig; /* the same in original form */
List *indexorderbyops; /* OIDs of sort ops for ORDER BY exprs */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 6cf49705d3a..02ed1212715 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -52,6 +52,7 @@ extern PGDLLIMPORT int max_parallel_workers_per_gather;
extern PGDLLIMPORT bool enable_seqscan;
extern PGDLLIMPORT bool enable_indexscan;
extern PGDLLIMPORT bool enable_indexonlyscan;
+extern PGDLLIMPORT bool enable_indexonlyfilter;
extern PGDLLIMPORT bool enable_bitmapscan;
extern PGDLLIMPORT bool enable_tidscan;
extern PGDLLIMPORT bool enable_sort;
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 001e75b5b76..d5e380c8275 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -41,6 +41,7 @@ extern Path *create_samplescan_path(PlannerInfo *root, RelOptInfo *rel,
extern IndexPath *create_index_path(PlannerInfo *root,
IndexOptInfo *index,
List *indexclauses,
+ List *indexfilters,
List *indexorderbys,
List *indexorderbycols,
List *pathkeys,
--
2.40.1
