From: Floris Van Nee <florisvannee@Optiver.com>
To: Dmitry Dolgov <9erthalion6@gmail.com>
Cc: Andy Fan <zhihui.fan1213@gmail.com>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Cc: Jesper Pedersen <jesper.pedersen@redhat.com>
Cc: David Rowley <dgrowleyml@gmail.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: Dilip Kumar <dilipbalaut@gmail.com>
Subject: RE: Index Skip Scan (new UniqueKeys)
Date: Sun, 12 Jul 2020 12:48:47 +0000
Message-ID: <ef9954d83a9e42fabfac235bdd87d05a@opammb0561.comp.optiver.com> (raw)
In-Reply-To: <20200711162103.hiygat3k6wu2d25p@localhost>
References: <20200609102247.jdlatmfyeecg52fi@localhost>
<CAKU4AWrqYz7-+rr=mGe8w6i=NsAZap6cKe=QoQsYGeb4AuiSaA@mail.gmail.com>
<20200629120709.52w2zi36mtzyliv2@localhost>
<fb18ee881ea24d31b5272b4e5053a6aa@opammb0561.comp.optiver.com>
<20200711162103.hiygat3k6wu2d25p@localhost>
>
> Good point, thanks for looking at this. With the latest planner version there
> are indeed more possibilities to use skipping. It never occured to me that
> some of those paths will still rely on index scan returning full data set. I'll look
> in details and add verification to prevent putting something like this on top of
> skip scan in the next version.
I believe the required changes are something like in attached patch. There were a few things I've changed:
- build_uniquekeys was constructing the list incorrectly. For a DISTINCT a,b, it would create two unique keys, one with a and one with b. However, it should be one unique key with (a,b).
- the uniquekeys that is built, still contains some redundant keys, that are normally eliminated from the path keys lists.
- the distinct_pathkeys may be NULL, even though there's a possibility for skipping. But it wouldn't create the uniquekeys in this case. This makes the planner not choose skip scans even though it could. For example in queries that do SELECT DISTINCT ON (a) * FROM t1 WHERE a=1 ORDER BY a,b; Since a is constant, it's eliminated from regular pathkeys.
- to combat the issues mentioned earlier, there's now a check in build_index_paths that checks if the query_pathkeys matches the useful_pathkeys. Note that we have to use the path keys here rather than any of the unique keys. The unique keys are only Expr nodes - they do not contain the necessary information about ordering. Due to elimination of some constant path keys, we have to search the attributes of the index to find the correct prefix to use in skipping.
- creating the skip scan path did not actually fill the Path's unique keys. It should just set this to query_uniquekeys.
I've attached the first two unique-keys patches (v9, 0001, 0002)), your patches, but rebased on v9 of unique keys (0003-0006) + a diff patch (0007) that applies my suggested changes on top of it.
-Floris
Attachments:
[application/octet-stream] 0001-Introduce-RelOptInfo-notnullattrs-attribute.patch (4.8K, ../ef9954d83a9e42fabfac235bdd87d05a@opammb0561.comp.optiver.com/2-0001-Introduce-RelOptInfo-notnullattrs-attribute.patch)
download | inline diff:
From c46a3317ed53ad8e24d1ed1f6b95b0687071f6c6 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 1/7] Introduce RelOptInfo->notnullattrs attribute
The notnullattrs is calculated from catalog and run-time query. That
infomation is translated to child relation as well for partitioned
table.
---
src/backend/optimizer/path/allpaths.c | 31 ++++++++++++++++++++++++++
src/backend/optimizer/plan/initsplan.c | 10 +++++++++
src/backend/optimizer/util/plancat.c | 10 +++++++++
src/include/nodes/pathnodes.h | 2 ++
4 files changed, 53 insertions(+)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.cindex c4e1967f12..9dade061c8 100644--- a/src/backend/optimizer/path/allpaths.c+++ b/src/backend/optimizer/path/allpaths.c@@ -1005,6 +1005,7 @@ set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
RelOptInfo *childrel;
ListCell *parentvars;
ListCell *childvars;
+ int i = -1;
/* append_rel_list contains all append rels; ignore others */
if (appinfo->parent_relid != parentRTindex)
@@ -1061,6 +1062,36 @@ set_append_rel_size(PlannerInfo *root, RelOptInfo *rel,
(Node *) rel->reltarget->exprs,
1, &appinfo);
+ /* Copy notnullattrs. */+ while ((i = bms_next_member(rel->notnullattrs, i)) > 0)+ {+ AttrNumber attno = i + FirstLowInvalidHeapAttributeNumber;+ AttrNumber child_attno;+ if (attno == 0)+ {+ /* Whole row is not null, so must be same for child */+ childrel->notnullattrs = bms_add_member(childrel->notnullattrs,+ attno - FirstLowInvalidHeapAttributeNumber);+ break;+ }+ if (attno < 0 )+ /* no need to translate system column */+ child_attno = attno;+ else+ {+ Node * node = list_nth(appinfo->translated_vars, attno - 1);+ if (!IsA(node, Var))+ /* This may happens at UNION case, like (SELECT a FROM t1 UNION SELECT a + 3+ * FROM t2) t and we know t.a is not null+ */+ continue;+ child_attno = castNode(Var, node)->varattno;+ }++ childrel->notnullattrs = bms_add_member(childrel->notnullattrs,+ child_attno - FirstLowInvalidHeapAttributeNumber);+ }+
/*
* We have to make child entries in the EquivalenceClass data
* structures as well. This is needed either if the parent
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.25.0
[application/octet-stream] 0002-Introduce-UniqueKey-attributes-on-RelOptInfo-struct.patch (58.6K, ../ef9954d83a9e42fabfac235bdd87d05a@opammb0561.comp.optiver.com/3-0002-Introduce-UniqueKey-attributes-on-RelOptInfo-struct.patch)
download | inline diff:
From b7f578b700956374312885fbc5060a23ab64da51 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= <yizhi.fzh@alibaba-inc.com>
Date: Mon, 11 May 2020 15:50:52 +0800
Subject: [PATCH 2/7] Introduce UniqueKey attributes on RelOptInfo struct.
UniqueKey is a set of exprs on RelOptInfo which represents the exprs
will be unique on the given RelOptInfo. You can see README.uniquekey
for more information.
---
src/backend/nodes/copyfuncs.c | 13 +
src/backend/nodes/list.c | 31 +
src/backend/nodes/makefuncs.c | 13 +
src/backend/nodes/outfuncs.c | 11 +
src/backend/nodes/readfuncs.c | 10 +
src/backend/optimizer/path/Makefile | 3 +-
src/backend/optimizer/path/README.uniquekey | 131 +++
src/backend/optimizer/path/allpaths.c | 10 +
src/backend/optimizer/path/joinpath.c | 9 +-
src/backend/optimizer/path/joinrels.c | 2 +
src/backend/optimizer/path/pathkeys.c | 3 +-
src/backend/optimizer/path/uniquekeys.c | 1131 +++++++++++++++++++
src/backend/optimizer/plan/planner.c | 13 +-
src/backend/optimizer/prep/prepunion.c | 2 +
src/backend/optimizer/util/appendinfo.c | 44 +
src/backend/optimizer/util/inherit.c | 16 +-
src/include/nodes/makefuncs.h | 3 +
src/include/nodes/nodes.h | 1 +
src/include/nodes/pathnodes.h | 29 +-
src/include/nodes/pg_list.h | 2 +
src/include/optimizer/appendinfo.h | 3 +
src/include/optimizer/optimizer.h | 2 +
src/include/optimizer/paths.h | 43 +
23 files changed, 1502 insertions(+), 23 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/copyfuncs.c b/src/backend/nodes/copyfuncs.cindex d8cf87e6d0..efe7c3ae10 100644--- a/src/backend/nodes/copyfuncs.c+++ b/src/backend/nodes/copyfuncs.c@@ -2273,6 +2273,16 @@ _copyPathKey(const PathKey *from)
return newnode;
}
+static UniqueKey *+_copyUniqueKey(const UniqueKey *from)+{+ UniqueKey *newnode = makeNode(UniqueKey);++ COPY_NODE_FIELD(exprs);+ COPY_SCALAR_FIELD(multi_nullvals);++ return newnode;+}
/*
* _copyRestrictInfo
*/
@@ -5152,6 +5162,9 @@ copyObjectImpl(const void *from)
case T_PathKey:
retval = _copyPathKey(from);
break;
+ case T_UniqueKey:+ retval = _copyUniqueKey(from);+ break;
case T_RestrictInfo:
retval = _copyRestrictInfo(from);
break;
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.cindex 80fa8c84e4..a7a99b70f2 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 every entry in "members" list is also present+ * in the "target" list.+ */+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 49de285f01..646cf7c9a1 100644--- a/src/backend/nodes/makefuncs.c+++ b/src/backend/nodes/makefuncs.c@@ -814,3 +814,16 @@ makeVacuumRelation(RangeVar *relation, Oid oid, List *va_cols)
v->va_cols = va_cols;
return v;
}
+++/*+ * makeUniqueKey+ */+UniqueKey*+makeUniqueKey(List *exprs, bool multi_nullvals)+{+ UniqueKey * ukey = makeNode(UniqueKey);+ ukey->exprs = exprs;+ ukey->multi_nullvals = multi_nullvals;+ return ukey;+}diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.cindex e2f177515d..c3a9632992 100644--- a/src/backend/nodes/outfuncs.c+++ b/src/backend/nodes/outfuncs.c@@ -2428,6 +2428,14 @@ _outPathKey(StringInfo str, const PathKey *node)
WRITE_BOOL_FIELD(pk_nulls_first);
}
+static void+_outUniqueKey(StringInfo str, const UniqueKey *node)+{+ WRITE_NODE_TYPE("UNIQUEKEY");+ WRITE_NODE_FIELD(exprs);+ WRITE_BOOL_FIELD(multi_nullvals);+}+
static void
_outPathTarget(StringInfo str, const PathTarget *node)
{
@@ -4127,6 +4135,9 @@ outNode(StringInfo str, const void *obj)
case T_PathKey:
_outPathKey(str, obj);
break;
+ case T_UniqueKey:+ _outUniqueKey(str, obj);+ break;
case T_PathTarget:
_outPathTarget(str, obj);
break;
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.cindex 42050ab719..3a18571d0c 100644--- a/src/backend/nodes/readfuncs.c+++ b/src/backend/nodes/readfuncs.c@@ -452,6 +452,14 @@ _readSetOperationStmt(void)
READ_DONE();
}
+static UniqueKey *+_readUniqueKey(void)+{+ READ_LOCALS(UniqueKey);+ READ_NODE_FIELD(exprs);+ READ_BOOL_FIELD(multi_nullvals);+ READ_DONE();+}
/*
* Stuff from primnodes.h.
@@ -2656,6 +2664,8 @@ parseNodeString(void)
return_value = _readCommonTableExpr();
else if (MATCH("SETOPERATIONSTMT", 16))
return_value = _readSetOperationStmt();
+ else if (MATCH("UNIQUEKEY", 9))+ return_value = _readUniqueKey();
else if (MATCH("ALIAS", 5))
return_value = _readAlias();
else if (MATCH("RANGEVAR", 8))
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..5eac761995--- /dev/null+++ b/src/backend/optimizer/path/README.uniquekey@@ -0,0 +1,131 @@+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;+} UniqueKey;++exprs is a list of exprs which is unique on current RelOptInfo. exprs = NIL+is a special case of UniqueKey, which means there is only one row in that+relation.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. this logic is handled specially in add_uniquekey_for_onerow+function.++multi_nullvals: true means multi null values may exist 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.+++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. Index Skip Scan (WIP)+6. 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.++1. The first part is about baserel. We handled 3 cases. suppose we have Unique+Index on (a, b).++1. SELECT a, b FROM t. UniqueKey (a, b)+2. SELECT a FROM t WHERE b = 1; UniqueKey (a)+3. SELECT .. FROM t WHERE a = 1 AND b = 1; UniqueKey (NIL). onerow case, every+ column is Unique.++2. The next part is joinrel, this part is most error-prone, 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.+++3. When we comes to subquery, we need to convert_subquery_unqiuekeys just like+convert_subquery_pathkeys. Only the UniqueKey insides subquery is referenced as+a Var in outer relation will be reused. The relationship between the outerrel.Var+and subquery.exprs is built with outerel->subroot->processed_tlist.+++4. As for the SRF functions, it will break the uniqueness of uniquekey, However it+is handled in adjust_paths_for_srfs, which happens after the query_planner. so+we will maintain the UniqueKey until there and reset it to NIL at that+places. This can't help on distinct/group by elimination cases but probably help+in some other cases, like reduce_unqiue_semijoins/remove_useless_joins and it is+semantic correctly.+++5. As for inherit table, we first main the UnqiueKey on childrel as well. But for+partitioned table we need to maintain 2 different kinds of+UnqiueKey. 1). UniqueKey on the parent relation 2). UniqueKey on child+relation for partition wise query.++Example:+CREATE TABLE p (a int not null, b int not null) partition by list (a);+CREATE TABLE p0 partition of p for values in (1);+CREATE TABLE p1 partition of p for values in (2);++create unique index p0_b on p0(b);+create unique index p1_b on p1(b);++Now b is only unique on partition level, so the distinct can't be removed on+the following cases. SELECT DISTINCT b FROM p;++Another example is SELECT DISTINCT a, b FROM p WHERE a = 1; Since only one+partition is chosen, the UniqueKey on child relation is same as the UniqueKey on+parent relation.++Another usage of UniqueKey on partition level is it be helpful for+partition-wise join.++As for the UniqueKey on parent table level, it comes with 2 different ways,+1). the UniqueKey is also derived in UniqueKey index, but the index must be same+in all the related children relations and the unique index must contains+Partition Key in it. Example:++CREATE UNIQUE INDEX p_ab ON p(a, b); -- where a is the partition key.++-- Query+SELECT a, b FROM p; the (a, b) is a UniqueKey of p.++2). If the parent relation has only one childrel, the UniqueKey on childrel is+ the UniqueKey on parent as well.diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.cindex 9dade061c8..b58bac6175 100644--- a/src/backend/optimizer/path/allpaths.c+++ b/src/backend/optimizer/path/allpaths.c@@ -579,6 +579,12 @@ set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte)
*/
check_index_predicates(root, rel);
+ /*+ * Now that we've marked which partial indexes are suitable, we can now+ * build the relation's unique keys.+ */+ populate_baserel_uniquekeys(root, rel, rel->indexlist);+
/* Mark rel with estimated output rows, width, etc */
set_baserel_size_estimates(root, rel);
}
@@ -1310,6 +1316,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);
}
@@ -2383,6 +2391,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/joinpath.c b/src/backend/optimizer/path/joinpath.cindex db54a6ba2e..ef0fd2fb0b 100644--- a/src/backend/optimizer/path/joinpath.c+++ b/src/backend/optimizer/path/joinpath.c@@ -71,13 +71,6 @@ static void consider_parallel_mergejoin(PlannerInfo *root,
static void hash_inner_and_outer(PlannerInfo *root, RelOptInfo *joinrel,
RelOptInfo *outerrel, RelOptInfo *innerrel,
JoinType jointype, JoinPathExtraData *extra);
-static List *select_mergejoin_clauses(PlannerInfo *root,- RelOptInfo *joinrel,- RelOptInfo *outerrel,- RelOptInfo *innerrel,- List *restrictlist,- JoinType jointype,- bool *mergejoin_allowed);
static void generate_mergejoin_paths(PlannerInfo *root,
RelOptInfo *joinrel,
RelOptInfo *innerrel,
@@ -1927,7 +1920,7 @@ hash_inner_and_outer(PlannerInfo *root,
* if it is mergejoinable and involves vars from the two sub-relations
* currently of interest.
*/
-static List *+List *
select_mergejoin_clauses(PlannerInfo *root,
RelOptInfo *joinrel,
RelOptInfo *outerrel,
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..b33bcd2f32--- /dev/null+++ b/src/backend/optimizer/path/uniquekeys.c@@ -0,0 +1,1131 @@+/*-------------------------------------------------------------------------+ *+ * 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/appendinfo.h"+#include "optimizer/optimizer.h"+#include "optimizer/tlist.h"+#include "rewrite/rewriteManip.h"+++/*+ * 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_uniqueindex(IndexOptInfo *unique_index,+ List *const_exprs,+ List *const_expr_opfamilies,+ Bitmapset *used_varattrs,+ bool *useful,+ bool *multi_nullvals);+static List *get_exprs_from_uniquekey(RelOptInfo *joinrel,+ RelOptInfo *rel1,+ UniqueKey *ukey);+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(PlannerInfo *root,+ RelOptInfo *parentrel,+ IndexOptInfo *from);+static bool simple_indexinfo_equal(IndexOptInfo *ind1, IndexOptInfo *ind2);+static void adjust_partition_unique_indexlist(PlannerInfo *root,+ 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+ * and baserestrictinfo+ */+void+populate_baserel_uniquekeys(PlannerInfo *root,+ RelOptInfo *baserel,+ List *indexlist)+{+ ListCell *lc;+ List *matched_uniq_indexes = NIL;++ /* Attrs appears in rel->reltarget->exprs. */+ Bitmapset *used_attrs = NULL;++ List *const_exprs = NIL;+ List *expr_opfamilies = NIL;++ Assert(baserel->rtekind == RTE_RELATION);++ foreach(lc, indexlist)+ {+ IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);+ if (!ind->unique || !ind->immediate ||+ (ind->indpred != NIL && !ind->predOK))+ continue;+ matched_uniq_indexes = lappend(matched_uniq_indexes, ind);+ }++ if (matched_uniq_indexes == NIL)+ return;++ /* Check which attrs is used in baserel->reltarget */+ pull_varattnos((Node *)baserel->reltarget->exprs, baserel->relid, &used_attrs);++ /* Check which attrno is used at a mergeable const filter */+ foreach(lc, baserel->baserestrictinfo)+ {+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);++ if (rinfo->mergeopfamilies == NIL)+ continue;++ if (bms_is_empty(rinfo->left_relids))+ {+ const_exprs = lappend(const_exprs, get_rightop(rinfo->clause));+ }+ else if (bms_is_empty(rinfo->right_relids))+ {+ const_exprs = lappend(const_exprs, get_leftop(rinfo->clause));+ }+ else+ continue;++ expr_opfamilies = lappend(expr_opfamilies, rinfo->mergeopfamilies);+ }++ foreach(lc, matched_uniq_indexes)+ {+ bool multi_nullvals, useful;+ List *exprs = get_exprs_from_uniqueindex(lfirst_node(IndexOptInfo, lc),+ const_exprs,+ expr_opfamilies,+ used_attrs,+ &useful,+ &multi_nullvals);+ if (useful)+ {+ if (exprs == NIL)+ {+ /* All the columns in Unique Index matched with a restrictinfo */+ add_uniquekey_for_onerow(baserel);+ return;+ }+ baserel->uniquekeys = lappend(baserel->uniquekeys,+ makeUniqueKey(exprs, multi_nullvals));+ }+ }+}+++/*+ * populate_partitionedrel_uniquekeys+ * The UniqueKey on partitionrel comes from 2 cases:+ * 1). Only one partition is involved in this query, the unique key can be+ * copied to parent rel from childrel.+ * 2). There are some unique index which includes partition key and exists+ * in all the related partitions.+ * We never mind rule 2 if we hit rule 1.+ */++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 (childrels == NIL)+ return;++ /*+ * If there is only one partition used in this query, the UniqueKey in childrel is+ * still valid in parent level, but we need convert the format from child expr to+ * parent expr.+ */+ if (list_length(childrels) == 1)+ {+ /* Check for Rule 1 */+ RelOptInfo *childrel = linitial_node(RelOptInfo, childrels);+ ListCell *lc;+ Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);+ if (relation_is_onerow(childrel))+ {+ add_uniquekey_for_onerow(rel);+ return;+ }++ foreach(lc, childrel->uniquekeys)+ {+ UniqueKey *ukey = lfirst_node(UniqueKey, lc);+ AppendRelInfo *appinfo = find_appinfo_by_child(root, childrel->relid);+ List *parent_exprs = NIL;+ bool can_reuse = true;+ ListCell *lc2;+ foreach(lc2, ukey->exprs)+ {+ Var *var = (Var *)lfirst(lc2);+ /*+ * If the expr comes from a expression, it is hard to build the expression+ * in parent so ignore that case for now.+ */+ if(!IsA(var, Var))+ {+ can_reuse = false;+ break;+ }+ /* Convert it to parent var */+ parent_exprs = lappend(parent_exprs, find_parent_var(appinfo, var));+ }+ if (can_reuse)+ rel->uniquekeys = lappend(rel->uniquekeys,+ makeUniqueKey(parent_exprs,+ ukey->multi_nullvals));+ }+ }+ else+ {+ /* Check for rule 2 */+ 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;++ /*+ * During simple_copy_indexinfo_to_parent, we need to convert var from+ * child var to parent var, index on expression is too complex to handle.+ * so ignore it for now.+ */+ if (ind->indexprs != NIL)+ continue;++ modified_index = simple_copy_indexinfo_to_parent(root, 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);+ }++ if (global_uniq_indexlist != NIL)+ {+ foreach(lc, childrels)+ {+ RelOptInfo *child = lfirst(lc);+ if (is_first)+ {+ is_first = false;+ continue;+ }+ adjust_partition_unique_indexlist(root, 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,+ RelOptInfo *inputrel)++{+ Query *parse = root->parse;+ bool input_ukey_added = false;+ ListCell *lc;++ if (relation_is_onerow(inputrel))+ {+ add_uniquekey_for_onerow(grouprel);+ return;+ }+ if (parse->groupingSets)+ return;++ /* A Normal group by without grouping set. */+ if (parse->groupClause)+ {+ /*+ * Current even the groupby clause is Unique already, but if query has aggref+ * We have to create grouprel still. To keep the UnqiueKey short, we will check+ * the UniqueKey of input_rel still valid, if so we reuse it.+ */+ foreach(lc, inputrel->uniquekeys)+ {+ UniqueKey *ukey = lfirst_node(UniqueKey, lc);+ if (list_is_subset(ukey->exprs, grouprel->reltarget->exprs))+ {+ grouprel->uniquekeys = lappend(grouprel->uniquekeys,+ ukey);+ input_ukey_added = true;+ }+ }+ if (!input_ukey_added)+ /*+ * group by clause must be a super-set of grouprel->reltarget->exprs except the+ * aggregation expr, so if such exprs is unique already, no bother to generate+ * new uniquekey for group by exprs.+ */+ 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. */+ add_uniquekey_for_onerow(unionrel);+ else+ unionrel->uniquekeys = lappend(unionrel->uniquekeys,+ makeUniqueKey(exprs,false));++}++/*+ * populate_joinrel_uniquekeys+ *+ * populate uniquekeys for joinrel. We will check each relation to see if its+ * UniqueKey is still valid via innerrel_keeps_unique, if so, we add it to+ * joinrel. The multi_nullvals field will be changed to true for some outer+ * join cases and one-row UniqueKey needs to be converted to normal 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;+ bool mergejoin_allowed;++ /* 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 = select_mergejoin_clauses(root, joinrel, outerrel, innerrel,+ restrictlist, jointype,+ &mergejoin_allowed);++ if (innerrel_keeps_unique(root, innerrel, outerrel, clause_list, true /* reverse */))+ {+ bool outer_impact = jointype == JOIN_FULL;+ 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 && !outer_impact)+ {+ add_uniquekey_for_onerow(joinrel);+ return;+ }+ else if (outer_onerow)+ {+ /*+ * The onerow outerrel becomes multi rows and multi_nullvals+ * will be changed to true. We also need to set the exprs correctly since it+ * can't be NIL any more.+ */+ ListCell *lc2;+ foreach(lc2, get_exprs_from_uniquekey(joinrel, outerrel, NULL))+ {+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ makeUniqueKey(lfirst(lc2), true));+ }+ }+ else+ {+ if (!ctx->uniquekey->multi_nullvals && outer_impact)+ /* Change multi_nullvals to true due to the full join. */+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ makeUniqueKey(ctx->uniquekey->exprs, true));+ 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))+ {+ bool outer_impact = jointype == JOIN_FULL || jointype == JOIN_LEFT;;++ foreach(lc, innerrel_ukey_ctx)+ {+ UniqueKeyContext ctx = (UniqueKeyContext)lfirst(lc);++ if (!list_is_subset(ctx->uniquekey->exprs, joinrel->reltarget->exprs))+ {+ ctx->useful = false;+ continue;+ }++ if (inner_onerow && !outer_impact)+ {+ add_uniquekey_for_onerow(joinrel);+ return;+ }+ else if (inner_onerow)+ {+ ListCell *lc2;+ foreach(lc2, get_exprs_from_uniquekey(joinrel, innerrel, NULL))+ {+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ makeUniqueKey(lfirst(lc2), true));+ }+ }+ else+ {+ if (!ctx->uniquekey->multi_nullvals && outer_impact)+ /* Need to change multi_nullvals to true due to the outer join. */+ joinrel->uniquekeys = lappend(joinrel->uniquekeys,+ makeUniqueKey(ctx->uniquekey->exprs,+ true));+ 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));++ }+}++/*+ * 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);+ return ukey->exprs == NIL && list_length(rel->uniquekeys) == 1;+}++/*+ * 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;+}+++/*+ * get_exprs_from_uniqueindex+ *+ * Return a list of exprs which is unique. set useful to false if this+ * unique index is not useful for us.+ */+static List *+get_exprs_from_uniqueindex(IndexOptInfo *unique_index,+ List *const_exprs,+ List *const_expr_opfamilies,+ Bitmapset *used_varattrs,+ bool *useful,+ bool *multi_nullvals)+{+ List *exprs = NIL;+ ListCell *indexpr_item;+ int c = 0;++ *useful = true;+ *multi_nullvals = false;++ indexpr_item = list_head(unique_index->indexprs);+ for(c = 0; c < unique_index->ncolumns; c++)+ {+ int attr = unique_index->indexkeys[c];+ Expr *expr;+ bool matched_const = false;+ ListCell *lc1, *lc2;++ if(attr > 0)+ {+ expr = list_nth_node(TargetEntry, unique_index->indextlist, c)->expr;+ }+ else if (attr == 0)+ {+ /* Expression index */+ expr = lfirst(indexpr_item);+ indexpr_item = lnext(unique_index->indexprs, indexpr_item);+ }+ else /* attr < 0 */+ {+ /* Index on system column is not supported */+ Assert(false);+ }++ /*+ * Check index_col = Const case with regarding to opfamily checking+ * If we can remove the index_col from the final UniqueKey->exprs.+ */+ forboth(lc1, const_exprs, lc2, const_expr_opfamilies)+ {+ if (list_member_oid((List *)lfirst(lc2), unique_index->opfamily[c])+ && match_index_to_operand((Node *) lfirst(lc1), c, unique_index))+ {+ matched_const = true;+ break;+ }+ }++ if (matched_const)+ continue;++ /* Check if the indexed expr is used in rel */+ if (attr > 0)+ {+ /*+ * Normal Indexed column, if the col is not used, then the index is useless+ * for uniquekey.+ */+ attr -= FirstLowInvalidHeapAttributeNumber;++ if (!bms_is_member(attr, used_varattrs))+ {+ *useful = false;+ break;+ }+ }+ else if (!list_member(unique_index->rel->reltarget->exprs, expr))+ {+ /* Expression index but the expression is not used in rel */+ *useful = false;+ break;+ }++ /* check not null property. */+ if (attr == 0)+ {+ /* We never know if a expression yields null or not */+ *multi_nullvals = true;+ }+ else if (!bms_is_member(attr, unique_index->rel->notnullattrs)+ && !bms_is_member(0 - FirstLowInvalidHeapAttributeNumber,+ unique_index->rel->notnullattrs))+ {+ *multi_nullvals = true;+ }++ exprs = lappend(exprs, expr);+ }+ return exprs;+}+++/*+ * 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 exprs = NIL and overwrites all the other UniqueKey on this RelOptInfo+ * since this one has strongest semantics.+ */+void+add_uniquekey_for_onerow(RelOptInfo *rel)+{+ /*+ * We overwrite the previous UniqueKey on purpose since this one has the+ * strongest semantic.+ */+ rel->uniquekeys = list_make1(makeUniqueKey(NIL, false));+}+++/*+ * 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;+}+++/*+ * get_exprs_from_uniquekey+ * Unify the way of get List of exprs from a one-row UniqueKey or+ * normal UniqueKey. for the onerow case, every expr in rel1 is a valid+ * 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));+ Assert(partrel->part_scheme->partnatts > 0);++ 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(get_tlist_exprs(ind1->indextlist, true),+ get_tlist_exprs(ind2->indextlist, true));+}+++/*+ * 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(PlannerInfo *root,+ RelOptInfo *parentrel,+ IndexOptInfo *from)+{+ IndexOptInfo *newnode = makeNode(IndexOptInfo);+ AppendRelInfo *appinfo = find_appinfo_by_child(root, from->rel->relid);+ ListCell *lc;+ int idx = 0;++ 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);++ /* Convert index exprs on child expr to expr on parent */+ foreach(lc, newnode->indextlist)+ {+ TargetEntry *tle = lfirst_node(TargetEntry, lc);+ /* Index on expression is ignored */+ Assert(IsA(tle->expr, Var));+ tle->expr = (Expr *) find_parent_var(appinfo, (Var *) tle->expr);+ newnode->indexkeys[idx] = castNode(Var, tle->expr)->varattno;+ idx++;+ }+ 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(PlannerInfo *root,+ 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(root, parentrel, p_ind);+ if (simple_indexinfo_equal(p_ind_copy, g_ind))+ {+ found_in_child = true;+ break;+ }+ }+ if (!found_in_child)+ /* The index doesn't exist in childrel, remove it from global_unique_indexes */+ *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 or not? levelsup = 1 is just a demo, maybe we need to+ * check every level other than 0, if so, looks we have to 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 */));+}+++/*+ * add_combined_uniquekey+ * The combination of both UniqueKeys is a valid UniqueKey for joinrel no matter+ * the jointype.+ */+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 or we have outer join,+ * the combined UniqueKey has multi_nullvals */+ bool multi_nullvals = outer_ukey->multi_nullvals ||+ inner_ukey->multi_nullvals || IS_OUTER_JOIN(jointype);++ /* The only case we can get onerow joinrel after join */+ if (relation_is_onerow(outer_rel)+ && relation_is_onerow(inner_rel)+ && 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));+ }+ }+ return false;+}diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.cindex b406d41e91..0551ae0512 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, input_rel);
return grouped_rel;
}
@@ -4615,7 +4619,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;
}
@@ -4911,7 +4915,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;
}
@@ -5172,6 +5176,8 @@ create_ordered_paths(PlannerInfo *root,
*/
Assert(ordered_rel->pathlist != NIL);
+ simple_copy_uniquekeys(input_rel, ordered_rel);+
return ordered_rel;
}
@@ -6049,6 +6055,9 @@ adjust_paths_for_srfs(PlannerInfo *root, RelOptInfo *rel,
if (list_length(targets) == 1)
return;
+ /* UniqueKey is not valid after handling the SRF. */+ rel->uniquekeys = NIL;+
/*
* Stack SRF-evaluation nodes atop each path for the 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/backend/optimizer/util/appendinfo.c b/src/backend/optimizer/util/appendinfo.cindex d722063cf3..44c37ecffc 100644--- a/src/backend/optimizer/util/appendinfo.c+++ b/src/backend/optimizer/util/appendinfo.c@@ -746,3 +746,47 @@ find_appinfos_by_relids(PlannerInfo *root, Relids relids, int *nappinfos)
}
return appinfos;
}
++/*+ * find_appinfo_by_child+ *+ */+AppendRelInfo *+find_appinfo_by_child(PlannerInfo *root, Index child_index)+{+ ListCell *lc;+ foreach(lc, root->append_rel_list)+ {+ AppendRelInfo *appinfo = lfirst_node(AppendRelInfo, lc);+ if (appinfo->child_relid == child_index)+ return appinfo;+ }+ elog(ERROR, "parent relation cant be found");+ return NULL;+}++/*+ * find_parent_var+ *+ */+Var *+find_parent_var(AppendRelInfo *appinfo, Var *child_var)+{+ ListCell *lc;+ Var *res = NULL;+ Index attno = 1;+ foreach(lc, appinfo->translated_vars)+ {+ Node *child_node = lfirst(lc);+ if (equal(child_node, child_var))+ {+ res = copyObject(child_var);+ res->varattno = attno;+ res->varno = appinfo->parent_relid;+ }+ attno++;+ }+ if (res == NULL)+ elog(ERROR, "parent var can't be found.");+ return res;+}diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.cindex 3132fd35a5..d66b40ec50 100644--- a/src/backend/optimizer/util/inherit.c+++ b/src/backend/optimizer/util/inherit.c@@ -736,6 +736,7 @@ apply_child_basequals(PlannerInfo *root, RelOptInfo *parentrel,
{
Node *onecq = (Node *) lfirst(lc2);
bool pseudoconstant;
+ RestrictInfo *child_rinfo;
/* check for pseudoconstant (no Vars or volatile functions) */
pseudoconstant =
@@ -747,13 +748,14 @@ apply_child_basequals(PlannerInfo *root, RelOptInfo *parentrel,
root->hasPseudoConstantQuals = true;
}
/* reconstitute RestrictInfo with appropriate properties */
- childquals = lappend(childquals,- make_restrictinfo((Expr *) onecq,- rinfo->is_pushed_down,- rinfo->outerjoin_delayed,- pseudoconstant,- rinfo->security_level,- NULL, NULL, NULL));+ child_rinfo = make_restrictinfo((Expr *) onecq,+ rinfo->is_pushed_down,+ rinfo->outerjoin_delayed,+ pseudoconstant,+ rinfo->security_level,+ NULL, NULL, NULL);+ child_rinfo->mergeopfamilies = rinfo->mergeopfamilies;+ childquals = lappend(childquals, child_rinfo);
/* track minimum security level among child quals */
cq_min_security = Min(cq_min_security, rinfo->security_level);
}
diff --git a/src/include/nodes/makefuncs.h b/src/include/nodes/makefuncs.hindex 31d9aedeeb..c83f17acb7 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);+
#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..02e4458bef 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,28 @@ 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. exprs = NIL+ * is a special case of UniqueKey, which means there is only 1 row in that+ * relation.+ * multi_nullvals: true means multi null values may exist 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.+ */+typedef struct UniqueKey+{+ NodeTag type;+ List *exprs;+ bool multi_nullvals;+} UniqueKey;+
/*
* PathTarget
*
@@ -2473,7 +2496,7 @@ typedef enum
*
* flags indicating what kinds of grouping are possible.
* partial_costs_set is true if the agg_partial_costs and agg_final_costs
- * have been initialized.+ * have been initialized.
* agg_partial_costs gives partial aggregation costs.
* agg_final_costs gives finalization costs.
* target_parallel_safe is true if target is parallel safe.
@@ -2503,8 +2526,8 @@ typedef struct
* limit_tuples is an estimated bound on the number of output tuples,
* or -1 if no LIMIT or couldn't estimate.
* count_est and offset_est are the estimated values of the LIMIT and OFFSET
- * expressions computed by preprocess_limit() (see comments for- * preprocess_limit() for more information).+ * expressions computed by preprocess_limit() (see comments for+ * preprocess_limit() for more information).
*/
typedef struct
{
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/appendinfo.h b/src/include/optimizer/appendinfo.hindex d6a27a60dd..e87c92a054 100644--- a/src/include/optimizer/appendinfo.h+++ b/src/include/optimizer/appendinfo.h@@ -32,4 +32,7 @@ extern Relids adjust_child_relids_multilevel(PlannerInfo *root, Relids relids,
extern AppendRelInfo **find_appinfos_by_relids(PlannerInfo *root,
Relids relids, int *nappinfos);
+extern AppendRelInfo *find_appinfo_by_child(PlannerInfo *root, Index child_index);+extern Var *find_parent_var(AppendRelInfo *appinfo, Var *child_var);+
#endif /* APPENDINFO_H */
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..9217a8d6c6 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -240,5 +240,48 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root,
int strategy, bool nulls_first);
extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
List *live_childrels);
+extern List *select_mergejoin_clauses(PlannerInfo *root,+ RelOptInfo *joinrel,+ RelOptInfo *outerrel,+ RelOptInfo *innerrel,+ List *restrictlist,+ JoinType jointype,+ bool *mergejoin_allowed);++/*+ * 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,+ RelOptInfo *inputrel);+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.25.0
[application/octet-stream] 0003-Extend-UniqueKeys.patch (13.0K, ../ef9954d83a9e42fabfac235bdd87d05a@opammb0561.comp.optiver.com/4-0003-Extend-UniqueKeys.patch)
download | inline diff:
From 6647da1f1c6886fba396babcafad2c3f192ea60e Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:33:56 +0200
Subject: [PATCH 3/7] 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 b33bcd2f32..7d9c0aefbf 100644--- a/src/backend/optimizer/path/uniquekeys.c+++ b/src/backend/optimizer/path/uniquekeys.c@@ -1129,3 +1129,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 0551ae0512..a5f3c28fb5 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;
}
@@ -4815,13 +4823,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 */
@@ -7517,6 +7531,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 02e4458bef..a5c406bd4e 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 */
@@ -1182,6 +1185,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 9217a8d6c6..0cb8030e33 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,
@@ -282,6 +285,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.25.0
[application/octet-stream] 0004-Index-skip-scan.patch (38.4K, ../ef9954d83a9e42fabfac235bdd87d05a@opammb0561.comp.optiver.com/5-0004-Index-skip-scan.patch)
download | inline diff:
From 9b853b827e8c27d5fbc89692b66f00ba32fcd8f5 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:39:13 +0200
Subject: [PATCH 4/7] 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 af87f172a7..8c552c22bd 100644--- a/doc/src/sgml/indexam.sgml+++ b/doc/src/sgml/indexam.sgml@@ -150,6 +150,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 a283e4d45c..3c6258761a 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);
@@ -1703,6 +1724,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)
@@ -1716,6 +1739,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 efe7c3ae10..236bb1435c 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 c3a9632992..88254446ce 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 3a18571d0c..9766fc11ed 100644--- a/src/backend/nodes/readfuncs.c+++ b/src/backend/nodes/readfuncs.c@@ -1829,6 +1829,7 @@ _readIndexScan(void)
READ_NODE_FIELD(indexorderbyorig);
READ_NODE_FIELD(indexorderbyops);
READ_ENUM_FIELD(indexorderdir, ScanDirection);
+ READ_INT_FIELD(indexskipprefixsize);
READ_DONE();
}
@@ -1848,6 +1849,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 945aa93374..fe6ef62e8f 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 031ca0327f..56b2cecdfd 100644--- a/src/backend/utils/misc/guc.c+++ b/src/backend/utils/misc/guc.c@@ -952,6 +952,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 e430e33c7b..95def9aa34 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 0187989fd1..cf1e729bec 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 a5c406bd4e..7287594582 100644--- a/src/include/nodes/pathnodes.h+++ b/src/include/nodes/pathnodes.h@@ -1229,6 +1229,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
@@ -1241,6 +1244,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 613db8eab6..c0f176eaaa 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 06c4c3e476..4da9594925 100644--- a/src/test/regress/expected/sysviews.out+++ b/src/test/regress/expected/sysviews.out@@ -79,6 +79,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_incremental_sort | on
enable_indexonlyscan | on
enable_indexscan | on
+ enable_indexskipscan | on
enable_material | on
enable_mergejoin | on
enable_nestloop | on
@@ -90,7 +91,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(18 rows)+(20 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.25.0
[application/octet-stream] 0005-Btree-implementation-of-skipping.patch (40.0K, ../ef9954d83a9e42fabfac235bdd87d05a@opammb0561.comp.optiver.com/6-0005-Btree-implementation-of-skipping.patch)
download | inline diff:
From 6456f0ff5e1a80a745bfb1e79ec90721ff9495d0 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:45:08 +0200
Subject: [PATCH 5/7] 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 f228c87a2b..b0162a0628 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()
@@ -1483,6 +1486,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
*
@@ -2479,3 +2893,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 79506c748b..efd27c6261 100644--- a/src/include/access/nbtree.h+++ b/src/include/access/nbtree.h@@ -938,6 +938,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 */
@@ -1095,6 +1098,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);
@@ -1119,6 +1124,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.25.0
[application/octet-stream] 0006-Index-skip-scan-documentation.patch (4.6K, ../ef9954d83a9e42fabfac235bdd87d05a@opammb0561.comp.optiver.com/7-0006-Index-skip-scan-documentation.patch)
download | inline diff:
From 0bea40cc7ab57fe5568e891a9e5e3d2d48054069 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:45:21 +0200
Subject: [PATCH 6/7] 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 b353c61683..aa89e96fc0 100644--- a/doc/src/sgml/config.sgml+++ b/doc/src/sgml/config.sgml@@ -4620,6 +4620,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 8c552c22bd..b3ca91211f 100644--- a/doc/src/sgml/indexam.sgml+++ b/doc/src/sgml/indexam.sgml@@ -694,6 +694,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.25.0
[application/octet-stream] 0007-planner-fixes.patch (11.2K, ../ef9954d83a9e42fabfac235bdd87d05a@opammb0561.comp.optiver.com/8-0007-planner-fixes.patch)
download | inline diff:
From 0bd1749cffc389fb38111903f38f18e84218e5d1 Mon Sep 17 00:00:00 2001
From: Floris van Nee <florisvannee@optiver.com>
Date: Sun, 12 Jul 2020 13:36:25 +0200
Subject: [PATCH 7/7] planner fixes
---
src/backend/optimizer/path/indxpath.c | 44 +++++++++++----
src/backend/optimizer/path/pathkeys.c | 72 +++++++++++++++++++++++++
src/backend/optimizer/path/uniquekeys.c | 17 +++---
src/backend/optimizer/plan/planner.c | 14 +++--
src/backend/optimizer/util/pathnode.c | 36 ++-----------
src/include/optimizer/pathnode.h | 2 +-
src/include/optimizer/paths.h | 4 ++
src/test/regress/expected/sysviews.out | 2 +-
8 files changed, 129 insertions(+), 62 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.cindex 340bbfcbb3..9eff71e5d5 100644--- a/src/backend/optimizer/path/indxpath.c+++ b/src/backend/optimizer/path/indxpath.c@@ -1119,15 +1119,27 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
/* Consider index skip scan as well */
if (root->query_uniquekeys != NULL && can_skip && !not_empty_qual)
{
- ListCell *lc;+ int numusefulkeys = list_length(useful_pathkeys);+ int numsortkeys = list_length(root->query_pathkeys);- foreach(lc, root->query_uniquekeys)+ if (numusefulkeys == numsortkeys)
{
- UniqueKey *ukey = lfirst_node(UniqueKey, lc);+ int prefix;+ if (list_length(root->distinct_pathkeys) > 0)+ prefix = find_index_prefix_for_pathkey(root,+ index,+ ForwardScanDirection,+ llast_node(PathKey,+ root->distinct_pathkeys));+ else+ /* all are distinct keys are constant and optimized away.+ * skipping with 1 is sufficient as all are constant anyway+ */+ prefix = 1;+
result = lappend(result,
create_skipscan_unique_path(root, index,
- (Path *) ipath,- ukey->exprs));+ (Path *) ipath, prefix));
}
}
@@ -1189,15 +1201,27 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
/* Consider index skip scan as well */
if (root->query_uniquekeys != NULL && can_skip && !not_empty_qual)
{
- ListCell *lc;+ int numusefulkeys = list_length(useful_pathkeys);+ int numsortkeys = list_length(root->query_pathkeys);- foreach(lc, root->query_uniquekeys)+ if (numusefulkeys == numsortkeys)
{
- UniqueKey *ukey = lfirst_node(UniqueKey, lc);+ int prefix;+ if (list_length(root->distinct_pathkeys) > 0)+ prefix = find_index_prefix_for_pathkey(root,+ index,+ BackwardScanDirection,+ llast_node(PathKey,+ root->distinct_pathkeys));+ else+ /* all are distinct keys are constant and optimized away.+ * skipping with 1 is sufficient as all are constant anyway+ */+ prefix = 1;+
result = lappend(result,
create_skipscan_unique_path(root, index,
- (Path *) ipath,- ukey->exprs));+ (Path *) ipath, prefix));
}
}
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.cindex a4fc4f252d..3fa533be95 100644--- a/src/backend/optimizer/path/pathkeys.c+++ b/src/backend/optimizer/path/pathkeys.c@@ -522,6 +522,78 @@ get_cheapest_parallel_safe_total_inner(List *paths)
* NEW PATHKEY FORMATION
****************************************************************************/
+/*+ * Find the prefix size for a specific path key in an index.+ * For example, an index with (a,b,c) finding path key b will+ * return prefix 2.+ * Returns 0 when not found.+ */+int+find_index_prefix_for_pathkey(PlannerInfo *root,+ IndexOptInfo *index,+ ScanDirection scandir,+ PathKey *pathkey)+{+ ListCell *lc;+ int i;++ i = 0;+ foreach(lc, index->indextlist)+ {+ TargetEntry *indextle = (TargetEntry *) lfirst(lc);+ Expr *indexkey;+ bool reverse_sort;+ bool nulls_first;+ PathKey *cpathkey;++ /*+ * INCLUDE columns are stored in index unordered, so they don't+ * support ordered index scan.+ */+ if (i >= index->nkeycolumns)+ break;++ /* We assume we don't need to make a copy of the tlist item */+ indexkey = indextle->expr;++ if (ScanDirectionIsBackward(scandir))+ {+ reverse_sort = !index->reverse_sort[i];+ nulls_first = !index->nulls_first[i];+ }+ else+ {+ reverse_sort = index->reverse_sort[i];+ nulls_first = index->nulls_first[i];+ }++ /*+ * OK, try to make a canonical pathkey for this sort key. Note we're+ * underneath any outer joins, so nullable_relids should be NULL.+ */+ cpathkey = make_pathkey_from_sortinfo(root,+ indexkey,+ NULL,+ index->sortopfamily[i],+ index->opcintype[i],+ index->indexcollations[i],+ reverse_sort,+ nulls_first,+ 0,+ index->rel->relids,+ false);++ if (cpathkey == pathkey)+ {+ return i + 1;+ }++ i++;+ }++ return 0;+}+
/*
* build_index_pathkeys
* Build a pathkeys list that describes the ordering induced by an index
diff --git a/src/backend/optimizer/path/uniquekeys.c b/src/backend/optimizer/path/uniquekeys.cindex 7d9c0aefbf..c02a3c0ed8 100644--- a/src/backend/optimizer/path/uniquekeys.c+++ b/src/backend/optimizer/path/uniquekeys.c@@ -1136,6 +1136,7 @@ build_uniquekeys(PlannerInfo *root, List *sortclauses)
List *result = NIL;
List *sortkeys;
ListCell *l;
+ List *exprs = NIL;
sortkeys = make_pathkeys_for_uniquekeys(root,
sortclauses,
@@ -1146,18 +1147,14 @@ build_uniquekeys(PlannerInfo *root, List *sortclauses)
{
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));+ EquivalenceMember *mem = (EquivalenceMember*) lfirst(list_head(ec->ec_members));+ if (EC_MUST_BE_REDUNDANT(ec))+ continue;+ exprs = lappend(exprs, mem->em_expr);
}
+ result = lappend(result, makeUniqueKey(exprs, false));+
return result;
}
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.cindex a5f3c28fb5..80fbaadd21 100644--- a/src/backend/optimizer/plan/planner.c+++ b/src/backend/optimizer/plan/planner.c@@ -3627,12 +3627,18 @@ standard_qp_callback(PlannerInfo *root, void *extra)
if (parse->distinctClause &&
grouping_is_sortable(parse->distinctClause))
+ {
root->distinct_pathkeys =
make_pathkeys_for_sortclauses(root,
parse->distinctClause,
tlist);
+ root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause);+ }
else
+ {
root->distinct_pathkeys = NIL;
+ root->query_uniquekeys = NIL;+ }
root->sort_pathkeys =
make_pathkeys_for_sortclauses(root,
@@ -3663,17 +3669,9 @@ 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;
}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.cindex cac2ca0b0f..340e8384e6 100644--- a/src/backend/optimizer/util/pathnode.c+++ b/src/backend/optimizer/util/pathnode.c@@ -2981,49 +2981,21 @@ create_upper_unique_path(PlannerInfo *root,
*/
IndexPath *
create_skipscan_unique_path(PlannerInfo *root, IndexOptInfo *index,
- Path *basepath, List *unique_exprs)+ Path *basepath, int prefix)
{
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;+ Assert(prefix > 0);+ pathnode->indexskipprefix = prefix;+ pathnode->path.uniquekeys = root->query_uniquekeys;
numDistinctRows = estimate_num_groups(root, exprs,
pathnode->path.rows,
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.hindex 705deaf7bd..8ec1780a56 100644--- a/src/include/optimizer/pathnode.h+++ b/src/include/optimizer/pathnode.h@@ -210,7 +210,7 @@ extern UpperUniquePath *create_upper_unique_path(PlannerInfo *root,
extern IndexPath *create_skipscan_unique_path(PlannerInfo *root,
IndexOptInfo *index,
Path *subpath,
- List *unique_exprs);+ int prefix);
extern AggPath *create_agg_path(PlannerInfo *root,
RelOptInfo *rel,
Path *subpath,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.hindex 0cb8030e33..f934f0011a 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -198,6 +198,10 @@ extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
Relids required_outer,
double fraction);
extern Path *get_cheapest_parallel_safe_total_inner(List *paths);
+extern int find_index_prefix_for_pathkey(PlannerInfo *root,+ IndexOptInfo *index,+ ScanDirection scandir,+ PathKey *pathkey);
extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
ScanDirection scandir);
extern List *build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.outindex 4da9594925..e64e20a8cb 100644--- a/src/test/regress/expected/sysviews.out+++ b/src/test/regress/expected/sysviews.out@@ -91,7 +91,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(20 rows)+(19 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.25.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: florisvannee@Optiver.com, 9erthalion6@gmail.com, zhihui.fan1213@gmail.com, jesper.pedersen@redhat.com, dgrowleyml@gmail.com, horikyota.ntt@gmail.com, pg@bowt.ie, thomas.munro@gmail.com, tomas.vondra@2ndquadrant.com, dilipbalaut@gmail.com
Subject: RE: Index Skip Scan (new UniqueKeys)
In-Reply-To: <ef9954d83a9e42fabfac235bdd87d05a@opammb0561.comp.optiver.com>
* 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