From: Dmitry Dolgov <9erthalion6@gmail.com>
To: PostgreSQL-development <pgsql-hackers@postgresql.org>
Cc: Jesper Pedersen <jesper.pedersen@redhat.com>
Cc: David Rowley <dgrowleyml@gmail.com>
Cc: Floris Van Nee <florisvannee@optiver.com>
Cc: Kyotaro Horiguchi <horikyota.ntt@gmail.com>
Cc: Peter Geoghegan <pg@bowt.ie>
Cc: Thomas Munro <thomas.munro@gmail.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Andy Fan <zhihui.fan1213@gmail.com>
Cc: Dilip Kumar <dilipbalaut@gmail.com>
Subject: Index Skip Scan (new UniqueKeys)
Date: Tue, 9 Jun 2020 12:22:47 +0200
Message-ID: <20200609102247.jdlatmfyeecg52fi@localhost> (raw)
Hi,
Here is a new version of index skip scan patch, based on v8 patch for
UniqueKeys implementation from [1]. I want to start a new thread to
simplify navigation, hopefully I didn't forget anyone who actively
participated in the discussion.
To simplify reviewing I've split it into several parts:
* First two are taken from [1] just for the reference and to make cfbot happy.
* Extend-UniqueKeys consists changes that needs to be done for
UniqueKeys to be used in skip scan. Essentially this is a reduced
version of previous implementation from Jesper & David, based on the
new UniqueKeys infrastructure, as it does the very same thing.
* Index-Skip-Scan contains not am specific code and the overall
infrastructure, including configuration elements and so on.
* Btree-implementation contains btree specific code to implement amskip,
introduced in the previous patch.
* The last one contains just documentation bits.
Interesting enough with a new UniqueKey implementation skipping is
applied in some tests unexpectedly. For those I've disabled
indexskipscan to avoid confusion.
[1]: https://www.postgresql.org/message-id/flat/CAKU4AWrwZMAL%3DuaFUDMf4WGOVkEL3ONbatqju9nSXTUucpp_pw%40m...Attachments:
[text/x-diff] v8-0001-Introduce-RelOptInfo-notnullattrs-attribute.patch (2.9K, ../20200609102247.jdlatmfyeecg52fi@localhost/2-v8-0001-Introduce-RelOptInfo-notnullattrs-attribute.patch)
download | inline diff:
From 159f7fdcbb1aa78f98c95d9fb3be2e3f4cadcd11 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Sun, 3 May 2020 22:37:46 +0800
Subject: [PATCH v35 1/6] Introduce RelOptInfo->notnullattrs attribute
---
src/backend/optimizer/plan/initsplan.c | 10 ++++++++++
src/backend/optimizer/util/plancat.c | 10 ++++++++++
src/include/nodes/pathnodes.h | 2 ++
3 files changed, 22 insertions(+)
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.cindex e978b491f6..95b1b14cd3 100644--- a/src/backend/optimizer/plan/initsplan.c+++ b/src/backend/optimizer/plan/initsplan.c@@ -830,6 +830,16 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
{
Node *qual = (Node *) lfirst(l);
+ /* Set the not null info now */+ ListCell *lc;+ List *non_nullable_vars = find_nonnullable_vars(qual);+ foreach(lc, non_nullable_vars)+ {+ Var *var = lfirst_node(Var, lc);+ RelOptInfo *rel = root->simple_rel_array[var->varno];+ rel->notnullattrs = bms_add_member(rel->notnullattrs,+ var->varattno - FirstLowInvalidHeapAttributeNumber);+ }
distribute_qual_to_rels(root, qual,
false, below_outer_join, JOIN_INNER,
root->qual_security_level,
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.cindex 25545029d7..0b2f9d398a 100644--- a/src/backend/optimizer/util/plancat.c+++ b/src/backend/optimizer/util/plancat.c@@ -117,6 +117,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
Relation relation;
bool hasindex;
List *indexinfos = NIL;
+ int i;
/*
* We need not lock the relation since it was already locked, either by
@@ -463,6 +464,15 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
if (inhparent && relation->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
set_relation_partition_info(root, rel, relation);
+ Assert(rel->notnullattrs == NULL);+ for(i = 0; i < relation->rd_att->natts; i++)+ {+ FormData_pg_attribute attr = relation->rd_att->attrs[i];+ if (attr.attnotnull)+ rel->notnullattrs = bms_add_member(rel->notnullattrs,+ attr.attnum - FirstLowInvalidHeapAttributeNumber);+ }+
table_close(relation, NoLock);
/*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.hindex 485d1b06c9..9e3ebd488a 100644--- a/src/include/nodes/pathnodes.h+++ b/src/include/nodes/pathnodes.h@@ -709,6 +709,8 @@ typedef struct RelOptInfo
PlannerInfo *subroot; /* if subquery */
List *subplan_params; /* if subquery */
int rel_parallel_workers; /* wanted number of parallel workers */
+ /* Not null attrs, start from -FirstLowInvalidHeapAttributeNumber */+ Bitmapset *notnullattrs;
/* Information about foreign tables and foreign joins */
Oid serverid; /* identifies server for the table or join */
--
2.21.0
[text/x-diff] v8-0002-Introuduce-RelOptInfo.uniquekeys-attribute.patch (48.2K, ../20200609102247.jdlatmfyeecg52fi@localhost/3-v8-0002-Introuduce-RelOptInfo.uniquekeys-attribute.patch)
download | inline diff:
From db5f1f0d1749e5657297b846a77ba12d6b38fcd7 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Sun, 3 May 2020 22:51:57 +0800
Subject: [PATCH v35 2/6] Introuduce RelOptInfo.uniquekeys attribute
---
src/backend/nodes/list.c | 31 +
src/backend/nodes/makefuncs.c | 21 +
src/backend/optimizer/path/Makefile | 3 +-
src/backend/optimizer/path/README.uniquekey | 71 ++
src/backend/optimizer/path/allpaths.c | 7 +
src/backend/optimizer/path/joinrels.c | 2 +
src/backend/optimizer/path/pathkeys.c | 3 +-
src/backend/optimizer/path/uniquekeys.c | 1135 +++++++++++++++++++
src/backend/optimizer/plan/planner.c | 10 +-
src/backend/optimizer/prep/prepunion.c | 2 +
src/include/nodes/makefuncs.h | 3 +
src/include/nodes/nodes.h | 1 +
src/include/nodes/pathnodes.h | 26 +
src/include/nodes/pg_list.h | 2 +
src/include/optimizer/optimizer.h | 2 +
src/include/optimizer/paths.h | 35 +
16 files changed, 1349 insertions(+), 5 deletions(-)
create mode 100644 src/backend/optimizer/path/README.uniquekey
create mode 100644 src/backend/optimizer/path/uniquekeys.c
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.cindex 80fa8c84e4..aa47eaed36 100644--- a/src/backend/nodes/list.c+++ b/src/backend/nodes/list.c@@ -687,6 +687,37 @@ list_member_oid(const List *list, Oid datum)
return false;
}
+/*+ * Return true iff there is an equal member in target for every+ * member in members+ */+bool+list_is_subset(const List *members, const List *target)+{+ const ListCell *lc1, *lc2;++ Assert(IsPointerList(members));+ Assert(IsPointerList(target));+ check_list_invariants(members);+ check_list_invariants(target);++ foreach(lc1, members)+ {+ bool found = false;+ foreach(lc2, target)+ {+ if (equal(lfirst(lc1), lfirst(lc2)))+ {+ found = true;+ break;+ }+ }+ if (!found)+ return false;+ }+ return true;+}+
/*
* Delete the n'th cell (counting from 0) in list.
*
diff --git a/src/backend/nodes/makefuncs.c b/src/backend/nodes/makefuncs.cindex b442b5a29e..3155e5c372 100644--- a/src/backend/nodes/makefuncs.c+++ b/src/backend/nodes/makefuncs.c@@ -812,3 +812,24 @@ makeVacuumRelation(RangeVar *relation, Oid oid, List *va_cols)
v->va_cols = va_cols;
return v;
}
+++/*+ * makeUniqueKey+ */+UniqueKey*+makeUniqueKey(List *exprs, bool multi_nullvals, bool onerow)+{+ UniqueKey * ukey = makeNode(UniqueKey);+ if (onerow)+ {+ Assert(exprs == NIL);+ Assert(!multi_nullvals);+ }+ else+ Assert(exprs != NIL);+ ukey->exprs = exprs;+ ukey->multi_nullvals = multi_nullvals;+ ukey->onerow = onerow;+ return ukey;+}diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefileindex 1e199ff66f..7b9820c25f 100644--- a/src/backend/optimizer/path/Makefile+++ b/src/backend/optimizer/path/Makefile@@ -21,6 +21,7 @@ OBJS = \
joinpath.o \
joinrels.o \
pathkeys.o \
- tidpath.o+ tidpath.o \+ uniquekeys.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/path/README.uniquekey b/src/backend/optimizer/path/README.uniquekeynew file mode 100644index 0000000000..dc0d6490f2--- /dev/null+++ b/src/backend/optimizer/path/README.uniquekey@@ -0,0 +1,71 @@+1. What is UniqueKey?+We can think UniqueKey is a set of exprs for a RelOptInfo, which we are insure+that doesn't yields same result among all the rows. The simplest UniqueKey+format is primary key.++However we define the UnqiueKey as below.++typedef struct UniqueKey+{+ NodeTag type;+ List *exprs;+ bool multi_nullvals;+ bool onerow;+} UniqueKey;++mutli_nuvals is used to track if the exprs allows multi nullvals. For a unique+index without its column marked as not null, it allows mulit_nullvals.++onerow is also a kind of UniqueKey which means the RelOptInfo will have 1 row at+most. it has a stronger semantic than others. like SELECT uk FROM t; uk is+normal unique key and may have different values.+SELECT colx FROM t WHERE uk = const. colx is unique AND we have only 1 value. This+field can used for innerrel_is_unique. and also be used as an optimization for+this case. We don't need to maintain multi UniqueKey, we just maintain one with+onerow = true and exprs = NIL.++onerow is set to true only for 2 cases right now. 1) SELECT .. FROM t WHERE uk =+1; 2). SELECT aggref(xx) from t; // Without group by.++The UniqueKey can be used at the following cases at least:+1. remove_useless_joins.+2. reduce_semianti_joins+3. remove distinct node if distinct clause is unique.+4. remove aggnode if group by clause is unique.+5. Aggregation Push Down without 2 phase aggregation if the join can't+ duplicated the aggregated rows. (work in progress feature)+++2. How is it maintained?++We have a set of populate_xxx_unqiuekeys functions to maintain the uniquekey on+various cases. xxx includes baserel, joinrel, partitionedrel, distinctrel,+groupedrel, unionrel. and we also need to convert the uniquekey from subquery+to outer relation, which is what convert_subquery_uniquekeys does.++The most error-prone part is joinrel, we simplified the rules like below:+1. If the relation's UniqueKey can't be duplicated after join, then is will be+ still valid for the join rel. The function we used here is+ innerrel_keeps_unique. The basic idea is innerrel.any_col = outer.uk.++2. If the UnqiueKey can't keep valid via the rule 1, the combination of the+ UniqueKey from both sides are valid for sure. We can prove this as: if the+ unique exprs from rel1 is duplicated by rel2, the duplicated rows must+ contains different unique exprs from rel2.+++More considerations about onerow:+1. If relation with one row and it can't be duplicated, it is still possible+ contains mulit_nullvas after outer join.+2. If the either UniqueKey can be duplicated after join, the can get one row+ only when both side is one row AND there is no outer join.+3. Whenever the onerow UniqueKey is not a valid any more, we need to convert one+ row UniqueKey to normal unique key since we don't store exprs for one-row+ relation. get_exprs_from_uniquekeys will be used here.+++More considerations about multi_nullvals after join:+1. If the original UnqiueKey has multi_nullvals, the final UniqueKey will have+ mulit_nullvals in any case.+2. If a unique key doesn't allow mulit_nullvals, after some outer join, it+ allows some outer join.diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.cindex d984da25d7..c3d21f0520 100644--- a/src/backend/optimizer/path/allpaths.c+++ b/src/backend/optimizer/path/allpaths.c@@ -786,6 +786,9 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
/* Consider TID scans */
create_tidscan_paths(root, rel);
++ /* Set UniqueKeys for this relation */+ populate_baserel_uniquekeys(root, rel, rel->indexlist);
}
/*
@@ -1276,6 +1279,8 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
/* Add paths to the append relation. */
add_paths_to_append_rel(root, rel, live_childrels);
+ if (IS_PARTITIONED_REL(rel))+ populate_partitionedrel_uniquekeys(root, rel, live_childrels);
}
@@ -2349,6 +2354,8 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
pathkeys, required_outer));
}
+ convert_subquery_uniquekeys(root, rel, sub_final_rel);+
/* If outer rel allows parallelism, do same for partial paths. */
if (rel->consider_parallel && bms_is_empty(required_outer))
{
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.cindex 2d343cd293..b9163ee8ff 100644--- a/src/backend/optimizer/path/joinrels.c+++ b/src/backend/optimizer/path/joinrels.c@@ -924,6 +924,8 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1,
/* Apply partitionwise join technique, if possible. */
try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist);
++ populate_joinrel_uniquekeys(root, joinrel, rel1, rel2, restrictlist, sjinfo->jointype);
}
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.cindex ce9bf87e9b..7e596d4194 100644--- a/src/backend/optimizer/path/pathkeys.c+++ b/src/backend/optimizer/path/pathkeys.c@@ -33,7 +33,6 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
static bool matches_boolean_partition_clause(RestrictInfo *rinfo,
RelOptInfo *partrel,
int partkeycol);
-static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle);
static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey);
@@ -1035,7 +1034,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
* We need this to ensure that we don't return pathkeys describing values
* that are unavailable above the level of the subquery scan.
*/
-static Var *+Var *
find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle)
{
ListCell *lc;
diff --git a/src/backend/optimizer/path/uniquekeys.c b/src/backend/optimizer/path/uniquekeys.cnew file mode 100644index 0000000000..957af61819--- /dev/null+++ b/src/backend/optimizer/path/uniquekeys.c@@ -0,0 +1,1135 @@+/*-------------------------------------------------------------------------+ *+ * uniquekeys.c+ * Utilities for matching and building unique keys+ *+ * Portions Copyright (c) 2020, PostgreSQL Global Development Group+ *+ * IDENTIFICATION+ * src/backend/optimizer/path/uniquekeys.c+ *+ *-------------------------------------------------------------------------+ */+#include "postgres.h"++#include "nodes/makefuncs.h"+#include "nodes/nodeFuncs.h"+#include "optimizer/pathnode.h"+#include "optimizer/paths.h"+#include "optimizer/optimizer.h"+#include "optimizer/tlist.h"+#include "rewrite/rewriteManip.h"+++static List *gather_mergeable_baserestrictlist(RelOptInfo *rel);+static List *gather_mergeable_joinclauses(RelOptInfo *joinrel,+ RelOptInfo *rel1,+ RelOptInfo *rel2,+ List *restirctlist,+ JoinType jointype);+static bool match_index_to_baserestrictinfo(IndexOptInfo *unique_ind,+ List *restrictlist);++/*+ * This struct is used to help populate_joinrel_uniquekeys.+ *+ * added_to_joinrel is true if a uniquekey (from outerrel or innerrel)+ * has been added to joinrel.+ * useful is true if the exprs of the uniquekey still appears in joinrel.+ */+typedef struct UniqueKeyContextData+{+ UniqueKey *uniquekey;+ bool added_to_joinrel;+ bool useful;+} *UniqueKeyContext;++static List *initililze_uniquecontext_for_joinrel(RelOptInfo *inputrel);+static bool innerrel_keeps_unique(PlannerInfo *root,+ RelOptInfo *outerrel,+ RelOptInfo *innerrel,+ List *restrictlist,+ bool reverse);+static List *get_exprs_from_uniquekey(RelOptInfo *joinrel,+ RelOptInfo *rel1,+ UniqueKey *ukey);+static bool clause_sides_match_join(RestrictInfo *rinfo,+ Relids outerrelids,+ Relids innerrelids);+static void add_uniquekey_from_index(RelOptInfo *rel,+ IndexOptInfo *unique_index);+static void add_uniquekey_for_onerow(RelOptInfo *rel);+static bool add_combined_uniquekey(RelOptInfo *joinrel,+ RelOptInfo *outer_rel,+ RelOptInfo *inner_rel,+ UniqueKey *outer_ukey,+ UniqueKey *inner_ukey,+ JoinType jointype);++/* Used for unique indexes checking for partitioned table */+static bool index_constains_partkey(RelOptInfo *partrel, IndexOptInfo *ind);+static IndexOptInfo *simple_copy_indexinfo_to_parent(RelOptInfo *parentrel,+ IndexOptInfo *from);+static bool simple_indexinfo_equal(IndexOptInfo *ind1, IndexOptInfo *ind2);+static void adjust_partition_unique_indexlist(RelOptInfo *parentrel,+ RelOptInfo *childrel,+ List **global_unique_index);++/* Helper function for grouped relation and distinct relation. */+static void add_uniquekey_from_sortgroups(PlannerInfo *root,+ RelOptInfo *rel,+ List *sortgroups);++/*+ * populate_baserel_uniquekeys+ * Populate 'baserel' uniquekeys list by looking at the rel's unique index+ * add baserestrictinfo+ */+void+populate_baserel_uniquekeys(PlannerInfo *root,+ RelOptInfo *baserel,+ List *indexlist)+{+ ListCell *lc;+ List *restrictlist;+ bool return_one_row = false;+ List *matched_uniq_indexes = NIL;++ Assert(baserel->rtekind == RTE_RELATION);++ if (root->parse->hasTargetSRFs)+ return;++ if (baserel->reloptkind == RELOPT_OTHER_MEMBER_REL)+ /*+ * Set UniqueKey on member rel is useless, we have to recompute it at+ * upper level, see populate_partitionedrel_uniquekeys for reference+ */+ return;++ restrictlist = gather_mergeable_baserestrictlist(baserel);++ foreach(lc, indexlist)+ {+ IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);+ if (!ind->unique || !ind->immediate ||+ (ind->indpred != NIL && !ind->predOK))+ continue;++ if (match_index_to_baserestrictinfo(ind, restrictlist))+ {+ return_one_row = true;+ break;+ }++ if (ind->indexprs != NIL)+ /* XXX: ignore index on expression so far */+ continue;+ matched_uniq_indexes = lappend(matched_uniq_indexes, ind);+ }++ if (return_one_row)+ {+ add_uniquekey_for_onerow(baserel);+ }+ else+ {+ foreach(lc, matched_uniq_indexes)+ add_uniquekey_from_index(baserel, lfirst_node(IndexOptInfo, lc));+ }+}+++/*+ * populate_partitioned_rel_uniquekeys+ * The unique index can only be used for UniqueKey based on:+ * 1). It must include partition key.+ * 2). It exists in all the related. partitions.+ */+void+populate_partitionedrel_uniquekeys(PlannerInfo *root,+ RelOptInfo *rel,+ List *childrels)+{+ ListCell *lc;+ List *global_uniq_indexlist = NIL;+ RelOptInfo *childrel;+ bool is_first = true;++ Assert(IS_PARTITIONED_REL(rel));++ if (root->parse->hasTargetSRFs)+ return;++ if (childrels == NIL)+ return;++ childrel = linitial_node(RelOptInfo, childrels);+ foreach(lc, childrel->indexlist)+ {+ IndexOptInfo *ind = lfirst(lc);+ IndexOptInfo *modified_index;+ if (!ind->unique || !ind->immediate ||+ (ind->indpred != NIL && !ind->predOK))+ continue;++ modified_index = simple_copy_indexinfo_to_parent(rel, ind);+ /*+ * If the unique index doesn't contain partkey, then it is unique+ * on this partition only, so it is useless for us.+ */+ if (!index_constains_partkey(rel, modified_index))+ continue;+ global_uniq_indexlist = lappend(global_uniq_indexlist, modified_index);+ }++ /* Fast path */+ if (global_uniq_indexlist == NIL)+ return;++ foreach(lc, childrels)+ {+ RelOptInfo *child = lfirst(lc);+ if (is_first)+ {+ is_first = false;+ continue;+ }+ adjust_partition_unique_indexlist(rel, child, &global_uniq_indexlist);+ }++ /* Now we have a list of unique index which are exactly same on all childrels,+ * Set the UniqueKey just like it is non-partition table+ */+ populate_baserel_uniquekeys(root, rel, global_uniq_indexlist);+}+++/*+ * populate_distinctrel_uniquekeys+ */+void+populate_distinctrel_uniquekeys(PlannerInfo *root,+ RelOptInfo *inputrel,+ RelOptInfo *distinctrel)+{+ /* The unique key before the distinct is still valid. */+ distinctrel->uniquekeys = list_copy(inputrel->uniquekeys);+ add_uniquekey_from_sortgroups(root, distinctrel, root->parse->distinctClause);+}++/*+ * populate_grouprel_uniquekeys+ */+void+populate_grouprel_uniquekeys(PlannerInfo *root,+ RelOptInfo *grouprel)+{+ Query *parse = root->parse;++ if (parse->hasTargetSRFs)+ return;++ if (parse->groupingSets)+ return;++ /* A Normal group by without grouping set. */+ if (parse->groupClause)+ add_uniquekey_from_sortgroups(root,+ grouprel,+ root->parse->groupClause);+ else+ /* It has aggregation but without a group by, so only one row returned */+ add_uniquekey_for_onerow(grouprel);+}++/*+ * simple_copy_uniquekeys+ * Using a function for the one-line code makes us easy to check where we simply+ * copied the uniquekey.+ */+void+simple_copy_uniquekeys(RelOptInfo *oldrel,+ RelOptInfo *newrel)+{+ newrel->uniquekeys = oldrel->uniquekeys;+}++/*+ * populate_unionrel_uniquekeys+ */+void+populate_unionrel_uniquekeys(PlannerInfo *root,+ RelOptInfo *unionrel)+{+ ListCell *lc;+ List *exprs = NIL;++ Assert(unionrel->uniquekeys == NIL);++ foreach(lc, unionrel->reltarget->exprs)+ {+ exprs = lappend(exprs, lfirst(lc));+ }++ if (exprs == NIL)+ /* SQL: select union select; is valid, we need to handle it here. */+ return;+ unionrel->uniquekeys = lappend(unionrel->uniquekeys,+ makeUniqueKey(exprs,+ false, /* allows_multinull */+ false /* onerow */));+}++/*+ * populate_joinrel_uniquekeys+ *+ * populate uniquekeys for joinrel. We will check each relation to see if it's+ * UniqueKey is still valid via innerrel_keeps_unique, if so, we add it to+ * joinrel. The multi_nullvals field will be changed from false to true+ * for some outer join cases and one-row UniqueKey needs to be converted to nomarl+ * UniqueKey for the same case as well.++ * For the uniquekey in either baserel which can't be unique after join, we still+ * check to see if combination of UniqueKeys from both side is still useful for us.+ * if yes, we add it to joinrel as well.+ */+void+populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel,+ RelOptInfo *outerrel, RelOptInfo *innerrel,+ List *restrictlist, JoinType jointype)+{+ ListCell *lc, *lc2;+ List *clause_list = NIL;+ List *outerrel_ukey_ctx;+ List *innerrel_ukey_ctx;+ bool inner_onerow, outer_onerow;++ if (root->parse->hasTargetSRFs)+ return;++ /* Care about the outerrel relation only for SEMI/ANTI join */+ if (jointype == JOIN_SEMI || jointype == JOIN_ANTI)+ {+ foreach(lc, outerrel->uniquekeys)+ {+ UniqueKey *uniquekey = lfirst_node(UniqueKey, lc);+ if (list_is_subset(uniquekey->exprs, joinrel->reltarget->exprs))+ joinrel->uniquekeys = lappend(joinrel->uniquekeys, uniquekey);+ }+ return;+ }++ Assert(jointype == JOIN_LEFT || jointype == JOIN_FULL || jointype == JOIN_INNER);++ /* Fast path */+ if (innerrel->uniquekeys == NIL || outerrel->uniquekeys == NIL)+ return;++ inner_onerow = relation_is_onerow(innerrel);+ outer_onerow = relation_is_onerow(outerrel);++ outerrel_ukey_ctx = initililze_uniquecontext_for_joinrel(outerrel);+ innerrel_ukey_ctx = initililze_uniquecontext_for_joinrel(innerrel);++ clause_list = gather_mergeable_joinclauses(joinrel, outerrel, innerrel,+ restrictlist, jointype);++ if (innerrel_keeps_unique(root, innerrel, outerrel, clause_list, true /* reverse */))+ {+ foreach(lc, outerrel_ukey_ctx)+ {+ UniqueKeyContext ctx = (UniqueKeyContext)lfirst(lc);++ if (!list_is_subset(ctx->uniquekey->exprs, joinrel->reltarget->exprs))+ {+ ctx->useful = false;+ continue;+ }++ /* Outer relation has one row, and the unique key is not duplicated after join,+ * the joinrel will still has one row unless the jointype == JOIN_FULL.+ */+ if (outer_onerow && jointype != JOIN_FULL)+ {+ add_uniquekey_for_onerow(joinrel);+ return;+ }+ else if (outer_onerow)+ {+ /* Full join case, the onerow becomes multi rows and multi_nullvals changes+ * to true. We also need to set the exprs correctly since it is not one-row+ * any more.+ */+ ListCell *lc2;+ foreach(lc2, get_exprs_from_uniquekey(joinrel, outerrel, NULL))+ {+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ makeUniqueKey(lfirst(lc2),+ true, /* multi_nullvals */+ false /* onerow */));+ }+ }+ else+ {+ if (!ctx->uniquekey->multi_nullvals && jointype == JOIN_FULL)+ /* Change multi_nullvals to true due to the full join. */+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ makeUniqueKey(ctx->uniquekey->exprs,+ true,+ ctx->uniquekey->onerow));+ else+ /* Just reuse it */+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ ctx->uniquekey);+ }+ ctx->added_to_joinrel = true;+ }+ }++ if (innerrel_keeps_unique(root, outerrel, innerrel, clause_list, false))+ {+ foreach(lc, innerrel_ukey_ctx)+ {+ UniqueKeyContext ctx = (UniqueKeyContext)lfirst(lc);++ if (!list_is_subset(ctx->uniquekey->exprs, joinrel->reltarget->exprs))+ {+ ctx->useful = false;+ continue;+ }++ /*+ * Inner relation has one row, and the unique key is not duplicated after join,+ * the joinrel will still has one row unless the jointype not in+ * (JOIN_FULL, JOIN_LEFT)+ */+ if (inner_onerow && jointype != JOIN_FULL && jointype != JOIN_LEFT)+ {+ add_uniquekey_for_onerow(joinrel);+ return;+ }+ else if (inner_onerow)+ {+ /* Full join or left outer join case, the inner one row becomes to multi rows+ * and multi_nullvals becomes to true. We also need to set the exprs correctly+ * since it is not one-row any more.+ */+ ListCell *lc2;+ foreach(lc2, get_exprs_from_uniquekey(joinrel, innerrel, NULL))+ {+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ makeUniqueKey(lfirst(lc2),+ true, /* multi_nullvals */+ false /* onerow */));+ }+ }+ else+ {+ if (!ctx->uniquekey->multi_nullvals &&+ (jointype == JOIN_FULL || jointype == JOIN_LEFT))+ /* Need to change multi_nullvals to true due to the outer join. */+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ makeUniqueKey(ctx->uniquekey->exprs,+ true,+ ctx->uniquekey->onerow));+ else+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ ctx->uniquekey);++ }+ ctx->added_to_joinrel = true;+ }+ }++ /* The combination of the UniqueKey from both sides is unique as well regardless+ * of join type, but no bother to add it if its subset has been added to joinrel+ * already or it is not useful for the joinrel.+ */+ foreach(lc, outerrel_ukey_ctx)+ {+ UniqueKeyContext ctx1 = (UniqueKeyContext) lfirst(lc);+ if (ctx1->added_to_joinrel || !ctx1->useful)+ continue;+ foreach(lc2, innerrel_ukey_ctx)+ {+ UniqueKeyContext ctx2 = (UniqueKeyContext) lfirst(lc2);+ if (ctx2->added_to_joinrel || !ctx2->useful)+ continue;+ if (add_combined_uniquekey(joinrel, outerrel, innerrel,+ ctx1->uniquekey, ctx2->uniquekey,+ jointype))+ /* If we set a onerow UniqueKey to joinrel, we don't need other. */+ return;+ }+ }+}+++/*+ * convert_subquery_uniquekeys+ *+ * Covert the UniqueKey in subquery to outer relation.+ */+void convert_subquery_uniquekeys(PlannerInfo *root,+ RelOptInfo *currel,+ RelOptInfo *sub_final_rel)+{+ ListCell *lc;++ if (sub_final_rel->uniquekeys == NIL)+ return;++ if (relation_is_onerow(sub_final_rel))+ {+ add_uniquekey_for_onerow(currel);+ return;+ }++ Assert(currel->subroot != NULL);++ foreach(lc, sub_final_rel->uniquekeys)+ {+ UniqueKey *ukey = lfirst_node(UniqueKey, lc);+ ListCell *lc;+ List *exprs = NIL;+ bool ukey_useful = true;++ /* One row case is handled above */+ Assert(ukey->exprs != NIL);+ foreach(lc, ukey->exprs)+ {+ Var *var;+ TargetEntry *tle = tlist_member(lfirst(lc),+ currel->subroot->processed_tlist);+ if (tle == NULL)+ {+ ukey_useful = false;+ break;+ }+ var = find_var_for_subquery_tle(currel, tle);+ if (var == NULL)+ {+ ukey_useful = false;+ break;+ }+ exprs = lappend(exprs, var);+ }++ if (ukey_useful)+ currel->uniquekeys = lappend(currel->uniquekeys,+ makeUniqueKey(exprs,+ ukey->multi_nullvals,+ ukey->onerow));+ }+}++/*+ * innerrel_keeps_unique+ *+ * Check if Unique key of the innerrel is valid after join. innerrel's UniqueKey+ * will be still valid if innerrel's any-column mergeop outrerel's uniquekey+ * exists in clause_list.+ *+ * Note: the clause_list must be a list of mergeable restrictinfo already.+ */+static bool+innerrel_keeps_unique(PlannerInfo *root,+ RelOptInfo *outerrel,+ RelOptInfo *innerrel,+ List *clause_list,+ bool reverse)+{+ ListCell *lc, *lc2, *lc3;++ if (outerrel->uniquekeys == NIL || innerrel->uniquekeys == NIL)+ return false;++ /* Check if there is outerrel's uniquekey in mergeable clause. */+ foreach(lc, outerrel->uniquekeys)+ {+ List *outer_uq_exprs = lfirst_node(UniqueKey, lc)->exprs;+ bool clauselist_matchs_all_exprs = true;+ foreach(lc2, outer_uq_exprs)+ {+ Node *outer_uq_expr = lfirst(lc2);+ bool find_uq_expr_in_clauselist = false;+ foreach(lc3, clause_list)+ {+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc3);+ Node *outer_expr;+ if (reverse)+ outer_expr = rinfo->outer_is_left ? get_rightop(rinfo->clause) : get_leftop(rinfo->clause);+ else+ outer_expr = rinfo->outer_is_left ? get_leftop(rinfo->clause) : get_rightop(rinfo->clause);+ if (equal(outer_expr, outer_uq_expr))+ {+ find_uq_expr_in_clauselist = true;+ break;+ }+ }+ if (!find_uq_expr_in_clauselist)+ {+ /* No need to check the next exprs in the current uniquekey */+ clauselist_matchs_all_exprs = false;+ break;+ }+ }++ if (clauselist_matchs_all_exprs)+ return true;+ }+ return false;+}+++/*+ * relation_is_onerow+ * Check if it is a one-row relation by checking UniqueKey.+ */+bool+relation_is_onerow(RelOptInfo *rel)+{+ UniqueKey *ukey;+ if (rel->uniquekeys == NIL)+ return false;+ ukey = linitial_node(UniqueKey, rel->uniquekeys);+ if (ukey->onerow)+ {+ /* Some helpful tiny check for UniqueKey. */++ /* 1. We will only store one UniqueKey for this rel. */+ Assert(list_length(rel->uniquekeys) == 1);+ /* 2. multi_nullvals must be false. */+ Assert(!ukey->multi_nullvals);+ /* 3. exprs must be NIL. */+ Assert(ukey->exprs == NIL);++ }+ return ukey->onerow;+}++/*+ * relation_has_uniquekeys_for+ * Returns true if we have proofs that 'rel' cannot return multiple rows with+ * the same values in each of 'exprs'. Otherwise returns false.+ */+bool+relation_has_uniquekeys_for(PlannerInfo *root, RelOptInfo *rel,+ List *exprs, bool allow_multinulls)+{+ ListCell *lc;++ /* For UniqueKey->onerow case, the uniquekey->exprs is empty as well+ * so we can't rely on list_is_subset to handle this special cases+ */+ if (exprs == NIL)+ return false;++ foreach(lc, rel->uniquekeys)+ {+ UniqueKey *ukey = lfirst_node(UniqueKey, lc);+ if (ukey->multi_nullvals && !allow_multinulls)+ continue;+ if (list_is_subset(ukey->exprs, exprs))+ return true;+ }+ return false;+}+++/*+ * Examine the rel's restriction clauses for usable var = const clauses+ */+static List*+gather_mergeable_baserestrictlist(RelOptInfo *rel)+{+ List *restrictlist = NIL;+ ListCell *lc;+ foreach(lc, rel->baserestrictinfo)+ {+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);++ /*+ * Note: can_join won't be set for a restriction clause, but+ * mergeopfamilies will be if it has a mergejoinable operator and+ * doesn't contain volatile functions.+ */+ if (restrictinfo->mergeopfamilies == NIL)+ continue; /* not mergejoinable */++ /*+ * The clause certainly doesn't refer to anything but the given rel.+ * If either side is pseudoconstant then we can use it.+ */+ if (bms_is_empty(restrictinfo->left_relids))+ {+ /* righthand side is inner */+ restrictinfo->outer_is_left = true;+ }+ else if (bms_is_empty(restrictinfo->right_relids))+ {+ /* lefthand side is inner */+ restrictinfo->outer_is_left = false;+ }+ else+ continue;++ /* OK, add to list */+ restrictlist = lappend(restrictlist, restrictinfo);+ }+ return restrictlist;+}+++/*+ * gather_mergeable_joinclauses+ */+static List*+gather_mergeable_joinclauses(RelOptInfo *joinrel,+ RelOptInfo *outerrel,+ RelOptInfo *innerrel,+ List *restrictlist,+ JoinType jointype)+{+ List *clause_list = NIL;+ ListCell *lc;+ foreach(lc, restrictlist)+ {+ RestrictInfo *restrictinfo = (RestrictInfo *)lfirst(lc);+ if (IS_OUTER_JOIN(jointype) &&+ RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids))+ continue;++ /* Ignore if it's not a mergejoinable clause */+ if (!restrictinfo->can_join ||+ restrictinfo->mergeopfamilies == NIL)+ continue; /* not mergejoinable */++ /*+ * Check if clause has the form "outer op inner" or "inner op outer",+ * and if so mark which side is inner.+ */+ if (!clause_sides_match_join(restrictinfo, outerrel->relids, innerrel->relids))+ continue; /* no good for these input relations. */++ /* OK, add to list */+ clause_list = lappend(clause_list, restrictinfo);+ }+ return clause_list;+}+++/*+ * Return true if uk = Const in the restrictlist+ */+static bool+match_index_to_baserestrictinfo(IndexOptInfo *unique_ind, List *restrictlist)+{+ int c = 0;++ /* A fast path to avoid the 2 loop scan. */+ if (list_length(restrictlist) < unique_ind->ncolumns)+ return false;++ for(c = 0; c < unique_ind->ncolumns; c++)+ {+ ListCell *lc;+ bool found_in_restrictinfo = false;+ foreach(lc, restrictlist)+ {+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);+ Node *rexpr;++ /*+ * The condition's equality operator must be a member of the+ * index opfamily, else it is not asserting the right kind of+ * equality behavior for this index. We check this first+ * since it's probably cheaper than match_index_to_operand().+ */+ if (!list_member_oid(rinfo->mergeopfamilies, unique_ind->opfamily[c]))+ continue;++ /*+ * XXX at some point we may need to check collations here too.+ * For the moment we assume all collations reduce to the same+ * notion of equality.+ */++ /* OK, see if the condition operand matches the index key */+ if (rinfo->outer_is_left)+ rexpr = get_rightop(rinfo->clause);+ else+ rexpr = get_leftop(rinfo->clause);++ if (match_index_to_operand(rexpr, c, unique_ind))+ {+ found_in_restrictinfo = true;+ break;+ }+ }+ if (!found_in_restrictinfo)+ return false;+ }+ return true;+}++/*+ * add_uniquekey_from_index+ * We only add the Index Vars whose expr exists in rel->reltarget+ */+static void+add_uniquekey_from_index(RelOptInfo *rel, IndexOptInfo *unique_index)+{+ int pos;+ List *exprs = NIL;+ bool multi_nullvals = false;++ /* Fast path.+ * Check if the indexed columns are used in this relation, if not return fast.+ */+ for(pos = 0; pos < unique_index->ncolumns; pos++)+ {+ int attno = unique_index->indexkeys[pos];+ if (bms_is_empty(rel->attr_needed[attno - rel->min_attr]))+ /* The indexed column is not needed in this relation. */+ return;+ if (!bms_is_member(attno - FirstLowInvalidHeapAttributeNumber,+ rel->notnullattrs))+ multi_nullvals = true;+ }++ exprs = get_tlist_exprs(unique_index->indextlist, true);+ rel->uniquekeys = lappend(rel->uniquekeys,+ makeUniqueKey(exprs,+ multi_nullvals,+ false));+}+++/*+ * add_uniquekey_for_onerow+ * If we are sure that the relation only returns one row, then all the columns+ * are unique. However we don't need to create UniqueKey for every column, we+ * just set UniqueKey->onerow to true is OK and leave the exprs = NIL.+ */+void+add_uniquekey_for_onerow(RelOptInfo *rel)+{+ rel->uniquekeys = list_make1(makeUniqueKey(NIL, /* No need to set exprs */+ false, /* onerow can't have multi_nullvals */+ true));++}++/*+ * initililze_uniquecontext_for_joinrel+ * Return a List of UniqueKeyContext for an inputrel+ */+static List *+initililze_uniquecontext_for_joinrel(RelOptInfo *inputrel)+{+ List *res = NIL;+ ListCell *lc;+ foreach(lc, inputrel->uniquekeys)+ {+ UniqueKeyContext context;+ context = palloc(sizeof(struct UniqueKeyContextData));+ context->uniquekey = lfirst_node(UniqueKey, lc);+ context->added_to_joinrel = false;+ context->useful = true;+ res = lappend(res, context);+ }+ return res;+}++/*+ * clause_sides_match_join+ * Determine whether a join clause is of the right form to use in this join.+ *+ * We already know that the clause is a binary opclause referencing only the+ * rels in the current join. The point here is to check whether it has the+ * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",+ * rather than mixing outer and inner vars on either side. If it matches,+ * we set the transient flag outer_is_left to identify which side is which.+ */+static bool+clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids,+ Relids innerrelids)+{+ if (bms_is_subset(rinfo->left_relids, outerrelids) &&+ bms_is_subset(rinfo->right_relids, innerrelids))+ {+ /* lefthand side is outer */+ rinfo->outer_is_left = true;+ return true;+ }+ else if (bms_is_subset(rinfo->left_relids, innerrelids) &&+ bms_is_subset(rinfo->right_relids, outerrelids))+ {+ /* righthand side is outer */+ rinfo->outer_is_left = false;+ return true;+ }+ return false; /* no good for these input relations */+}++/*+ * get_exprs_from_uniquekey+ * Unify the way of get List of exprs from a one-row UniqueKey or+ * normal UniqueKey. Return a List of exprs.+ *+ * rel1: The relation which you want to get the exprs.+ * ukey: The UniqueKey you want to get the exprs.+ */+static List *+get_exprs_from_uniquekey(RelOptInfo *joinrel, RelOptInfo *rel1, UniqueKey *ukey)+{+ ListCell *lc;+ bool onerow = rel1 != NULL && relation_is_onerow(rel1);++ List *res = NIL;+ Assert(onerow || ukey);+ if (onerow)+ {+ /* Only cares about the exprs still exist in joinrel */+ foreach(lc, joinrel->reltarget->exprs)+ {+ Bitmapset *relids = pull_varnos(lfirst(lc));+ if (bms_is_subset(relids, rel1->relids))+ {+ res = lappend(res, list_make1(lfirst(lc)));+ }+ }+ }+ else+ {+ res = list_make1(ukey->exprs);+ }+ return res;+}++/*+ * Partitioned table Unique Keys.+ * The partition table unique key is maintained as:+ * 1. The index must be unique as usual.+ * 2. The index must contains partition key.+ * 3. The index must exist on all the child rel. see simple_indexinfo_equal for+ * how we compare it.+ */++/* index_constains_partkey+ * return true if the index contains the partiton key.+ */+static bool+index_constains_partkey(RelOptInfo *partrel, IndexOptInfo *ind)+{+ ListCell *lc;+ int i;+ Assert(IS_PARTITIONED_REL(partrel));++ for(i = 0; i < partrel->part_scheme->partnatts; i++)+ {+ Node *part_expr = linitial(partrel->partexprs[i]);+ bool found_in_index = false;+ foreach(lc, ind->indextlist)+ {+ Expr *index_expr = lfirst_node(TargetEntry, lc)->expr;+ if (equal(index_expr, part_expr))+ {+ found_in_index = true;+ break;+ }+ }+ if (!found_in_index)+ return false;+ }+ return true;+}++/*+ * simple_indexinfo_equal+ *+ * Used to check if the 2 index is same as each other. The index here+ * is COPIED from childrel and did some tiny changes(see+ * simple_copy_indexinfo_to_parent)+ */+static bool+simple_indexinfo_equal(IndexOptInfo *ind1, IndexOptInfo *ind2)+{+ Size oid_cmp_len = sizeof(Oid) * ind1->ncolumns;+ return ind1->ncolumns == ind2->ncolumns &&+ ind1->unique == ind2->unique &&+ memcmp(ind1->indexkeys, ind2->indexkeys, sizeof(int) * ind1->ncolumns) == 0 &&+ memcmp(ind1->opfamily, ind2->opfamily, oid_cmp_len) == 0 &&+ memcmp(ind1->opcintype, ind2->opcintype, oid_cmp_len) == 0 &&+ memcmp(ind1->sortopfamily, ind2->sortopfamily, oid_cmp_len) == 0 &&+ equal(ind1->indextlist, ind2->indextlist);+}+++/*+ * The below macros are used for simple_copy_indexinfo_to_parent which is so+ * customized that I don't want to put it to copyfuncs.c. So copy it here.+ */+#define COPY_POINTER_FIELD(fldname, sz) \+ do { \+ Size _size = (sz); \+ newnode->fldname = palloc(_size); \+ memcpy(newnode->fldname, from->fldname, _size); \+ } while (0)++#define COPY_NODE_FIELD(fldname) \+ (newnode->fldname = copyObjectImpl(from->fldname))++#define COPY_SCALAR_FIELD(fldname) \+ (newnode->fldname = from->fldname)+++/*+ * simple_copy_indexinfo_to_parent (from partition)+ * Copy the IndexInfo from child relation to parent relation with some modification,+ * which is used to test:+ * 1. If the same index exists in all the childrels.+ * 2. If the parentrel->reltarget/basicrestrict info matches this index.+ */+static IndexOptInfo *+simple_copy_indexinfo_to_parent(RelOptInfo *parentrel,+ IndexOptInfo *from)+{+ IndexOptInfo *newnode = makeNode(IndexOptInfo);++ COPY_SCALAR_FIELD(ncolumns);+ COPY_SCALAR_FIELD(nkeycolumns);+ COPY_SCALAR_FIELD(unique);+ COPY_SCALAR_FIELD(immediate);+ /* We just need to know if it is NIL or not */+ COPY_SCALAR_FIELD(indpred);+ COPY_SCALAR_FIELD(predOK);+ COPY_POINTER_FIELD(indexkeys, from->ncolumns * sizeof(int));+ COPY_POINTER_FIELD(indexcollations, from->ncolumns * sizeof(Oid));+ COPY_POINTER_FIELD(opfamily, from->ncolumns * sizeof(Oid));+ COPY_POINTER_FIELD(opcintype, from->ncolumns * sizeof(Oid));+ COPY_POINTER_FIELD(sortopfamily, from->ncolumns * sizeof(Oid));+ COPY_NODE_FIELD(indextlist);++ /*+ * Change relid from partition relid to parent relid so that the later+ * index match work.+ */+ ChangeVarNodes((Node*) newnode->indextlist,+ from->rel->relid,+ parentrel->relid, 0);+ newnode->rel = parentrel;+ return newnode;+}++/*+ * adjust_partition_unique_indexlist+ *+ * global_unique_indexes: At the beginning, it contains the copy & modified+ * unique index from the first partition. And then check if each index in it still+ * exists in the following partitions. If no, remove it. at last, it has an+ * index list which exists in all the partitions.+ */+static void+adjust_partition_unique_indexlist(RelOptInfo *parentrel,+ RelOptInfo *childrel,+ List **global_unique_indexes)+{+ ListCell *lc, *lc2;+ foreach(lc, *global_unique_indexes)+ {+ IndexOptInfo *g_ind = lfirst_node(IndexOptInfo, lc);+ bool found_in_child = false;++ foreach(lc2, childrel->indexlist)+ {+ IndexOptInfo *p_ind = lfirst_node(IndexOptInfo, lc2);+ IndexOptInfo *p_ind_copy;+ if (!p_ind->unique || !p_ind->immediate ||+ (p_ind->indpred != NIL && !p_ind->predOK))+ continue;+ p_ind_copy = simple_copy_indexinfo_to_parent(parentrel, p_ind);+ if (simple_indexinfo_equal(p_ind_copy, g_ind))+ {+ found_in_child = true;+ break;+ }+ }++ if (!found_in_child)+ /* There is no same index on other childrel, remove it */+ *global_unique_indexes = foreach_delete_current(*global_unique_indexes, lc);+ }+}++/* Helper function for groupres/distinctrel */+static void+add_uniquekey_from_sortgroups(PlannerInfo *root, RelOptInfo *rel, List *sortgroups)+{+ Query *parse = root->parse;+ List *exprs;++ /* XXX: If there are some vars which is not in current levelsup, the semantic is+ * imprecise, should we avoid it? levelsup = 1 is just a demo, maybe we need to+ * check every level other than 0, if so, we need write another pull_var_walker.+ */+ List *upper_vars = pull_vars_of_level((Node*)sortgroups, 1);++ if (upper_vars != NIL)+ return;++ exprs = get_sortgrouplist_exprs(sortgroups, parse->targetList);+ rel->uniquekeys = lappend(rel->uniquekeys,+ makeUniqueKey(exprs,+ false, /* sortgroupclause can't be multi_nullvals */+ false));++}+++/*+ * add_combined_uniquekey+ * The combination of both UniqueKeys is a valid UniqueKey for joinrel no matter+ * the jointype.+ * Note: This function is called when either single side of the UniqueKeys is not+ * valid any more after join.+ */+bool+add_combined_uniquekey(RelOptInfo *joinrel,+ RelOptInfo *outer_rel,+ RelOptInfo *inner_rel,+ UniqueKey *outer_ukey,+ UniqueKey *inner_ukey,+ JoinType jointype)+{++ ListCell *lc1, *lc2;++ /* Either side has multi_nullvals, the combined UniqueKey has multi_nullvals */+ bool multi_nullvals = outer_ukey->multi_nullvals || inner_ukey->multi_nullvals;++ /* If we have outer join, it implies we will have mutli_nullvals */+ multi_nullvals = multi_nullvals || IS_OUTER_JOIN(jointype);++ /* The only case we can get onerow joinrel after join */+ if (outer_ukey->onerow && inner_ukey->onerow && jointype == JOIN_INNER)+ {+ add_uniquekey_for_onerow(joinrel);+ return true;+ }++ foreach(lc1, get_exprs_from_uniquekey(joinrel, outer_rel, outer_ukey))+ {+ foreach(lc2, get_exprs_from_uniquekey(joinrel, inner_rel, inner_ukey))+ {+ List *exprs = list_concat_copy(lfirst_node(List, lc1), lfirst_node(List, lc2));+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ makeUniqueKey(exprs,+ multi_nullvals,+ false));+ }+ }+ return false;+}diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.cindex 357850624c..370903ef5e 100644--- a/src/backend/optimizer/plan/planner.c+++ b/src/backend/optimizer/plan/planner.c@@ -2389,6 +2389,8 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
add_path(final_rel, path);
}
+ simple_copy_uniquekeys(current_rel, final_rel);+
/*
* Generate partial paths for final_rel, too, if outer query levels might
* be able to make use of them.
@@ -3899,6 +3901,8 @@ create_grouping_paths(PlannerInfo *root,
}
set_cheapest(grouped_rel);
++ populate_grouprel_uniquekeys(root, grouped_rel);
return grouped_rel;
}
@@ -4616,7 +4620,7 @@ create_window_paths(PlannerInfo *root,
/* Now choose the best path(s) */
set_cheapest(window_rel);
-+ simple_copy_uniquekeys(input_rel, window_rel);
return window_rel;
}
@@ -4912,7 +4916,7 @@ create_distinct_paths(PlannerInfo *root,
/* Now choose the best path(s) */
set_cheapest(distinct_rel);
-+ populate_distinctrel_uniquekeys(root, input_rel, distinct_rel);
return distinct_rel;
}
@@ -5173,6 +5177,8 @@ create_ordered_paths(PlannerInfo *root,
*/
Assert(ordered_rel->pathlist != NIL);
+ simple_copy_uniquekeys(input_rel, ordered_rel);+
return ordered_rel;
}
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.cindex 951aed80e7..e94e92937c 100644--- a/src/backend/optimizer/prep/prepunion.c+++ b/src/backend/optimizer/prep/prepunion.c@@ -689,6 +689,8 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
/* Undo effects of possibly forcing tuple_fraction to 0 */
root->tuple_fraction = save_fraction;
+ /* Add the UniqueKeys */+ populate_unionrel_uniquekeys(root, result_rel);
return result_rel;
}
diff --git a/src/include/nodes/makefuncs.h b/src/include/nodes/makefuncs.hindex 31d9aedeeb..33f6ddc948 100644--- a/src/include/nodes/makefuncs.h+++ b/src/include/nodes/makefuncs.h@@ -16,6 +16,7 @@
#include "nodes/execnodes.h"
#include "nodes/parsenodes.h"
+#include "nodes/pathnodes.h"
extern A_Expr *makeA_Expr(A_Expr_Kind kind, List *name,
@@ -105,4 +106,6 @@ extern GroupingSet *makeGroupingSet(GroupingSetKind kind, List *content, int loc
extern VacuumRelation *makeVacuumRelation(RangeVar *relation, Oid oid, List *va_cols);
+extern UniqueKey* makeUniqueKey(List *exprs, bool multi_nullvals, bool onerow);+
#endif /* MAKEFUNC_H */
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.hindex 381d84b4e4..41110ed888 100644--- a/src/include/nodes/nodes.h+++ b/src/include/nodes/nodes.h@@ -264,6 +264,7 @@ typedef enum NodeTag
T_EquivalenceMember,
T_PathKey,
T_PathTarget,
+ T_UniqueKey,
T_RestrictInfo,
T_IndexClause,
T_PlaceHolderVar,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.hindex 9e3ebd488a..675956f06d 100644--- a/src/include/nodes/pathnodes.h+++ b/src/include/nodes/pathnodes.h@@ -730,6 +730,7 @@ typedef struct RelOptInfo
QualCost baserestrictcost; /* cost of evaluating the above */
Index baserestrict_min_security; /* min security_level found in
* baserestrictinfo */
+ List *uniquekeys; /* List of UniqueKey */
List *joininfo; /* RestrictInfo structures for join clauses
* involving this rel */
bool has_eclass_joins; /* T means joininfo is incomplete */
@@ -1047,6 +1048,31 @@ typedef struct PathKey
} PathKey;
+/*+ * UniqueKey+ *+ * Represents the unique properties held by a RelOptInfo.+ *+ * exprs is a list of exprs which is unique on current RelOptInfo.+ * multi_nullvals: true means multi null values may exists in these exprs, so the+ * uniqueness is not guaranteed in this case. This field is necessary for+ * remove_useless_join & reduce_unique_semijoins where we don't mind these+ * duplicated NULL values. It is set to true for 2 cases. One is a unique key+ * from a unique index but the related column is nullable. The other one is for+ * outer join. see populate_joinrel_uniquekeys for detail.+ * onerow means the related relation return 1 row only. Like filter with unique+ * index, aggregate without group node, join 2 1-row relations. An optimization+ * is if the onerow is set to true, we will set not record every expr as a UniqueKey,+ * we store exprs as a NIL instead.+ */+typedef struct UniqueKey+{+ NodeTag type;+ List *exprs;+ bool multi_nullvals;+ bool onerow;+} UniqueKey;+
/*
* PathTarget
*
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.hindex 14ea2766ad..621f54a9f8 100644--- a/src/include/nodes/pg_list.h+++ b/src/include/nodes/pg_list.h@@ -528,6 +528,8 @@ extern bool list_member_ptr(const List *list, const void *datum);
extern bool list_member_int(const List *list, int datum);
extern bool list_member_oid(const List *list, Oid datum);
+extern bool list_is_subset(const List *members, const List *target);+
extern List *list_delete(List *list, void *datum);
extern List *list_delete_ptr(List *list, void *datum);
extern List *list_delete_int(List *list, int datum);
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.hindex 3e4171056e..9445141263 100644--- a/src/include/optimizer/optimizer.h+++ b/src/include/optimizer/optimizer.h@@ -23,6 +23,7 @@
#define OPTIMIZER_H
#include "nodes/parsenodes.h"
+#include "nodes/pathnodes.h"
/*
* We don't want to include nodes/pathnodes.h here, because non-planner
@@ -156,6 +157,7 @@ extern TargetEntry *get_sortgroupref_tle(Index sortref,
List *targetList);
extern TargetEntry *get_sortgroupclause_tle(SortGroupClause *sgClause,
List *targetList);
+extern Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle);
extern Node *get_sortgroupclause_expr(SortGroupClause *sgClause,
List *targetList);
extern List *get_sortgrouplist_exprs(List *sgClauses,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.hindex 10b6e81079..651e48acbb 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -241,4 +241,39 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root,
extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
List *live_childrels);
+/*+ * uniquekeys.c+ * Utilities for matching and building unique keys+ */+extern void populate_baserel_uniquekeys(PlannerInfo *root,+ RelOptInfo *baserel,+ List* unique_index_list);+extern void populate_partitionedrel_uniquekeys(PlannerInfo *root,+ RelOptInfo *rel,+ List *childrels);+extern void populate_distinctrel_uniquekeys(PlannerInfo *root,+ RelOptInfo *inputrel,+ RelOptInfo *distinctrel);+extern void populate_grouprel_uniquekeys(PlannerInfo *root,+ RelOptInfo *grouprel);+extern void populate_unionrel_uniquekeys(PlannerInfo *root,+ RelOptInfo *unionrel);+extern void simple_copy_uniquekeys(RelOptInfo *oldrel,+ RelOptInfo *newrel);+extern void convert_subquery_uniquekeys(PlannerInfo *root,+ RelOptInfo *currel,+ RelOptInfo *sub_final_rel);+extern void populate_joinrel_uniquekeys(PlannerInfo *root,+ RelOptInfo *joinrel,+ RelOptInfo *rel1,+ RelOptInfo *rel2,+ List *restrictlist,+ JoinType jointype);++extern bool relation_has_uniquekeys_for(PlannerInfo *root,+ RelOptInfo *rel,+ List *exprs,+ bool allow_multinulls);+extern bool relation_is_onerow(RelOptInfo *rel);+
#endif /* PATHS_H */
--
2.21.0
[text/x-diff] v35-0001-Extend-UniqueKeys.patch (13.0K, ../20200609102247.jdlatmfyeecg52fi@localhost/4-v35-0001-Extend-UniqueKeys.patch)
download | inline diff:
From fef5a9e20249b60b2979635f2c487c3f1c810715 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:33:56 +0200
Subject: [PATCH v35 3/6] Extend UniqueKeys
Prepares index skip scan implementation using UniqueKeys. Allows to
specify what are the "requested" keys that should be unique, and add
them to necessary Paths to make them useful later.
Proposed by David Rowley, contains few bits out of previous version from
Jesper Pedersen.
---
src/backend/optimizer/path/pathkeys.c | 59 +++++++++++++++++++++
src/backend/optimizer/path/uniquekeys.c | 68 +++++++++++++++++++++++++
src/backend/optimizer/plan/planner.c | 38 +++++++++++++-
src/backend/optimizer/util/pathnode.c | 32 +++++++++---
src/include/nodes/pathnodes.h | 5 ++
src/include/optimizer/pathnode.h | 1 +
src/include/optimizer/paths.h | 8 +++
7 files changed, 201 insertions(+), 10 deletions(-)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.cindex 7e596d4194..a4fc4f252d 100644--- a/src/backend/optimizer/path/pathkeys.c+++ b/src/backend/optimizer/path/pathkeys.c@@ -29,6 +29,7 @@
#include "utils/lsyscache.h"
+static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys);
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
static bool matches_boolean_partition_clause(RestrictInfo *rinfo,
RelOptInfo *partrel,
@@ -95,6 +96,29 @@ make_canonical_pathkey(PlannerInfo *root,
return pk;
}
+/*+ * pathkey_is_unique+ * Checks if the new pathkey's equivalence class is the same as that of+ * any existing member of the pathkey list.+ */+static bool+pathkey_is_unique(PathKey *new_pathkey, List *pathkeys)+{+ EquivalenceClass *new_ec = new_pathkey->pk_eclass;+ ListCell *lc;++ /* If same EC already is already in the list, then not unique */+ foreach(lc, pathkeys)+ {+ PathKey *old_pathkey = (PathKey *) lfirst(lc);++ if (new_ec == old_pathkey->pk_eclass)+ return false;+ }++ return true;+}+
/*
* pathkey_is_redundant
* Is a pathkey redundant with one already in the given list?
@@ -1151,6 +1175,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root,
return pathkeys;
}
+/*+ * make_pathkeys_for_uniquekeyclauses+ * Generate a pathkeys list to be used for uniquekey clauses+ */+List *+make_pathkeys_for_uniquekeys(PlannerInfo *root,+ List *sortclauses,+ List *tlist)+{+ List *pathkeys = NIL;+ ListCell *l;++ foreach(l, sortclauses)+ {+ SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);+ Expr *sortkey;+ PathKey *pathkey;++ sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);+ Assert(OidIsValid(sortcl->sortop));+ pathkey = make_pathkey_from_sortop(root,+ sortkey,+ root->nullable_baserels,+ sortcl->sortop,+ sortcl->nulls_first,+ sortcl->tleSortGroupRef,+ true);++ if (pathkey_is_unique(pathkey, pathkeys))+ pathkeys = lappend(pathkeys, pathkey);+ }++ return pathkeys;+}+
/****************************************************************************
* PATHKEYS AND MERGECLAUSES
****************************************************************************/
diff --git a/src/backend/optimizer/path/uniquekeys.c b/src/backend/optimizer/path/uniquekeys.cindex 957af61819..e4fd088964 100644--- a/src/backend/optimizer/path/uniquekeys.c+++ b/src/backend/optimizer/path/uniquekeys.c@@ -1133,3 +1133,71 @@ add_combined_uniquekey(RelOptInfo *joinrel,
}
return false;
}
++List*+build_uniquekeys(PlannerInfo *root, List *sortclauses)+{+ List *result = NIL;+ List *sortkeys;+ ListCell *l;++ sortkeys = make_pathkeys_for_uniquekeys(root,+ sortclauses,+ root->processed_tlist);++ /* Create a uniquekey and add it to the list */+ foreach(l, sortkeys)+ {+ PathKey *pathkey = (PathKey *) lfirst(l);+ EquivalenceClass *ec = pathkey->pk_eclass;+ ListCell *k;+ List *exprs = NIL;++ foreach(k, ec->ec_members)+ {+ EquivalenceMember *mem = (EquivalenceMember *) lfirst(k);+ exprs = lappend(exprs, mem->em_expr);+ }++ result = lappend(result, makeUniqueKey(exprs, false, false));+ }++ return result;+}++bool+query_has_uniquekeys_for(PlannerInfo *root, List *pathkeys,+ bool allow_multinulls)+{+ ListCell *lc;+ List *exprs = NIL;++ /* For UniqueKey->onerow case, the uniquekey->exprs is empty as well+ * so we can't rely on list_is_subset to handle this special cases+ */+ if (pathkeys == NIL)+ return false;++ foreach(lc, pathkeys)+ {+ PathKey *pathkey = (PathKey *) lfirst(lc);+ EquivalenceClass *ec = pathkey->pk_eclass;+ ListCell *k;++ foreach(k, ec->ec_members)+ {+ EquivalenceMember *mem = (EquivalenceMember *) lfirst(k);+ exprs = lappend(exprs, mem->em_expr);+ }+ }++ foreach(lc, root->query_uniquekeys)+ {+ UniqueKey *ukey = lfirst_node(UniqueKey, lc);+ if (ukey->multi_nullvals && !allow_multinulls)+ continue;+ if (list_is_subset(ukey->exprs, exprs))+ return true;+ }+ return false;+}diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.cindex 370903ef5e..812bd99e6e 100644--- a/src/backend/optimizer/plan/planner.c+++ b/src/backend/optimizer/plan/planner.c@@ -3663,9 +3663,17 @@ standard_qp_callback(PlannerInfo *root, void *extra)
root->query_pathkeys = root->window_pathkeys;
else if (list_length(root->distinct_pathkeys) >
list_length(root->sort_pathkeys))
+ {
root->query_pathkeys = root->distinct_pathkeys;
+ root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause);+ }
else if (root->sort_pathkeys)
+ {
root->query_pathkeys = root->sort_pathkeys;
++ if (root->distinct_pathkeys)+ root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause);+ }
else
root->query_pathkeys = NIL;
}
@@ -4816,13 +4824,19 @@ create_distinct_paths(PlannerInfo *root,
Path *path = (Path *) lfirst(lc);
if (pathkeys_contained_in(needed_pathkeys, path->pathkeys))
- {
add_path(distinct_rel, (Path *)
create_upper_unique_path(root, distinct_rel,
path,
list_length(root->distinct_pathkeys),
numDistinctRows));
- }+ }++ foreach(lc, input_rel->unique_pathlist)+ {+ Path *path = (Path *) lfirst(lc);++ if (query_has_uniquekeys_for(root, needed_pathkeys, false))+ add_path(distinct_rel, path);
}
/* For explicit-sort case, always use the more rigorous clause */
@@ -7514,6 +7528,26 @@ apply_scanjoin_target_to_paths(PlannerInfo *root,
}
}
+ foreach(lc, rel->unique_pathlist)+ {+ Path *subpath = (Path *) lfirst(lc);++ /* Shouldn't have any parameterized paths anymore */+ Assert(subpath->param_info == NULL);++ if (tlist_same_exprs)+ subpath->pathtarget->sortgrouprefs =+ scanjoin_target->sortgrouprefs;+ else+ {+ Path *newpath;++ newpath = (Path *) create_projection_path(root, rel, subpath,+ scanjoin_target);+ lfirst(lc) = newpath;+ }+ }+
/*
* Now, if final scan/join target contains SRFs, insert ProjectSetPath(s)
* atop each existing path. (Note that this function doesn't look at the
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.cindex e845a4b1ae..60656bdca5 100644--- a/src/backend/optimizer/util/pathnode.c+++ b/src/backend/optimizer/util/pathnode.c@@ -416,10 +416,10 @@ set_cheapest(RelOptInfo *parent_rel)
* 'parent_rel' is the relation entry to which the path corresponds.
* 'new_path' is a potential path for parent_rel.
*
- * Returns nothing, but modifies parent_rel->pathlist.+ * Returns modified pathlist.
*/
-void-add_path(RelOptInfo *parent_rel, Path *new_path)+static List *+add_path_to(RelOptInfo *parent_rel, List *pathlist, Path *new_path)
{
bool accept_new = true; /* unless we find a superior old path */
int insert_at = 0; /* where to insert new item */
@@ -440,7 +440,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
* for more than one old path to be tossed out because new_path dominates
* it.
*/
- foreach(p1, parent_rel->pathlist)+ foreach(p1, pathlist)
{
Path *old_path = (Path *) lfirst(p1);
bool remove_old = false; /* unless new proves superior */
@@ -584,8 +584,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
*/
if (remove_old)
{
- parent_rel->pathlist = foreach_delete_current(parent_rel->pathlist,- p1);+ pathlist = foreach_delete_current(pathlist, p1);
/*
* Delete the data pointed-to by the deleted cell, if possible
@@ -612,8 +611,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
if (accept_new)
{
/* Accept the new path: insert it at proper place in pathlist */
- parent_rel->pathlist =- list_insert_nth(parent_rel->pathlist, insert_at, new_path);+ pathlist = list_insert_nth(pathlist, insert_at, new_path);
}
else
{
@@ -621,6 +619,23 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
if (!IsA(new_path, IndexPath))
pfree(new_path);
}
++ return pathlist;+}++void+add_path(RelOptInfo *parent_rel, Path *new_path)+{+ parent_rel->pathlist = add_path_to(parent_rel,+ parent_rel->pathlist, new_path);+}++void+add_unique_path(RelOptInfo *parent_rel, Path *new_path)+{+ parent_rel->unique_pathlist = add_path_to(parent_rel,+ parent_rel->unique_pathlist,+ new_path);
}
/*
@@ -2539,6 +2554,7 @@ create_projection_path(PlannerInfo *root,
pathnode->path.pathkeys = subpath->pathkeys;
pathnode->subpath = subpath;
+ pathnode->path.uniquekeys = subpath->uniquekeys;
/*
* We might not need a separate Result node. If the input plan node type
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.hindex 675956f06d..455d9d64ba 100644--- a/src/include/nodes/pathnodes.h+++ b/src/include/nodes/pathnodes.h@@ -297,6 +297,7 @@ struct PlannerInfo
List *query_pathkeys; /* desired pathkeys for query_planner() */
+ List *query_uniquekeys; /* unique keys required for the query */
List *group_pathkeys; /* groupClause pathkeys, if any */
List *window_pathkeys; /* pathkeys of bottom window, if any */
List *distinct_pathkeys; /* distinctClause pathkeys, if any */
@@ -679,6 +680,7 @@ typedef struct RelOptInfo
List *pathlist; /* Path structures */
List *ppilist; /* ParamPathInfos used in pathlist */
List *partial_pathlist; /* partial Paths */
+ List *unique_pathlist; /* unique Paths */
struct Path *cheapest_startup_path;
struct Path *cheapest_total_path;
struct Path *cheapest_unique_path;
@@ -866,6 +868,7 @@ struct IndexOptInfo
bool amsearchnulls; /* can AM search for NULL/NOT NULL entries? */
bool amhasgettuple; /* does AM have amgettuple interface? */
bool amhasgetbitmap; /* does AM have amgetbitmap interface? */
+ bool amcanskip; /* can AM skip duplicate values? */
bool amcanparallel; /* does AM support parallel scan? */
/* Rather than include amapi.h here, we declare amcostestimate like this */
void (*amcostestimate) (); /* AM's cost estimator */
@@ -1185,6 +1188,8 @@ typedef struct Path
List *pathkeys; /* sort ordering of path's output */
/* pathkeys is a List of PathKey nodes; see above */
++ List *uniquekeys; /* the unique keys, or NIL if none */
} Path;
/* Macro for extracting a path's parameterization relids; beware double eval */
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.hindex 715a24ad29..6796ad8cb7 100644--- a/src/include/optimizer/pathnode.h+++ b/src/include/optimizer/pathnode.h@@ -27,6 +27,7 @@ extern int compare_fractional_path_costs(Path *path1, Path *path2,
double fraction);
extern void set_cheapest(RelOptInfo *parent_rel);
extern void add_path(RelOptInfo *parent_rel, Path *new_path);
+extern void add_unique_path(RelOptInfo *parent_rel, Path *new_path);
extern bool add_path_precheck(RelOptInfo *parent_rel,
Cost startup_cost, Cost total_cost,
List *pathkeys, Relids required_outer);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.hindex 651e48acbb..686193fd81 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -215,6 +215,9 @@ extern List *build_join_pathkeys(PlannerInfo *root,
extern List *make_pathkeys_for_sortclauses(PlannerInfo *root,
List *sortclauses,
List *tlist);
+extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root,+ List *sortclauses,+ List *tlist);
extern void initialize_mergeclause_eclasses(PlannerInfo *root,
RestrictInfo *restrictinfo);
extern void update_mergeclause_eclasses(PlannerInfo *root,
@@ -274,6 +277,11 @@ extern bool relation_has_uniquekeys_for(PlannerInfo *root,
RelOptInfo *rel,
List *exprs,
bool allow_multinulls);
+extern bool query_has_uniquekeys_for(PlannerInfo *root,+ List *exprs,+ bool allow_multinulls);
extern bool relation_is_onerow(RelOptInfo *rel);
+extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses);+
#endif /* PATHS_H */
--
2.21.0
[text/x-diff] v35-0002-Index-skip-scan.patch (38.4K, ../20200609102247.jdlatmfyeecg52fi@localhost/5-v35-0002-Index-skip-scan.patch)
download | inline diff:
From 2ae3b43a94f93ea447fce1b78ad27d1c7ba36862 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:39:13 +0200
Subject: [PATCH v35 4/6] Index skip scan
Implementation of basic Index Skip Scan (see Loose Index Scan in the
wiki [1]) infrastructure on top of IndexOnlyScan and IndexScan.
Introduces a new index am function amskip to allow advance past
duplicate key values in a scan. This innocently looking description
could be a bit tricky on the edge between am specific and common parts
of the implementation, mostly due to different information available at
each level, e.g. visibility. This means the common parts should apply
skipping multiple times if necessary.
Original patch and design were proposed by Thomas Munro [2], revived and
improved by Dmitry Dolgov and Jesper Pedersen.
[1] https://wiki.postgresql.org/wiki/Loose_indexscan
[2] https://www.postgresql.org/message-id/flat/CADLWmXXbTSBxP-MzJuPAYSsL_2f0iPm5VWPbCvDbVvfX93FKkw%40mail.gmail.com
Author: Jesper Pedersen, Dmitry Dolgov
Reviewed-by: Thomas Munro, David Rowley, Floris Van Nee, Kyotaro Horiguchi, Tomas Vondra, Peter Geoghegan
---
contrib/bloom/blutils.c | 1 +
doc/src/sgml/indexam.sgml | 1 +
src/backend/access/brin/brin.c | 1 +
src/backend/access/gin/ginutil.c | 1 +
src/backend/access/gist/gist.c | 1 +
src/backend/access/hash/hash.c | 1 +
src/backend/access/index/indexam.c | 18 ++++
src/backend/access/spgist/spgutils.c | 1 +
src/backend/commands/explain.c | 25 +++++
src/backend/executor/nodeIndexonlyscan.c | 97 ++++++++++++++++++-
src/backend/executor/nodeIndexscan.c | 56 ++++++++++-
src/backend/nodes/copyfuncs.c | 2 +
src/backend/nodes/outfuncs.c | 2 +
src/backend/nodes/readfuncs.c | 2 +
src/backend/optimizer/path/costsize.c | 1 +
src/backend/optimizer/path/indxpath.c | 96 ++++++++++++++++++
src/backend/optimizer/plan/createplan.c | 20 ++--
src/backend/optimizer/util/pathnode.c | 64 ++++++++++++
src/backend/optimizer/util/plancat.c | 1 +
src/backend/utils/misc/guc.c | 9 ++
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/access/amapi.h | 8 ++
src/include/access/genam.h | 2 +
src/include/access/sdir.h | 7 ++
src/include/nodes/execnodes.h | 6 ++
src/include/nodes/pathnodes.h | 4 +
src/include/nodes/plannodes.h | 4 +
src/include/optimizer/cost.h | 1 +
src/include/optimizer/pathnode.h | 4 +
src/test/regress/expected/sysviews.out | 3 +-
30 files changed, 429 insertions(+), 11 deletions(-)
diff --git a/contrib/bloom/blutils.c b/contrib/bloom/blutils.cindex d3bf8665df..4eec21b99e 100644--- a/contrib/bloom/blutils.c+++ b/contrib/bloom/blutils.c@@ -134,6 +134,7 @@ blhandler(PG_FUNCTION_ARGS)
amroutine->ambulkdelete = blbulkdelete;
amroutine->amvacuumcleanup = blvacuumcleanup;
amroutine->amcanreturn = NULL;
+ amroutine->amskip = NULL;
amroutine->amcostestimate = blcostestimate;
amroutine->amoptions = bloptions;
amroutine->amproperty = NULL;
diff --git a/doc/src/sgml/indexam.sgml b/doc/src/sgml/indexam.sgmlindex 37f8d8760a..6844a4d5c8 100644--- a/doc/src/sgml/indexam.sgml+++ b/doc/src/sgml/indexam.sgml@@ -148,6 +148,7 @@ typedef struct IndexAmRoutine
amendscan_function amendscan;
ammarkpos_function ammarkpos; /* can be NULL */
amrestrpos_function amrestrpos; /* can be NULL */
+ amskip_function amskip; /* can be NULL */
/* interface functions to support parallel index scans */
amestimateparallelscan_function amestimateparallelscan; /* can be NULL */
diff --git a/src/backend/access/brin/brin.c b/src/backend/access/brin/brin.cindex 7db3ae5ee0..e3e09efa31 100644--- a/src/backend/access/brin/brin.c+++ b/src/backend/access/brin/brin.c@@ -115,6 +115,7 @@ brinhandler(PG_FUNCTION_ARGS)
amroutine->ambulkdelete = brinbulkdelete;
amroutine->amvacuumcleanup = brinvacuumcleanup;
amroutine->amcanreturn = NULL;
+ amroutine->amskip = NULL;
amroutine->amcostestimate = brincostestimate;
amroutine->amoptions = brinoptions;
amroutine->amproperty = NULL;
diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.cindex a400f1fedb..7e83a8ee58 100644--- a/src/backend/access/gin/ginutil.c+++ b/src/backend/access/gin/ginutil.c@@ -66,6 +66,7 @@ ginhandler(PG_FUNCTION_ARGS)
amroutine->ambulkdelete = ginbulkdelete;
amroutine->amvacuumcleanup = ginvacuumcleanup;
amroutine->amcanreturn = NULL;
+ amroutine->amskip = NULL;
amroutine->amcostestimate = gincostestimate;
amroutine->amoptions = ginoptions;
amroutine->amproperty = NULL;
diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.cindex 79fe6eb8d6..6fe9f8f5a9 100644--- a/src/backend/access/gist/gist.c+++ b/src/backend/access/gist/gist.c@@ -87,6 +87,7 @@ gisthandler(PG_FUNCTION_ARGS)
amroutine->ambulkdelete = gistbulkdelete;
amroutine->amvacuumcleanup = gistvacuumcleanup;
amroutine->amcanreturn = gistcanreturn;
+ amroutine->amskip = NULL;
amroutine->amcostestimate = gistcostestimate;
amroutine->amoptions = gistoptions;
amroutine->amproperty = gistproperty;
diff --git a/src/backend/access/hash/hash.c b/src/backend/access/hash/hash.cindex 3ec6d528e7..85d44ee58d 100644--- a/src/backend/access/hash/hash.c+++ b/src/backend/access/hash/hash.c@@ -84,6 +84,7 @@ hashhandler(PG_FUNCTION_ARGS)
amroutine->ambulkdelete = hashbulkdelete;
amroutine->amvacuumcleanup = hashvacuumcleanup;
amroutine->amcanreturn = NULL;
+ amroutine->amskip = NULL;
amroutine->amcostestimate = hashcostestimate;
amroutine->amoptions = hashoptions;
amroutine->amproperty = NULL;
diff --git a/src/backend/access/index/indexam.c b/src/backend/access/index/indexam.cindex 6b9750c244..c7b70997ff 100644--- a/src/backend/access/index/indexam.c+++ b/src/backend/access/index/indexam.c@@ -33,6 +33,7 @@
* index_can_return - does index support index-only scans?
* index_getprocid - get a support procedure OID
* index_getprocinfo - get a support procedure's lookup info
+ * index_skip - advance past duplicate key values in a scan
*
* NOTES
* This file contains the index_ routines which used
@@ -736,6 +737,23 @@ index_can_return(Relation indexRelation, int attno)
return indexRelation->rd_indam->amcanreturn(indexRelation, attno);
}
+/* ----------------+ * index_skip+ *+ * Skip past all tuples where the first 'prefix' columns have the+ * same value as the last tuple returned in the current scan.+ * ----------------+ */+bool+index_skip(IndexScanDesc scan, ScanDirection direction,+ ScanDirection indexdir, bool scanstart, int prefix)+{+ SCAN_CHECKS;++ return scan->indexRelation->rd_indam->amskip(scan, direction,+ indexdir, scanstart, prefix);+}+
/* ----------------
* index_getprocid
*
diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.cindex 0efe05e552..0491ea172a 100644--- a/src/backend/access/spgist/spgutils.c+++ b/src/backend/access/spgist/spgutils.c@@ -69,6 +69,7 @@ spghandler(PG_FUNCTION_ARGS)
amroutine->ambulkdelete = spgbulkdelete;
amroutine->amvacuumcleanup = spgvacuumcleanup;
amroutine->amcanreturn = spgcanreturn;
+ amroutine->amskip = NULL;
amroutine->amcostestimate = spgcostestimate;
amroutine->amoptions = spgoptions;
amroutine->amproperty = spgproperty;
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.cindex efd7201d61..f1551b5f9e 100644--- a/src/backend/commands/explain.c+++ b/src/backend/commands/explain.c@@ -148,6 +148,7 @@ static void ExplainXMLTag(const char *tagname, int flags, ExplainState *es);
static void ExplainIndentText(ExplainState *es);
static void ExplainJSONLineEnding(ExplainState *es);
static void ExplainYAMLLineStarting(ExplainState *es);
+static void ExplainIndexSkipScanKeys(int skipPrefixSize, ExplainState *es);
static void escape_yaml(StringInfo buf, const char *str);
@@ -1096,6 +1097,22 @@ ExplainPreScanNode(PlanState *planstate, Bitmapset **rels_used)
return planstate_tree_walker(planstate, ExplainPreScanNode, rels_used);
}
+/*+ * ExplainIndexSkipScanKeys -+ * Append information about index skip scan to es->str.+ *+ * Can be used to print the skip prefix size.+ */+static void+ExplainIndexSkipScanKeys(int skipPrefixSize, ExplainState *es)+{+ if (skipPrefixSize > 0)+ {+ if (es->format != EXPLAIN_FORMAT_TEXT)+ ExplainPropertyInteger("Distinct Prefix", NULL, skipPrefixSize, es);+ }+}+
/*
* ExplainNode -
* Appends a description of a plan tree to es->str
@@ -1433,6 +1450,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
{
IndexScan *indexscan = (IndexScan *) plan;
+ ExplainIndexSkipScanKeys(indexscan->indexskipprefixsize, es);+
ExplainIndexScanDetails(indexscan->indexid,
indexscan->indexorderdir,
es);
@@ -1443,6 +1462,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
{
IndexOnlyScan *indexonlyscan = (IndexOnlyScan *) plan;
+ ExplainIndexSkipScanKeys(indexonlyscan->indexskipprefixsize, es);+
ExplainIndexScanDetails(indexonlyscan->indexid,
indexonlyscan->indexorderdir,
es);
@@ -1702,6 +1723,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
switch (nodeTag(plan))
{
case T_IndexScan:
+ if (((IndexScan *) plan)->indexskipprefixsize > 0)+ ExplainPropertyBool("Skip scan", true, es);
show_scan_qual(((IndexScan *) plan)->indexqualorig,
"Index Cond", planstate, ancestors, es);
if (((IndexScan *) plan)->indexqualorig)
@@ -1715,6 +1738,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
planstate, es);
break;
case T_IndexOnlyScan:
+ if (((IndexOnlyScan *) plan)->indexskipprefixsize > 0)+ ExplainPropertyBool("Skip scan", true, es);
show_scan_qual(((IndexOnlyScan *) plan)->indexqual,
"Index Cond", planstate, ancestors, es);
if (((IndexOnlyScan *) plan)->indexqual)
diff --git a/src/backend/executor/nodeIndexonlyscan.c b/src/backend/executor/nodeIndexonlyscan.cindex 5617ac29e7..c4e4b087a7 100644--- a/src/backend/executor/nodeIndexonlyscan.c+++ b/src/backend/executor/nodeIndexonlyscan.c@@ -41,6 +41,7 @@
#include "miscadmin.h"
#include "storage/bufmgr.h"
#include "storage/predicate.h"
+#include "storage/itemptr.h"
#include "utils/memutils.h"
#include "utils/rel.h"
@@ -62,9 +63,26 @@ IndexOnlyNext(IndexOnlyScanState *node)
EState *estate;
ExprContext *econtext;
ScanDirection direction;
+ ScanDirection readDirection;
IndexScanDesc scandesc;
TupleTableSlot *slot;
ItemPointer tid;
+ ItemPointerData startTid;+ IndexOnlyScan *indexonlyscan = (IndexOnlyScan *) node->ss.ps.plan;++ /*+ * Tells if the current position was reached via skipping. In this case+ * there is no nead for the index_getnext_tid+ */+ bool skipped = false;++ /*+ * Index only scan must be aware that in case of skipping we can return to+ * the starting point due to visibility checks. In this situation we need+ * to jump further, and number of skipping attempts tell us how far do we+ * need to do so.+ */+ int skipAttempts = 0;
/*
* extract necessary information from index scan node
@@ -72,7 +90,7 @@ IndexOnlyNext(IndexOnlyScanState *node)
estate = node->ss.ps.state;
direction = estate->es_direction;
/* flip direction if this is an overall backward scan */
- if (ScanDirectionIsBackward(((IndexOnlyScan *) node->ss.ps.plan)->indexorderdir))+ if (ScanDirectionIsBackward(indexonlyscan->indexorderdir))
{
if (ScanDirectionIsForward(direction))
direction = BackwardScanDirection;
@@ -114,16 +132,87 @@ IndexOnlyNext(IndexOnlyScanState *node)
node->ioss_OrderByKeys,
node->ioss_NumOrderByKeys);
}
+ else+ {+ ItemPointerCopy(&scandesc->xs_heaptid, &startTid);+ }++ /*+ * Check if we need to skip to the next key prefix, because we've been+ * asked to implement DISTINCT.+ *+ * When fetching a cursor in the direction opposite to a general scan+ * direction, the result must be what normal fetching should have+ * returned, but in reversed order. In other words, return the last or+ * first scanned tuple in a DISTINCT set, depending on a cursor direction.+ * Due to that we skip also when the first tuple wasn't emitted yet, but+ * the directions are opposite.+ */+ if (node->ioss_SkipPrefixSize > 0 &&+ (node->ioss_FirstTupleEmitted ||+ ScanDirectionsAreOpposite(direction, indexonlyscan->indexorderdir)))+ {+ if (!index_skip(scandesc, direction, indexonlyscan->indexorderdir,+ !node->ioss_FirstTupleEmitted, node->ioss_SkipPrefixSize))+ {+ /*+ * Reached end of index. At this point currPos is invalidated, and+ * we need to reset ioss_FirstTupleEmitted, since otherwise after+ * going backwards, reaching the end of index, and going forward+ * again we apply skip again. It would be incorrect and lead to an+ * extra skipped item.+ */+ node->ioss_FirstTupleEmitted = false;+ return ExecClearTuple(slot);+ }+ else+ {+ skipAttempts = 1;+ skipped = true;+ tid = &scandesc->xs_heaptid;+ }+ }++ readDirection = skipped ? indexonlyscan->indexorderdir : direction;
/*
* OK, now that we have what we need, fetch the next tuple.
*/
- while ((tid = index_getnext_tid(scandesc, direction)) != NULL)+ while (skipped || (tid = index_getnext_tid(scandesc, readDirection)) != NULL)
{
bool tuple_from_heap = false;
CHECK_FOR_INTERRUPTS();
+ /*+ * While doing index only skip scan with advancing and reading in+ * different directions we can return to the same position where we+ * started after visibility check. Recognize such situations and skip+ * more.+ */+ if ((readDirection != direction) &&+ ItemPointerIsValid(&startTid) && ItemPointerEquals(&startTid, tid))+ {+ int i;+ skipAttempts += 1;++ for (i = 0; i < skipAttempts; i++)+ {+ if (!index_skip(scandesc, direction,+ indexonlyscan->indexorderdir,+ !node->ioss_FirstTupleEmitted,+ node->ioss_SkipPrefixSize))+ {+ node->ioss_FirstTupleEmitted = false;+ return ExecClearTuple(slot);+ }+ }++ tid = &scandesc->xs_heaptid;+ }++ skipped = false;+
/*
* We can skip the heap fetch if the TID references a heap page on
* which all tuples are known visible to everybody. In any case,
@@ -250,6 +339,8 @@ IndexOnlyNext(IndexOnlyScanState *node)
ItemPointerGetBlockNumber(tid),
estate->es_snapshot);
+ node->ioss_FirstTupleEmitted = true;+
return slot;
}
@@ -504,6 +595,8 @@ ExecInitIndexOnlyScan(IndexOnlyScan *node, EState *estate, int eflags)
indexstate->ss.ps.plan = (Plan *) node;
indexstate->ss.ps.state = estate;
indexstate->ss.ps.ExecProcNode = ExecIndexOnlyScan;
+ indexstate->ioss_SkipPrefixSize = node->indexskipprefixsize;+ indexstate->ioss_FirstTupleEmitted = false;
/*
* Miscellaneous initialization
diff --git a/src/backend/executor/nodeIndexscan.c b/src/backend/executor/nodeIndexscan.cindex d0a96a38e0..449aaec3ac 100644--- a/src/backend/executor/nodeIndexscan.c+++ b/src/backend/executor/nodeIndexscan.c@@ -85,6 +85,13 @@ IndexNext(IndexScanState *node)
ScanDirection direction;
IndexScanDesc scandesc;
TupleTableSlot *slot;
+ IndexScan *indexscan = (IndexScan *) node->ss.ps.plan;++ /*+ * tells if the current position was reached via skipping. In this case+ * there is no nead for the index_getnext_tid+ */+ bool skipped = false;
/*
* extract necessary information from index scan node
@@ -92,7 +99,7 @@ IndexNext(IndexScanState *node)
estate = node->ss.ps.state;
direction = estate->es_direction;
/* flip direction if this is an overall backward scan */
- if (ScanDirectionIsBackward(((IndexScan *) node->ss.ps.plan)->indexorderdir))+ if (ScanDirectionIsBackward(indexscan->indexorderdir))
{
if (ScanDirectionIsForward(direction))
direction = BackwardScanDirection;
@@ -117,6 +124,12 @@ IndexNext(IndexScanState *node)
node->iss_ScanDesc = scandesc;
+ /* Index skip scan assumes xs_want_itup, so set it to true */+ if (indexscan->indexskipprefixsize > 0)+ node->iss_ScanDesc->xs_want_itup = true;+ else+ node->iss_ScanDesc->xs_want_itup = false;+
/*
* If no run-time keys to calculate or they are ready, go ahead and
* pass the scankeys to the index AM.
@@ -127,12 +140,48 @@ IndexNext(IndexScanState *node)
node->iss_OrderByKeys, node->iss_NumOrderByKeys);
}
+ /*+ * Check if we need to skip to the next key prefix, because we've been+ * asked to implement DISTINCT.+ *+ * When fetching a cursor in the direction opposite to a general scan+ * direction, the result must be what normal fetching should have+ * returned, but in reversed order. In other words, return the last or+ * first scanned tuple in a DISTINCT set, depending on a cursor direction.+ * Due to that we skip also when the first tuple wasn't emitted yet, but+ * the directions are opposite.+ */+ if (node->iss_SkipPrefixSize > 0 &&+ (node->iss_FirstTupleEmitted ||+ ScanDirectionsAreOpposite(direction, indexscan->indexorderdir)))+ {+ if (!index_skip(scandesc, direction, indexscan->indexorderdir,+ !node->iss_FirstTupleEmitted, node->iss_SkipPrefixSize))+ {+ /*+ * Reached end of index. At this point currPos is invalidated, and+ * we need to reset iss_FirstTupleEmitted, since otherwise after+ * going backwards, reaching the end of index, and going forward+ * again we apply skip again. It would be incorrect and lead to an+ * extra skipped item.+ */+ node->iss_FirstTupleEmitted = false;+ return ExecClearTuple(slot);+ }+ else+ {+ skipped = true;+ index_fetch_heap(scandesc, slot);+ }+ }+
/*
* ok, now that we have what we need, fetch the next tuple.
*/
- while (index_getnext_slot(scandesc, direction, slot))+ while (skipped || index_getnext_slot(scandesc, direction, slot))
{
CHECK_FOR_INTERRUPTS();
+ skipped = false;
/*
* If the index was lossy, we have to recheck the index quals using
@@ -149,6 +198,7 @@ IndexNext(IndexScanState *node)
}
}
+ node->iss_FirstTupleEmitted = true;
return slot;
}
@@ -910,6 +960,8 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags)
indexstate->ss.ps.plan = (Plan *) node;
indexstate->ss.ps.state = estate;
indexstate->ss.ps.ExecProcNode = ExecIndexScan;
+ indexstate->iss_SkipPrefixSize = node->indexskipprefixsize;+ indexstate->iss_FirstTupleEmitted = false;
/*
* Miscellaneous initialization
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.cindex d8cf87e6d0..20a921a700 100644--- a/src/backend/nodes/copyfuncs.c+++ b/src/backend/nodes/copyfuncs.c@@ -493,6 +493,7 @@ _copyIndexScan(const IndexScan *from)
COPY_NODE_FIELD(indexorderbyorig);
COPY_NODE_FIELD(indexorderbyops);
COPY_SCALAR_FIELD(indexorderdir);
+ COPY_SCALAR_FIELD(indexskipprefixsize);
return newnode;
}
@@ -518,6 +519,7 @@ _copyIndexOnlyScan(const IndexOnlyScan *from)
COPY_NODE_FIELD(indexorderby);
COPY_NODE_FIELD(indextlist);
COPY_SCALAR_FIELD(indexorderdir);
+ COPY_SCALAR_FIELD(indexskipprefixsize);
return newnode;
}
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.cindex e2f177515d..58c2b64ed3 100644--- a/src/backend/nodes/outfuncs.c+++ b/src/backend/nodes/outfuncs.c@@ -562,6 +562,7 @@ _outIndexScan(StringInfo str, const IndexScan *node)
WRITE_NODE_FIELD(indexorderbyorig);
WRITE_NODE_FIELD(indexorderbyops);
WRITE_ENUM_FIELD(indexorderdir, ScanDirection);
+ WRITE_INT_FIELD(indexskipprefixsize);
}
static void
@@ -576,6 +577,7 @@ _outIndexOnlyScan(StringInfo str, const IndexOnlyScan *node)
WRITE_NODE_FIELD(indexorderby);
WRITE_NODE_FIELD(indextlist);
WRITE_ENUM_FIELD(indexorderdir, ScanDirection);
+ WRITE_INT_FIELD(indexskipprefixsize);
}
static void
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.cindex 42050ab719..17a3e5a722 100644--- a/src/backend/nodes/readfuncs.c+++ b/src/backend/nodes/readfuncs.c@@ -1821,6 +1821,7 @@ _readIndexScan(void)
READ_NODE_FIELD(indexorderbyorig);
READ_NODE_FIELD(indexorderbyops);
READ_ENUM_FIELD(indexorderdir, ScanDirection);
+ READ_INT_FIELD(indexskipprefixsize);
READ_DONE();
}
@@ -1840,6 +1841,7 @@ _readIndexOnlyScan(void)
READ_NODE_FIELD(indexorderby);
READ_NODE_FIELD(indextlist);
READ_ENUM_FIELD(indexorderdir, ScanDirection);
+ READ_INT_FIELD(indexskipprefixsize);
READ_DONE();
}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.cindex b976afb69d..d7d3f7e9fa 100644--- a/src/backend/optimizer/path/costsize.c+++ b/src/backend/optimizer/path/costsize.c@@ -125,6 +125,7 @@ int max_parallel_workers_per_gather = 2;
bool enable_seqscan = true;
bool enable_indexscan = true;
bool enable_indexonlyscan = true;
+bool enable_indexskipscan = true;
bool enable_bitmapscan = true;
bool enable_tidscan = true;
bool enable_sort = true;
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.cindex 2a50272da6..340bbfcbb3 100644--- a/src/backend/optimizer/path/indxpath.c+++ b/src/backend/optimizer/path/indxpath.c@@ -790,6 +790,16 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
{
IndexPath *ipath = (IndexPath *) lfirst(lc);
+ /*+ * To prevent unique paths from index skip scans being potentially used+ * when not needed scan keep them in a separate pathlist.+ */+ if (ipath->indexskipprefix != 0)+ {+ add_unique_path(rel, (Path *) ipath);+ continue;+ }+
if (index->amhasgettuple)
add_path(rel, (Path *) ipath);
@@ -878,6 +888,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
bool pathkeys_possibly_useful;
bool index_is_ordered;
bool index_only_scan;
+ bool not_empty_qual = false;+ bool can_skip;
int indexcol;
/*
@@ -1027,6 +1039,60 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
index_only_scan = (scantype != ST_BITMAPSCAN &&
check_index_only(rel, index));
+ /* Check if an index skip scan is possible. */+ can_skip = enable_indexskipscan & index->amcanskip;++ /*+ * Skip scan is not supported when there are qual conditions, which are not+ * covered by index. The reason for that is that those conditions are+ * evaluated later, already after skipping was applied.+ *+ * TODO: This implementation is too restrictive, and doesn't allow e.g.+ * index expressions. For that we need to examine index_clauses too.+ */+ if (can_skip && root->parse->jointree != NULL)+ {+ ListCell *lc;++ foreach(lc, (List *)root->parse->jointree->quals)+ {+ Node *expr, *qual = (Node *) lfirst(lc);+ Var *var;+ bool found = false;++ if (!is_opclause(qual))+ {+ not_empty_qual = true;+ break;+ }++ expr = get_leftop(qual);++ if (!IsA(expr, Var))+ {+ not_empty_qual = true;+ break;+ }++ var = (Var *) expr;++ for (int i = 0; i < index->ncolumns; i++)+ {+ if (index->indexkeys[i] == var->varattno)+ {+ found = true;+ break;+ }+ }++ if (!found)+ {+ not_empty_qual = true;+ break;+ }+ }+ }+
/*
* 4. Generate an indexscan path if there are relevant restriction clauses
* in the current clauses, OR the index ordering is potentially useful for
@@ -1050,6 +1116,21 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
false);
result = lappend(result, ipath);
+ /* Consider index skip scan as well */+ if (root->query_uniquekeys != NULL && can_skip && !not_empty_qual)+ {+ ListCell *lc;++ foreach(lc, root->query_uniquekeys)+ {+ UniqueKey *ukey = lfirst_node(UniqueKey, lc);+ result = lappend(result,+ create_skipscan_unique_path(root, index,+ (Path *) ipath,+ ukey->exprs));+ }+ }+
/*
* If appropriate, consider parallel index scan. We don't allow
* parallel index scan for bitmap index scans.
@@ -1105,6 +1186,21 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
false);
result = lappend(result, ipath);
+ /* Consider index skip scan as well */+ if (root->query_uniquekeys != NULL && can_skip && !not_empty_qual)+ {+ ListCell *lc;++ foreach(lc, root->query_uniquekeys)+ {+ UniqueKey *ukey = lfirst_node(UniqueKey, lc);+ result = lappend(result,+ create_skipscan_unique_path(root, index,+ (Path *) ipath,+ ukey->exprs));+ }+ }+
/* If appropriate, consider parallel index scan */
if (index->amcanparallel &&
rel->consider_parallel && outer_relids == NULL &&
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.cindex eb9543f6ad..5b591036fb 100644--- a/src/backend/optimizer/plan/createplan.c+++ b/src/backend/optimizer/plan/createplan.c@@ -177,12 +177,14 @@ static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
Oid indexid, List *indexqual, List *indexqualorig,
List *indexorderby, List *indexorderbyorig,
List *indexorderbyops,
- ScanDirection indexscandir);+ ScanDirection indexscandir,+ int skipprefix);
static IndexOnlyScan *make_indexonlyscan(List *qptlist, List *qpqual,
Index scanrelid, Oid indexid,
List *indexqual, List *indexorderby,
List *indextlist,
- ScanDirection indexscandir);+ ScanDirection indexscandir,+ int skipprefix);
static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
List *indexqual,
List *indexqualorig);
@@ -3005,7 +3007,8 @@ create_indexscan_plan(PlannerInfo *root,
fixed_indexquals,
fixed_indexorderbys,
best_path->indexinfo->indextlist,
- best_path->indexscandir);+ best_path->indexscandir,+ best_path->indexskipprefix);
else
scan_plan = (Scan *) make_indexscan(tlist,
qpqual,
@@ -3016,7 +3019,8 @@ create_indexscan_plan(PlannerInfo *root,
fixed_indexorderbys,
indexorderbys,
indexorderbyops,
- best_path->indexscandir);+ best_path->indexscandir,+ best_path->indexskipprefix);
copy_generic_path_info(&scan_plan->plan, &best_path->path);
@@ -5283,7 +5287,8 @@ make_indexscan(List *qptlist,
List *indexorderby,
List *indexorderbyorig,
List *indexorderbyops,
- ScanDirection indexscandir)+ ScanDirection indexscandir,+ int skipPrefixSize)
{
IndexScan *node = makeNode(IndexScan);
Plan *plan = &node->scan.plan;
@@ -5300,6 +5305,7 @@ make_indexscan(List *qptlist,
node->indexorderbyorig = indexorderbyorig;
node->indexorderbyops = indexorderbyops;
node->indexorderdir = indexscandir;
+ node->indexskipprefixsize = skipPrefixSize;
return node;
}
@@ -5312,7 +5318,8 @@ make_indexonlyscan(List *qptlist,
List *indexqual,
List *indexorderby,
List *indextlist,
- ScanDirection indexscandir)+ ScanDirection indexscandir,+ int skipPrefixSize)
{
IndexOnlyScan *node = makeNode(IndexOnlyScan);
Plan *plan = &node->scan.plan;
@@ -5327,6 +5334,7 @@ make_indexonlyscan(List *qptlist,
node->indexorderby = indexorderby;
node->indextlist = indextlist;
node->indexorderdir = indexscandir;
+ node->indexskipprefixsize = skipPrefixSize;
return node;
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.cindex 60656bdca5..cac2ca0b0f 100644--- a/src/backend/optimizer/util/pathnode.c+++ b/src/backend/optimizer/util/pathnode.c@@ -2971,6 +2971,70 @@ create_upper_unique_path(PlannerInfo *root,
return pathnode;
}
+/*+ * create_skipscan_unique_path+ * Creates a pathnode the same as an existing IndexPath except based on+ * skipping duplicate values. This may or may not be cheaper than using+ * create_upper_unique_path.+ *+ * The input path must be an IndexPath for an index that supports amskip.+ */+IndexPath *+create_skipscan_unique_path(PlannerInfo *root, IndexOptInfo *index,+ Path *basepath, List *unique_exprs)+{+ IndexPath *pathnode = makeNode(IndexPath);+ int numDistinctRows;+ int distinctPrefixKeys;+ ListCell *lc;+ List *exprs = NIL;+++ distinctPrefixKeys = list_length(unique_exprs);++ Assert(IsA(basepath, IndexPath));++ /* We don't want to modify basepath, so make a copy. */+ memcpy(pathnode, basepath, sizeof(IndexPath));++ /*+ * Normally we can think about distinctPrefixKeys as just+ * a number of distinct keys. But if lets say we have a+ * distinct key a, and the index contains b, a in exactly+ * this order. In such situation we need to use position+ * of a in the index as distinctPrefixKeys, otherwise skip+ * will happen only by the first column.+ */+ foreach(lc, unique_exprs)+ {+ Expr *unique_expr = (Expr *) lfirst(lc);+ Var *var = (Var *) unique_expr;++ exprs = lappend(exprs, unique_expr);++ for (int i = 0; i < index->ncolumns; i++)+ {+ if (index->indexkeys[i] == var->varattno)+ {+ distinctPrefixKeys = Max(i + 1, distinctPrefixKeys);+ break;+ }+ }+ }++ Assert(distinctPrefixKeys > 0);+ pathnode->indexskipprefix = distinctPrefixKeys;++ numDistinctRows = estimate_num_groups(root, exprs,+ pathnode->path.rows,+ NULL);++ pathnode->path.total_cost = pathnode->path.startup_cost * numDistinctRows;+ pathnode->path.rows = numDistinctRows;++ return pathnode;+}+
/*
* create_agg_path
* Creates a pathnode that represents performing aggregation/grouping
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.cindex 0b2f9d398a..6da71e5828 100644--- a/src/backend/optimizer/util/plancat.c+++ b/src/backend/optimizer/util/plancat.c@@ -272,6 +272,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->amoptionalkey = amroutine->amoptionalkey;
info->amsearcharray = amroutine->amsearcharray;
info->amsearchnulls = amroutine->amsearchnulls;
+ info->amcanskip = (amroutine->amskip != NULL);
info->amcanparallel = amroutine->amcanparallel;
info->amhasgettuple = (amroutine->amgettuple != NULL);
info->amhasgetbitmap = amroutine->amgetbitmap != NULL &&
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.cindex 2f3e0a70e0..8da64916d3 100644--- a/src/backend/utils/misc/guc.c+++ b/src/backend/utils/misc/guc.c@@ -961,6 +961,15 @@ static struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {+ {"enable_indexskipscan", PGC_USERSET, QUERY_TUNING_METHOD,+ gettext_noop("Enables the planner's use of index-skip-scan plans."),+ NULL+ },+ &enable_indexskipscan,+ 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/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sampleindex ac02bd0c00..ab7f086d52 100644--- a/src/backend/utils/misc/postgresql.conf.sample+++ b/src/backend/utils/misc/postgresql.conf.sample@@ -355,6 +355,7 @@
#enable_hashjoin = on
#enable_indexscan = on
#enable_indexonlyscan = on
+#enable_indexskipscan = on
#enable_material = on
#enable_mergejoin = on
#enable_nestloop = on
diff --git a/src/include/access/amapi.h b/src/include/access/amapi.hindex 4325faa460..85cca4d520 100644--- a/src/include/access/amapi.h+++ b/src/include/access/amapi.h@@ -130,6 +130,13 @@ typedef void (*amrescan_function) (IndexScanDesc scan,
typedef bool (*amgettuple_function) (IndexScanDesc scan,
ScanDirection direction);
+/* skip past duplicates in a given prefix */+typedef bool (*amskip_function) (IndexScanDesc scan,+ ScanDirection dir,+ ScanDirection indexdir,+ bool start,+ int prefix);+
/* fetch all valid tuples */
typedef int64 (*amgetbitmap_function) (IndexScanDesc scan,
TIDBitmap *tbm);
@@ -231,6 +238,7 @@ typedef struct IndexAmRoutine
amendscan_function amendscan;
ammarkpos_function ammarkpos; /* can be NULL */
amrestrpos_function amrestrpos; /* can be NULL */
+ amskip_function amskip; /* can be NULL */
/* interface functions to support parallel index scans */
amestimateparallelscan_function amestimateparallelscan; /* can be NULL */
diff --git a/src/include/access/genam.h b/src/include/access/genam.hindex 931257bd81..95ce4a5d80 100644--- a/src/include/access/genam.h+++ b/src/include/access/genam.h@@ -180,6 +180,8 @@ extern IndexBulkDeleteResult *index_bulk_delete(IndexVacuumInfo *info,
extern IndexBulkDeleteResult *index_vacuum_cleanup(IndexVacuumInfo *info,
IndexBulkDeleteResult *stats);
extern bool index_can_return(Relation indexRelation, int attno);
+extern bool index_skip(IndexScanDesc scan, ScanDirection direction,+ ScanDirection indexdir, bool start, int prefix);
extern RegProcedure index_getprocid(Relation irel, AttrNumber attnum,
uint16 procnum);
extern FmgrInfo *index_getprocinfo(Relation irel, AttrNumber attnum,
diff --git a/src/include/access/sdir.h b/src/include/access/sdir.hindex 23feb90986..094a127464 100644--- a/src/include/access/sdir.h+++ b/src/include/access/sdir.h@@ -55,4 +55,11 @@ typedef enum ScanDirection
#define ScanDirectionIsForward(direction) \
((bool) ((direction) == ForwardScanDirection))
+/*+ * ScanDirectionsAreOpposite+ * True iff scan directions are backward/forward or forward/backward.+ */+#define ScanDirectionsAreOpposite(dirA, dirB) \+ ((bool) (dirA != NoMovementScanDirection && dirA == -dirB))+
#endif /* SDIR_H */
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.hindex 98e0072b8a..d4bf0b7c34 100644--- a/src/include/nodes/execnodes.h+++ b/src/include/nodes/execnodes.h@@ -1429,6 +1429,8 @@ typedef struct IndexScanState
ExprContext *iss_RuntimeContext;
Relation iss_RelationDesc;
struct IndexScanDescData *iss_ScanDesc;
+ int iss_SkipPrefixSize;+ bool iss_FirstTupleEmitted;
/* These are needed for re-checking ORDER BY expr ordering */
pairingheap *iss_ReorderQueue;
@@ -1458,6 +1460,8 @@ typedef struct IndexScanState
* TableSlot slot for holding tuples fetched from the table
* VMBuffer buffer in use for visibility map testing, if any
* PscanLen size of parallel index-only scan descriptor
+ * SkipPrefixSize number of keys for skip-based DISTINCT+ * FirstTupleEmitted has the first tuple been emitted
* ----------------
*/
typedef struct IndexOnlyScanState
@@ -1476,6 +1480,8 @@ typedef struct IndexOnlyScanState
struct IndexScanDescData *ioss_ScanDesc;
TupleTableSlot *ioss_TableSlot;
Buffer ioss_VMBuffer;
+ int ioss_SkipPrefixSize;+ bool ioss_FirstTupleEmitted;
Size ioss_PscanLen;
} IndexOnlyScanState;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.hindex 455d9d64ba..95ef75a018 100644--- a/src/include/nodes/pathnodes.h+++ b/src/include/nodes/pathnodes.h@@ -1232,6 +1232,9 @@ typedef struct Path
* we need not recompute them when considering using the same index in a
* bitmap index/heap scan (see BitmapHeapPath). The costs of the IndexPath
* itself represent the costs of an IndexScan or IndexOnlyScan plan type.
+ *+ * 'indexskipprefix' represents the number of columns to consider for skip+ * scans.
*----------
*/
typedef struct IndexPath
@@ -1244,6 +1247,7 @@ typedef struct IndexPath
ScanDirection indexscandir;
Cost indextotalcost;
Selectivity indexselectivity;
+ int indexskipprefix;
} IndexPath;
/*
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.hindex 83e01074ed..efafdf9361 100644--- a/src/include/nodes/plannodes.h+++ b/src/include/nodes/plannodes.h@@ -409,6 +409,8 @@ typedef struct IndexScan
List *indexorderbyorig; /* the same in original form */
List *indexorderbyops; /* OIDs of sort ops for ORDER BY exprs */
ScanDirection indexorderdir; /* forward or backward or don't care */
+ int indexskipprefixsize; /* the size of the prefix for distinct+ * scans */
} IndexScan;
/* ----------------
@@ -436,6 +438,8 @@ typedef struct IndexOnlyScan
List *indexorderby; /* list of index ORDER BY exprs */
List *indextlist; /* TargetEntry list describing index's cols */
ScanDirection indexorderdir; /* forward or backward or don't care */
+ int indexskipprefixsize; /* the size of the prefix for distinct+ * scans */
} IndexOnlyScan;
/* ----------------
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.hindex 9710e5c0a4..6e24e520f8 100644--- a/src/include/optimizer/cost.h+++ b/src/include/optimizer/cost.h@@ -50,6 +50,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_indexskipscan;
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.hindex 6796ad8cb7..705deaf7bd 100644--- a/src/include/optimizer/pathnode.h+++ b/src/include/optimizer/pathnode.h@@ -207,6 +207,10 @@ extern UpperUniquePath *create_upper_unique_path(PlannerInfo *root,
Path *subpath,
int numCols,
double numGroups);
+extern IndexPath *create_skipscan_unique_path(PlannerInfo *root,+ IndexOptInfo *index,+ Path *subpath,+ List *unique_exprs);
extern AggPath *create_agg_path(PlannerInfo *root,
RelOptInfo *rel,
Path *subpath,
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.outindex a126f0ad61..7e3a36a1b9 100644--- a/src/test/regress/expected/sysviews.out+++ b/src/test/regress/expected/sysviews.out@@ -81,6 +81,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_incrementalsort | on
enable_indexonlyscan | on
enable_indexscan | on
+ enable_indexskipscan | on
enable_material | on
enable_mergejoin | on
enable_nestloop | on
@@ -92,7 +93,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(20 rows)+(21 rows)
-- Test that the pg_timezone_names and pg_timezone_abbrevs views are
-- more-or-less working. We can't test their contents in any great detail
--
2.21.0
[text/x-diff] v35-0003-Btree-implementation-of-skipping.patch (40.0K, ../20200609102247.jdlatmfyeecg52fi@localhost/6-v35-0003-Btree-implementation-of-skipping.patch)
download | inline diff:
From e460810b71b1b85306512a8c9598a3be9ae0f86e Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:45:08 +0200
Subject: [PATCH v35 5/6] Btree implementation of skipping
Implementation of Index Skip Scan for Btree. To make it suitable for
both situations when there are small number of distinct values and
significant amount of distinct values the following approach is taken -
instead of searching from the root for every value we're searching for
then first on the current page, and then if not found continue searching
from the root.
Author: Jesper Pedersen, Dmitry Dolgov
Reviewed-by: Thomas Munro, David Rowley, Floris Van Nee, Kyotaro Horiguchi, Tomas Vondra, Peter Geoghegan
---
src/backend/access/nbtree/nbtree.c | 13 +
src/backend/access/nbtree/nbtsearch.c | 471 ++++++++++++-
src/include/access/nbtree.h | 7 +
src/test/regress/expected/join.out | 3 +
src/test/regress/expected/select_distinct.out | 621 ++++++++++++++++++
src/test/regress/sql/join.sql | 5 +
src/test/regress/sql/select_distinct.sql | 254 +++++++
7 files changed, 1373 insertions(+), 1 deletion(-)
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.cindex e947addef6..f5ca715827 100644--- a/src/backend/access/nbtree/nbtree.c+++ b/src/backend/access/nbtree/nbtree.c@@ -136,6 +136,7 @@ bthandler(PG_FUNCTION_ARGS)
amroutine->ambulkdelete = btbulkdelete;
amroutine->amvacuumcleanup = btvacuumcleanup;
amroutine->amcanreturn = btcanreturn;
+ amroutine->amskip = btskip;
amroutine->amcostestimate = btcostestimate;
amroutine->amoptions = btoptions;
amroutine->amproperty = btproperty;
@@ -385,6 +386,8 @@ btbeginscan(Relation rel, int nkeys, int norderbys)
*/
so->currTuples = so->markTuples = NULL;
+ so->skipScanKey = NULL;+
scan->xs_itupdesc = RelationGetDescr(rel);
scan->opaque = so;
@@ -452,6 +455,16 @@ btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
_bt_preprocess_array_keys(scan);
}
+/*+ * btskip() -- skip to the beginning of the next key prefix+ */+bool+btskip(IndexScanDesc scan, ScanDirection direction,+ ScanDirection indexdir, bool start, int prefix)+{+ return _bt_skip(scan, direction, indexdir, start, prefix);+}+
/*
* btendscan() -- close down a scan
*/
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.cindex 4534224812..7941ad3609 100644--- a/src/backend/access/nbtree/nbtsearch.c+++ b/src/backend/access/nbtree/nbtsearch.c@@ -45,7 +45,10 @@ static bool _bt_parallel_readpage(IndexScanDesc scan, BlockNumber blkno,
static Buffer _bt_walk_left(Relation rel, Buffer buf, Snapshot snapshot);
static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir);
static inline void _bt_initialize_more_data(BTScanOpaque so, ScanDirection dir);
-+static inline void _bt_update_skip_scankeys(IndexScanDesc scan,+ Relation indexRel);+static inline bool _bt_scankey_within_page(IndexScanDesc scan, BTScanInsert key,+ Buffer buf, ScanDirection dir);
/*
* _bt_drop_lock_and_maybe_pin()
@@ -1486,6 +1489,417 @@ _bt_next(IndexScanDesc scan, ScanDirection dir)
return true;
}
+/*+ * _bt_skip() -- Skip items that have the same prefix as the most recently+ * fetched index tuple.+ *+ * The current position is set so that a subsequent call to _bt_next will+ * fetch the first tuple that differs in the leading 'prefix' keys.+ *+ * There are four different kinds of skipping (depending on dir and+ * indexdir, that are important to distinguish, especially in the presense+ * of an index condition:+ *+ * * Advancing forward and reading forward+ * simple scan+ *+ * * Advancing forward and reading backward+ * scan inside a cursor fetching backward, when skipping is necessary+ * right from the start+ *+ * * Advancing backward and reading forward+ * scan with order by desc inside a cursor fetching forward, when+ * skipping is necessary right from the start+ *+ * * Advancing backward and reading backward+ * simple scan with order by desc+ *+ * The current page is searched for the next unique value. If none is found+ * we will do a scan from the root in order to find the next page with+ * a unique value.+ */+bool+_bt_skip(IndexScanDesc scan, ScanDirection dir,+ ScanDirection indexdir, bool scanstart, int prefix)+{+ BTScanOpaque so = (BTScanOpaque) scan->opaque;+ BTStack stack;+ Buffer buf;+ OffsetNumber offnum;+ BTScanPosItem *currItem;+ Relation indexRel = scan->indexRelation;++ /* We want to return tuples, and we need a starting point */+ Assert(scan->xs_want_itup);+ Assert(scan->xs_itup);++ if (so->numKilled > 0)+ _bt_killitems(scan);++ /* If skipScanKey is NULL then we initialize it with _bt_mkscankey */+ if (so->skipScanKey == NULL)+ {+ so->skipScanKey = _bt_mkscankey(indexRel, scan->xs_itup);+ so->skipScanKey->keysz = prefix;+ so->skipScanKey->scantid = NULL;+ }+ so->skipScanKey->nextkey = ScanDirectionIsForward(dir);+ _bt_update_skip_scankeys(scan, indexRel);++ /* Check if the next unique key can be found within the current page.+ * Since we do not lock the current page between jumps, it's possible+ * that it was splitted since the last time we saw it. This is fine in+ * case of scanning forward, since page split to the right and we are+ * still on the left most page. In case of scanning backwards it's+ * possible to loose some pages and we need to remember the previous+ * page, and then follow the right link from the current page until we+ * find the original one.+ *+ * Since the whole idea of checking the current page is to protect+ * ourselves and make more performant statistic mismatch case when+ * there are too many distinct values for jumping, it's not clear if+ * the complexity of this solution in case of backward scan is+ * justified, so for now just avoid it.+ */+ if (BufferIsValid(so->currPos.buf) && ScanDirectionIsForward(dir))+ {+ LockBuffer(so->currPos.buf, BT_READ);++ if (_bt_scankey_within_page(scan, so->skipScanKey, so->currPos.buf, dir))+ {+ bool keyFound = false;++ offnum = _bt_binsrch(scan->indexRelation, so->skipScanKey, so->currPos.buf);++ /* Lock the page for SERIALIZABLE transactions */+ PredicateLockPage(scan->indexRelation, BufferGetBlockNumber(so->currPos.buf),+ scan->xs_snapshot);++ /* We know in which direction to look */+ _bt_initialize_more_data(so, dir);++ /* Now read the data */+ keyFound = _bt_readpage(scan, dir, offnum);++ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);+ ReleaseBuffer(so->currPos.buf);+ so->currPos.buf = InvalidBuffer;++ if (keyFound)+ {+ /* set IndexTuple */+ currItem = &so->currPos.items[so->currPos.itemIndex];+ scan->xs_heaptid = currItem->heapTid;+ scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);+ return true;+ }+ }+ else+ {+ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);+ }+ }++ if (BufferIsValid(so->currPos.buf))+ {+ ReleaseBuffer(so->currPos.buf);+ so->currPos.buf = InvalidBuffer;+ }++ /*+ * We haven't found scan key within the current page, so let's scan from+ * the root. Use _bt_search and _bt_binsrch to get the buffer and offset+ * number+ */+ stack = _bt_search(scan->indexRelation, so->skipScanKey,+ &buf, BT_READ, scan->xs_snapshot);+ _bt_freestack(stack);+ so->currPos.buf = buf;+ offnum = _bt_binsrch(scan->indexRelation, so->skipScanKey, buf);++ /* Lock the page for SERIALIZABLE transactions */+ PredicateLockPage(scan->indexRelation, BufferGetBlockNumber(buf),+ scan->xs_snapshot);++ /* We know in which direction to look */+ _bt_initialize_more_data(so, dir);++ /*+ * Simplest case is when both directions are forward, when we are already+ * at the next distinct key at the beginning of the series (so everything+ * else would be done in _bt_readpage)+ *+ * The case when both directions are backwards is also simple, but we need+ * to go one step back, since we need a last element from the previous+ * series.+ */+ if (ScanDirectionIsBackward(dir) && ScanDirectionIsBackward(indexdir))+ offnum = OffsetNumberPrev(offnum);++ /*+ * Andvance backward but read forward. At this moment we are at the next+ * distinct key at the beginning of the series. In case if scan just+ * started, we can read forward without doing anything else. Otherwise+ * find previous distinct key and the beginning of it's series and read+ * forward from there. To do so, go back one step, perform binary search+ * to find the first item in the series and let _bt_readpage do everything+ * else.+ */+ else if (ScanDirectionIsBackward(dir) && ScanDirectionIsForward(indexdir))+ {+ if (!scanstart)+ {+ /* Reading forward means we expect to see more data on the right */+ so->currPos.moreRight = true;++ offnum = _bt_binsrch(scan->indexRelation, so->skipScanKey, buf);++ /* One step back to find a previous value */+ _bt_readpage(scan, dir, offnum);++ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);+ if (_bt_next(scan, dir))+ {+ LockBuffer(so->currPos.buf, BT_READ);+ _bt_update_skip_scankeys(scan, indexRel);++ /*+ * And now find the last item from the sequence for the+ * current, value with the intention do OffsetNumberNext. As a+ * result we end up on a first element from the sequence.+ */+ if (_bt_scankey_within_page(scan, so->skipScanKey, so->currPos.buf, dir))+ offnum = _bt_binsrch(scan->indexRelation, so->skipScanKey, buf);+ else+ {+ if (BufferIsValid(so->currPos.buf))+ {+ /* Before leaving current page, deal with any killed items */+ if (so->numKilled > 0)+ _bt_killitems(scan);++ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);+ ReleaseBuffer(so->currPos.buf);+ so->currPos.buf = InvalidBuffer;+ }++ stack = _bt_search(scan->indexRelation, so->skipScanKey,+ &buf, BT_READ, scan->xs_snapshot);+ _bt_freestack(stack);+ so->currPos.buf = buf;+ offnum = _bt_binsrch(scan->indexRelation, so->skipScanKey, buf);+ }+ }+ else+ {+ pfree(so->skipScanKey);+ so->skipScanKey = NULL;+ return false;+ }+ }+ }++ /*+ * Advance forward but read backward. At this moment we are at the next+ * distinct key at the beginning of the series. In case if scan just+ * started, we can go one step back and read forward without doing+ * anything else. Otherwise find the next distinct key and the beginning+ * of it's series, go one step back and read backward from there.+ *+ * An interesting situation can happen if one of distinct keys do not pass+ * a corresponding index condition at all. In this case reading backward+ * can lead to a previous distinct key being found, creating a loop. To+ * avoid that check the value to be returned, and jump one more time if+ * it's the same as at the beginning. Note that we do not check visibility+ * here, and dead tuples could also lead to the same situation. This has to+ * be checked on the caller side.+ */+ else if (ScanDirectionIsForward(dir) && ScanDirectionIsBackward(indexdir))+ {+ if (scanstart)+ offnum = OffsetNumberPrev(offnum);+ else+ {+ OffsetNumber nextOffset,+ startOffset,+ jumpOffset;++ IndexTuple startItup = CopyIndexTuple(scan->xs_itup);+ Page page = BufferGetPage(so->currPos.buf);++ /* We are at the end and need to return */+ if ((offnum > PageGetMaxOffsetNumber(page)) &+ (so->currPos.nextPage == P_NONE))+ {+ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);++ BTScanPosUnpinIfPinned(so->currPos);+ BTScanPosInvalidate(so->currPos);++ pfree(so->skipScanKey);+ so->skipScanKey = NULL;+ return false;+ }++ nextOffset = startOffset = ItemPointerGetOffsetNumber(&scan->xs_itup->t_tid);++ /* Reading backwards means we expect to see more data on the left */+ so->currPos.moreLeft = true;++ while (nextOffset == startOffset)+ {+ IndexTuple itup;+ CHECK_FOR_INTERRUPTS();++ /*+ * Find a next index tuple to update scan key. It could be at+ * the end, so check for max offset+ */+ if (!_bt_readpage(scan, ForwardScanDirection, offnum))+ {+ /*+ * There's no actually-matching data on this page. Try to+ * advance to the next page. Return false if there's no+ * matching data at all.+ */+ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);+ if (!_bt_steppage(scan, dir))+ {+ pfree(so->skipScanKey);+ so->skipScanKey = NULL;+ return false;+ }+ LockBuffer(so->currPos.buf, BT_READ);+ }++ currItem = &so->currPos.items[so->currPos.firstItem];+ itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);++ scan->xs_itup = itup;++ _bt_update_skip_scankeys(scan, indexRel);+ if (BufferIsValid(so->currPos.buf))+ {+ /* Before leaving current page, deal with any killed items */+ if (so->numKilled > 0)+ _bt_killitems(scan);++ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);+ ReleaseBuffer(so->currPos.buf);+ so->currPos.buf = InvalidBuffer;+ }++ stack = _bt_search(scan->indexRelation, so->skipScanKey,+ &buf, BT_READ, scan->xs_snapshot);+ _bt_freestack(stack);+ so->currPos.buf = buf;+ jumpOffset = offnum = _bt_binsrch(scan->indexRelation, so->skipScanKey, buf);+ offnum = OffsetNumberPrev(offnum);++ if (!_bt_readpage(scan, indexdir, offnum))+ {+ /*+ * There's no actually-matching data on this page. Try to+ * advance to the next page. Return false if there's no+ * matching data at all.+ */+ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);+ if (!_bt_steppage(scan, indexdir))+ {+ pfree(so->skipScanKey);+ so->skipScanKey = NULL;+ return false;+ }+ LockBuffer(so->currPos.buf, BT_READ);+ }++ currItem = &so->currPos.items[so->currPos.lastItem];+ itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);+ nextOffset = ItemPointerGetOffsetNumber(&itup->t_tid);++ /*+ * To check if we returned the same tuple, try to find a+ * startItup on the current page. For that we need to update+ * scankey to match the whole tuple and set nextkey to return+ * an exact tuple, not the next one. If the nextOffset is the+ * same as before, it means we are in the loop, return offnum+ * to the original position and jump further+ */+ scan->xs_itup = startItup;+ _bt_update_skip_scankeys(scan, indexRel);++ so->skipScanKey->keysz = IndexRelationGetNumberOfKeyAttributes(indexRel);+ so->skipScanKey->nextkey = false;++ if (_bt_scankey_within_page(scan, so->skipScanKey,+ so->currPos.buf, dir))+ {+ OffsetNumber maxoff;+ startOffset = _bt_binsrch(scan->indexRelation,+ so->skipScanKey,+ so->currPos.buf);++ page = BufferGetPage(so->currPos.buf);+ maxoff = PageGetMaxOffsetNumber(page);++ if (nextOffset <= startOffset)+ {+ offnum = jumpOffset;+ nextOffset = startOffset;+ }++ if ((offnum > maxoff) & (so->currPos.nextPage == P_NONE))+ {+ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);++ BTScanPosUnpinIfPinned(so->currPos);+ BTScanPosInvalidate(so->currPos);++ pfree(so->skipScanKey);+ so->skipScanKey = NULL;+ return false;+ }+ }++ /* Return original scankey options */+ so->skipScanKey->keysz = prefix;+ so->skipScanKey->nextkey = ScanDirectionIsForward(dir);+ }+ }+ }++ /* Now read the data */+ if (!_bt_readpage(scan, indexdir, offnum))+ {+ /*+ * There's no actually-matching data on this page. Try to advance to+ * the next page. Return false if there's no matching data at all.+ */+ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);+ if (!_bt_steppage(scan, dir))+ {+ pfree(so->skipScanKey);+ so->skipScanKey = NULL;+ return false;+ }+ }+ else+ {+ /* Drop the lock, and maybe the pin, on the current page */+ LockBuffer(so->currPos.buf, BUFFER_LOCK_UNLOCK);+ }++ /* And set IndexTuple */+ currItem = &so->currPos.items[so->currPos.itemIndex];+ scan->xs_heaptid = currItem->heapTid;+ scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);++ so->currPos.moreLeft = true;+ so->currPos.moreRight = true;++ return true;+}+
/*
* _bt_readpage() -- Load data from current index page into so->currPos
*
@@ -2482,3 +2896,58 @@ _bt_initialize_more_data(BTScanOpaque so, ScanDirection dir)
so->numKilled = 0; /* just paranoia */
so->markItemIndex = -1; /* ditto */
}
++/*+ * _bt_update_skip_scankeys() -- set up a new values for the existing scankeys+ * based on the current index tuple+ */+static inline void+_bt_update_skip_scankeys(IndexScanDesc scan, Relation indexRel)+{+ TupleDesc itupdesc;+ int indnkeyatts,+ i;+ BTScanOpaque so = (BTScanOpaque) scan->opaque;+ ScanKey scankeys = so->skipScanKey->scankeys;++ itupdesc = RelationGetDescr(indexRel);+ indnkeyatts = IndexRelationGetNumberOfKeyAttributes(indexRel);+ for (i = 0; i < indnkeyatts; i++)+ {+ Datum datum;+ bool null;+ int flags;++ datum = index_getattr(scan->xs_itup, i + 1, itupdesc, &null);+ flags = (null ? SK_ISNULL : 0) |+ (indexRel->rd_indoption[i] << SK_BT_INDOPTION_SHIFT);+ scankeys[i].sk_flags = flags;+ scankeys[i].sk_argument = datum;+ }+}++/*+ * _bt_scankey_within_page() -- check if the provided scankey could be found+ * within a page, specified by the buffer.+ *+ * Scankey nextkey will tell us if we need to find a current key or the next+ * one, which affects whether or not it's ok to be equal to the page highkey.+ */+static inline bool+_bt_scankey_within_page(IndexScanDesc scan, BTScanInsert key,+ Buffer buf, ScanDirection dir)+{+ OffsetNumber low, high;+ Page page = BufferGetPage(buf);+ BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);+ int high_compare = key->nextkey ? 0 : 1;++ low = P_FIRSTDATAKEY(opaque);+ high = PageGetMaxOffsetNumber(page);++ if (unlikely(high < low))+ return false;++ return (_bt_compare(scan->indexRelation, key, page, low) > 0 &&+ _bt_compare(scan->indexRelation, key, page, high) < high_compare);+}diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.hindex 4e2b056b54..7068e7d268 100644--- a/src/include/access/nbtree.h+++ b/src/include/access/nbtree.h@@ -937,6 +937,9 @@ typedef struct BTScanOpaqueData
*/
int markItemIndex; /* itemIndex, or -1 if not valid */
+ /* Work space for _bt_skip */+ BTScanInsert skipScanKey; /* used to control skipping */+
/* keep these last in struct for efficiency */
BTScanPosData currPos; /* current position data */
BTScanPosData markPos; /* marked position, if any */
@@ -1094,6 +1097,8 @@ extern OffsetNumber _bt_binsrch_insert(Relation rel, BTInsertState insertstate);
extern int32 _bt_compare(Relation rel, BTScanInsert key, Page page, OffsetNumber offnum);
extern bool _bt_first(IndexScanDesc scan, ScanDirection dir);
extern bool _bt_next(IndexScanDesc scan, ScanDirection dir);
+extern bool _bt_skip(IndexScanDesc scan, ScanDirection dir,+ ScanDirection indexdir, bool start, int prefix);
extern Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost,
Snapshot snapshot);
@@ -1118,6 +1123,8 @@ extern void _bt_end_vacuum_callback(int code, Datum arg);
extern Size BTreeShmemSize(void);
extern void BTreeShmemInit(void);
extern bytea *btoptions(Datum reloptions, bool validate);
+extern bool btskip(IndexScanDesc scan, ScanDirection dir,+ ScanDirection indexdir, bool start, int prefix);
extern bool btproperty(Oid index_oid, int attno,
IndexAMProperty prop, const char *propname,
bool *res, bool *isnull);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.outindex a46b1573bd..a47e9faed2 100644--- a/src/test/regress/expected/join.out+++ b/src/test/regress/expected/join.out@@ -4429,6 +4429,8 @@ select d.* from d left join (select * from b group by b.id, b.c_id) s
-> Seq Scan on d
(8 rows)
+-- disable index skip scan to prevent it interfering with the plan+set enable_indexskipscan to off;
-- similarly, but keying off a DISTINCT clause
explain (costs off)
select d.* from d left join (select distinct * from b) s
@@ -4446,6 +4448,7 @@ select d.* from d left join (select distinct * from b) s
-> Seq Scan on d
(9 rows)
+set enable_indexskipscan to on;
-- check join removal works when uniqueness of the join condition is enforced
-- by a UNION
explain (costs off)
diff --git a/src/test/regress/expected/select_distinct.out b/src/test/regress/expected/select_distinct.outindex 11c6f50fbf..b811f7d7a1 100644--- a/src/test/regress/expected/select_distinct.out+++ b/src/test/regress/expected/select_distinct.out@@ -306,3 +306,624 @@ SELECT null IS NOT DISTINCT FROM null as "yes";
t
(1 row)
+-- index only skip scan+CREATE TABLE distinct_a (a int, b int, c int);+INSERT INTO distinct_a (+ SELECT five, tenthous, 10 FROM+ generate_series(1, 5) five,+ generate_series(1, 10000) tenthous+);+CREATE INDEX ON distinct_a (a, b);+CREATE INDEX ON distinct_a ((a + 1));+ANALYZE distinct_a;+SELECT DISTINCT a FROM distinct_a;+ a +---+ 1+ 2+ 3+ 4+ 5+(5 rows)++SELECT DISTINCT a FROM distinct_a WHERE a = 1;+ a +---+ 1+(1 row)++SELECT DISTINCT a FROM distinct_a ORDER BY a DESC;+ a +---+ 5+ 4+ 3+ 2+ 1+(5 rows)++EXPLAIN (COSTS OFF)+SELECT DISTINCT a FROM distinct_a;+ QUERY PLAN +--------------------------------------------------------+ Index Only Scan using distinct_a_a_b_idx on distinct_a+ Skip scan: true+(2 rows)++-- test index skip scan with a condition on a non unique field+SELECT DISTINCT ON (a) a, b FROM distinct_a WHERE b = 2;+ a | b +---+---+ 1 | 2+ 2 | 2+ 3 | 2+ 4 | 2+ 5 | 2+(5 rows)++-- test index skip scan backwards+SELECT DISTINCT ON (a) a, b FROM distinct_a ORDER BY a DESC, b DESC;+ a | b +---+-------+ 5 | 10000+ 4 | 10000+ 3 | 10000+ 2 | 10000+ 1 | 10000+(5 rows)++-- test index skip scan for expressions+EXPLAIN (COSTS OFF)+SELECT DISTINCT (a + 1) FROM distinct_a;+ QUERY PLAN +----------------------------------------------------+ Index Scan using distinct_a_expr_idx on distinct_a+ Skip scan: true+(2 rows)++SELECT DISTINCT (a + 1) FROM distinct_a;+ ?column? +----------+ 2+ 3+ 4+ 5+ 6+(5 rows)++-- check colums order+CREATE INDEX distinct_a_b_a on distinct_a (b, a);+SELECT DISTINCT a FROM distinct_a WHERE b = 2;+ a +---+ 1+ 2+ 3+ 4+ 5+(5 rows)++SELECT DISTINCT on (a, b) a, b FROM distinct_a WHERE b = 2;+ a | b +---+---+ 1 | 2+ 2 | 2+ 3 | 2+ 4 | 2+ 5 | 2+(5 rows)++EXPLAIN (COSTS OFF)+SELECT DISTINCT a FROM distinct_a WHERE b = 2;+ QUERY PLAN +----------------------------------------------------+ Index Only Scan using distinct_a_b_a on distinct_a+ Skip scan: true+ Index Cond: (b = 2)+(3 rows)++EXPLAIN (COSTS OFF)+SELECT DISTINCT on (a, b) a, b FROM distinct_a WHERE b = 2;+ QUERY PLAN +----------------------------------------------------+ Index Only Scan using distinct_a_b_a on distinct_a+ Skip scan: true+ Index Cond: (b = 2)+(3 rows)++DROP INDEX distinct_a_b_a;+-- test opposite scan/index directions inside a cursor+-- forward/backward+BEGIN;+DECLARE c SCROLL CURSOR FOR+SELECT DISTINCT ON (a) a,b FROM distinct_a ORDER BY a, b;+FETCH FROM c;+ a | b +---+---+ 1 | 1+(1 row)++FETCH BACKWARD FROM c;+ a | b +---+---+(0 rows)++FETCH 6 FROM c;+ a | b +---+---+ 1 | 1+ 2 | 1+ 3 | 1+ 4 | 1+ 5 | 1+(5 rows)++FETCH BACKWARD 6 FROM c;+ a | b +---+---+ 5 | 1+ 4 | 1+ 3 | 1+ 2 | 1+ 1 | 1+(5 rows)++FETCH 6 FROM c;+ a | b +---+---+ 1 | 1+ 2 | 1+ 3 | 1+ 4 | 1+ 5 | 1+(5 rows)++FETCH BACKWARD 6 FROM c;+ a | b +---+---+ 5 | 1+ 4 | 1+ 3 | 1+ 2 | 1+ 1 | 1+(5 rows)++END;+-- backward/forward+BEGIN;+DECLARE c SCROLL CURSOR FOR+SELECT DISTINCT ON (a) a,b FROM distinct_a ORDER BY a DESC, b DESC;+FETCH FROM c;+ a | b +---+-------+ 5 | 10000+(1 row)++FETCH BACKWARD FROM c;+ a | b +---+---+(0 rows)++FETCH 6 FROM c;+ a | b +---+-------+ 5 | 10000+ 4 | 10000+ 3 | 10000+ 2 | 10000+ 1 | 10000+(5 rows)++FETCH BACKWARD 6 FROM c;+ a | b +---+-------+ 1 | 10000+ 2 | 10000+ 3 | 10000+ 4 | 10000+ 5 | 10000+(5 rows)++FETCH 6 FROM c;+ a | b +---+-------+ 5 | 10000+ 4 | 10000+ 3 | 10000+ 2 | 10000+ 1 | 10000+(5 rows)++FETCH BACKWARD 6 FROM c;+ a | b +---+-------+ 1 | 10000+ 2 | 10000+ 3 | 10000+ 4 | 10000+ 5 | 10000+(5 rows)++END;+-- test missing values and skipping from the end+CREATE TABLE distinct_abc(a int, b int, c int);+CREATE INDEX ON distinct_abc(a, b, c);+INSERT INTO distinct_abc+ VALUES (1, 1, 1),+ (1, 1, 2),+ (1, 2, 2),+ (1, 2, 3),+ (2, 2, 1),+ (2, 2, 3),+ (3, 1, 1),+ (3, 1, 2),+ (3, 2, 2),+ (3, 2, 3);+EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a,b,c FROM distinct_abc WHERE c = 2;+ QUERY PLAN +--------------------------------------------------------------+ Index Only Scan using distinct_abc_a_b_c_idx on distinct_abc+ Skip scan: true+ Index Cond: (c = 2)+(3 rows)++BEGIN;+DECLARE c SCROLL CURSOR FOR+SELECT DISTINCT ON (a) a,b,c FROM distinct_abc WHERE c = 2;+FETCH ALL FROM c;+ a | b | c +---+---+---+ 1 | 1 | 2+ 3 | 1 | 2+(2 rows)++FETCH BACKWARD ALL FROM c;+ a | b | c +---+---+---+ 3 | 1 | 2+ 1 | 1 | 2+(2 rows)++END;+EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a,b,c FROM distinct_abc WHERE c = 2+ORDER BY a DESC, b DESC;+ QUERY PLAN +-----------------------------------------------------------------------+ Index Only Scan Backward using distinct_abc_a_b_c_idx on distinct_abc+ Skip scan: true+ Index Cond: (c = 2)+(3 rows)++BEGIN;+DECLARE c SCROLL CURSOR FOR+SELECT DISTINCT ON (a) a,b,c FROM distinct_abc WHERE c = 2+ORDER BY a DESC, b DESC;+FETCH ALL FROM c;+ a | b | c +---+---+---+ 3 | 2 | 2+ 1 | 2 | 2+(2 rows)++FETCH BACKWARD ALL FROM c;+ a | b | c +---+---+---+ 1 | 2 | 2+ 3 | 2 | 2+(2 rows)++END;+DROP TABLE distinct_abc;+-- index skip scan+SELECT DISTINCT ON (a) a, b, c+FROM distinct_a ORDER BY a;+ a | b | c +---+---+----+ 1 | 1 | 10+ 2 | 1 | 10+ 3 | 1 | 10+ 4 | 1 | 10+ 5 | 1 | 10+(5 rows)++SELECT DISTINCT ON (a) a, b, c+FROM distinct_a WHERE a = 1 ORDER BY a;+ a | b | c +---+---+----+ 1 | 1 | 10+(1 row)++EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a, b, c+FROM distinct_a ORDER BY a;+ QUERY PLAN +---------------------------------------------------+ Index Scan using distinct_a_a_b_idx on distinct_a+ Skip scan: true+(2 rows)++EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a, b, c+FROM distinct_a WHERE a = 1 ORDER BY a;+ QUERY PLAN +-----------------------------------------------------+ Unique+ -> Bitmap Heap Scan on distinct_a+ Recheck Cond: (a = 1)+ -> Bitmap Index Scan on distinct_a_a_b_idx+ Index Cond: (a = 1)+(5 rows)++-- check colums order+SELECT DISTINCT a FROM distinct_a WHERE b = 2 AND c = 10;+ a +---+ 1+ 2+ 3+ 4+ 5+(5 rows)++EXPLAIN (COSTS OFF)+SELECT DISTINCT a FROM distinct_a WHERE b = 2 AND c = 10;+ QUERY PLAN +---------------------------------------------------------+ Unique+ -> Index Scan using distinct_a_a_b_idx on distinct_a+ Index Cond: (b = 2)+ Filter: (c = 10)+(4 rows)++-- check projection case+SELECT DISTINCT a, a FROM distinct_a WHERE b = 2;+ a | a +---+---+ 1 | 1+ 2 | 2+ 3 | 3+ 4 | 4+ 5 | 5+(5 rows)++SELECT DISTINCT a, 1 FROM distinct_a WHERE b = 2;+ a | ?column? +---+----------+ 1 | 1+ 2 | 1+ 3 | 1+ 4 | 1+ 5 | 1+(5 rows)++-- test cursor forward/backward movements+BEGIN;+DECLARE c SCROLL CURSOR FOR SELECT DISTINCT a FROM distinct_a;+FETCH FROM c;+ a +---+ 1+(1 row)++FETCH BACKWARD FROM c;+ a +---+(0 rows)++FETCH 6 FROM c;+ a +---+ 1+ 2+ 3+ 4+ 5+(5 rows)++FETCH BACKWARD 6 FROM c;+ a +---+ 5+ 4+ 3+ 2+ 1+(5 rows)++FETCH 6 FROM c;+ a +---+ 1+ 2+ 3+ 4+ 5+(5 rows)++FETCH BACKWARD 6 FROM c;+ a +---+ 5+ 4+ 3+ 2+ 1+(5 rows)++END;+DROP TABLE distinct_a;+-- test tuples visibility+CREATE TABLE distinct_visibility (a int, b int);+INSERT INTO distinct_visibility (select a, b from generate_series(1,5) a, generate_series(1, 10000) b);+CREATE INDEX ON distinct_visibility (a, b);+ANALYZE distinct_visibility;+SELECT DISTINCT ON (a) a, b FROM distinct_visibility ORDER BY a, b;+ a | b +---+---+ 1 | 1+ 2 | 1+ 3 | 1+ 4 | 1+ 5 | 1+(5 rows)++DELETE FROM distinct_visibility WHERE a = 2 and b = 1;+SELECT DISTINCT ON (a) a, b FROM distinct_visibility ORDER BY a, b;+ a | b +---+---+ 1 | 1+ 2 | 2+ 3 | 1+ 4 | 1+ 5 | 1+(5 rows)++SELECT DISTINCT ON (a) a, b FROM distinct_visibility ORDER BY a DESC, b DESC;+ a | b +---+-------+ 5 | 10000+ 4 | 10000+ 3 | 10000+ 2 | 10000+ 1 | 10000+(5 rows)++DELETE FROM distinct_visibility WHERE a = 2 and b = 10000;+SELECT DISTINCT ON (a) a, b FROM distinct_visibility ORDER BY a DESC, b DESC;+ a | b +---+-------+ 5 | 10000+ 4 | 10000+ 3 | 10000+ 2 | 9999+ 1 | 10000+(5 rows)++DROP TABLE distinct_visibility;+-- test page boundaries+CREATE TABLE distinct_boundaries AS+ SELECT a, b::int2 b, (b % 2)::int2 c FROM+ generate_series(1, 5) a,+ generate_series(1,366) b;+CREATE INDEX ON distinct_boundaries (a, b, c);+ANALYZE distinct_boundaries;+EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a, b, c from distinct_boundaries+WHERE b >= 1 and c = 0 ORDER BY a, b;+ QUERY PLAN +----------------------------------------------------------------------------+ Index Only Scan using distinct_boundaries_a_b_c_idx on distinct_boundaries+ Skip scan: true+ Index Cond: ((b >= 1) AND (c = 0))+(3 rows)++SELECT DISTINCT ON (a) a, b, c from distinct_boundaries+WHERE b >= 1 and c = 0 ORDER BY a, b;+ a | b | c +---+---+---+ 1 | 2 | 0+ 2 | 2 | 0+ 3 | 2 | 0+ 4 | 2 | 0+ 5 | 2 | 0+(5 rows)++DROP TABLE distinct_boundaries;+-- test tuple killing+-- DESC ordering+CREATE TABLE distinct_killed AS+ SELECT a, b, b % 2 AS c, 10 AS d+ FROM generate_series(1, 5) a,+ generate_series(1,1000) b;+CREATE INDEX ON distinct_killed (a, b, c, d);+DELETE FROM distinct_killed where a = 3;+BEGIN;+ DECLARE c SCROLL CURSOR FOR+ SELECT DISTINCT ON (a) a,b,c,d+ FROM distinct_killed ORDER BY a DESC, b DESC;+ FETCH FORWARD ALL FROM c;+ a | b | c | d +---+------+---+----+ 5 | 1000 | 0 | 10+ 4 | 1000 | 0 | 10+ 2 | 1000 | 0 | 10+ 1 | 1000 | 0 | 10+(4 rows)++ FETCH BACKWARD ALL FROM c;+ a | b | c | d +---+------+---+----+ 1 | 1000 | 0 | 10+ 2 | 1000 | 0 | 10+ 4 | 1000 | 0 | 10+ 5 | 1000 | 0 | 10+(4 rows)++COMMIT;+DROP TABLE distinct_killed;+-- regular ordering+CREATE TABLE distinct_killed AS+ SELECT a, b, b % 2 AS c, 10 AS d+ FROM generate_series(1, 5) a,+ generate_series(1,1000) b;+CREATE INDEX ON distinct_killed (a, b, c, d);+DELETE FROM distinct_killed where a = 3;+BEGIN;+ DECLARE c SCROLL CURSOR FOR+ SELECT DISTINCT ON (a) a,b,c,d+ FROM distinct_killed ORDER BY a, b;+ FETCH FORWARD ALL FROM c;+ a | b | c | d +---+---+---+----+ 1 | 1 | 1 | 10+ 2 | 1 | 1 | 10+ 4 | 1 | 1 | 10+ 5 | 1 | 1 | 10+(4 rows)++ FETCH BACKWARD ALL FROM c;+ a | b | c | d +---+---+---+----+ 5 | 1 | 1 | 10+ 4 | 1 | 1 | 10+ 2 | 1 | 1 | 10+ 1 | 1 | 1 | 10+(4 rows)++COMMIT;+DROP TABLE distinct_killed;+-- partial delete+CREATE TABLE distinct_killed AS+ SELECT a, b, b % 2 AS c, 10 AS d+ FROM generate_series(1, 5) a,+ generate_series(1,1000) b;+CREATE INDEX ON distinct_killed (a, b, c, d);+DELETE FROM distinct_killed WHERE a = 3 AND b <= 999;+BEGIN;+ DECLARE c SCROLL CURSOR FOR+ SELECT DISTINCT ON (a) a,b,c,d+ FROM distinct_killed ORDER BY a DESC, b DESC;+ FETCH FORWARD ALL FROM c;+ a | b | c | d +---+------+---+----+ 5 | 1000 | 0 | 10+ 4 | 1000 | 0 | 10+ 3 | 1000 | 0 | 10+ 2 | 1000 | 0 | 10+ 1 | 1000 | 0 | 10+(5 rows)++ FETCH BACKWARD ALL FROM c;+ a | b | c | d +---+------+---+----+ 1 | 1000 | 0 | 10+ 2 | 1000 | 0 | 10+ 3 | 1000 | 0 | 10+ 4 | 1000 | 0 | 10+ 5 | 1000 | 0 | 10+(5 rows)++COMMIT;+DROP TABLE distinct_killed;diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sqlindex 1403e0ffe7..13e35fda88 100644--- a/src/test/regress/sql/join.sql+++ b/src/test/regress/sql/join.sql@@ -1519,11 +1519,16 @@ explain (costs off)
select d.* from d left join (select * from b group by b.id, b.c_id) s
on d.a = s.id;
+-- disable index skip scan to prevent it interfering with the plan+set enable_indexskipscan to off;+
-- similarly, but keying off a DISTINCT clause
explain (costs off)
select d.* from d left join (select distinct * from b) s
on d.a = s.id;
+set enable_indexskipscan to on;+
-- check join removal works when uniqueness of the join condition is enforced
-- by a UNION
explain (costs off)
diff --git a/src/test/regress/sql/select_distinct.sql b/src/test/regress/sql/select_distinct.sqlindex 33102744eb..da07988d35 100644--- a/src/test/regress/sql/select_distinct.sql+++ b/src/test/regress/sql/select_distinct.sql@@ -135,3 +135,257 @@ SELECT 1 IS NOT DISTINCT FROM 2 as "no";
SELECT 2 IS NOT DISTINCT FROM 2 as "yes";
SELECT 2 IS NOT DISTINCT FROM null as "no";
SELECT null IS NOT DISTINCT FROM null as "yes";
++-- index only skip scan+CREATE TABLE distinct_a (a int, b int, c int);+INSERT INTO distinct_a (+ SELECT five, tenthous, 10 FROM+ generate_series(1, 5) five,+ generate_series(1, 10000) tenthous+);+CREATE INDEX ON distinct_a (a, b);+CREATE INDEX ON distinct_a ((a + 1));+ANALYZE distinct_a;++SELECT DISTINCT a FROM distinct_a;+SELECT DISTINCT a FROM distinct_a WHERE a = 1;+SELECT DISTINCT a FROM distinct_a ORDER BY a DESC;++EXPLAIN (COSTS OFF)+SELECT DISTINCT a FROM distinct_a;++-- test index skip scan with a condition on a non unique field+SELECT DISTINCT ON (a) a, b FROM distinct_a WHERE b = 2;++-- test index skip scan backwards+SELECT DISTINCT ON (a) a, b FROM distinct_a ORDER BY a DESC, b DESC;++-- test index skip scan for expressions+EXPLAIN (COSTS OFF)+SELECT DISTINCT (a + 1) FROM distinct_a;+SELECT DISTINCT (a + 1) FROM distinct_a;++-- check colums order+CREATE INDEX distinct_a_b_a on distinct_a (b, a);++SELECT DISTINCT a FROM distinct_a WHERE b = 2;+SELECT DISTINCT on (a, b) a, b FROM distinct_a WHERE b = 2;++EXPLAIN (COSTS OFF)+SELECT DISTINCT a FROM distinct_a WHERE b = 2;++EXPLAIN (COSTS OFF)+SELECT DISTINCT on (a, b) a, b FROM distinct_a WHERE b = 2;++DROP INDEX distinct_a_b_a;++-- test opposite scan/index directions inside a cursor+-- forward/backward+BEGIN;+DECLARE c SCROLL CURSOR FOR+SELECT DISTINCT ON (a) a,b FROM distinct_a ORDER BY a, b;++FETCH FROM c;+FETCH BACKWARD FROM c;++FETCH 6 FROM c;+FETCH BACKWARD 6 FROM c;++FETCH 6 FROM c;+FETCH BACKWARD 6 FROM c;++END;++-- backward/forward+BEGIN;+DECLARE c SCROLL CURSOR FOR+SELECT DISTINCT ON (a) a,b FROM distinct_a ORDER BY a DESC, b DESC;++FETCH FROM c;+FETCH BACKWARD FROM c;++FETCH 6 FROM c;+FETCH BACKWARD 6 FROM c;++FETCH 6 FROM c;+FETCH BACKWARD 6 FROM c;++END;++-- test missing values and skipping from the end+CREATE TABLE distinct_abc(a int, b int, c int);+CREATE INDEX ON distinct_abc(a, b, c);+INSERT INTO distinct_abc+ VALUES (1, 1, 1),+ (1, 1, 2),+ (1, 2, 2),+ (1, 2, 3),+ (2, 2, 1),+ (2, 2, 3),+ (3, 1, 1),+ (3, 1, 2),+ (3, 2, 2),+ (3, 2, 3);++EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a,b,c FROM distinct_abc WHERE c = 2;++BEGIN;+DECLARE c SCROLL CURSOR FOR+SELECT DISTINCT ON (a) a,b,c FROM distinct_abc WHERE c = 2;++FETCH ALL FROM c;+FETCH BACKWARD ALL FROM c;++END;++EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a,b,c FROM distinct_abc WHERE c = 2+ORDER BY a DESC, b DESC;++BEGIN;+DECLARE c SCROLL CURSOR FOR+SELECT DISTINCT ON (a) a,b,c FROM distinct_abc WHERE c = 2+ORDER BY a DESC, b DESC;++FETCH ALL FROM c;+FETCH BACKWARD ALL FROM c;++END;++DROP TABLE distinct_abc;++-- index skip scan+SELECT DISTINCT ON (a) a, b, c+FROM distinct_a ORDER BY a;+SELECT DISTINCT ON (a) a, b, c+FROM distinct_a WHERE a = 1 ORDER BY a;++EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a, b, c+FROM distinct_a ORDER BY a;+EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a, b, c+FROM distinct_a WHERE a = 1 ORDER BY a;++-- check colums order+SELECT DISTINCT a FROM distinct_a WHERE b = 2 AND c = 10;++EXPLAIN (COSTS OFF)+SELECT DISTINCT a FROM distinct_a WHERE b = 2 AND c = 10;++-- check projection case+SELECT DISTINCT a, a FROM distinct_a WHERE b = 2;+SELECT DISTINCT a, 1 FROM distinct_a WHERE b = 2;++-- test cursor forward/backward movements+BEGIN;+DECLARE c SCROLL CURSOR FOR SELECT DISTINCT a FROM distinct_a;++FETCH FROM c;+FETCH BACKWARD FROM c;++FETCH 6 FROM c;+FETCH BACKWARD 6 FROM c;++FETCH 6 FROM c;+FETCH BACKWARD 6 FROM c;++END;++DROP TABLE distinct_a;++-- test tuples visibility+CREATE TABLE distinct_visibility (a int, b int);+INSERT INTO distinct_visibility (select a, b from generate_series(1,5) a, generate_series(1, 10000) b);+CREATE INDEX ON distinct_visibility (a, b);+ANALYZE distinct_visibility;++SELECT DISTINCT ON (a) a, b FROM distinct_visibility ORDER BY a, b;+DELETE FROM distinct_visibility WHERE a = 2 and b = 1;+SELECT DISTINCT ON (a) a, b FROM distinct_visibility ORDER BY a, b;++SELECT DISTINCT ON (a) a, b FROM distinct_visibility ORDER BY a DESC, b DESC;+DELETE FROM distinct_visibility WHERE a = 2 and b = 10000;+SELECT DISTINCT ON (a) a, b FROM distinct_visibility ORDER BY a DESC, b DESC;+DROP TABLE distinct_visibility;++-- test page boundaries+CREATE TABLE distinct_boundaries AS+ SELECT a, b::int2 b, (b % 2)::int2 c FROM+ generate_series(1, 5) a,+ generate_series(1,366) b;++CREATE INDEX ON distinct_boundaries (a, b, c);+ANALYZE distinct_boundaries;++EXPLAIN (COSTS OFF)+SELECT DISTINCT ON (a) a, b, c from distinct_boundaries+WHERE b >= 1 and c = 0 ORDER BY a, b;++SELECT DISTINCT ON (a) a, b, c from distinct_boundaries+WHERE b >= 1 and c = 0 ORDER BY a, b;++DROP TABLE distinct_boundaries;++-- test tuple killing++-- DESC ordering+CREATE TABLE distinct_killed AS+ SELECT a, b, b % 2 AS c, 10 AS d+ FROM generate_series(1, 5) a,+ generate_series(1,1000) b;++CREATE INDEX ON distinct_killed (a, b, c, d);++DELETE FROM distinct_killed where a = 3;++BEGIN;+ DECLARE c SCROLL CURSOR FOR+ SELECT DISTINCT ON (a) a,b,c,d+ FROM distinct_killed ORDER BY a DESC, b DESC;+ FETCH FORWARD ALL FROM c;+ FETCH BACKWARD ALL FROM c;+COMMIT;++DROP TABLE distinct_killed;++-- regular ordering+CREATE TABLE distinct_killed AS+ SELECT a, b, b % 2 AS c, 10 AS d+ FROM generate_series(1, 5) a,+ generate_series(1,1000) b;++CREATE INDEX ON distinct_killed (a, b, c, d);++DELETE FROM distinct_killed where a = 3;++BEGIN;+ DECLARE c SCROLL CURSOR FOR+ SELECT DISTINCT ON (a) a,b,c,d+ FROM distinct_killed ORDER BY a, b;+ FETCH FORWARD ALL FROM c;+ FETCH BACKWARD ALL FROM c;+COMMIT;++DROP TABLE distinct_killed;++-- partial delete+CREATE TABLE distinct_killed AS+ SELECT a, b, b % 2 AS c, 10 AS d+ FROM generate_series(1, 5) a,+ generate_series(1,1000) b;++CREATE INDEX ON distinct_killed (a, b, c, d);++DELETE FROM distinct_killed WHERE a = 3 AND b <= 999;++BEGIN;+ DECLARE c SCROLL CURSOR FOR+ SELECT DISTINCT ON (a) a,b,c,d+ FROM distinct_killed ORDER BY a DESC, b DESC;+ FETCH FORWARD ALL FROM c;+ FETCH BACKWARD ALL FROM c;+COMMIT;++DROP TABLE distinct_killed;--
2.21.0
[text/x-diff] v35-0004-Index-skip-scan-documentation.patch (4.6K, ../20200609102247.jdlatmfyeecg52fi@localhost/7-v35-0004-Index-skip-scan-documentation.patch)
download | inline diff:
From 8b23b1130f9338b8ef852e93efaa1b2f9e58319e Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:45:21 +0200
Subject: [PATCH v35 6/6] Index skip scan documentation
Covers added GUC and the extenion of index am interface.
Author: Jesper Pedersen, Dmitry Dolgov
Reviewed-by: Thomas Munro, David Rowley, Floris Van Nee, Kyotaro Horiguchi, Tomas Vondra, Peter Geoghegan
---
doc/src/sgml/config.sgml | 15 ++++++++++
doc/src/sgml/indexam.sgml | 62 +++++++++++++++++++++++++++++++++++++++
doc/src/sgml/indices.sgml | 23 +++++++++++++++
3 files changed, 100 insertions(+)
diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgmlindex aca8f73a50..0da4ba1a12 100644--- a/doc/src/sgml/config.sgml+++ b/doc/src/sgml/config.sgml@@ -4652,6 +4652,21 @@ ANY <replaceable class="parameter">num_sync</replaceable> ( <replaceable class="
</listitem>
</varlistentry>
+ <varlistentry id="guc-enable-indexskipscan" xreflabel="enable_indexskipscan">+ <term><varname>enable_indexskipscan</varname> (<type>boolean</type>)+ <indexterm>+ <primary><varname>enable_indexskipscan</varname> configuration parameter</primary>+ </indexterm>+ </term>+ <listitem>+ <para>+ Enables or disables the query planner's use of index-skip-scan plan+ types (see <xref linkend="indexes-index-skip-scans"/>). The default is+ <literal>on</literal>.+ </para>+ </listitem>+ </varlistentry>+
<varlistentry id="guc-enable-material" xreflabel="enable_material">
<term><varname>enable_material</varname> (<type>boolean</type>)
<indexterm>
diff --git a/doc/src/sgml/indexam.sgml b/doc/src/sgml/indexam.sgmlindex 6844a4d5c8..a726d80878 100644--- a/doc/src/sgml/indexam.sgml+++ b/doc/src/sgml/indexam.sgml@@ -692,6 +692,68 @@ amrestrpos (IndexScanDesc scan);
<para>
<programlisting>
+bool+amskip (IndexScanDesc scan,+ ScanDirection direction,+ ScanDirection indexdir,+ bool scanstart,+ int prefix);+</programlisting>+ Skip past all tuples where the first 'prefix' columns have the same value as+ the last tuple returned in the current scan. The arguments are:++ <variablelist>+ <varlistentry>+ <term><parameter>scan</parameter></term>+ <listitem>+ <para>+ Index scan information+ </para>+ </listitem>+ </varlistentry>++ <varlistentry>+ <term><parameter>direction</parameter></term>+ <listitem>+ <para>+ The direction in which data is advancing.+ </para>+ </listitem>+ </varlistentry>++ <varlistentry>+ <term><parameter>indexdir</parameter></term>+ <listitem>+ <para>+ The index direction, in which data must be read.+ </para>+ </listitem>+ </varlistentry>++ <varlistentry>+ <term><parameter>scanstart</parameter></term>+ <listitem>+ <para>+ Whether or not it is a start of the scan.+ </para>+ </listitem>+ </varlistentry>++ <varlistentry>+ <term><parameter>prefix</parameter></term>+ <listitem>+ <para>+ Distinct prefix size.+ </para>+ </listitem>+ </varlistentry>++ </variablelist>++ </para>++ <para>+<programlisting>
Size
amestimateparallelscan (void);
</programlisting>
diff --git a/doc/src/sgml/indices.sgml b/doc/src/sgml/indices.sgmlindex 28adaba72d..1cf8550e0c 100644--- a/doc/src/sgml/indices.sgml+++ b/doc/src/sgml/indices.sgml@@ -1281,6 +1281,29 @@ SELECT target FROM tests WHERE subject = 'some-subject' AND success;
and later will recognize such cases and allow index-only scans to be
generated, but older versions will not.
</para>
++ <sect2 id="indexes-index-skip-scans">+ <title>Index Skip Scans</title>++ <indexterm zone="indexes-index-skip-scans">+ <primary>index</primary>+ <secondary>index-skip scans</secondary>+ </indexterm>+ <indexterm zone="indexes-index-skip-scans">+ <primary>index-skip scan</primary>+ </indexterm>++ <para>+ When the rows retrieved from an index scan are then deduplicated by+ eliminating rows matching on a prefix of index keys (e.g. when using+ <literal>SELECT DISTINCT</literal>), the planner will consider+ skipping groups of rows with a matching key prefix. When a row with+ a particular prefix is found, remaining rows with the same key prefix+ are skipped. The larger the number of rows with the same key prefix+ rows (i.e. the lower the number of distinct key prefixes in the index),+ the more efficient this is.+ </para>+ </sect2>
</sect1>
--
2.21.0
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: 9erthalion6@gmail.com, jesper.pedersen@redhat.com, dgrowleyml@gmail.com, florisvannee@optiver.com, horikyota.ntt@gmail.com, pg@bowt.ie, thomas.munro@gmail.com, tomas.vondra@2ndquadrant.com, zhihui.fan1213@gmail.com, dilipbalaut@gmail.com
Subject: Re: Index Skip Scan (new UniqueKeys)
In-Reply-To: <20200609102247.jdlatmfyeecg52fi@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox