($INBOX_DIR/description missing)
help / color / mirror / Atom feedFrom: jesperpedersen <[email protected]>
Subject: [PATCH 1/2] Unique key
Date: Mon, 11 Nov 2019 08:49:43 -0500
Design by David Rowley.
Author: Jesper Pedersen
---
src/backend/nodes/outfuncs.c | 14 +++
src/backend/nodes/print.c | 39 +++++++
src/backend/optimizer/path/Makefile | 3 +-
src/backend/optimizer/path/allpaths.c | 8 ++
src/backend/optimizer/path/costsize.c | 5 +
src/backend/optimizer/path/indxpath.c | 41 +++++++
src/backend/optimizer/path/pathkeys.c | 71 ++++++++++--
src/backend/optimizer/path/uniquekey.c | 147 +++++++++++++++++++++++++
src/backend/optimizer/plan/planagg.c | 1 +
src/backend/optimizer/plan/planmain.c | 1 +
src/backend/optimizer/plan/planner.c | 17 ++-
src/backend/optimizer/util/pathnode.c | 12 ++
src/include/nodes/nodes.h | 1 +
src/include/nodes/pathnodes.h | 18 +++
src/include/nodes/print.h | 1 +
src/include/optimizer/pathnode.h | 1 +
src/include/optimizer/paths.h | 11 ++
17 files changed, 378 insertions(+), 13 deletions(-)
create mode 100644 src/backend/optimizer/path/uniquekey.c
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index b0dcd02ff6..1ccd68d3aa 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1720,6 +1720,7 @@ _outPathInfo(StringInfo str, const Path *node)
=09WRITE_FLOAT_FIELD(startup_cost, "%.2f");
=09WRITE_FLOAT_FIELD(total_cost, "%.2f");
=09WRITE_NODE_FIELD(pathkeys);
+=09WRITE_NODE_FIELD(uniquekeys);
}
=20
/*
@@ -2201,6 +2202,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *no=
de)
=09WRITE_NODE_FIELD(eq_classes);
=09WRITE_BOOL_FIELD(ec_merging_done);
=09WRITE_NODE_FIELD(canon_pathkeys);
+=09WRITE_NODE_FIELD(canon_uniquekeys);
=09WRITE_NODE_FIELD(left_join_clauses);
=09WRITE_NODE_FIELD(right_join_clauses);
=09WRITE_NODE_FIELD(full_join_clauses);
@@ -2210,6 +2212,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *no=
de)
=09WRITE_NODE_FIELD(placeholder_list);
=09WRITE_NODE_FIELD(fkey_list);
=09WRITE_NODE_FIELD(query_pathkeys);
+=09WRITE_NODE_FIELD(query_uniquekeys);
=09WRITE_NODE_FIELD(group_pathkeys);
=09WRITE_NODE_FIELD(window_pathkeys);
=09WRITE_NODE_FIELD(distinct_pathkeys);
@@ -2397,6 +2400,14 @@ _outPathKey(StringInfo str, const PathKey *node)
=09WRITE_BOOL_FIELD(pk_nulls_first);
}
=20
+static void
+_outUniqueKey(StringInfo str, const UniqueKey *node)
+{
+=09WRITE_NODE_TYPE("UNIQUEKEY");
+
+=09WRITE_NODE_FIELD(eq_clause);
+}
+
static void
_outPathTarget(StringInfo str, const PathTarget *node)
{
@@ -4083,6 +4094,9 @@ outNode(StringInfo str, const void *obj)
=09=09=09case T_PathKey:
=09=09=09=09_outPathKey(str, obj);
=09=09=09=09break;
+=09=09=09case T_UniqueKey:
+=09=09=09=09_outUniqueKey(str, obj);
+=09=09=09=09break;
=09=09=09case T_PathTarget:
=09=09=09=09_outPathTarget(str, obj);
=09=09=09=09break;
diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c
index 4ecde6b421..62c9d4ef7a 100644
--- a/src/backend/nodes/print.c
+++ b/src/backend/nodes/print.c
@@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtabl=
e)
=09printf(")\n");
}
=20
+/*
+ * print_uniquekeys -
+ *=09 unique_key an UniqueKey
+ */
+void
+print_uniquekeys(const List *uniquekeys, const List *rtable)
+{
+=09ListCell *l;
+
+=09printf("(");
+=09foreach(l, uniquekeys)
+=09{
+=09=09UniqueKey *unique_key =3D (UniqueKey *) lfirst(l);
+=09=09EquivalenceClass *eclass =3D (EquivalenceClass *) unique_key->eq_cla=
use;
+=09=09ListCell *k;
+=09=09bool=09=09first =3D true;
+
+=09=09/* chase up */
+=09=09while (eclass->ec_merged)
+=09=09=09eclass =3D eclass->ec_merged;
+
+=09=09printf("(");
+=09=09foreach(k, eclass->ec_members)
+=09=09{
+=09=09=09EquivalenceMember *mem =3D (EquivalenceMember *) lfirst(k);
+
+=09=09=09if (first)
+=09=09=09=09first =3D false;
+=09=09=09else
+=09=09=09=09printf(", ");
+=09=09=09print_expr((Node *) mem->em_expr, rtable);
+=09=09}
+=09=09printf(")");
+=09=09if (lnext(uniquekeys, l))
+=09=09=09printf(", ");
+=09}
+=09printf(")\n");
+}
+
/*
* print_tl
*=09 print targetlist in a more legible way.
diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/pa=
th/Makefile
index 1e199ff66f..63cc1505d9 100644
--- a/src/backend/optimizer/path/Makefile
+++ b/src/backend/optimizer/path/Makefile
@@ -21,6 +21,7 @@ OBJS =3D \
=09joinpath.o \
=09joinrels.o \
=09pathkeys.o \
-=09tidpath.o
+=09tidpath.o \
+=09uniquekey.o
=20
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/=
path/allpaths.c
index db3a68a51d..5fc9b81746 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent=
)
=09=09print_pathkeys(path->pathkeys, root->parse->rtable);
=09}
=20
+=09if (path->uniquekeys)
+=09{
+=09=09for (i =3D 0; i < indent; i++)
+=09=09=09printf("\t");
+=09=09printf(" uniquekeys: ");
+=09=09print_uniquekeys(path->uniquekeys, root->parse->rtable);
+=09}
+
=09if (join)
=09{
=09=09JoinPath *jp =3D (JoinPath *) path;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/=
path/costsize.c
index c5f6593485..0ec9a6db76 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -705,6 +705,11 @@ cost_index(IndexPath *path, PlannerInfo *root, double =
loop_count,
=09=09path->path.parallel_aware =3D true;
=09}
=20
+=09/* Consider cost based on unique key */
+=09if (path->path.uniquekeys)
+=09{
+=09}
+
=09/*
=09 * Now interpolate based on estimated index order correlation to get to=
tal
=09 * disk I/O cost for main table accesses.
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/=
path/indxpath.c
index 37b257cd0e..aa0da49119 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *=
index,
static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
=09=09=09=09=09=09=09=09=09 EquivalenceClass *ec, EquivalenceMember *em,
=09=09=09=09=09=09=09=09=09 void *arg);
+static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys);
=20
=20
/*
@@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
=09List=09 *orderbyclausecols;
=09List=09 *index_pathkeys;
=09List=09 *useful_pathkeys;
+=09List=09 *useful_uniquekeys;
=09bool=09=09found_lower_saop_clause;
=09bool=09=09pathkeys_possibly_useful;
=09bool=09=09index_is_ordered;
@@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *re=
l,
=09if (index_clauses !=3D NIL || useful_pathkeys !=3D NIL || useful_predic=
ate ||
=09=09index_only_scan)
=09{
+=09=09if (has_useful_uniquekeys(root))
+=09=09=09useful_uniquekeys =3D get_uniquekeys_for_index(root, useful_pathk=
eys);
+
=09=09ipath =3D create_index_path(root, index,
=09=09=09=09=09=09=09=09 index_clauses,
=09=09=09=09=09=09=09=09 orderbyclauses,
=09=09=09=09=09=09=09=09 orderbyclausecols,
=09=09=09=09=09=09=09=09 useful_pathkeys,
+=09=09=09=09=09=09=09=09 useful_uniquekeys,
=09=09=09=09=09=09=09=09 index_is_ordered ?
=09=09=09=09=09=09=09=09 ForwardScanDirection :
=09=09=09=09=09=09=09=09 NoMovementScanDirection,
@@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
=09=09=09=09=09=09=09=09=09 orderbyclauses,
=09=09=09=09=09=09=09=09=09 orderbyclausecols,
=09=09=09=09=09=09=09=09=09 useful_pathkeys,
+=09=09=09=09=09=09=09=09=09 useful_uniquekeys,
=09=09=09=09=09=09=09=09=09 index_is_ordered ?
=09=09=09=09=09=09=09=09=09 ForwardScanDirection :
=09=09=09=09=09=09=09=09=09 NoMovementScanDirection,
@@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *re=
l,
=09=09=09=09=09=09=09=09=09=09=09=09=09index_pathkeys);
=09=09if (useful_pathkeys !=3D NIL)
=09=09{
+=09=09=09if (has_useful_uniquekeys(root))
+=09=09=09=09useful_uniquekeys =3D get_uniquekeys_for_index(root, useful_pa=
thkeys);
+
=09=09=09ipath =3D create_index_path(root, index,
=09=09=09=09=09=09=09=09=09 index_clauses,
=09=09=09=09=09=09=09=09=09 NIL,
=09=09=09=09=09=09=09=09=09 NIL,
=09=09=09=09=09=09=09=09=09 useful_pathkeys,
+=09=09=09=09=09=09=09=09=09 useful_uniquekeys,
=09=09=09=09=09=09=09=09=09 BackwardScanDirection,
=09=09=09=09=09=09=09=09=09 index_only_scan,
=09=09=09=09=09=09=09=09=09 outer_relids,
@@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
=09=09=09=09=09=09=09=09=09=09 NIL,
=09=09=09=09=09=09=09=09=09=09 NIL,
=09=09=09=09=09=09=09=09=09=09 useful_pathkeys,
+=09=09=09=09=09=09=09=09=09=09 useful_uniquekeys,
=09=09=09=09=09=09=09=09=09=09 BackwardScanDirection,
=09=09=09=09=09=09=09=09=09=09 index_only_scan,
=09=09=09=09=09=09=09=09=09=09 outer_relids,
@@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index,
=09return clause;
}
=20
+/*
+ * get_uniquekeys_for_index
+ */
+static List *
+get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys)
+{
+=09ListCell *lc;
+
+=09if (pathkeys)
+=09{
+=09=09List *uniquekeys =3D NIL;
+=09=09foreach(lc, pathkeys)
+=09=09{
+=09=09=09UniqueKey *unique_key;
+=09=09=09PathKey *pk =3D (PathKey *) lfirst(lc);
+=09=09=09EquivalenceClass *ec =3D (EquivalenceClass *) pk->pk_eclass;
+
+=09=09=09unique_key =3D makeNode(UniqueKey);
+=09=09=09unique_key->eq_clause =3D ec;
+=09=09=09
+=09=09=09lappend(uniquekeys, unique_key);
+=09=09}
+
+=09=09if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys))
+=09=09=09return uniquekeys;
+=09}
+
+=09return NIL;
+}
=20
/*************************************************************************=
***
*=09=09=09=09---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS=09----
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/=
path/pathkeys.c
index 2f4fea241a..b0dc1bc22a 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -29,6 +29,7 @@
#include "utils/lsyscache.h"
=20
=20
+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,
=09=09=09=09=09=09=09=09=09=09=09 RelOptInfo *partrel,
@@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root,
=09return pk;
}
=20
+/*
+ * pathkey_is_unique
+ *=09 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)
+{
+=09EquivalenceClass *new_ec =3D new_pathkey->pk_eclass;
+=09ListCell *lc;
+
+=09/* If same EC already is already in the list, then not unique */
+=09foreach(lc, pathkeys)
+=09{
+=09=09PathKey *old_pathkey =3D (PathKey *) lfirst(lc);
+
+=09=09if (new_ec =3D=3D old_pathkey->pk_eclass)
+=09=09=09return false;
+=09}
+
+=09return true;
+}
+
/*
* pathkey_is_redundant
*=09 Is a pathkey redundant with one already in the given list?
@@ -135,22 +159,12 @@ static bool
pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
{
=09EquivalenceClass *new_ec =3D new_pathkey->pk_eclass;
-=09ListCell *lc;
=20
=09/* Check for EC containing a constant --- unconditionally redundant */
=09if (EC_MUST_BE_REDUNDANT(new_ec))
=09=09return true;
=20
-=09/* If same EC already used in list, then redundant */
-=09foreach(lc, pathkeys)
-=09{
-=09=09PathKey *old_pathkey =3D (PathKey *) lfirst(lc);
-
-=09=09if (new_ec =3D=3D old_pathkey->pk_eclass)
-=09=09=09return true;
-=09}
-
-=09return false;
+=09return !pathkey_is_unique(new_pathkey, pathkeys);
}
=20
/*
@@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root,
=09return pathkeys;
}
=20
+/*
+ * make_pathkeys_for_uniquekeyclauses
+ *=09=09Generate a pathkeys list to be used for uniquekey clauses
+ */
+List *
+make_pathkeys_for_uniquekeys(PlannerInfo *root,
+=09=09=09=09=09=09=09 List *sortclauses,
+=09=09=09=09=09=09=09 List *tlist)
+{
+=09List=09 *pathkeys =3D NIL;
+=09ListCell *l;
+
+=09foreach(l, sortclauses)
+=09{
+=09=09SortGroupClause *sortcl =3D (SortGroupClause *) lfirst(l);
+=09=09Expr=09 *sortkey;
+=09=09PathKey *pathkey;
+
+=09=09sortkey =3D (Expr *) get_sortgroupclause_expr(sortcl, tlist);
+=09=09Assert(OidIsValid(sortcl->sortop));
+=09=09pathkey =3D make_pathkey_from_sortop(root,
+=09=09=09=09=09=09=09=09=09=09 sortkey,
+=09=09=09=09=09=09=09=09=09=09 root->nullable_baserels,
+=09=09=09=09=09=09=09=09=09=09 sortcl->sortop,
+=09=09=09=09=09=09=09=09=09=09 sortcl->nulls_first,
+=09=09=09=09=09=09=09=09=09=09 sortcl->tleSortGroupRef,
+=09=09=09=09=09=09=09=09=09=09 true);
+
+=09=09if (pathkey_is_unique(pathkey, pathkeys))
+=09=09=09pathkeys =3D lappend(pathkeys, pathkey);
+=09}
+
+=09return pathkeys;
+}
+
/*************************************************************************=
***
*=09=09PATHKEYS AND MERGECLAUSES
*************************************************************************=
***/
diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer=
/path/uniquekey.c
new file mode 100644
index 0000000000..13d4ebb98c
--- /dev/null
+++ b/src/backend/optimizer/path/uniquekey.c
@@ -0,0 +1,147 @@
+/*------------------------------------------------------------------------=
-
+ *
+ * uniquekey.c
+ *=09 Utilities for matching and building unique keys
+ *
+ * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ *=09 src/backend/optimizer/path/uniquekey.c
+ *
+ *------------------------------------------------------------------------=
-
+ */
+#include "postgres.h"
+
+#include "optimizer/pathnode.h"
+#include "optimizer/paths.h"
+#include "nodes/pg_list.h"
+
+static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceC=
lass *eclass);
+
+/*
+ * Build a list of unique keys
+ */
+List*
+build_uniquekeys(PlannerInfo *root, List *sortclauses)
+{
+=09List *result =3D NIL;
+=09List *sortkeys;
+=09ListCell *l;
+
+=09sortkeys =3D make_pathkeys_for_uniquekeys(root,
+=09=09=09=09=09=09=09=09=09=09=09sortclauses,
+=09=09=09=09=09=09=09=09=09=09=09root->processed_tlist);
+
+=09/* Create a uniquekey and add it to the list */
+=09foreach(l, sortkeys)
+=09{
+=09=09PathKey *pathkey =3D (PathKey *) lfirst(l);
+=09=09EquivalenceClass *ec =3D pathkey->pk_eclass;
+=09=09UniqueKey *unique_key =3D make_canonical_uniquekey(root, ec);
+
+=09=09result =3D lappend(result, unique_key);
+=09}
+
+=09return result;
+}
+
+/*
+ * uniquekeys_contained_in
+ *=09 Are the keys2 included in the keys1 superset
+ */
+bool
+uniquekeys_contained_in(List *keys1, List *keys2)
+{
+=09ListCell *key1,
+=09=09=09 *key2;
+
+=09/*
+=09 * Fall out quickly if we are passed two identical lists. This mostly
+=09 * catches the case where both are NIL, but that's common enough to
+=09 * warrant the test.
+=09 */
+=09if (keys1 =3D=3D keys2)
+=09=09return true;
+
+=09foreach(key2, keys2)
+=09{
+=09=09bool found =3D false;
+=09=09UniqueKey *uniquekey2 =3D (UniqueKey *) lfirst(key2);
+
+=09=09foreach(key1, keys1)
+=09=09{
+=09=09=09UniqueKey *uniquekey1 =3D (UniqueKey *) lfirst(key1);
+
+=09=09=09if (uniquekey1->eq_clause =3D=3D uniquekey2->eq_clause)
+=09=09=09{
+=09=09=09=09found =3D true;
+=09=09=09=09break;
+=09=09=09}
+=09=09}
+
+=09=09if (!found)
+=09=09=09return false;
+=09}
+
+=09return true;
+}
+
+/*
+ * has_useful_uniquekeys
+ *=09=09Detect whether the planner could have any uniquekeys that are
+ *=09=09useful.
+ */
+bool
+has_useful_uniquekeys(PlannerInfo *root)
+{
+=09if (root->query_uniquekeys !=3D NIL)
+=09=09return true;=09/* there are some */
+=09return false;=09=09/* definitely useless */
+}
+
+/*
+ * make_canonical_uniquekey
+ *=09 Given the parameters for a UniqueKey, find any pre-existing matchin=
g
+ *=09 uniquekey in the query's list of "canonical" uniquekeys. Make a ne=
w
+ *=09 entry if there's not one already.
+ *
+ * Note that this function must not be used until after we have completed
+ * merging EquivalenceClasses. (We don't try to enforce that here; instea=
d,
+ * equivclass.c will complain if a merge occurs after root->canon_uniqueke=
ys
+ * has become nonempty.)
+ */
+static UniqueKey *
+make_canonical_uniquekey(PlannerInfo *root,
+=09=09=09=09=09=09 EquivalenceClass *eclass)
+{
+=09UniqueKey *uk;
+=09ListCell *lc;
+=09MemoryContext oldcontext;
+
+=09/* The passed eclass might be non-canonical, so chase up to the top */
+=09while (eclass->ec_merged)
+=09=09eclass =3D eclass->ec_merged;
+
+=09foreach(lc, root->canon_uniquekeys)
+=09{
+=09=09uk =3D (UniqueKey *) lfirst(lc);
+=09=09if (eclass =3D=3D uk->eq_clause)
+=09=09=09return uk;
+=09}
+
+=09/*
+=09 * Be sure canonical uniquekeys are allocated in the main planning cont=
ext.
+=09 * Not an issue in normal planning, but it is for GEQO.
+=09 */
+=09oldcontext =3D MemoryContextSwitchTo(root->planner_cxt);
+
+=09uk =3D makeNode(UniqueKey);
+=09uk->eq_clause =3D eclass;
+
+=09root->canon_uniquekeys =3D lappend(root->canon_uniquekeys, uk);
+
+=09MemoryContextSwitchTo(oldcontext);
+
+=09return uk;
+}
diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/p=
lan/planagg.c
index 9381939c82..3d32f6dfd6 100644
--- a/src/backend/optimizer/plan/planagg.c
+++ b/src/backend/optimizer/plan/planagg.c
@@ -512,6 +512,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra)
=09=09=09=09=09=09=09=09=09 root->parse->targetList);
=20
=09root->query_pathkeys =3D root->sort_pathkeys;
+=09root->query_uniquekeys =3D NIL;
}
=20
/*
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/=
plan/planmain.c
index f0c1b52a2e..3ccde03ab7 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -70,6 +70,7 @@ query_planner(PlannerInfo *root,
=09root->join_rel_level =3D NULL;
=09root->join_cur_level =3D 0;
=09root->canon_pathkeys =3D NIL;
+=09root->canon_uniquekeys =3D NIL;
=09root->left_join_clauses =3D NIL;
=09root->right_join_clauses =3D NIL;
=09root->full_join_clauses =3D NIL;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/p=
lan/planner.c
index 17c5f086fb..2507ec7d2a 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -3652,15 +3652,30 @@ standard_qp_callback(PlannerInfo *root, void *extra=
)
=09 * much easier, since we know that the parser ensured that one is a
=09 * superset of the other.
=09 */
+=09root->query_uniquekeys =3D NIL;
+
=09if (root->group_pathkeys)
+=09{
=09=09root->query_pathkeys =3D root->group_pathkeys;
+
+=09=09if (!root->parse->hasAggs)
+=09=09=09root->query_uniquekeys =3D build_uniquekeys(root, qp_extra->group=
Clause);
+=09}
=09else if (root->window_pathkeys)
=09=09root->query_pathkeys =3D root->window_pathkeys;
=09else if (list_length(root->distinct_pathkeys) >
=09=09=09 list_length(root->sort_pathkeys))
+=09{
=09=09root->query_pathkeys =3D root->distinct_pathkeys;
+=09=09root->query_uniquekeys =3D build_uniquekeys(root, parse->distinctCla=
use);
+=09}
=09else if (root->sort_pathkeys)
+=09{
=09=09root->query_pathkeys =3D root->sort_pathkeys;
+
+=09=09if (root->distinct_pathkeys)
+=09=09=09root->query_uniquekeys =3D build_uniquekeys(root, parse->distinct=
Clause);
+=09}
=09else
=09=09root->query_pathkeys =3D NIL;
}
@@ -6217,7 +6232,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid)
=20
=09/* Estimate the cost of index scan */
=09indexScanPath =3D create_index_path(root, indexInfo,
-=09=09=09=09=09=09=09=09=09 NIL, NIL, NIL, NIL,
+=09=09=09=09=09=09=09=09=09 NIL, NIL, NIL, NIL, NIL,
=09=09=09=09=09=09=09=09=09 ForwardScanDirection, false,
=09=09=09=09=09=09=09=09=09 NULL, 1.0, false);
=20
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/=
util/pathnode.c
index 34acb732ee..f268112386 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -941,6 +941,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel,
=09pathnode->parallel_safe =3D rel->consider_parallel;
=09pathnode->parallel_workers =3D parallel_workers;
=09pathnode->pathkeys =3D NIL;=09/* seqscan has unordered result */
+=09pathnode->uniquekeys =3D NIL;
=20
=09cost_seqscan(pathnode, root, rel, pathnode->param_info);
=20
@@ -965,6 +966,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *r=
el, Relids required_outer
=09pathnode->parallel_safe =3D rel->consider_parallel;
=09pathnode->parallel_workers =3D 0;
=09pathnode->pathkeys =3D NIL;=09/* samplescan has unordered result */
+=09pathnode->uniquekeys =3D NIL;
=20
=09cost_samplescan(pathnode, root, rel, pathnode->param_info);
=20
@@ -1001,6 +1003,7 @@ create_index_path(PlannerInfo *root,
=09=09=09=09 List *indexorderbys,
=09=09=09=09 List *indexorderbycols,
=09=09=09=09 List *pathkeys,
+=09=09=09=09 List *uniquekeys,
=09=09=09=09 ScanDirection indexscandir,
=09=09=09=09 bool indexonly,
=09=09=09=09 Relids required_outer,
@@ -1019,6 +1022,7 @@ create_index_path(PlannerInfo *root,
=09pathnode->path.parallel_safe =3D rel->consider_parallel;
=09pathnode->path.parallel_workers =3D 0;
=09pathnode->path.pathkeys =3D pathkeys;
+=09pathnode->path.uniquekeys =3D uniquekeys;
=20
=09pathnode->indexinfo =3D index;
=09pathnode->indexclauses =3D indexclauses;
@@ -1062,6 +1066,7 @@ create_bitmap_heap_path(PlannerInfo *root,
=09pathnode->path.parallel_safe =3D rel->consider_parallel;
=09pathnode->path.parallel_workers =3D parallel_degree;
=09pathnode->path.pathkeys =3D NIL;=09/* always unordered */
+=09pathnode->path.uniquekeys =3D NIL;
=20
=09pathnode->bitmapqual =3D bitmapqual;
=20
@@ -1923,6 +1928,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInf=
o *rel,
=09pathnode->parallel_safe =3D rel->consider_parallel;
=09pathnode->parallel_workers =3D 0;
=09pathnode->pathkeys =3D pathkeys;
+=09pathnode->uniquekeys =3D NIL;
=20
=09cost_functionscan(pathnode, root, rel, pathnode->param_info);
=20
@@ -1949,6 +1955,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptIn=
fo *rel,
=09pathnode->parallel_safe =3D rel->consider_parallel;
=09pathnode->parallel_workers =3D 0;
=09pathnode->pathkeys =3D NIL;=09/* result is always unordered */
+=09pathnode->uniquekeys =3D NIL;
=20
=09cost_tablefuncscan(pathnode, root, rel, pathnode->param_info);
=20
@@ -1975,6 +1982,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo =
*rel,
=09pathnode->parallel_safe =3D rel->consider_parallel;
=09pathnode->parallel_workers =3D 0;
=09pathnode->pathkeys =3D NIL;=09/* result is always unordered */
+=09pathnode->uniquekeys =3D NIL;
=20
=09cost_valuesscan(pathnode, root, rel, pathnode->param_info);
=20
@@ -2000,6 +2008,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *re=
l, Relids required_outer)
=09pathnode->parallel_safe =3D rel->consider_parallel;
=09pathnode->parallel_workers =3D 0;
=09pathnode->pathkeys =3D NIL;=09/* XXX for now, result is always unordere=
d */
+=09pathnode->uniquekeys =3D NIL;
=20
=09cost_ctescan(pathnode, root, rel, pathnode->param_info);
=20
@@ -2026,6 +2035,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, Re=
lOptInfo *rel,
=09pathnode->parallel_safe =3D rel->consider_parallel;
=09pathnode->parallel_workers =3D 0;
=09pathnode->pathkeys =3D NIL;=09/* result is always unordered */
+=09pathnode->uniquekeys =3D NIL;
=20
=09cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info);
=20
@@ -2052,6 +2062,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo =
*rel,
=09pathnode->parallel_safe =3D rel->consider_parallel;
=09pathnode->parallel_workers =3D 0;
=09pathnode->pathkeys =3D NIL;=09/* result is always unordered */
+=09pathnode->uniquekeys =3D NIL;
=20
=09cost_resultscan(pathnode, root, rel, pathnode->param_info);
=20
@@ -2078,6 +2089,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptIn=
fo *rel,
=09pathnode->parallel_safe =3D rel->consider_parallel;
=09pathnode->parallel_workers =3D 0;
=09pathnode->pathkeys =3D NIL;=09/* result is always unordered */
+=09pathnode->uniquekeys =3D NIL;
=20
=09/* Cost is the same as for a regular CTE scan */
=09cost_ctescan(pathnode, root, rel, pathnode->param_info);
diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index bce2d59b0d..cbb6ba2586 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -261,6 +261,7 @@ typedef enum NodeTag
=09T_EquivalenceMember,
=09T_PathKey,
=09T_PathTarget,
+=09T_UniqueKey,
=09T_RestrictInfo,
=09T_IndexClause,
=09T_PlaceHolderVar,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 23a06d718e..6198c31cd4 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -267,6 +267,8 @@ struct PlannerInfo
=20
=09List=09 *canon_pathkeys; /* list of "canonical" PathKeys */
=20
+=09List=09 *canon_uniquekeys; /* list of "canonical" UniqueKeys */
+
=09List=09 *left_join_clauses;=09/* list of RestrictInfos for mergejoina=
ble
=09=09=09=09=09=09=09=09=09 * outer join clauses w/nonnullable var on
=09=09=09=09=09=09=09=09=09 * left */
@@ -295,6 +297,8 @@ struct PlannerInfo
=20
=09List=09 *query_pathkeys; /* desired pathkeys for query_planner() */
=20
+=09List=09 *query_uniquekeys; /* */
+
=09List=09 *group_pathkeys; /* groupClause pathkeys, if any */
=09List=09 *window_pathkeys;=09/* pathkeys of bottom window, if any */
=09List=09 *distinct_pathkeys;=09/* distinctClause pathkeys, if any */
@@ -1075,6 +1079,15 @@ typedef struct ParamPathInfo
=09List=09 *ppi_clauses;=09/* join clauses available from outer rels */
} ParamPathInfo;
=20
+/*
+ * UniqueKey
+ */
+typedef struct UniqueKey
+{
+=09NodeTag=09=09type;
+
+=09EquivalenceClass *eq_clause;=09/* equivalence class */
+} UniqueKey;
=20
/*
* Type "Path" is used as-is for sequential-scan paths, as well as some ot=
her
@@ -1104,6 +1117,9 @@ typedef struct ParamPathInfo
*
* "pathkeys" is a List of PathKey nodes (see above), describing the sort
* ordering of the path's output rows.
+ *
+ * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above),
+ * describing the XXX.
*/
typedef struct Path
{
@@ -1127,6 +1143,8 @@ typedef struct Path
=20
=09List=09 *pathkeys;=09=09/* sort ordering of path's output */
=09/* pathkeys is a List of PathKey nodes; see above */
+
+=09List=09 *uniquekeys;=09/* the unique keys, or NIL if none */
} Path;
=20
/* Macro for extracting a path's parameterization relids; beware double ev=
al */
diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h
index cbff56a724..f1a7112877 100644
--- a/src/include/nodes/print.h
+++ b/src/include/nodes/print.h
@@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump);
extern void print_rt(const List *rtable);
extern void print_expr(const Node *expr, const List *rtable);
extern void print_pathkeys(const List *pathkeys, const List *rtable);
+extern void print_uniquekeys(const List *uniquekeys, const List *rtable);
extern void print_tl(const List *tlist, const List *rtable);
extern void print_slot(TupleTableSlot *slot);
=20
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathn=
ode.h
index a12af54971..37a946f857 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -44,6 +44,7 @@ extern IndexPath *create_index_path(PlannerInfo *root,
=09=09=09=09=09=09=09=09=09List *indexorderbys,
=09=09=09=09=09=09=09=09=09List *indexorderbycols,
=09=09=09=09=09=09=09=09=09List *pathkeys,
+=09=09=09=09=09=09=09=09=09List *uniquekeys,
=09=09=09=09=09=09=09=09=09ScanDirection indexscandir,
=09=09=09=09=09=09=09=09=09bool indexonly,
=09=09=09=09=09=09=09=09=09Relids required_outer,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index c6c34630c2..c79e47eeaf 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root,
extern List *make_pathkeys_for_sortclauses(PlannerInfo *root,
=09=09=09=09=09=09=09=09=09=09 List *sortclauses,
=09=09=09=09=09=09=09=09=09=09 List *tlist);
+extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root,
+=09=09=09=09=09=09=09=09=09=09 List *sortclauses,
+=09=09=09=09=09=09=09=09=09=09 List *tlist);
extern void initialize_mergeclause_eclasses(PlannerInfo *root,
=09=09=09=09=09=09=09=09=09=09=09RestrictInfo *restrictinfo);
extern void update_mergeclause_eclasses(PlannerInfo *root,
@@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *ro=
ot,
extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
=09=09=09=09=09=09=09=09=09List *live_childrels);
=20
+/*
+ * uniquekey.c
+ *=09 Utilities for matching and building unique keys
+ */
+extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses);
+extern bool uniquekeys_contained_in(List *keys1, List *keys2);
+extern bool has_useful_uniquekeys(PlannerInfo *root);
+
#endif=09=09=09=09=09=09=09/* PATHS_H */
--=20
2.21.0
--------------25BA7482CCCC3CA4CEC0D330
Content-Type: text/x-patch; charset=UTF-8;
name="v29_0002-Index-skip-scan.patch"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
filename="v29_0002-Index-skip-scan.patch"
view thread (49+ messages) latest in thread
reply
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: [email protected]
Cc: [email protected]
Subject: Re: [PATCH 1/2] Unique key
In-Reply-To: <no-message-id-1883349@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox