From: Dmitry Dolgov <9erthalion6@gmail.com>
To: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: Peter Geoghegan <pg@bowt.ie>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Cc: Jesper Pedersen <jesper.pedersen@redhat.com>
Cc: David Rowley <dgrowleyml@gmail.com>
Cc: Floris Van Nee <florisvannee@optiver.com>
Cc: Kyotaro Horiguchi <horikyota.ntt@gmail.com>
Cc: Thomas Munro <thomas.munro@gmail.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Andy Fan <zhihui.fan1213@gmail.com>
Cc: Dilip Kumar <dilipbalaut@gmail.com>
Subject: Re: Index Skip Scan (new UniqueKeys)
Date: Sun, 14 Mar 2021 15:48:33 +0100
Message-ID: <20210314144833.tbfnn3pbrpjgl56z@localhost> (raw)
In-Reply-To: <20201205175542.fqrhbhp3co7cgvkj@localhost>
References: <CAH2-Wzkyx9A28bb5yNiN+6iRDJpGS0sQdAhyWEAA_yjrsh98-Q@mail.gmail.com>
<20200727102431.mjspwec4yhzeyny2@localhost>
<20200815141240.wuyc6ijkmnywywtn@localhost>
<CAH2-Wz=z8yXENbUWgP+3PhfS7HfB9bj01XuuSY8bj4jasQj_3A@mail.gmail.com>
<20201006152039.xs2ul7il52sowhlu@localhost>
<20201024164553.tel5uynf2dzyh4az@localhost>
<598ff988-5ebb-f6f7-0c9d-82208dff3bbd@iki.fi>
<20201201202119.jcsr7z6cdiffuops@localhost>
<6020ad2b-357f-da90-de7b-60b79452fc66@iki.fi>
<20201205175542.fqrhbhp3co7cgvkj@localhost>
> On Sat, Dec 05, 2020 at 06:55:42PM +0100, Dmitry Dolgov wrote:
> > On Tue, Dec 01, 2020 at 10:59:22PM +0200, Heikki Linnakangas wrote:
> >
> > > > - Does this optimization apply to bitmap index scans?
> > >
> > > No, from what I understand it doesn't.
> >
> > Would it be hard to add? Don't need to solve everything in the first
> > version of this, but I think in principle you could do the same
> > optimization for bitmap index scans, so if the current API can't do it,
> > that's maybe an indication that the API isn't quite right.
>
> I would expect it should not be hard as at the moment all parts seems
> relatively generic. But of course I need to check, while it seems no one
> had bitmap index scans in mind while developing this patch.
>
> On Sun, Dec 06, 2020 at 09:27:08AM +1300, Thomas Munro wrote:
>
> FWIW here's what I wrote about that years ago[1]:
> [1] https://www.postgresql.org/message-id/CADLWmXWALK8NPZqdnRQiPnrzAnic7NxYKynrkzO_vxYr8enWww%40mail.gma...
Thanks, that clarifies this topic a bit.
> > If you care whether the qual is evaluated by the index AM or not, you need
> > to also check that the operator is indexable. Attached is a query that
> > demonstrates that problem.
> > ...
> > Also, you should probably check that the index quals are in the operator
> > family as that used for the DISTINCT.
>
> Yes, good point, will change this in the next version.
Sorry for such long silence, now I've got a bit of free time after
subscripting patch to work on this one. Here is rebased version with a
few changes to address Heikki feedback about checking if the qual
operator is indexable. But...
This version is based on the old version of UniqueKey patch (first two
attached patches), mostly because IIUC there is still no final version
of it ([1], [2]). This means index skip scan could be reviewed and
discussed (and I'm planning to review the current design to see if it's
possible to improve it in the view of the latest changes), but
independently of the UniqueKey integration as it's subject to change.
But I'm afraid if things will go as it is and there will be not much
progress with the UniqueKey patch, I will have to withdraw this one
until everything is sorted out there.
[1]: https://www.postgresql.org/message-id/flat/CAKU4AWpQjAqJwQ2X-aR9g3+ZHRzU1k8hNP7A+_mLuOv-n5aVKA@mail....
[2]: https://www.postgresql.org/message-id/flat/CAKU4AWrU35c9g3cE15JmVwh6B2Hzf4hf7cZUkRsiktv7AKR3Ag@mail....Attachments:
[text/x-diff] v38-0001-Introduce-RelOptInfo-notnullattrs-attribute.patch (4.8K, ../20210314144833.tbfnn3pbrpjgl56z@localhost/2-v38-0001-Introduce-RelOptInfo-notnullattrs-attribute.patch)
download | inline diff:
From 70abf7131184a8cfc7e6b6d23b42c5d42633ea7f 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 v38 1/6] 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 d73ac562eb..37b4223adb 100644--- a/src/backend/optimizer/path/allpaths.c+++ b/src/backend/optimizer/path/allpaths.c@@ -998,6 +998,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)
@@ -1054,6 +1055,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 02f813cebd..d27167dc76 100644--- a/src/backend/optimizer/plan/initsplan.c+++ b/src/backend/optimizer/plan/initsplan.c@@ -829,6 +829,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,
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 c5947fa418..eebabcfccf 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
@@ -480,6 +481,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 86405a274e..0d61f04d27 100644--- a/src/include/nodes/pathnodes.h+++ b/src/include/nodes/pathnodes.h@@ -718,6 +718,8 @@ typedef struct RelOptInfo
int rel_parallel_workers; /* wanted number of parallel workers */
uint32 amflags; /* Bitmask of optional features supported by
* the table AM */
+ /* 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.26.2
[text/x-diff] v38-0002-Introduce-UniqueKey-attributes-on-RelOptInfo-str.patch (59.3K, ../20210314144833.tbfnn3pbrpjgl56z@localhost/3-v38-0002-Introduce-UniqueKey-attributes-on-RelOptInfo-str.patch)
download | inline diff:
From ebb2d2ef3ec64bdb98cc1bff057b3383e1dc40c6 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 v38 2/6] 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 | 1135 +++++++++++++++++++
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 | 18 +-
src/include/nodes/makefuncs.h | 3 +
src/include/nodes/nodes.h | 1 +
src/include/nodes/pathnodes.h | 29 +-
src/include/nodes/pg_list.h | 10 +
src/include/optimizer/appendinfo.h | 3 +
src/include/optimizer/optimizer.h | 2 +
src/include/optimizer/paths.h | 43 +
23 files changed, 1515 insertions(+), 24 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 da91cbd2b1..75c1c5e824 100644--- a/src/backend/nodes/copyfuncs.c+++ b/src/backend/nodes/copyfuncs.c@@ -2296,6 +2296,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
*/
@@ -5220,6 +5230,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 dbf6b30233..ca099495a1 100644--- a/src/backend/nodes/list.c+++ b/src/backend/nodes/list.c@@ -702,6 +702,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 01c110cd2f..40415d0f5b 100644--- a/src/backend/nodes/makefuncs.c+++ b/src/backend/nodes/makefuncs.c@@ -815,3 +815,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 6493a03ff8..44154cde6a 100644--- a/src/backend/nodes/outfuncs.c+++ b/src/backend/nodes/outfuncs.c@@ -2456,6 +2456,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)
{
@@ -4198,6 +4206,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 c5e136e9c3..b3e212bf1c 100644--- a/src/backend/nodes/readfuncs.c+++ b/src/backend/nodes/readfuncs.c@@ -492,6 +492,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.
@@ -2717,6 +2725,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 37b4223adb..d52ad59f89 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);
}
@@ -1297,6 +1303,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);
}
@@ -2304,6 +2312,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 57ce97fd53..697ac047fb 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 0dbe2ac726..7271f044ec 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 bd9a176d7d..139278829b 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..77ed2b2eff--- /dev/null+++ b/src/backend/optimizer/path/uniquekeys.c@@ -0,0 +1,1135 @@+/*-------------------------------------------------------------------------+ *+ * uniquekeys.c+ * Utilities for matching and building unique keys+ *+ * Portions Copyright (c) 2020, PostgreSQL Global Development Group+ *+ * IDENTIFICATION+ * src/backend/optimizer/path/uniquekeys.c+ *+ *-------------------------------------------------------------------------+ */+#include "postgres.h"++#include "nodes/makefuncs.h"+#include "nodes/nodeFuncs.h"+#include "optimizer/pathnode.h"+#include "optimizer/paths.h"+#include "optimizer/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(PlannerInfo *root,+ RelOptInfo *joinrel,+ RelOptInfo *rel1,+ UniqueKey *ukey);+static void add_uniquekey_for_onerow(RelOptInfo *rel);+static bool add_combined_uniquekey(PlannerInfo *root,+ 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(root, 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(root, 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(root, 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(PlannerInfo *root, 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(root, 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(PlannerInfo *root,+ 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(root, joinrel, outer_rel, outer_ukey))+ {+ foreach(lc2, get_exprs_from_uniquekey(root, 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 424d25cbd5..8d8e493f5c 100644--- a/src/backend/optimizer/plan/planner.c+++ b/src/backend/optimizer/plan/planner.c@@ -2387,6 +2387,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;
}
@@ -4621,7 +4625,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;
}
@@ -4935,7 +4939,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;
}
@@ -5196,6 +5200,8 @@ create_ordered_paths(PlannerInfo *root,
*/
Assert(ordered_rel->pathlist != NIL);
+ simple_copy_uniquekeys(input_rel, ordered_rel);+
return ordered_rel;
}
@@ -6073,6 +6079,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 becdcbb872..b7626545bf 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 86922a273c..6817c9c787 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 be1c9ddd96..3eec1f4d74 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,14 +748,15 @@ apply_child_basequals(PlannerInfo *root, RelOptInfo *parentrel,
root->hasPseudoConstantQuals = true;
}
/* reconstitute RestrictInfo with appropriate properties */
- childquals = lappend(childquals,- make_restrictinfo(root,- (Expr *) onecq,- rinfo->is_pushed_down,- rinfo->outerjoin_delayed,- pseudoconstant,- rinfo->security_level,- NULL, NULL, NULL));+ child_rinfo = make_restrictinfo(root,+ (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 48a7ebfe45..4fe1824eb0 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,
@@ -106,4 +107,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 e22df890ef..3320273ac1 100644--- a/src/include/nodes/nodes.h+++ b/src/include/nodes/nodes.h@@ -265,6 +265,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 0d61f04d27..80561b1003 100644--- a/src/include/nodes/pathnodes.h+++ b/src/include/nodes/pathnodes.h@@ -739,6 +739,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 */
@@ -1059,6 +1060,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
*
@@ -2496,7 +2519,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.
@@ -2526,8 +2549,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 404e03f132..85c65e910c 100644--- a/src/include/nodes/pg_list.h+++ b/src/include/nodes/pg_list.h@@ -566,6 +566,16 @@ extern pg_nodiscard List *list_delete_first(List *list);
extern pg_nodiscard List *list_delete_last(List *list);
extern pg_nodiscard List *list_delete_nth_cell(List *list, int n);
extern pg_nodiscard List *list_delete_cell(List *list, ListCell *cell);
+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);+extern List *list_delete_oid(List *list, Oid datum);+extern List *list_delete_first(List *list);+extern List *list_delete_last(List *list);+extern List *list_delete_nth_cell(List *list, int n);+extern List *list_delete_cell(List *list, ListCell *cell);
extern List *list_union(const List *list1, const List *list2);
extern List *list_union_ptr(const List *list1, const List *list2);
diff --git a/src/include/optimizer/appendinfo.h b/src/include/optimizer/appendinfo.hindex 4cbf8c26cc..43b8d05f69 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 d587952b7d..843aafa51e 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"
/* Test if an expression node represents a SRF call. Beware multiple eval! */
#define IS_SRF_CALL(node) \
@@ -168,6 +169,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 035d3e1206..1adf99c9ee 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -247,5 +247,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.26.2
[text/x-diff] v38-0003-Extend-UniqueKeys.patch (13.0K, ../20210314144833.tbfnn3pbrpjgl56z@localhost/4-v38-0003-Extend-UniqueKeys.patch)
download | inline diff:
From 7fb5f631308279a327224697d117a16ad65cbb06 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:33:56 +0200
Subject: [PATCH v38 3/6] Extend UniqueKeys
Prepares index skip scan implementation using UniqueKeys. Allows to
specify what are the "requested" keys that should be unique, and add
them to necessary Paths to make them useful later.
Proposed by David Rowley, contains few bits out of previous version from
Jesper Pedersen.
---
src/backend/optimizer/path/pathkeys.c | 62 +++++++++++++++++++++++++
src/backend/optimizer/path/uniquekeys.c | 61 ++++++++++++++++++++++++
src/backend/optimizer/plan/planner.c | 36 +++++++++++++-
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, 195 insertions(+), 10 deletions(-)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.cindex 139278829b..4c90f63705 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,44 @@ 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 (EC_MUST_BE_REDUNDANT(pathkey->pk_eclass))+ continue;++ 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 77ed2b2eff..1aa11ec447 100644--- a/src/backend/optimizer/path/uniquekeys.c+++ b/src/backend/optimizer/path/uniquekeys.c@@ -1133,3 +1133,64 @@ add_combined_uniquekey(PlannerInfo *root,
}
return false;
}
++List*+build_uniquekeys(PlannerInfo *root, List *sortclauses)+{+ List *result = NIL;+ List *sortkeys;+ ListCell *l;+ List *exprs = NIL;++ 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;+ EquivalenceMember *mem = (EquivalenceMember*) lfirst(list_head(ec->ec_members));+ exprs = lappend(exprs, mem->em_expr);+ }++ result = lappend(result, makeUniqueKey(exprs, false));++ return result;+}++bool+query_has_uniquekeys_for(PlannerInfo *root, List *pathuniquekeys,+ bool allow_multinulls)+{+ ListCell *lc;+ ListCell *lc2;++ /* root->query_uniquekeys are the requested DISTINCT clauses on query level+ * pathuniquekeys are the unique keys on current path.+ * All requested query_uniquekeys must be satisfied by the pathuniquekeys+ */+ foreach(lc, root->query_uniquekeys)+ {+ UniqueKey *query_ukey = lfirst_node(UniqueKey, lc);+ bool satisfied = false;+ foreach(lc2, pathuniquekeys)+ {+ UniqueKey *ukey = lfirst_node(UniqueKey, lc2);+ if (ukey->multi_nullvals && !allow_multinulls)+ continue;+ if (list_length(ukey->exprs) == 0 &&+ list_length(query_ukey->exprs) != 0)+ continue;+ if (list_is_subset(ukey->exprs, query_ukey->exprs))+ {+ satisfied = true;+ break;+ }+ }+ if (!satisfied)+ return false;+ }+ return true;+}diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.cindex 8d8e493f5c..35d8fd0cb0 100644--- a/src/backend/optimizer/plan/planner.c+++ b/src/backend/optimizer/plan/planner.c@@ -3625,12 +3625,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,
@@ -4845,13 +4851,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, path->uniquekeys, false))+ add_path(distinct_rel, path);
}
/* For explicit-sort case, always use the more rigorous clause */
@@ -7491,6 +7503,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 69b83071cf..c995921c88 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);
}
/*
@@ -2597,6 +2612,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 80561b1003..27ff639053 100644--- a/src/include/nodes/pathnodes.h+++ b/src/include/nodes/pathnodes.h@@ -293,6 +293,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 */
@@ -686,6 +687,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;
@@ -874,6 +876,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? */
bool amcanmarkpos; /* does AM support mark/restore? */
/* Rather than include amapi.h here, we declare amcostestimate like this */
@@ -1194,6 +1197,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 54f4b782fc..aa6c3e439e 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 1adf99c9ee..b571ddec11 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -222,6 +222,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,
@@ -289,6 +292,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.26.2
[text/x-diff] v38-0004-Index-skip-scan.patch (45.0K, ../20210314144833.tbfnn3pbrpjgl56z@localhost/5-v38-0004-Index-skip-scan.patch)
download | inline diff:
From 74d1d7c91e536070deccf2176c53d57e5aa8f3a1 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:39:13 +0200
Subject: [PATCH v38 4/6] Index skip scan
Implementation of basic Index Skip Scan (see Loose Index Scan in the
wiki [1]) infrastructure on top of IndexOnlyScan and IndexScan.
Introduces a new index am function amskip to allow advance past
duplicate key values in a scan. This innocently looking description
could be a bit tricky on the edge between am specific and common parts
of the implementation, mostly due to different information available at
each level, e.g. visibility. This means the common parts should apply
skipping multiple times if necessary.
Original patch and design were proposed by Thomas Munro [2], revived and
improved by Dmitry Dolgov and Jesper Pedersen.
[1] https://wiki.postgresql.org/wiki/Loose_indexscan
[2] https://www.postgresql.org/message-id/flat/CADLWmXXbTSBxP-MzJuPAYSsL_2f0iPm5VWPbCvDbVvfX93FKkw%40mail.gmail.com
Author: Jesper Pedersen, Dmitry Dolgov
Reviewed-by: Thomas Munro, David Rowley, Floris Van Nee, Kyotaro Horiguchi, Tomas Vondra, Peter Geoghegan
---
contrib/bloom/blutils.c | 1 +
doc/src/sgml/indexam.sgml | 1 +
src/backend/access/brin/brin.c | 1 +
src/backend/access/gin/ginutil.c | 1 +
src/backend/access/gist/gist.c | 1 +
src/backend/access/hash/hash.c | 1 +
src/backend/access/index/indexam.c | 18 ++
src/backend/access/spgist/spgutils.c | 1 +
src/backend/commands/explain.c | 25 +++
src/backend/executor/nodeIndexonlyscan.c | 97 ++++++++-
src/backend/executor/nodeIndexscan.c | 56 ++++-
src/backend/nodes/copyfuncs.c | 2 +
src/backend/nodes/outfuncs.c | 2 +
src/backend/nodes/readfuncs.c | 2 +
src/backend/optimizer/path/costsize.c | 1 +
src/backend/optimizer/path/indxpath.c | 196 +++++++++++++++++-
src/backend/optimizer/path/pathkeys.c | 54 ++++-
src/backend/optimizer/plan/createplan.c | 20 +-
src/backend/optimizer/util/pathnode.c | 37 ++++
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 | 7 +
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/include/optimizer/paths.h | 5 +-
src/test/regress/expected/sysviews.out | 3 +-
32 files changed, 554 insertions(+), 17 deletions(-)
diff --git a/contrib/bloom/blutils.c b/contrib/bloom/blutils.cindex 1e505b1da5..a58bdf7604 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 ec5741df6d..3442ae816b 100644--- a/doc/src/sgml/indexam.sgml+++ b/doc/src/sgml/indexam.sgml@@ -151,6 +151,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 27ba596c6e..1ec10ec513 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 6b9b04cf42..d776d2732f 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 0683f42c25..fed061184e 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 0752fb38a9..fd7c13ee4c 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 3d2dbed708..2544ea24f1 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
@@ -739,6 +740,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, prefix);+}+
/* ----------------
* index_getprocid
*
diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.cindex d8b1815061..b2ed0712f2 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 afc45429ba..a160de5493 100644--- a/src/backend/commands/explain.c+++ b/src/backend/commands/explain.c@@ -149,6 +149,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);
@@ -1098,6 +1099,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
@@ -1439,6 +1456,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
{
IndexScan *indexscan = (IndexScan *) plan;
+ ExplainIndexSkipScanKeys(indexscan->indexskipprefixsize, es);+
ExplainIndexScanDetails(indexscan->indexid,
indexscan->indexorderdir,
es);
@@ -1449,6 +1468,8 @@ ExplainNode(PlanState *planstate, List *ancestors,
{
IndexOnlyScan *indexonlyscan = (IndexOnlyScan *) plan;
+ ExplainIndexSkipScanKeys(indexonlyscan->indexskipprefixsize, es);+
ExplainIndexScanDetails(indexonlyscan->indexid,
indexonlyscan->indexorderdir,
es);
@@ -1709,6 +1730,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)
@@ -1722,6 +1745,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 0754e28a9a..0fad258202 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();
+ /*+ * If we already emitted first tuple, 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) && node->ioss_FirstTupleEmitted &&+ 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 2fffb1b437..71aac4493d 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 75c1c5e824..481dbf2e00 100644--- a/src/backend/nodes/copyfuncs.c+++ b/src/backend/nodes/copyfuncs.c@@ -491,6 +491,7 @@ _copyIndexScan(const IndexScan *from)
COPY_NODE_FIELD(indexorderbyorig);
COPY_NODE_FIELD(indexorderbyops);
COPY_SCALAR_FIELD(indexorderdir);
+ COPY_SCALAR_FIELD(indexskipprefixsize);
return newnode;
}
@@ -516,6 +517,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 44154cde6a..eb51324c61 100644--- a/src/backend/nodes/outfuncs.c+++ b/src/backend/nodes/outfuncs.c@@ -560,6 +560,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
@@ -574,6 +575,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 b3e212bf1c..a23a405523 100644--- a/src/backend/nodes/readfuncs.c+++ b/src/backend/nodes/readfuncs.c@@ -1870,6 +1870,7 @@ _readIndexScan(void)
READ_NODE_FIELD(indexorderbyorig);
READ_NODE_FIELD(indexorderbyops);
READ_ENUM_FIELD(indexorderdir, ScanDirection);
+ READ_INT_FIELD(indexskipprefixsize);
READ_DONE();
}
@@ -1889,6 +1890,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 a25b674a19..658bacabf4 100644--- a/src/backend/optimizer/path/costsize.c+++ b/src/backend/optimizer/path/costsize.c@@ -132,6 +132,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 ff536e6b24..bd0a073998 100644--- a/src/backend/optimizer/path/indxpath.c+++ b/src/backend/optimizer/path/indxpath.c@@ -784,6 +784,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);
@@ -866,12 +876,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
double loop_count;
List *orderbyclauses;
List *orderbyclausecols;
- List *index_pathkeys;+ List *index_pathkeys = NIL;
List *useful_pathkeys;
+ List *index_pathkeys_pos = NIL;
bool found_lower_saop_clause;
bool pathkeys_possibly_useful;
bool index_is_ordered;
bool index_only_scan;
+ bool not_empty_qual = false;+ bool can_skip;
int indexcol;
/*
@@ -989,7 +1002,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
if (index_is_ordered && pathkeys_possibly_useful)
{
index_pathkeys = build_index_pathkeys(root, index,
- ForwardScanDirection);+ ForwardScanDirection,+ &index_pathkeys_pos);
useful_pathkeys = truncate_useless_pathkeys(root, rel,
index_pathkeys);
orderbyclauses = NIL;
@@ -1021,6 +1035,129 @@ 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;++ if (can_skip)+ {+ /*+ * 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 (root->parse->jointree != NULL)+ {+ ListCell *lc;++ foreach(lc, (List *) root->parse->jointree->quals)+ {+ Node *expr, *qual = (Node *) lfirst(lc);+ OpExpr *expr_op;+ Var *var;+ bool found = false;++ if (!is_opclause(qual))+ {+ not_empty_qual = true;+ break;+ }++ expr = get_leftop(qual);+ expr_op = (OpExpr *) qual;++ if (!IsA(expr, Var))+ {+ not_empty_qual = true;+ break;+ }++ var = (Var *) expr;++ /*+ * Check if the qual operator is indexable by any columns of+ * the index, test collation and opfamily.+ */+ for (int i = 0; i < index->ncolumns; i++)+ {+ if (index->indexkeys[i] == var->varattno &&+ IndexCollMatchesExprColl(index->indexcollations[i],+ expr_op->inputcollid) &&+ op_in_opfamily(expr_op->opno, index->opfamily[i]))+ {+ found = true;+ break;+ }+ }++ if (!found)+ {+ not_empty_qual = true;+ break;+ }+ }+ }++ /*+ * For an index scan verify that index fully covers distinct+ * expressions, otherwise there is not enough information for skipping+ */+ if (!index_only_scan && root->query_uniquekeys != NULL)+ {+ ListCell *lc;++ foreach(lc, root->query_uniquekeys)+ {+ UniqueKey *uniqueKey = (UniqueKey *) lfirst(lc);+ ListCell *lc1;++ foreach(lc1, uniqueKey->exprs)+ {+ Expr *expr = (Expr *) lfirst(lc1);+ bool found = false;++ if (!IsA(expr, Var))+ {+ ListCell *lc2;++ foreach(lc2, index->indexprs)+ {+ if(equal(lfirst(lc1), lfirst(lc2)))+ {+ found = true;+ break;+ }+ }+ }+ else+ {+ Var *var = (Var *) expr;++ for (int i = 0; i < index->ncolumns; i++)+ {+ if (index->indexkeys[i] == var->varattno)+ {+ found = true;+ break;+ }+ }+ }++ if (!found)+ {+ can_skip = false;+ break;+ }+ }++ if (!can_skip)+ break;+ }+ }+ }+
/*
* 4. Generate an indexscan path if there are relevant restriction clauses
* in the current clauses, OR the index ordering is potentially useful for
@@ -1044,6 +1181,32 @@ 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)+ {+ int numusefulkeys = list_length(useful_pathkeys);+ int numsortkeys = list_length(root->query_pathkeys);++ if (numusefulkeys == numsortkeys)+ {+ int prefix;+ if (list_length(root->distinct_pathkeys) > 0)+ prefix = find_index_prefix_for_pathkey(index_pathkeys,+ index_pathkeys_pos,+ 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, prefix));+ }+ }+
/*
* If appropriate, consider parallel index scan. We don't allow
* parallel index scan for bitmap index scans.
@@ -1082,7 +1245,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
if (index_is_ordered && pathkeys_possibly_useful)
{
index_pathkeys = build_index_pathkeys(root, index,
- BackwardScanDirection);+ BackwardScanDirection,+ &index_pathkeys_pos);
useful_pathkeys = truncate_useless_pathkeys(root, rel,
index_pathkeys);
if (useful_pathkeys != NIL)
@@ -1099,6 +1263,32 @@ 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)+ {+ int numusefulkeys = list_length(useful_pathkeys);+ int numsortkeys = list_length(root->query_pathkeys);++ if (numusefulkeys == numsortkeys)+ {+ int prefix;+ if (list_length(root->distinct_pathkeys) > 0)+ prefix = find_index_prefix_for_pathkey(index_pathkeys,+ index_pathkeys_pos,+ 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, prefix));+ }+ }+
/* If appropriate, consider parallel index scan */
if (index->amcanparallel &&
rel->consider_parallel && outer_relids == NULL &&
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.cindex 4c90f63705..e15637b514 100644--- a/src/backend/optimizer/path/pathkeys.c+++ b/src/backend/optimizer/path/pathkeys.c@@ -522,6 +522,47 @@ 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. Optionally+ * pathkeys_positions can be provided, to specify at which position in the+ * original pathkey list this particular key could be found (this is helpful+ * when we deal with redundant pathkeys).+ *+ * Returns 0 when not found.+ */+int+find_index_prefix_for_pathkey(List *index_pathkeys,+ List *pathkeys_positions,+ PathKey *target_pathkey)+{+ ListCell *lc;+ int i;++ i = 0;+ foreach(lc, index_pathkeys)+ {+ PathKey *cpathkey = (PathKey *) lfirst(lc);++ if (cpathkey == target_pathkey)+ {+ /*+ * Prefix expected to start from 1, increment positions since+ * they're 0 based.+ */+ if (pathkeys_positions != NIL &&+ pathkeys_positions->length > i)+ return list_nth_int(pathkeys_positions, i) + 1;+ else+ return i + 1;+ }++ i++;+ }++ return 0;+}+
/*
* build_index_pathkeys
* Build a pathkeys list that describes the ordering induced by an index
@@ -534,7 +575,9 @@ get_cheapest_parallel_safe_total_inner(List *paths)
* We iterate only key columns of covering indexes, since non-key columns
* don't influence index ordering. The result is canonical, meaning that
* redundant pathkeys are removed; it may therefore have fewer entries than
- * there are key columns in the index.+ * there are key columns in the index. Since by removing redundant pathkeys the+ * information about original position is lost, return it via positions+ * argument.
*
* Another reason for stopping early is that we may be able to tell that
* an index column's sort order is uninteresting for this query. However,
@@ -545,7 +588,8 @@ get_cheapest_parallel_safe_total_inner(List *paths)
List *
build_index_pathkeys(PlannerInfo *root,
IndexOptInfo *index,
- ScanDirection scandir)+ ScanDirection scandir,+ List **positions)
{
List *retval = NIL;
ListCell *lc;
@@ -554,6 +598,8 @@ build_index_pathkeys(PlannerInfo *root,
if (index->sortopfamily == NULL)
return NIL; /* non-orderable index */
+ *positions = NIL;+
i = 0;
foreach(lc, index->indextlist)
{
@@ -607,7 +653,11 @@ build_index_pathkeys(PlannerInfo *root,
* for this query. Add it to list, unless it's redundant.
*/
if (!pathkey_is_redundant(cpathkey, retval))
+ {
retval = lappend(retval, cpathkey);
+ *positions = lappend_int(*positions,+ foreach_current_index(lc));+ }
}
else
{
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.cindex 906cab7053..c2969a0279 100644--- a/src/backend/optimizer/plan/createplan.c+++ b/src/backend/optimizer/plan/createplan.c@@ -181,12 +181,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);
@@ -2997,7 +2999,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,
@@ -3008,7 +3011,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);
@@ -5340,7 +5344,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;
@@ -5357,6 +5362,7 @@ make_indexscan(List *qptlist,
node->indexorderbyorig = indexorderbyorig;
node->indexorderbyops = indexorderbyops;
node->indexorderdir = indexscandir;
+ node->indexskipprefixsize = skipPrefixSize;
return node;
}
@@ -5369,7 +5375,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;
@@ -5384,6 +5391,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 c995921c88..a768f43e22 100644--- a/src/backend/optimizer/util/pathnode.c+++ b/src/backend/optimizer/util/pathnode.c@@ -3029,6 +3029,43 @@ 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, int prefix)+{+ IndexPath *pathnode = makeNode(IndexPath);+ int numDistinctRows;+ UniqueKey *ukey;++ Assert(IsA(basepath, IndexPath));++ /* We don't want to modify basepath, so make a copy. */+ memcpy(pathnode, basepath, sizeof(IndexPath));++ ukey = linitial_node(UniqueKey, root->query_uniquekeys);++ Assert(prefix > 0);+ pathnode->indexskipprefix = prefix;+ pathnode->path.uniquekeys = root->query_uniquekeys;++ numDistinctRows = estimate_num_groups(root, ukey->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 eebabcfccf..cb31b64047 100644--- a/src/backend/optimizer/util/plancat.c+++ b/src/backend/optimizer/util/plancat.c@@ -281,6 +281,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 855076b1fd..6354958ed3 100644--- a/src/backend/utils/misc/guc.c+++ b/src/backend/utils/misc/guc.c@@ -960,6 +960,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 f46c2dd7a8..4eecf2d95d 100644--- a/src/backend/utils/misc/postgresql.conf.sample+++ b/src/backend/utils/misc/postgresql.conf.sample@@ -359,6 +359,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 d357ebb559..eacf890dbe 100644--- a/src/include/access/amapi.h+++ b/src/include/access/amapi.h@@ -173,6 +173,12 @@ 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,+ int prefix);+
/* fetch all valid tuples */
typedef int64 (*amgetbitmap_function) (IndexScanDesc scan,
TIDBitmap *tbm);
@@ -275,6 +281,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 4515401869..f14baadea0 100644--- a/src/include/access/genam.h+++ b/src/include/access/genam.h@@ -183,6 +183,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 8154adf3b8..6690c2a0b0 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 e31ad6204e..9982343e8a 100644--- a/src/include/nodes/execnodes.h+++ b/src/include/nodes/execnodes.h@@ -1427,6 +1427,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;
@@ -1456,6 +1458,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
@@ -1474,6 +1478,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 27ff639053..01e68fe6db 100644--- a/src/include/nodes/pathnodes.h+++ b/src/include/nodes/pathnodes.h@@ -1241,6 +1241,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
@@ -1253,6 +1256,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 95292d7573..a23ea622ed 100644--- a/src/include/nodes/plannodes.h+++ b/src/include/nodes/plannodes.h@@ -403,6 +403,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;
/* ----------------
@@ -430,6 +432,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 1be93be098..0f22fcef99 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 aa6c3e439e..872c858a60 100644--- a/src/include/optimizer/pathnode.h+++ b/src/include/optimizer/pathnode.h@@ -210,6 +210,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,+ 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 b571ddec11..45a985e8c1 100644--- a/src/include/optimizer/paths.h+++ b/src/include/optimizer/paths.h@@ -205,8 +205,11 @@ 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(List *index_pathkeys,+ List *pathkey_positions,+ PathKey *target_pathkey);
extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
- ScanDirection scandir);+ ScanDirection scandir, List **positions);
extern List *build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel,
ScanDirection scandir, bool *partialkeys);
extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.outindex 6d048e309c..eda1b0a3b4 100644--- a/src/test/regress/expected/sysviews.out+++ b/src/test/regress/expected/sysviews.out@@ -102,6 +102,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
@@ -113,7 +114,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(18 rows)+(21 rows)
-- Test that the pg_timezone_names and pg_timezone_abbrevs views are
-- more-or-less working. We can't test their contents in any great detail
--
2.26.2
[text/x-diff] v38-0005-Btree-implementation-of-skipping.patch (44.3K, ../20210314144833.tbfnn3pbrpjgl56z@localhost/6-v38-0005-Btree-implementation-of-skipping.patch)
download | inline diff:
From 666d7b1e219ff28ec4677cca1a3eaa838f61e845 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:45:08 +0200
Subject: [PATCH v38 5/6] Btree implementation of skipping
Implementation of Index Skip Scan for Btree. To make it suitable for
both situations when there are small number of distinct values and
significant amount of distinct values the following approach is taken -
instead of searching from the root for every value we're searching for
then first on the current page, and then if not found continue searching
from the root.
Author: Jesper Pedersen, Dmitry Dolgov
Reviewed-by: Thomas Munro, David Rowley, Floris Van Nee, Kyotaro Horiguchi, Tomas Vondra, Peter Geoghegan
---
src/backend/access/nbtree/nbtree.c | 13 +
src/backend/access/nbtree/nbtsearch.c | 506 ++++++++++++-
src/include/access/nbtree.h | 7 +
src/test/regress/expected/join.out | 3 +
src/test/regress/expected/select_distinct.out | 681 ++++++++++++++++++
src/test/regress/expected/sysviews.out | 2 +-
src/test/regress/sql/join.sql | 5 +
src/test/regress/sql/select_distinct.sql | 298 ++++++++
8 files changed, 1513 insertions(+), 2 deletions(-)
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.cindex 2bcc79ac2f..ff8d16a76d 100644--- a/src/backend/access/nbtree/nbtree.c+++ b/src/backend/access/nbtree/nbtree.c@@ -123,6 +123,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;
@@ -374,6 +375,8 @@ btbeginscan(Relation rel, int nkeys, int norderbys)
*/
so->currTuples = so->markTuples = NULL;
+ so->skipScanKey = NULL;+
scan->xs_itupdesc = RelationGetDescr(rel);
scan->opaque = so;
@@ -440,6 +443,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, int prefix)+{+ return _bt_skip(scan, direction, indexdir, prefix);+}+
/*
* btendscan() -- close down a scan
*/
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.cindex d1177d8772..77e5b91b22 100644--- a/src/backend/access/nbtree/nbtsearch.c+++ b/src/backend/access/nbtree/nbtsearch.c@@ -45,7 +45,11 @@ 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);
/*
* _bt_drop_lock_and_maybe_pin()
@@ -1486,6 +1490,452 @@ _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, int prefix)+{+ BTScanOpaque so = (BTScanOpaque) scan->opaque;+ BTStack stack;+ Buffer buf;+ OffsetNumber offnum;+ BTScanPosItem *currItem;+ Relation indexRel = scan->indexRelation;+ bool scanstart = !BTScanPosIsValid(so->currPos);++ /* 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))+ {+ _bt_lockbuf(indexRel, so->currPos.buf, BT_READ);++ if (_bt_scankey_within_page(scan, so->skipScanKey, so->currPos.buf))+ {+ 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);++ _bt_unlockbuf(indexRel, so->currPos.buf);+ 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+ _bt_unlockbuf(indexRel, so->currPos.buf);+ }++ 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)) ||+ (ScanDirectionIsForward(dir) && ScanDirectionIsBackward(indexdir) & scanstart))+ 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) && !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);++ _bt_unlockbuf(indexRel, so->currPos.buf);+ if (_bt_next(scan, dir))+ {+ _bt_lockbuf(indexRel, 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))+ 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);++ _bt_unlockbuf(indexRel, so->currPos.buf);+ 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) && !scanstart)+ {+ IndexTuple startItup = CopyIndexTuple(scan->xs_itup);+ bool nextFound = false;++ /* Reading backwards means we expect to see more data on the left */+ so->currPos.moreLeft = true;++ while (!nextFound)+ {+ IndexTuple itup;+ OffsetNumber jumpOffset;+ 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.+ */+ _bt_unlockbuf(indexRel, so->currPos.buf);+ if (!_bt_steppage(scan, dir))+ {+ pfree(so->skipScanKey);+ so->skipScanKey = NULL;+ return false;+ }+ _bt_lockbuf(indexRel, 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);++ _bt_unlockbuf(indexRel, so->currPos.buf);+ 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;++ /*+ * We need to remember the original offset after the jump,+ * since in case of looping this would be the next starting+ * point+ */+ 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.+ */+ _bt_unlockbuf(indexRel, so->currPos.buf);+ if (!_bt_steppage(scan, indexdir))+ {+ pfree(so->skipScanKey);+ so->skipScanKey = NULL;+ return false;+ }+ _bt_lockbuf(indexRel, so->currPos.buf, BT_READ);+ }++ currItem = &so->currPos.items[so->currPos.lastItem];+ itup = CopyIndexTuple((IndexTuple)+ (so->currTuples + currItem->tupleOffset));++ /*+ * 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 tuple we found in+ * this way is equal to what we wanted to return, it means we+ * are in the loop, return offnum to the original position and+ * jump further+ *+ * Note that to compare tids we need to keep the leaf pinned,+ * otherwise there is a danger of vacuum cleaning up relevant+ * tuples.+ */+ 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))+ {+ OffsetNumber maxoff, startOffset;+ IndexTuple verifiedItup;+ Page page = BufferGetPage(so->currPos.buf);+ startOffset = _bt_binsrch(scan->indexRelation,+ so->skipScanKey,+ so->currPos.buf);++ maxoff = PageGetMaxOffsetNumber(page);++ /* Now read the data */+ if (_bt_readpage(scan, ForwardScanDirection, startOffset))+ {+ ItemPointer resultTids, verifyTids;+ int nresult = 1,+ nverify = 1;++ currItem = &so->currPos.items[so->currPos.itemIndex];+ verifiedItup = (IndexTuple) (so->currTuples + currItem->tupleOffset);++ /*+ * We need to keep in mind that tuples we deal with+ * could be also posting tuples and represent a list of+ * tids.+ */+ if (BTreeTupleIsPosting(verifiedItup))+ {+ nverify = BTreeTupleGetNPosting(verifiedItup);+ verifyTids = BTreeTupleGetPosting(verifiedItup);+ for (int i = 1; i < nverify; i++)+ verifyTids[i] = *BTreeTupleGetPostingN(verifiedItup, i);+ }+ else+ verifyTids = &verifiedItup->t_tid;++ if (BTreeTupleIsPosting(itup))+ {+ nresult = BTreeTupleGetNPosting(itup);+ resultTids = BTreeTupleGetPosting(itup);+ for (int i = 1; i < nresult; i++)+ resultTids[i] = *BTreeTupleGetPostingN(itup, i);+ }+ else+ resultTids = &itup->t_tid;++ /* One not equal means they're not equal. */+ for(int i = 0; i < nverify; i++)+ {+ for(int j = 0; j < nresult; j++)+ {+ if (!ItemPointerEquals(&resultTids[j], &verifyTids[i]))+ {+ nextFound = true;+ break;+ }+ }+ }++ if (!nextFound)+ offnum = jumpOffset;+ }++ if ((offnum > maxoff) && (so->currPos.nextPage == P_NONE))+ {+ _bt_unlockbuf(indexRel, so->currPos.buf);++ BTScanPosUnpinIfPinned(so->currPos);+ BTScanPosInvalidate(so->currPos);++ pfree(so->skipScanKey);+ so->skipScanKey = NULL;+ return false;+ }+ }+ else+ /*+ * If startItup could be not found within the current page,+ * assume we found something new+ */+ nextFound = true;++ /* 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.+ */+ _bt_unlockbuf(indexRel, so->currPos.buf);+ 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 */+ _bt_unlockbuf(indexRel, so->currPos.buf);++ /* And set IndexTuple */+ currItem = &so->currPos.items[so->currPos.itemIndex];+ scan->xs_heaptid = currItem->heapTid;+ scan->xs_itup = (IndexTuple) (so->currTuples + currItem->tupleOffset);++ so->currPos.moreLeft = true;+ so->currPos.moreRight = true;++ return true;+}+
/*
* _bt_readpage() -- Load data from current index page into so->currPos
*
@@ -2482,3 +2932,57 @@ _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)+{+ 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 eb284b6042..581bee7b42 100644--- a/src/include/access/nbtree.h+++ b/src/include/access/nbtree.h@@ -1045,6 +1045,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 */
@@ -1206,6 +1209,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, int prefix);
extern Buffer _bt_get_endpoint(Relation rel, uint32 level, bool rightmost,
Snapshot snapshot);
@@ -1230,6 +1235,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, 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 5c7528c029..a52e25b3c3 100644--- a/src/test/regress/expected/join.out+++ b/src/test/regress/expected/join.out@@ -4530,6 +4530,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
@@ -4547,6 +4549,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..862e983b55 100644--- a/src/test/regress/expected/select_distinct.out+++ b/src/test/regress/expected/select_distinct.out@@ -306,3 +306,684 @@ 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 +---------------------------------------------------+ Index Scan using distinct_a_a_b_idx on distinct_a+ Skip scan: true+ Index Cond: (a = 1)+(3 rows)++EXPLAIN (COSTS OFF)+SELECT DISTINCT *+FROM distinct_a;+ QUERY PLAN +------------------------------+ HashAggregate+ Group Key: a, b, c+ -> Seq Scan on distinct_a+(3 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;+-- test posting lists+CREATE TABLE distinct_posting (a int, b int, c int);+CREATE INDEX ON distinct_posting (a, b, c);+INSERT INTO distinct_posting+ 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);+INSERT INTO distinct_posting (+ SELECT 1 as a, 1 as b, 1 AS c+ FROM generate_series(1,1000) i+);+BEGIN;+ DECLARE c SCROLL CURSOR FOR+ SELECT DISTINCT ON (a) a,b,c FROM distinct_posting 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)++COMMIT;+-- test that quals are check for indexability before applied+CREATE TABLE Indexable_quals (a text, b text, c text);+CREATE INDEX ON indexable_quals (a, b, c);+INSERT INTO indexable_quals VALUES ('a1', 'b', 'xxx');+INSERT INTO indexable_quals VALUES ('a1', 'b', 'yyy');+INSERT INTO indexable_quals VALUES ('a2', 'b', 'xxx');+INSERT INTO indexable_quals VALUES ('a2', 'b', 'yyy');+SELECT DISTINCT ON (a, b) a, b+FROM indexable_quals WHERE c LIKE '%y%' AND a LIKE 'a%' AND b = 'b';+ a | b +----+---+ a1 | b+ a2 | b+(2 rows)+diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.outindex eda1b0a3b4..9471c0a9d9 100644--- a/src/test/regress/expected/sysviews.out+++ b/src/test/regress/expected/sysviews.out@@ -114,7 +114,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(21 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
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sqlindex 6a209a27aa..bee79132ad 100644--- a/src/test/regress/sql/join.sql+++ b/src/test/regress/sql/join.sql@@ -1569,11 +1569,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..f07abbb0f7 100644--- a/src/test/regress/sql/select_distinct.sql+++ b/src/test/regress/sql/select_distinct.sql@@ -135,3 +135,301 @@ 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;+EXPLAIN (COSTS OFF)+SELECT DISTINCT *+FROM distinct_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;++-- test posting lists+CREATE TABLE distinct_posting (a int, b int, c int);+CREATE INDEX ON distinct_posting (a, b, c);+INSERT INTO distinct_posting+ 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);++INSERT INTO distinct_posting (+ SELECT 1 as a, 1 as b, 1 AS c+ FROM generate_series(1,1000) i+);++BEGIN;+ DECLARE c SCROLL CURSOR FOR+ SELECT DISTINCT ON (a) a,b,c FROM distinct_posting WHERE c = 2+ ORDER BY a DESC, b DESC;+ FETCH ALL FROM c;++ FETCH BACKWARD ALL FROM c;+COMMIT;++-- test that quals are check for indexability before applied+CREATE TABLE Indexable_quals (a text, b text, c text);+CREATE INDEX ON indexable_quals (a, b, c);++INSERT INTO indexable_quals VALUES ('a1', 'b', 'xxx');+INSERT INTO indexable_quals VALUES ('a1', 'b', 'yyy');+INSERT INTO indexable_quals VALUES ('a2', 'b', 'xxx');+INSERT INTO indexable_quals VALUES ('a2', 'b', 'yyy');++SELECT DISTINCT ON (a, b) a, b+FROM indexable_quals WHERE c LIKE '%y%' AND a LIKE 'a%' AND b = 'b';--
2.26.2
[text/x-diff] v38-0006-Index-skip-scan-documentation.patch (4.6K, ../20210314144833.tbfnn3pbrpjgl56z@localhost/7-v38-0006-Index-skip-scan-documentation.patch)
download | inline diff:
From da583ec267670e80eb2c2420ef7f89700418c966 Mon Sep 17 00:00:00 2001
From: Dmitrii Dolgov <9erthalion6@gmail.com>
Date: Mon, 8 Jun 2020 20:45:21 +0200
Subject: [PATCH v38 6/6] Index skip scan documentation
Covers added GUC and the extenion of index am interface.
Author: Jesper Pedersen, Dmitry Dolgov
Reviewed-by: Thomas Munro, David Rowley, Floris Van Nee, Kyotaro Horiguchi, Tomas Vondra, Peter Geoghegan
---
doc/src/sgml/config.sgml | 15 ++++++++++
doc/src/sgml/indexam.sgml | 62 +++++++++++++++++++++++++++++++++++++++
doc/src/sgml/indices.sgml | 23 +++++++++++++++
3 files changed, 100 insertions(+)
diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgmlindex a218d78bef..da916634ab 100644--- a/doc/src/sgml/config.sgml+++ b/doc/src/sgml/config.sgml@@ -4886,6 +4886,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 3442ae816b..0f211df7a1 100644--- a/doc/src/sgml/indexam.sgml+++ b/doc/src/sgml/indexam.sgml@@ -769,6 +769,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 623962d1d8..6589cb80ba 100644--- a/doc/src/sgml/indices.sgml+++ b/doc/src/sgml/indices.sgml@@ -1295,6 +1295,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.26.2
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: 9erthalion6@gmail.com, hlinnaka@iki.fi, pg@bowt.ie, jesper.pedersen@redhat.com, dgrowleyml@gmail.com, florisvannee@optiver.com, horikyota.ntt@gmail.com, thomas.munro@gmail.com, tomas.vondra@2ndquadrant.com, zhihui.fan1213@gmail.com, dilipbalaut@gmail.com
Subject: Re: Index Skip Scan (new UniqueKeys)
In-Reply-To: <20210314144833.tbfnn3pbrpjgl56z@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox