Thread: Use unique index for longer pathkeys.
Hello, This is the continuation from the last CF.
This patch intends to make PG to use index for longer pathkeys
than index columns when,
- The index is a unique index.- All index columns are NOT NULL.- The index column list is a subset of query_pathkeys.
The use cases for this patch are,
- (Useless?) DISTINCT on the table with PK constraints.
This alone is useless but this situation could take place when processing UNION (without ALL), which silently adds
DISTINCT* to element queries. Especially effective with ORDER BY and LIMIT clauses. But this needs another patch
forUNION optimization. This is the main motive for this patch.
- Unfortunately, other use cases are somewhat boresome, mainly effective for essentially unnecessary ORDER BY or
DISTINCT.To streatch a point, naively or mechanically composed queires could be saved by this patch..
====
Duing last CF, I proposed to match long pathkeys against index
columns during creating index paths. This worked fine but also it
is difficult to make sure that all side-effects are
eliminated. Finally Tom Lane suggested to truncate pathkeys while
generation of the pathkeys itself. So this patch comes.
This patch consists of mainly three parts.
1. Mark index as 'Uniquely orders the table' if the conditions are satisfied. This is the same from the previous
patch.
2. Collect the "common primary pathkeys", which is pathkeys that can perfectly sort all involved RTE's.
(collect_common_primary_pathkeys())
3. Trim the query pathkeys using the common primary pathkeys. (trim_query_pathkeys())
These steps take place between set_base_rel_sizes() and
set_base_rel_pathlists() in make_one_rel(). The reason for the
position is that the step 2 above needs all inheritence tables to
be extended in PlannerInfo and set_base_rel_sizes (currently)
does that. Then the trimmed pathkeys are used in
set_base_rel_pathlists so trim_query_pathkeys should be before
it. (This needs to be written as a comment?)
Finally, the new patch has grown up to twice in size.. Although
it seems a bit large, I think that side-effects are clearly
avoided.
This message is attatched by two patches.
1. pathkey_and_uniqueindx_typ2_v1.patch : This new patch.
2. pathkey_and_uniqueindx_v10_20130411.patch : The last version of the previous approach.
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index fdaa964..47b8056 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -50,6 +50,7 @@ int geqo_threshold;join_search_hook_type join_search_hook = NULL;
+static List *collect_common_primary_pathkeys(PlannerInfo *root);static void set_base_rel_sizes(PlannerInfo
*root);staticvoid set_base_rel_pathlists(PlannerInfo *root);static void set_rel_size(PlannerInfo *root, RelOptInfo
*rel,
@@ -58,6 +59,7 @@ static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti,
RangeTblEntry*rte);static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry
*rte);
+static void trim_query_pathkeys(PlannerInfo * root);static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo
*rel, RangeTblEntry *rte);static void set_foreign_size(PlannerInfo *root, RelOptInfo *rel,
@@ -102,6 +104,214 @@ static void recurse_push_qual(Node *setOp, Query *topquery, RangeTblEntry *rte,
Indexrti, Node *qual);static void remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel);
+/*
+ * collect_common_primary_pathkeys: Collects common unique and non-null index
+ * pathkeys from all base relations in current root.
+ */
+
+static List *
+collect_common_primary_pathkeys(PlannerInfo *root)
+{
+ List *result = NIL;
+ Index rti;
+ int nindex = -1;
+ List **pathkeys_array0 = NULL;
+ List **pathkeys_array = NULL;
+ List **pathkeys_array2 = NULL;
+ bool multipass = (root->simple_rel_array_size > 2);
+
+ for (rti = 1 ; rti < root->simple_rel_array_size && nindex ; rti++)
+ {
+ RelOptInfo *rel = root->simple_rel_array[rti];
+ List **pktmp;
+
+ if (rel == NULL)
+ continue;
+
+ Assert (rel->relid == rti);
+
+ /*
+ * Scan all base relations except parent relations.
+ */
+ if (root->simple_rte_array[rti]->inh ||
+ (rel->reloptkind != RELOPT_BASEREL &&
+ rel->reloptkind != RELOPT_OTHER_MEMBER_REL))
+ continue;
+
+ /* pathkeys_array is NULL for the first iteration */
+ if (pathkeys_array == NULL)
+ {
+ ListCell *lc;
+ int i = 0;
+
+ /* Skip rigging for "AND" operation if not needed. */
+ if (multipass)
+ {
+ nindex = 0;
+
+ foreach (lc, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+
+ if (index->full_ordered && index->indpred == NIL)
+ nindex++;
+ }
+
+ if (nindex == 0)
+ return NULL;
+
+ pathkeys_array0 = palloc0(sizeof(List*) * nindex * 2);
+ pathkeys_array = pathkeys_array0;
+ pathkeys_array2 = pathkeys_array0 + nindex;
+ }
+
+ foreach (lc, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+
+ if (index->full_ordered && index->indpred == NIL)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+ List *idx_pathkeys;
+
+ idx_pathkeys = build_index_pathkeys(root, index,
+ ForwardScanDirection);
+ if (idx_pathkeys)
+ {
+ if (multipass)
+ pathkeys_array[i++] = idx_pathkeys;
+ else
+ result = lappend(result, idx_pathkeys);
+ }
+ }
+ }
+ nindex = i;
+ }
+ else
+ {
+ int i;
+ int nmatch = 0;
+ ListCell *lc;
+
+ Assert(multipass);
+
+ for (i = 0 ; i < nindex ; i++) pathkeys_array2[i] = NULL;
+
+ foreach (lc, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+
+ if (index->full_ordered && index->indpred == NIL)
+ {
+ List *idx_pathkeys;
+
+ idx_pathkeys = build_index_pathkeys(root, index,
+ ForwardScanDirection);
+ if (!idx_pathkeys)
+ continue;
+
+ /*
+ * AND operation: drop pathkeys which don't see identical
+ * one in this relation.
+ */
+ for (i = 0 ; i < nindex ; i++)
+ {
+ if (!pathkeys_array2[i] &&
+ compare_pathkeys(pathkeys_array[i], idx_pathkeys)
+ == PATHKEYS_EQUAL)
+ {
+ pathkeys_array2[i] = pathkeys_array[i];
+ nmatch++;
+
+ /* Also drop possible duplicate pathkeys. */
+ break;
+ }
+ }
+ }
+ }
+ if (nmatch == 0)
+ return NULL;
+
+ /* swap two pathkeys arrays */
+ pktmp = pathkeys_array2;
+ pathkeys_array2 = pathkeys_array;
+ pathkeys_array = pktmp;
+ }
+ }
+
+ if (multipass)
+ {
+ int i;
+
+ for (i = 0 ; i < nindex ; i++)
+ {
+ if (pathkeys_array[i])
+ result = lappend(result, pathkeys_array[i]);
+ }
+ pfree(pathkeys_array0);
+ }
+
+ return result;
+}
+
+/*
+ * trim_query_pathkeys: trim pathkeys following common primary pathkeys.
+ *
+ * Primary pathkeys are pathkeys which perfectly sorts tuples in its owner
+ * table so the query pathkeys can be replaced with the primary pathkeys when
+ * the latter prefixes the former. Common primary pathkeys are the primary
+ * pathkeys shared among all base relations accessed in current root. In
+ * general cases, all pathkeys other than sort_pathkeys are allowed to flip
+ * ordering direction in part of its members, but grouping (orderless)
+ * pathkeys might have the same ordering directions with sort_pathkeys in most
+ * cases where sort_pathkeys exists. So just disable partial flipping for all
+ * pathkeys if sort_pathkeys exists.
+ */
+static void
+trim_query_pathkeys(PlannerInfo * root)
+{
+ ListCell *lc;
+
+ foreach(lc, collect_common_primary_pathkeys(root))
+ {
+ List *pk_guide = (List*) lfirst(lc);
+
+ if (root->sort_pathkeys)
+ {
+ root->sort_pathkeys =
+ shorten_pathkeys_following(root, root->sort_pathkeys, pk_guide,
+ false);
+
+ /*
+ * Replace guide pathkeys with new sort_pathkeys if they differs
+ * from each other only by sorting directions.
+ */
+ if (compare_pathkeys(root->sort_pathkeys,
+ pk_guide) != PATHKEYS_EQUAL &&
+ compare_pathkeys_ignoring_strategy(root->sort_pathkeys,
+ pk_guide) == PATHKEYS_EQUAL)
+ pk_guide = root->sort_pathkeys;
+ }
+
+ root->group_pathkeys =
+ shorten_pathkeys_following(root, root->group_pathkeys, pk_guide,
+ true);
+
+ /*
+ * Currently window_pathkeys for multiple partitioning columns is
+ * composed of a pathkey of RowExpr, which cannot be compared (easily)
+ * with other pathkeys. Skip it.
+ */
+
+ root->distinct_pathkeys =
+ shorten_pathkeys_following(root, root->distinct_pathkeys,pk_guide,
+ true);
+
+ root->query_pathkeys =
+ shorten_pathkeys_following(root,root->query_pathkeys,pk_guide,
+ true);
+ }
+}/* * make_one_rel
@@ -139,6 +349,7 @@ make_one_rel(PlannerInfo *root, List *joinlist) * Generate access paths for the base rels.
*/ set_base_rel_sizes(root);
+ trim_query_pathkeys(root); set_base_rel_pathlists(root); /*
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 5d953df..0fdb15a 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -311,6 +311,53 @@ compare_pathkeys(List *keys1, List *keys2) return PATHKEYS_EQUAL;}
+PathKeysComparison
+compare_pathkeys_ignoring_strategy(List *keys1, List *keys2)
+{
+ ListCell *key1,
+ *key2;
+
+ /*
+ * Fall out quickly if we are passed two identical lists. This mostly
+ * catches the case where both are NIL, but that's common enough to
+ * warrant the test.
+ */
+ if (keys1 == keys2)
+ return PATHKEYS_EQUAL;
+
+ forboth(key1, keys1, key2, keys2)
+ {
+ PathKey *pathkey1 = (PathKey *) lfirst(key1);
+ PathKey *pathkey2 = (PathKey *) lfirst(key2);
+
+ if (pathkey1 != pathkey2)
+ {
+ Assert(pathkey1->pk_strategy == BTGreaterStrategyNumber ||
+ pathkey1->pk_strategy == BTLessStrategyNumber);
+ Assert(pathkey2->pk_strategy == BTGreaterStrategyNumber ||
+ pathkey2->pk_strategy == BTLessStrategyNumber);
+
+ if (pathkey1->pk_eclass != pathkey2->pk_eclass ||
+ pathkey1->pk_opfamily != pathkey2->pk_opfamily ||
+ !((pathkey1->pk_strategy == pathkey2->pk_strategy &&
+ pathkey1->pk_nulls_first == pathkey2->pk_nulls_first) ||
+ (pathkey1->pk_strategy != pathkey2->pk_strategy &&
+ pathkey1->pk_nulls_first != pathkey2->pk_nulls_first)))
+ return PATHKEYS_DIFFERENT; /* no need to keep looking */
+ }
+ }
+
+ /*
+ * If we reached the end of only one list, the other is longer and
+ * therefore not a subset.
+ */
+ if (key1 != NULL)
+ return PATHKEYS_BETTER1; /* key1 is longer */
+ if (key2 != NULL)
+ return PATHKEYS_BETTER2; /* key2 is longer */
+ return PATHKEYS_EQUAL;
+}
+/* * pathkeys_contained_in * Common special case of compare_pathkeys: we just want to know
@@ -1525,3 +1572,87 @@ has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel) return true; /* might
beable to use them for ordering */ return false; /* definitely useless */}
+
+/*
+ * shorten_pathkeys_following: returns pk_guide if it prefixes pk_target
+ * regardless of the ordering directions of the pathkeys.
+ * allow_partial_flip allows ordering directions to be partially different
+ * between pk_target and pk_guide.
+ */
+List *
+shorten_pathkeys_following(PlannerInfo *root, List *pk_target, List *pk_guide,
+ bool allow_partial_flip)
+{
+ ListCell *tlc, *glc;
+ int same = 0, reverse = 0;
+ List *result;
+
+ if (pk_target == NIL)
+ return NIL;
+
+ if (list_length(pk_target) < list_length(pk_guide))
+ return pk_target;
+
+ forboth(tlc, pk_target, glc, pk_guide)
+ {
+ PathKey *tpk = (PathKey *) lfirst(tlc);
+ PathKey *gpk = (PathKey *) lfirst(glc);
+
+ if (tpk == gpk)
+ {
+ same++;
+ continue;
+ }
+
+ Assert(tpk->pk_strategy == BTGreaterStrategyNumber ||
+ tpk->pk_strategy == BTLessStrategyNumber);
+ Assert(gpk->pk_strategy == BTGreaterStrategyNumber ||
+ gpk->pk_strategy == BTLessStrategyNumber);
+
+ if (tpk->pk_eclass == gpk->pk_eclass &&
+ tpk->pk_opfamily == gpk->pk_opfamily &&
+ tpk->pk_strategy != gpk->pk_strategy &&
+ tpk->pk_nulls_first != gpk->pk_nulls_first)
+ {
+ reverse++;
+ continue;
+ }
+
+ return pk_target;
+ }
+
+ /* trailing members in pk_target don't matter */
+
+ /* reverse == 0 means that pk_guide exactly prefixes pk_target */
+ if (allow_partial_flip || reverse == 0)
+ return pk_guide;
+
+ /*
+ * Don't replace pathkeys if partial flip is not allowed but partially
+ * flipped.
+ */
+ Assert(reverse > 0);
+ if (same > 0)
+ return pk_target;
+
+ /* make then reutrn the reverse pathkeys of pk_guide */
+ result = NIL;
+ foreach (glc, pk_guide)
+ {
+ PathKey *gpk = (PathKey *) lfirst(glc);
+ PathKey *pk;
+ EquivalenceClass *ec = gpk->pk_eclass;
+ int revstr;
+
+ if (gpk->pk_strategy == BTGreaterStrategyNumber)
+ revstr = BTLessStrategyNumber;
+ else
+ revstr = BTGreaterStrategyNumber;
+
+ pk = make_canonical_pathkey(root, ec, gpk->pk_opfamily, revstr,
+ !gpk->pk_nulls_first);
+
+ result = lappend(result, pk);
+ }
+ return result;
+}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index b2becfa..5520e76 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -231,6 +231,8 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, */
if (info->relam == BTREE_AM_OID) {
+ bool has_nullable_keycol = false;
+ /* * If it's a btree index, we can use its opfamily OIDs * directly as
thesort ordering opfamily OIDs.
@@ -244,10 +246,26 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, for (i
=0; i < ncolumns; i++) { int16 opt = indexRelation->rd_indoption[i];
+ int16 keyattno = index->indkey.values[i]; info->reverse_sort[i] = (opt &
INDOPTION_DESC)!= 0; info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
+
+ if (keyattno > 0)
+ {
+ has_nullable_keycol |=
+ !relation->rd_att->attrs[keyattno - 1]->attnotnull;
+ }
+ /* OID should not be NULL if exists */
+ else if (keyattno != ObjectIdAttributeNumber)
+ has_nullable_keycol = true; }
+
+ /* Check to see if it is a full-ordered index */
+ if (IndexIsValid(index) &&
+ index->indisunique && index->indimmediate &&
+ !has_nullable_keycol)
+ info->full_ordered = true; } else if (indexRelation->rd_am->amcanorder)
{
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 300136e..a6b371e 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -525,6 +525,7 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */ bool immediate; /* is uniqueness
enforcedimmediately? */
+ bool full_ordered; /* don't key columns duplicate? */ bool hypothetical; /* true if index
doesn'treally exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9b22fda..506673f 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -147,6 +147,8 @@ typedef enum} PathKeysComparison;extern PathKeysComparison compare_pathkeys(List *keys1, List
*keys2);
+extern PathKeysComparison compare_pathkeys_ignoring_strategy(List *keys1,
+ List *keys2);extern bool pathkeys_contained_in(List
*keys1,List *keys2);extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
Relids required_outer,
@@ -187,5 +189,8 @@ extern List *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
List *pathkeys);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
+extern List *shorten_pathkeys_following(PlannerInfo *root,
+ List *pk_target, List *pk_guide,
+ bool allow_partial_flip);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index bfb4b9f..ff5c88c 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1790,6 +1790,7 @@ _outIndexOptInfo(StringInfo str, const IndexOptInfo *node) WRITE_BOOL_FIELD(predOK);
WRITE_BOOL_FIELD(unique); WRITE_BOOL_FIELD(immediate);
+ WRITE_BOOL_FIELD(allnotnull); WRITE_BOOL_FIELD(hypothetical); /* we don't bother with fields copied from the
pg_amentry */}
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index a912174..4376e95 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -951,8 +951,11 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, { index_pathkeys =
build_index_pathkeys(root,index, ForwardScanDirection);
- useful_pathkeys = truncate_useless_pathkeys(root, rel,
- index_pathkeys);
+ if (index_pathkeys_are_extensible(root, index, index_pathkeys))
+ useful_pathkeys = root->query_pathkeys;
+ else
+ useful_pathkeys = truncate_useless_pathkeys(root, rel,
+ index_pathkeys); orderbyclauses = NIL;
orderbyclausecols= NIL; }
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 9179c61..5edca4f 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -502,6 +502,76 @@ build_index_pathkeys(PlannerInfo *root,}/*
+ * index_pathkeys_are_extensible
+ * Check whether the pathkeys are extensible to query_pathkeys.
+ */
+bool
+index_pathkeys_are_extensible(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *pathkeys)
+{
+ bool result;
+ ListCell *lc1, *remain;
+
+ if (root->query_pathkeys == NIL || pathkeys == NIL)
+ return false;
+
+ /* This index is not suitable for pathkey extension */
+ if (!index->unique || !index->immediate || !index->allnotnull)
+ return false;
+
+ /* pathkeys is a prefixing proper subset of index tlist */
+ if (list_length(pathkeys) < list_length(index->indextlist))
+ return false;
+
+ if (!pathkeys_contained_in(pathkeys, root->query_pathkeys))
+ return false;
+
+ if (list_length(pathkeys) == list_length(root->query_pathkeys))
+ return true;
+
+ Assert(list_length(root->query_pathkeys) > list_length(pathkeys));
+
+ /*
+ * Check if all unchecked elements of query_patheys are simple Vars for
+ * the same relation.
+ */
+
+ /* list_nth_cell is not exposed publicly.. */
+ if (list_length(pathkeys) == list_length(root->query_pathkeys) - 1)
+ remain = list_tail(root->query_pathkeys);
+ else
+ {
+ int n = list_length(pathkeys);
+
+ remain = root->query_pathkeys->head;
+ while(n-- > 0) remain = remain->next;
+ }
+
+ result = true;
+ for_each_cell(lc1, remain)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc1);
+ ListCell *lc2;
+
+ foreach(lc2, pathkey->pk_eclass->ec_members)
+ {
+ EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2);
+
+ if (!bms_equal(member->em_relids, index->rel->relids) ||
+ !IsA(member->em_expr, Var))
+ {
+ result = false;
+ break;
+ }
+ }
+
+ if (!result) break;
+ }
+ return result;
+}
+
+/* * build_expression_pathkey * Build a pathkeys list that describes an ordering by a single expression *
usingthe given sort operator.
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 73ba2f6..c61cddb 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -333,6 +333,26 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->immediate= index->indimmediate; info->hypothetical = false;
+ info->allnotnull = true;
+ for (i = 0; i < ncolumns; i++)
+ {
+ int attrno = info->indexkeys[i];
+
+ if (attrno == 0)
+ {
+ info->allnotnull = false;
+ break;
+ }
+ else if (attrno > 0)
+ {
+ if (!relation->rd_att->attrs[attrno - 1]->attnotnull)
+ {
+ info->allnotnull = false;
+ break;
+ }
+ }
+ }
+ /* * Estimate the index size. If it's not a partial index, we lock * the
number-of-tuplesestimate to equal the parent table; if it
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index c607b36..119bb31 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -525,6 +525,7 @@ typedef struct IndexOptInfo bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */ bool immediate; /* is uniqueness
enforcedimmediately? */
+ bool allnotnull; /* true if index's keys are all not null */ bool hypothetical; /* true
ifindex doesn't really exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9b22fda..8abdb99 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -187,5 +187,8 @@ extern List *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
List *pathkeys);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
+extern bool index_pathkeys_are_extensible(PlannerInfo *root,
+ IndexOptInfo *index,
+ List *pathkeys);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
Hi. I took a quick look at this patch, more or less because nobody else did. > Duing last CF, I proposed to match long pathkeys against index columns > during creating index paths. This worked fine but also it is difficult > to make sure that all side-effects are eliminated. Finally Tom Lane > suggested to truncate pathkeys while generation of the pathkeys > itself. So this patch comes. I found your older patch quite straightforward to understand, but the new one much more difficult to follow (but that's not saying much, I am not very familiar with the planner code in general). Do you have any references to the discussion about the side-effects that needed to be eliminated with the earlier patch? -- Abhijit
Thank you for taking a look on this patch. > I took a quick look at this patch, more or less because nobody else did. > > > Duing last CF, I proposed to match long pathkeys against index columns > > during creating index paths. This worked fine but also it is difficult > > to make sure that all side-effects are eliminated. Finally Tom Lane > > suggested to truncate pathkeys while generation of the pathkeys > > itself. So this patch comes. > > I found your older patch quite straightforward to understand, but the > new one much more difficult to follow (but that's not saying much, I > am not very familiar with the planner code in general). I think it's quite natural to think so. > Do you have any references to the discussion about the side-effects that > needed to be eliminated with the earlier patch? The biggest side-effects (or simplly defect) found so far is discussed here, http://www.postgresql.org/message-id/01bd01cf0b4e$9b960ad0$d2c22070$@etsuro@lab.ntt.co.jp This was caused by omitting the membership of the Var under inspection while cheking if the pathkeys is extensible. http://www.postgresql.org/message-id/20140107.145900.196068363.horiguchi.kyotaro@lab.ntt.co.jp After all, Tom said that the right way to do this is not such whacking-a-mole thing but loosen pathkeys previously so that the planner naturally do what the previous patch did without any special treat. http://www.postgresql.org/message-id/5212.1397599817@sss.pgh.pa.us So the new patch comes. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
On Fri, Jun 13, 2014 at 1:11 PM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
>
> Hello, This is the continuation from the last CF.
>
> This patch intends to make PG to use index for longer pathkeys
> than index columns when,
>
> - The index is a unique index.
> - All index columns are NOT NULL.
> - The index column list is a subset of query_pathkeys.
>
> ====
>
> This patch consists of mainly three parts.
>
> 1. Mark index as 'Uniquely orders the table' if the conditions
> are satisfied. This is the same from the previous patch.
>
> 2. Collect the "common primary pathkeys", which is pathkeys that
> can perfectly sort all involved
> RTE's. (collect_common_primary_pathkeys())
>
> 3. Trim the query pathkeys using the common primary pathkeys.
> (trim_query_pathkeys())
I have spent some time on this patch and would like to share my
1.
It seems to me that the new flag (IndexOptInfo.full_ordered) introduced in
>
> Hello, This is the continuation from the last CF.
>
> This patch intends to make PG to use index for longer pathkeys
> than index columns when,
>
> - The index is a unique index.
> - All index columns are NOT NULL.
> - The index column list is a subset of query_pathkeys.
>
> ====
>
> This patch consists of mainly three parts.
>
> 1. Mark index as 'Uniquely orders the table' if the conditions
> are satisfied. This is the same from the previous patch.
>
> 2. Collect the "common primary pathkeys", which is pathkeys that
> can perfectly sort all involved
> RTE's. (collect_common_primary_pathkeys())
>
> 3. Trim the query pathkeys using the common primary pathkeys.
> (trim_query_pathkeys())
I have spent some time on this patch and would like to share my
findings as below with you.
1.
It seems to me that the new flag (IndexOptInfo.full_ordered) introduced in
this patch is not getting set properly. Please refer below test:
Shouldn't above query use index scan after patch?
> Finally, the new patch has grown up to twice in size.. Although
> it seems a bit large, I think that side-effects are clearly
> avoided.
I am bit worried about the extra cycles added by this patch as compare
create table t (a int, b int, c int, d text);
create unique index i_t_pkey on t(a, b);
insert into t (select a % 10, a / 10, a, 't' from generate_series(0, 100000) a);
analyze;
explain (costs off, analyze on) select distinct * from t;
Unptached -
postgres=# explain (costs off, analyze on) select distinct * from t;
QUERY PLAN
---------------------------------------------------------------------------
Unique (actual time=331.624..597.278 rows=100001 loops=1)
-> Sort (actual time=330.889..430.449 rows=100001 loops=1)
Sort Key: a, b, c, d
Sort Method: external merge Disk: 2344kB
-> Seq Scan on t (actual time=0.013..74.202 rows=100001 loops=1)
Execution time: 665.332 ms
(6 rows)
Patch (pathkey_and_uniqueindx_typ2_v1) -
postgres=# explain (costs off, analyze on) select distinct * from t;
QUERY PLAN
---------------------------------------------------------------------------
Unique (actual time=336.033..601.144 rows=100001 loops=1)
-> Sort (actual time=336.027..436.621 rows=100001 loops=1)
Sort Key: a, b, c, d
Sort Method: external merge Disk: 2344kB
-> Seq Scan on t (actual time=0.014..78.826 rows=100001 loops=1)
Execution time: 667.387 ms
(6 rows)
Shouldn't above query use index scan after patch?
2.
typedef struct IndexOptInfo
bool predOK; /* true if predicate matches query */
bool unique; /* true if a unique index */
bool immediate; /* is uniqueness enforced immediately? */
+ bool full_ordered; /* don't key columns duplicate? */
It seems you have forgotten to update out function _outIndexOptInfo().
3.
+ root->distinct_pathkeys =
+ shorten_pathkeys_following(root, root->distinct_pathkeys,pk_guide,
+ true);
+
+ root->query_pathkeys =
+ shorten_pathkeys_following(root,root->query_pathkeys,pk_guide,
+ true);
Add a space after each parameter in function call.
4.
+PathKeysComparison
+compare_pathkeys_ignoring_strategy(List *keys1, List *keys2)
a. This function return 4 different type of values (PATHKEYS_EQUAL,
PATHKEYS_DIFFERENT, PATHKEYS_BETTER1, PATHKEYS_BETTER2),
however the caller just checks for PATHKEYS_EQUAL, isn't it better to just
return either PATHKEYS_EQUAL or PATHKEYS_DIFFERENT.
b. Another idea could be that instead of writting separate function,
pass an additional parameter to compare_pathkeys() to distinguish
for ignore strategy case.
c. In any case, I think it is good to add comments on top of newly
introduced function (compare_pathkeys_ignoring_strategy) or extend
the comments of compare_pathkeys() if you want to add a new parameter
to it.
> Finally, the new patch has grown up to twice in size.. Although
> it seems a bit large, I think that side-effects are clearly
> avoided.
I am bit worried about the extra cycles added by this patch as compare
to your previous patch; example
During trimming of paths, it will build index paths (build_index_pathkeys())
which it will anyway do again during creation of index paths:
create_index_paths()->get_index_paths()->build_index_paths()->build_index_pathkeys()
I am not sure if this has direct impact, however I am suspecting trimming
logic can add quite a few instructions even for cases when it is not beneficial.
At this moment, I also don't have better idea, so lets proceed with review of this
patch unless there is any other better way to achieve it.
Thank you for reviewing, the revised patch will come later. At Mon, 14 Jul 2014 11:01:52 +0530, Amit Kapila <amit.kapila16@gmail.com> wrote in <CAA4eK1+6b6Wjwf51oZMrL+mKFH8xUp9J-pEhQvoR8SE7sWyTWw@mail.gmail.com> > On Fri, Jun 13, 2014 at 1:11 PM, Kyotaro HORIGUCHI < > horiguchi.kyotaro@lab.ntt.co.jp> wrote: > > > > Hello, This is the continuation from the last CF. > > > > This patch intends to make PG to use index for longer pathkeys > > than index columns when, > > > > - The index is a unique index. > > - All index columns are NOT NULL. > > - The index column list is a subset of query_pathkeys. > > > > ==== > > > > This patch consists of mainly three parts. (snip) > > I have spent some time on this patch and would like to share my > findings as below with you. > > 1. > It seems to me that the new flag (IndexOptInfo.full_ordered) introduced in > this patch is not getting set properly. Please refer below test: Yeah, probably you omitted the second condition above. > create table t (a int, b int, c int, d text); The following definition instead will make this work. NULLs cannot be unique. | create table t (a int not null, b int not null, c int, d text); > create unique index i_t_pkey on t(a, b); > insert into t (select a % 10, a / 10, a, 't' from generate_series(0, > 100000) a); > analyze; > explain (costs off, analyze on) select distinct * from t; ... > 2. > typedef struct IndexOptInfo > bool predOK; /* true if predicate matches query */ > bool unique; /* true if a unique index */ > bool immediate; /* is uniqueness enforced immediately? */ > + bool full_ordered; /* don't key columns duplicate? */ > > It seems you have forgotten to update out function _outIndexOptInfo(). Mmm, it's surely what I didn't intended to make:( , but the member actually works in collect_common_primary_pathkeys. The correct (desirable) code should use (allnotnull && unique) instead of (full_ordered). I'll fix this in the comming version later but they are equivelant in functionality. It's not a mistake of forgetting update out (so broken), but branching from wrong point (so it works contrary to the expectation):) > 3. > + root->distinct_pathkeys = > + shorten_pathkeys_following(root, root->distinct_pathkeys,pk_guide, > + true); > + > + root->query_pathkeys = > + shorten_pathkeys_following(root,root->query_pathkeys,pk_guide, > + true); > > Add a space after each parameter in function call. Thank you for pointing out. > 4. > +PathKeysComparison > +compare_pathkeys_ignoring_strategy(List *keys1, List *keys2) > > a. This function return 4 different type of values (PATHKEYS_EQUAL, > PATHKEYS_DIFFERENT, PATHKEYS_BETTER1, PATHKEYS_BETTER2), > however the caller just checks for PATHKEYS_EQUAL, isn't it better to > just > return either PATHKEYS_EQUAL or PATHKEYS_DIFFERENT. Hmm.. I agree that it is practically removable, but I think it is necessary from the view of similarity to the function with the similar name. Perhaps I want another name which don't suggest the similarity to compare_pathekeys(), say, bool pathkeys_are_equal_ignoring_strategy() to change the rerurn values set. > b. Another idea could be that instead of writting separate function, > pass an additional parameter to compare_pathkeys() to distinguish > for ignore strategy case. It sounds reasonable. According to my faint memory, the reason why the function is separated from the original one is, perhaps, simplly a editorial reason. > c. In any case, I think it is good to add comments on top of newly > introduced function (compare_pathkeys_ignoring_strategy) or extend > the comments of compare_pathkeys() if you want to add a new parameter > to it. Ouch, thank you for pointing out. I'll add comment if it remains in the next patch. > > Finally, the new patch has grown up to twice in size.. Although > > it seems a bit large, I think that side-effects are clearly > > avoided. > > I am bit worried about the extra cycles added by this patch as compare > to your previous patch; example > During trimming of paths, it will build index paths (build_index_pathkeys()) > which it will anyway do again during creation of index paths: > create_index_paths()->get_index_paths()->build_index_paths()->build_index_pathkeys() I felt the same thing. On stupid measure to reduce cycles would be caching created pathkeys in IndexOptInfo. I'll try in the next patch. > I am not sure if this has direct impact, however I am suspecting trimming > logic can add quite a few instructions even for cases when it is not > beneficial. > At this moment, I also don't have better idea, so lets proceed with review > of this > patch unless there is any other better way to achieve it. I suppose there's some shortcut which can exclude the cases where obviously there's no use of pathkeys trimming, for example, using only pathkey lengths. I'll seek for it. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
On Mon, Jul 14, 2014 at 4:02 PM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
> At Mon, 14 Jul 2014 11:01:52 +0530, Amit Kapila <amit.kapila16@gmail.com> wrote in <CAA4eK1+6b6Wjwf51oZMrL+mKFH8xUp9J-pEhQvoR8SE7sWyTWw@mail.gmail.com>
> > On Fri, Jun 13, 2014 at 1:11 PM, Kyotaro HORIGUCHI <
> > horiguchi.kyotaro@lab.ntt.co.jp> wrote:
> > I am bit worried about the extra cycles added by this patch as compare
> > to your previous patch; example
> > During trimming of paths, it will build index paths (build_index_pathkeys())
> > which it will anyway do again during creation of index paths:
> > create_index_paths()->get_index_paths()->build_index_paths()->build_index_pathkeys()
>
> I felt the same thing. On stupid measure to reduce cycles would
> be caching created pathkeys in IndexOptInfo. I'll try in the next
> patch.
> At Mon, 14 Jul 2014 11:01:52 +0530, Amit Kapila <amit.kapila16@gmail.com> wrote in <CAA4eK1+6b6Wjwf51oZMrL+mKFH8xUp9J-pEhQvoR8SE7sWyTWw@mail.gmail.com>
> > On Fri, Jun 13, 2014 at 1:11 PM, Kyotaro HORIGUCHI <
> > horiguchi.kyotaro@lab.ntt.co.jp> wrote:
> > I am bit worried about the extra cycles added by this patch as compare
> > to your previous patch; example
> > During trimming of paths, it will build index paths (build_index_pathkeys())
> > which it will anyway do again during creation of index paths:
> > create_index_paths()->get_index_paths()->build_index_paths()->build_index_pathkeys()
>
> I felt the same thing. On stupid measure to reduce cycles would
> be caching created pathkeys in IndexOptInfo. I'll try in the next
> patch.
I suggest to wait for overall review of patch before trying this out,
we can try to see what is the best way to avoid this if required, once
other part of patch is reviewed and proved to be problem free.
Other than this I agree with the other points you mentioned in mail
Other than this I agree with the other points you mentioned in mail
and may be you can just handle those in next version of your patch.
Hi, the attached is the revised version.
- defined allnotnull instead of full_ordered in RelOptInfo and changed to use it.
- compare_pathkeys_ignoring_strategy() is now integrated into compare_pathkeys().
- index pathkeys caching in RelOptInfo added. (build_index_pathkeys() does)
- Refactoring collect_common_primary_pathkeys mainly from a reason of eliminating code duplicates and readability.
- trim_query_pathkeys now tries to trim window_pathkeys. The old comment came from my misunderstanding. Window
pathkeysare not always RowExpr and RowExpr pathkeys are feedable from not only PARTITION BY clause but also ORDER BY,
DISTINCTor GROUP BY clauses. The comment for the function is modified.
- Some cosmetic fixes including spacing after commas.
- The shortcut judgement is *not* included.
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 9573a9b..546e112 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1789,9 +1789,11 @@ _outIndexOptInfo(StringInfo str, const IndexOptInfo *node) /* indexprs is redundant since we
printindextlist */ WRITE_NODE_FIELD(indpred); WRITE_NODE_FIELD(indextlist);
+ /* cached pathkeys are omitted as indexkeys */ WRITE_BOOL_FIELD(predOK); WRITE_BOOL_FIELD(unique);
WRITE_BOOL_FIELD(immediate);
+ WRITE_BOOL_FIELD(allnotnull); WRITE_BOOL_FIELD(hypothetical); /* we don't bother with fields copied from the
pg_amentry */}
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index c81efe9..751eb6a 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -58,6 +58,7 @@ int geqo_threshold;join_search_hook_type join_search_hook = NULL;
+static List *collect_common_primary_pathkeys(PlannerInfo *root);static void set_base_rel_sizes(PlannerInfo
*root);staticvoid set_base_rel_pathlists(PlannerInfo *root);static void set_rel_size(PlannerInfo *root, RelOptInfo
*rel,
@@ -66,6 +67,7 @@ static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti,
RangeTblEntry*rte);static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry
*rte);
+static void trim_query_pathkeys(PlannerInfo * root);static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo
*rel, RangeTblEntry *rte);static void set_foreign_size(PlannerInfo *root, RelOptInfo *rel,
@@ -112,6 +114,203 @@ static void recurse_push_qual(Node *setOp, Query *topquery, RangeTblEntry *rte,
Indexrti, Node *qual);static void remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel);
+/*
+ * collect_common_primary_pathkeys: Collects common unique and non-null index
+ * pathkeys from all base relations in current root.
+ */
+static List *
+collect_common_primary_pathkeys(PlannerInfo *root)
+{
+ List *result = NIL;
+ Index rti;
+ int nindex = 0;
+ List **pathkeys_array0 = NULL;
+ List **pathkeys_array = NULL;
+ List **pathkeys_array2 = NULL;
+ bool do_conjunction = (root->simple_rel_array_size > 2);
+
+ for (rti = 1 ; rti < root->simple_rel_array_size ; rti++)
+ {
+ RelOptInfo *rel = root->simple_rel_array[rti];
+ int prev_nindex = 0;
+ ListCell *lc;
+
+ if (rel == NULL)
+ continue;
+
+ Assert (rel->relid == rti);
+
+ /* Scan all base relations except parent relations. */
+ if (root->simple_rte_array[rti]->inh ||
+ (rel->reloptkind != RELOPT_BASEREL &&
+ rel->reloptkind != RELOPT_OTHER_MEMBER_REL))
+ continue;
+
+ if (do_conjunction)
+ {
+ if (pathkeys_array2)
+ memset(&pathkeys_array2, 0, sizeof(List*) * nindex);
+ else
+ {
+ /* Rig for AND (conjunction) operation. */
+ nindex = 0;
+
+ foreach (lc, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+
+ if (index->allnotnull &&
+ index->unique && index->immediate &&
+ index->indpred == NIL)
+ nindex++;
+ }
+
+ if (nindex == 0)
+ return NULL; /* No common primary pathkeys exists.*/
+
+ pathkeys_array0 = palloc0(sizeof(List*) * nindex * 2);
+ pathkeys_array = pathkeys_array0;
+ pathkeys_array2 = pathkeys_array0 + nindex;
+ }
+ }
+
+ prev_nindex = nindex;
+ nindex = 0;
+
+ foreach (lc, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+ List *idx_pathkeys;
+
+ /* Only indexes that can unique sort are needed. */
+ if (!index->allnotnull ||
+ !(index->unique && index->immediate) ||
+ index->indpred != NIL)
+ continue;
+
+ idx_pathkeys = build_index_pathkeys(root, index,
+ ForwardScanDirection);
+ if (!idx_pathkeys)
+ continue;
+
+ if (!do_conjunction)
+ {
+ result = lappend(result, idx_pathkeys);
+ nindex++;
+ }
+ else
+ {
+ /*
+ * AND operation: drop pathkeys which don't see identical
+ * one in this relation.
+ */
+ int i;
+
+ for (i = 0 ; i < prev_nindex ; i++)
+ {
+ if (compare_pathkeys(pathkeys_array[i],
+ idx_pathkeys,
+ false) == PATHKEYS_EQUAL)
+ break;
+ }
+ if (prev_nindex < 1 || i < prev_nindex)
+ pathkeys_array2[nindex++] = idx_pathkeys;
+ }
+ }
+
+ if (nindex == 0)
+ {
+ /* No common primary pathkeys remained, exit. */
+ if (pathkeys_array0)
+ pfree(pathkeys_array0);
+ return NULL;
+ }
+
+ if (do_conjunction)
+ {
+ List **pktmp;
+
+ /* swap two pathkeys arrays for the next iteration */
+ pktmp = pathkeys_array2;
+ pathkeys_array2 = pathkeys_array;
+ pathkeys_array = pktmp;
+ }
+ }
+
+ if (do_conjunction)
+ {
+ int i;
+
+ for (i = 0 ; i < nindex ; i++)
+ {
+ if (pathkeys_array[i])
+ result = lappend(result, pathkeys_array[i]);
+ }
+ pfree(pathkeys_array0);
+ }
+
+ return result;
+}
+
+/*
+ * trim_query_pathkeys: trim pathkeys following common primary pathkeys.
+ *
+ * Primary pathkeys are pathkeys which perfectly sorts tuples in its owner
+ * table so the query pathkeys can be replaced with the primary pathkeys when
+ * the latter prefixes the former. Common primary pathkeys are the primary
+ * pathkeys shared among all base relations accessed in current root.
+ *
+ * This function doesn't trim RowExpr pathkeys.
+ */
+static void
+trim_query_pathkeys(PlannerInfo * root)
+{
+ ListCell *lc;
+
+ foreach(lc, collect_common_primary_pathkeys(root))
+ {
+ List *pk_guide = (List*) lfirst(lc);
+
+ if (root->sort_pathkeys)
+ {
+ /* sort_pathkeys is not allowd to flip sorting directions
+ * differently from other pathkeys. So try to trim sort_pathkeys
+ * first preserving per-key directions, then try to trim other
+ * pathkeys using the trimmed sort_pathkeys as the guide.
+ */
+
+ root->sort_pathkeys =
+ shorten_pathkeys_following(root, root->sort_pathkeys, pk_guide,
+ false);
+
+ /*
+ * Replace guide pathkeys with new sort_pathkeys if they differs
+ * from each other only by sorting directions.
+ */
+ if (compare_pathkeys(root->sort_pathkeys,
+ pk_guide, false) != PATHKEYS_EQUAL &&
+ compare_pathkeys(root->sort_pathkeys,
+ pk_guide, true) == PATHKEYS_EQUAL)
+ pk_guide = root->sort_pathkeys;
+ }
+
+ root->group_pathkeys =
+ shorten_pathkeys_following(root, root->group_pathkeys, pk_guide,
+ true);
+
+ root->window_pathkeys =
+ shorten_pathkeys_following(root, root->window_pathkeys, pk_guide,
+ true);
+
+ root->distinct_pathkeys =
+ shorten_pathkeys_following(root, root->distinct_pathkeys, pk_guide,
+ true);
+
+ root->query_pathkeys =
+ shorten_pathkeys_following(root, root->query_pathkeys, pk_guide,
+ true);
+ }
+}/* * make_one_rel
@@ -149,6 +348,7 @@ make_one_rel(PlannerInfo *root, List *joinlist) * Generate access paths for the base rels.
*/ set_base_rel_sizes(root);
+ trim_query_pathkeys(root); set_base_rel_pathlists(root); /*
@@ -755,7 +955,7 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, List
*existing_pathkeys= (List *) lfirst(lpk); if (compare_pathkeys(existing_pathkeys,
- childkeys) == PATHKEYS_EQUAL)
+ childkeys, false) == PATHKEYS_EQUAL) {
found = true; break;
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 5d953df..6cc9754 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -275,10 +275,13 @@ make_pathkey_from_sortop(PlannerInfo *root, * one is "better" than the other. * * We
assumethe pathkeys are canonical, and so they can be checked for
- * equality by simple pointer comparison.
+ * equality by simple pointer comparison when ignore_strategy is false.
+ *
+ * If ignore_strategy is true, the two pathkeys with no difference other
+ * than strategy are regarded as the same. */PathKeysComparison
-compare_pathkeys(List *keys1, List *keys2)
+compare_pathkeys(List *keys1, List *keys2, bool ignore_strategy){ ListCell *key1, *key2;
@@ -296,7 +299,23 @@ compare_pathkeys(List *keys1, List *keys2) PathKey *pathkey1 = (PathKey *) lfirst(key1);
PathKey *pathkey2 = (PathKey *) lfirst(key2);
- if (pathkey1 != pathkey2)
+ if (pathkey1 == pathkey2)
+ continue;
+
+ if (!ignore_strategy)
+ return PATHKEYS_DIFFERENT; /* no need to keep looking */
+
+ Assert(pathkey1->pk_strategy == BTGreaterStrategyNumber ||
+ pathkey1->pk_strategy == BTLessStrategyNumber);
+ Assert(pathkey2->pk_strategy == BTGreaterStrategyNumber ||
+ pathkey2->pk_strategy == BTLessStrategyNumber);
+
+ if (pathkey1->pk_eclass != pathkey2->pk_eclass ||
+ pathkey1->pk_opfamily != pathkey2->pk_opfamily ||
+ !((pathkey1->pk_strategy == pathkey2->pk_strategy &&
+ pathkey1->pk_nulls_first == pathkey2->pk_nulls_first) ||
+ (pathkey1->pk_strategy != pathkey2->pk_strategy &&
+ pathkey1->pk_nulls_first != pathkey2->pk_nulls_first))) return PATHKEYS_DIFFERENT; /* no
needto keep looking */ }
@@ -319,7 +338,7 @@ compare_pathkeys(List *keys1, List *keys2)boolpathkeys_contained_in(List *keys1, List *keys2){
- switch (compare_pathkeys(keys1, keys2))
+ switch (compare_pathkeys(keys1, keys2, false)) { case PATHKEYS_EQUAL: case PATHKEYS_BETTER2:
@@ -440,10 +459,15 @@ build_index_pathkeys(PlannerInfo *root, List *retval = NIL; ListCell *lc; int
i;
+ List *cached_pathkeys = (ScanDirectionIsBackward(scandir) ?
+ index->indbwpathkeys : index->indfwpathkeys); if (index->sortopfamily == NULL)
return NIL; /* non-orderable index */
+ if (cached_pathkeys)
+ return cached_pathkeys; /* Return cached pathkeys if any */
+ i = 0; foreach(lc, index->indextlist) {
@@ -498,6 +522,12 @@ build_index_pathkeys(PlannerInfo *root, i++; }
+ /* Store created pathkeys for future use */
+ if (ScanDirectionIsBackward(scandir))
+ index->indbwpathkeys = retval;
+ else
+ index->indfwpathkeys = retval;
+ return retval;}
@@ -1525,3 +1555,87 @@ has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel) return true; /* might
beable to use them for ordering */ return false; /* definitely useless */}
+
+/*
+ * shorten_pathkeys_following: returns pk_guide if it prefixes pk_target
+ * regardless of the ordering directions of the pathkeys.
+ * allow_partial_flip allows ordering directions to be partially different
+ * between pk_target and pk_guide.
+ */
+List *
+shorten_pathkeys_following(PlannerInfo *root, List *pk_target, List *pk_guide,
+ bool allow_partial_flip)
+{
+ ListCell *tlc, *glc;
+ int same = 0, reverse = 0;
+ List *result;
+
+ if (pk_target == NIL)
+ return NIL;
+
+ if (list_length(pk_target) < list_length(pk_guide))
+ return pk_target;
+
+ forboth(tlc, pk_target, glc, pk_guide)
+ {
+ PathKey *tpk = (PathKey *) lfirst(tlc);
+ PathKey *gpk = (PathKey *) lfirst(glc);
+
+ if (tpk == gpk)
+ {
+ same++;
+ continue;
+ }
+
+ Assert(tpk->pk_strategy == BTGreaterStrategyNumber ||
+ tpk->pk_strategy == BTLessStrategyNumber);
+ Assert(gpk->pk_strategy == BTGreaterStrategyNumber ||
+ gpk->pk_strategy == BTLessStrategyNumber);
+
+ if (tpk->pk_eclass == gpk->pk_eclass &&
+ tpk->pk_opfamily == gpk->pk_opfamily &&
+ tpk->pk_strategy != gpk->pk_strategy &&
+ tpk->pk_nulls_first != gpk->pk_nulls_first)
+ {
+ reverse++;
+ continue;
+ }
+
+ return pk_target;
+ }
+
+ /* trailing members in pk_target don't matter */
+
+ /* reverse == 0 means that pk_guide exactly prefixes pk_target */
+ if (allow_partial_flip || reverse == 0)
+ return pk_guide;
+
+ /*
+ * Don't replace pathkeys if partial flip is not allowed but partially
+ * flipped.
+ */
+ Assert(reverse > 0);
+ if (same > 0)
+ return pk_target;
+
+ /* make then reutrn the reverse pathkeys of pk_guide */
+ result = NIL;
+ foreach (glc, pk_guide)
+ {
+ PathKey *gpk = (PathKey *) lfirst(glc);
+ PathKey *pk;
+ EquivalenceClass *ec = gpk->pk_eclass;
+ int revstr;
+
+ if (gpk->pk_strategy == BTGreaterStrategyNumber)
+ revstr = BTLessStrategyNumber;
+ else
+ revstr = BTGreaterStrategyNumber;
+
+ pk = make_canonical_pathkey(root, ec, gpk->pk_opfamily, revstr,
+ !gpk->pk_nulls_first);
+
+ result = lappend(result, pk);
+ }
+ return result;
+}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index d129f8d..9433a40 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -312,14 +312,14 @@ set_cheapest(RelOptInfo *parent_rel) if (cmp > 0 || (cmp == 0 &&
compare_pathkeys(cheapest_startup_path->pathkeys,
- path->pathkeys) == PATHKEYS_BETTER2))
+ path->pathkeys, false) == PATHKEYS_BETTER2)) cheapest_startup_path =
path; cmp = compare_path_costs(cheapest_total_path, path, TOTAL_COST); if (cmp > 0 ||
(cmp == 0 && compare_pathkeys(cheapest_total_path->pathkeys,
- path->pathkeys) == PATHKEYS_BETTER2))
+ path->pathkeys, false) == PATHKEYS_BETTER2)) cheapest_total_path =
path; } }
@@ -455,7 +455,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) old_path_pathkeys =
old_path->param_info? NIL : old_path->pathkeys; keyscmp = compare_pathkeys(new_path_pathkeys,
- old_path_pathkeys);
+ old_path_pathkeys, false); if (keyscmp != PATHKEYS_DIFFERENT)
{ switch (costcmp)
@@ -653,7 +653,7 @@ add_path_precheck(RelOptInfo *parent_rel, old_path_pathkeys = old_path->param_info ?
NIL: old_path->pathkeys; keyscmp = compare_pathkeys(new_path_pathkeys,
- old_path_pathkeys);
+ old_path_pathkeys, false); if (keyscmp == PATHKEYS_EQUAL ||
keyscmp == PATHKEYS_BETTER2) {
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index b2becfa..1cebd2b 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -241,12 +241,28 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->reverse_sort= (bool *) palloc(sizeof(bool) * ncolumns); info->nulls_first = (bool *)
palloc(sizeof(bool)* ncolumns);
+ info->allnotnull = true; for (i = 0; i < ncolumns; i++) {
int16 opt = indexRelation->rd_indoption[i];
+ int16 attno = info->indexkeys[i]; info->reverse_sort[i] = (opt &
INDOPTION_DESC)!= 0; info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
+
+ if (!info->allnotnull) continue;
+
+ /* Check if there's no nullable key column */
+ if (attno > 0)
+ {
+ if (!relation->rd_att->attrs[attno - 1]->attnotnull)
+ info->allnotnull = false;
+ }
+ else if (attno != ObjectIdAttributeNumber)
+ {
+ /* OID is apparently not-null */
+ info->allnotnull = false;
+ } } } else if (indexRelation->rd_am->amcanorder)
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index dacbe9c..4855667 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -524,10 +524,13 @@ typedef struct IndexOptInfo List *indpred; /* predicate if a partial index, else
NIL*/ List *indextlist; /* targetlist representing index columns */
+ List *indfwpathkeys; /* index pathkeys for forward scan */
+ List *indbwpathkeys; /* index pathkeys for backwad scan */ bool predOK; /* true if
predicatematches query */ bool unique; /* true if a unique index */ bool immediate;
/* is uniqueness enforced immediately? */
+ bool allnotnull; /* all columns are "NOT NULL" ? */ bool hypothetical; /* true if index
doesn'treally exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9b22fda..f637fc3 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -146,7 +146,10 @@ typedef enum PATHKEYS_DIFFERENT /* neither pathkey includes the other */}
PathKeysComparison;
-extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
+extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2,
+ bool ignore_strategy);
+extern PathKeysComparison compare_pathkeys_ignoring_strategy(List *keys1,
+ List *keys2);extern bool pathkeys_contained_in(List
*keys1,List *keys2);extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
Relids required_outer,
@@ -187,5 +190,8 @@ extern List *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
List *pathkeys);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
+extern List *shorten_pathkeys_following(PlannerInfo *root,
+ List *pk_target, List *pk_guide,
+ bool allow_partial_flip);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
On Tue, Jul 15, 2014 at 2:17 PM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
>
> Hi, the attached is the revised version.
Thanks Horiguchi-San for the updated patch.
Today while looking into updated patch, I was wondering why can't
{
..
if (rte->inh)
{
ListCell *l;
foreach(l, root->append_rel_list)
{
AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
/* append_rel_list contains all append rels; ignore others */
if (appinfo->parent_relid != relid)
continue;
(void) build_simple_rel(root, appinfo->child_relid,
RELOPT_OTHER_MEMBER_REL);
}
}
}
Could you please explain me why the index information built in above
>
> Hi, the attached is the revised version.
Thanks Horiguchi-San for the updated patch.
Today while looking into updated patch, I was wondering why can't
we eliminate useless keys in query_pathkeys when we actually build
the same in function standard_qp_callback(), basically somewhat
similar to what we do in
standard_qp_callback->make_pathkeys_for_sortclauses->pathkey_is_redundant().
We already have index information related to base_rels before building
query pathkeys. I noticed that you mentioned the below in your original
mail which indicates that information related to inheritance tables is built
only after set_base_rel_sizes()
"These steps take place between set_base_rel_sizes() and
set_base_rel_pathlists() in make_one_rel(). The reason for the
position is that the step 2 above needs all inheritence tables to
be extended in PlannerInfo and set_base_rel_sizes (currently)
does that".
position is that the step 2 above needs all inheritence tables to
be extended in PlannerInfo and set_base_rel_sizes (currently)
does that".
Now I am not sure why such information is not build during
build_simple_rel() in below code path:
build_simple_rel(){
..
if (rte->inh)
{
ListCell *l;
foreach(l, root->append_rel_list)
{
AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
/* append_rel_list contains all append rels; ignore others */
if (appinfo->parent_relid != relid)
continue;
(void) build_simple_rel(root, appinfo->child_relid,
RELOPT_OTHER_MEMBER_REL);
}
}
}
path is not sufficient or is there any other case which I am missing?
With Regards,
With Regards,
Sorry , previous version has bugs. It stamps over the stack and
crashesX( The attached is the bug fixed version, with no
substantial changes.
> On Tue, Jul 15, 2014 at 2:17 PM, Kyotaro HORIGUCHI <
> horiguchi.kyotaro@lab.ntt.co.jp> wrote:
> >
> > Hi, the attached is the revised version.
>
> Thanks Horiguchi-San for the updated patch.
# By the way, this style of calling a person is quite common
# among Japanese since the first-name basis implies very close
# relationship or it frequently conveys offensive shade. But I'm
# not sure what should I call others who're not Japases native.
Anyway,
> Today while looking into updated patch, I was wondering why can't
> we eliminate useless keys in query_pathkeys when we actually build
> the same in function standard_qp_callback(), basically somewhat
> similar to what we do in
> standard_qp_callback->make_pathkeys_for_sortclauses->pathkey_is_redundant().
I agree that standard_qp_callback is basically more preferable.
> We already have index information related to base_rels before building
> query pathkeys. I noticed that you mentioned the below in your original
> mail which indicates that information related to inheritance tables is built
> only after set_base_rel_sizes()
>
> "These steps take place between set_base_rel_sizes() and
> set_base_rel_pathlists() in make_one_rel(). The reason for the
> position is that the step 2 above needs all inheritence tables to
> be extended in PlannerInfo and set_base_rel_sizes (currently)
> does that".
Sorry, my memory had been worn down. After some reconfirmation,
this description found to be a bit (quite?) wrong.
collect_common_primary_pathkeys needs root->eq_classes to be set
up beforehand, not appendrels. Bacause build_index_pathkeys
doesn't work before every EC member for all relation involved is
already registered.
standard_qp_callback registers EC members in the following path
but only for the primary(?) tlist of the subquery, so EC members
for the child relations are not registered at the time.
.->make_pathekeys_sortclauses->make_pathkey_from_sortop ->make_pathkey_from_sortinfo->get_eclass_for_sort_expr
EC members for the child rels are registered in
set_base_rel_sizes->set_rel_size->set_append_rel_size ->add_child_rel_equivalences
So trim_query_pathkeys (collect_common...) doesn't work before
set_base_rel_sizes(). These EC members needed to be registered at
least if root->query_pathkeys exists so this seems to be done in
standard_qp_callback adding a separate inheritance tree walk.
# rel->has_elcass_joins seems not working but it is not the topic
# here.
> Could you please explain me why the index information built in above
> path is not sufficient or is there any other case which I am missing?
Is the description above enough to be the explaination for the
place? Sorry for the inaccurate description.
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 9573a9b..546e112 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -1789,9 +1789,11 @@ _outIndexOptInfo(StringInfo str, const IndexOptInfo *node) /* indexprs is redundant since we
printindextlist */ WRITE_NODE_FIELD(indpred); WRITE_NODE_FIELD(indextlist);
+ /* cached pathkeys are omitted as indexkeys */ WRITE_BOOL_FIELD(predOK); WRITE_BOOL_FIELD(unique);
WRITE_BOOL_FIELD(immediate);
+ WRITE_BOOL_FIELD(allnotnull); WRITE_BOOL_FIELD(hypothetical); /* we don't bother with fields copied from the
pg_amentry */}
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index c81efe9..c12d0e7 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -58,6 +58,7 @@ int geqo_threshold;join_search_hook_type join_search_hook = NULL;
+static List *collect_common_primary_pathkeys(PlannerInfo *root);static void set_base_rel_sizes(PlannerInfo
*root);staticvoid set_base_rel_pathlists(PlannerInfo *root);static void set_rel_size(PlannerInfo *root, RelOptInfo
*rel,
@@ -66,6 +67,7 @@ static void set_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, Index rti,
RangeTblEntry*rte);static void set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry
*rte);
+static void trim_query_pathkeys(PlannerInfo * root);static void set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo
*rel, RangeTblEntry *rte);static void set_foreign_size(PlannerInfo *root, RelOptInfo *rel,
@@ -112,6 +114,203 @@ static void recurse_push_qual(Node *setOp, Query *topquery, RangeTblEntry *rte,
Indexrti, Node *qual);static void remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel);
+/*
+ * collect_common_primary_pathkeys: Collects common unique and non-null index
+ * pathkeys from all base relations in current root.
+ */
+static List *
+collect_common_primary_pathkeys(PlannerInfo *root)
+{
+ List *result = NIL;
+ Index rti;
+ int nindex = 0;
+ List **pathkeys_array0 = NULL;
+ List **pathkeys_array = NULL;
+ List **pathkeys_array2 = NULL;
+ bool do_conjunction = (root->simple_rel_array_size > 2);
+
+ for (rti = 1 ; rti < root->simple_rel_array_size ; rti++)
+ {
+ RelOptInfo *rel = root->simple_rel_array[rti];
+ int prev_nindex = 0;
+ ListCell *lc;
+
+ if (rel == NULL)
+ continue;
+
+ Assert (rel->relid == rti);
+
+ prev_nindex = nindex;
+ nindex = 0;
+
+ /* Scan all base relations except parent relations. */
+ if (root->simple_rte_array[rti]->inh ||
+ (rel->reloptkind != RELOPT_BASEREL &&
+ rel->reloptkind != RELOPT_OTHER_MEMBER_REL))
+ continue;
+
+ if (do_conjunction)
+ {
+ if (pathkeys_array2)
+ memset(pathkeys_array2, 0, sizeof(List*) * nindex);
+ else
+ {
+ /* Rig for AND (conjunction) operation. */
+ int nindex_tmp = 0;
+
+ foreach (lc, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+
+ if (index->allnotnull &&
+ index->unique && index->immediate &&
+ index->indpred == NIL)
+ nindex_tmp++;
+ }
+
+ if (nindex_tmp == 0)
+ return NULL; /* No common primary pathkeys exists.*/
+
+ pathkeys_array0 = palloc0(sizeof(List*) * nindex_tmp * 2);
+ pathkeys_array = pathkeys_array0;
+ pathkeys_array2 = pathkeys_array0 + nindex_tmp;
+ }
+ }
+
+ foreach (lc, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
+ List *idx_pathkeys;
+
+ /* Only indexes that can unique sort are needed. */
+ if (!index->allnotnull ||
+ !(index->unique && index->immediate) ||
+ index->indpred != NIL)
+ continue;
+
+ idx_pathkeys = build_index_pathkeys(root, index,
+ ForwardScanDirection);
+ if (!idx_pathkeys)
+ continue;
+
+ if (!do_conjunction)
+ {
+ result = lappend(result, idx_pathkeys);
+ nindex++;
+ }
+ else
+ {
+ /*
+ * AND operation: drop pathkeys which don't see identical
+ * one in this relation.
+ */
+ int i;
+
+ for (i = 0 ; i < prev_nindex ; i++)
+ {
+ if (compare_pathkeys(pathkeys_array[i],
+ idx_pathkeys,
+ false) == PATHKEYS_EQUAL)
+ break;
+ }
+ if (prev_nindex < 1 || i < prev_nindex)
+ pathkeys_array2[nindex++] = idx_pathkeys;
+ }
+ }
+
+ if (nindex == 0)
+ {
+ /* No common primary pathkeys remained, exit. */
+ if (pathkeys_array0)
+ pfree(pathkeys_array0);
+ return NULL;
+ }
+
+ if (do_conjunction)
+ {
+ List **pktmp;
+
+ /* swap two pathkeys arrays for the next iteration */
+ pktmp = pathkeys_array2;
+ pathkeys_array2 = pathkeys_array;
+ pathkeys_array = pktmp;
+ }
+ }
+
+ if (do_conjunction)
+ {
+ int i;
+
+ for (i = 0 ; i < nindex ; i++)
+ {
+ if (pathkeys_array[i])
+ result = lappend(result, pathkeys_array[i]);
+ }
+ pfree(pathkeys_array0);
+ }
+
+ return result;
+}
+
+/*
+ * trim_query_pathkeys: trim pathkeys following common primary pathkeys.
+ *
+ * Primary pathkeys are pathkeys which perfectly sorts tuples in its owner
+ * table so the query pathkeys can be replaced with the primary pathkeys when
+ * the latter prefixes the former. Common primary pathkeys are the primary
+ * pathkeys shared among all base relations accessed in current root.
+ *
+ * This function doesn't trim RowExpr pathkeys.
+ */
+static void
+trim_query_pathkeys(PlannerInfo * root)
+{
+ ListCell *lc;
+
+ foreach(lc, collect_common_primary_pathkeys(root))
+ {
+ List *pk_guide = (List*) lfirst(lc);
+
+ if (root->sort_pathkeys)
+ {
+ /* sort_pathkeys is not allowd to flip sorting directions
+ * differently from other pathkeys. So try to trim sort_pathkeys
+ * first preserving per-key directions, then try to trim other
+ * pathkeys using the trimmed sort_pathkeys as the guide.
+ */
+
+ root->sort_pathkeys =
+ shorten_pathkeys_following(root, root->sort_pathkeys, pk_guide,
+ false);
+
+ /*
+ * Replace guide pathkeys with new sort_pathkeys if they differs
+ * from each other only by sorting directions.
+ */
+ if (compare_pathkeys(root->sort_pathkeys,
+ pk_guide, false) != PATHKEYS_EQUAL &&
+ compare_pathkeys(root->sort_pathkeys,
+ pk_guide, true) == PATHKEYS_EQUAL)
+ pk_guide = root->sort_pathkeys;
+ }
+
+ root->group_pathkeys =
+ shorten_pathkeys_following(root, root->group_pathkeys, pk_guide,
+ true);
+
+ root->window_pathkeys =
+ shorten_pathkeys_following(root, root->window_pathkeys, pk_guide,
+ true);
+
+ root->distinct_pathkeys =
+ shorten_pathkeys_following(root, root->distinct_pathkeys, pk_guide,
+ true);
+
+ root->query_pathkeys =
+ shorten_pathkeys_following(root, root->query_pathkeys, pk_guide,
+ true);
+ }
+}/* * make_one_rel
@@ -149,6 +348,7 @@ make_one_rel(PlannerInfo *root, List *joinlist) * Generate access paths for the base rels.
*/ set_base_rel_sizes(root);
+ trim_query_pathkeys(root); set_base_rel_pathlists(root); /*
@@ -755,7 +955,7 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, List
*existing_pathkeys= (List *) lfirst(lpk); if (compare_pathkeys(existing_pathkeys,
- childkeys) == PATHKEYS_EQUAL)
+ childkeys, false) == PATHKEYS_EQUAL) {
found = true; break;
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 5d953df..6cc9754 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -275,10 +275,13 @@ make_pathkey_from_sortop(PlannerInfo *root, * one is "better" than the other. * * We
assumethe pathkeys are canonical, and so they can be checked for
- * equality by simple pointer comparison.
+ * equality by simple pointer comparison when ignore_strategy is false.
+ *
+ * If ignore_strategy is true, the two pathkeys with no difference other
+ * than strategy are regarded as the same. */PathKeysComparison
-compare_pathkeys(List *keys1, List *keys2)
+compare_pathkeys(List *keys1, List *keys2, bool ignore_strategy){ ListCell *key1, *key2;
@@ -296,7 +299,23 @@ compare_pathkeys(List *keys1, List *keys2) PathKey *pathkey1 = (PathKey *) lfirst(key1);
PathKey *pathkey2 = (PathKey *) lfirst(key2);
- if (pathkey1 != pathkey2)
+ if (pathkey1 == pathkey2)
+ continue;
+
+ if (!ignore_strategy)
+ return PATHKEYS_DIFFERENT; /* no need to keep looking */
+
+ Assert(pathkey1->pk_strategy == BTGreaterStrategyNumber ||
+ pathkey1->pk_strategy == BTLessStrategyNumber);
+ Assert(pathkey2->pk_strategy == BTGreaterStrategyNumber ||
+ pathkey2->pk_strategy == BTLessStrategyNumber);
+
+ if (pathkey1->pk_eclass != pathkey2->pk_eclass ||
+ pathkey1->pk_opfamily != pathkey2->pk_opfamily ||
+ !((pathkey1->pk_strategy == pathkey2->pk_strategy &&
+ pathkey1->pk_nulls_first == pathkey2->pk_nulls_first) ||
+ (pathkey1->pk_strategy != pathkey2->pk_strategy &&
+ pathkey1->pk_nulls_first != pathkey2->pk_nulls_first))) return PATHKEYS_DIFFERENT; /* no
needto keep looking */ }
@@ -319,7 +338,7 @@ compare_pathkeys(List *keys1, List *keys2)boolpathkeys_contained_in(List *keys1, List *keys2){
- switch (compare_pathkeys(keys1, keys2))
+ switch (compare_pathkeys(keys1, keys2, false)) { case PATHKEYS_EQUAL: case PATHKEYS_BETTER2:
@@ -440,10 +459,15 @@ build_index_pathkeys(PlannerInfo *root, List *retval = NIL; ListCell *lc; int
i;
+ List *cached_pathkeys = (ScanDirectionIsBackward(scandir) ?
+ index->indbwpathkeys : index->indfwpathkeys); if (index->sortopfamily == NULL)
return NIL; /* non-orderable index */
+ if (cached_pathkeys)
+ return cached_pathkeys; /* Return cached pathkeys if any */
+ i = 0; foreach(lc, index->indextlist) {
@@ -498,6 +522,12 @@ build_index_pathkeys(PlannerInfo *root, i++; }
+ /* Store created pathkeys for future use */
+ if (ScanDirectionIsBackward(scandir))
+ index->indbwpathkeys = retval;
+ else
+ index->indfwpathkeys = retval;
+ return retval;}
@@ -1525,3 +1555,87 @@ has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel) return true; /* might
beable to use them for ordering */ return false; /* definitely useless */}
+
+/*
+ * shorten_pathkeys_following: returns pk_guide if it prefixes pk_target
+ * regardless of the ordering directions of the pathkeys.
+ * allow_partial_flip allows ordering directions to be partially different
+ * between pk_target and pk_guide.
+ */
+List *
+shorten_pathkeys_following(PlannerInfo *root, List *pk_target, List *pk_guide,
+ bool allow_partial_flip)
+{
+ ListCell *tlc, *glc;
+ int same = 0, reverse = 0;
+ List *result;
+
+ if (pk_target == NIL)
+ return NIL;
+
+ if (list_length(pk_target) < list_length(pk_guide))
+ return pk_target;
+
+ forboth(tlc, pk_target, glc, pk_guide)
+ {
+ PathKey *tpk = (PathKey *) lfirst(tlc);
+ PathKey *gpk = (PathKey *) lfirst(glc);
+
+ if (tpk == gpk)
+ {
+ same++;
+ continue;
+ }
+
+ Assert(tpk->pk_strategy == BTGreaterStrategyNumber ||
+ tpk->pk_strategy == BTLessStrategyNumber);
+ Assert(gpk->pk_strategy == BTGreaterStrategyNumber ||
+ gpk->pk_strategy == BTLessStrategyNumber);
+
+ if (tpk->pk_eclass == gpk->pk_eclass &&
+ tpk->pk_opfamily == gpk->pk_opfamily &&
+ tpk->pk_strategy != gpk->pk_strategy &&
+ tpk->pk_nulls_first != gpk->pk_nulls_first)
+ {
+ reverse++;
+ continue;
+ }
+
+ return pk_target;
+ }
+
+ /* trailing members in pk_target don't matter */
+
+ /* reverse == 0 means that pk_guide exactly prefixes pk_target */
+ if (allow_partial_flip || reverse == 0)
+ return pk_guide;
+
+ /*
+ * Don't replace pathkeys if partial flip is not allowed but partially
+ * flipped.
+ */
+ Assert(reverse > 0);
+ if (same > 0)
+ return pk_target;
+
+ /* make then reutrn the reverse pathkeys of pk_guide */
+ result = NIL;
+ foreach (glc, pk_guide)
+ {
+ PathKey *gpk = (PathKey *) lfirst(glc);
+ PathKey *pk;
+ EquivalenceClass *ec = gpk->pk_eclass;
+ int revstr;
+
+ if (gpk->pk_strategy == BTGreaterStrategyNumber)
+ revstr = BTLessStrategyNumber;
+ else
+ revstr = BTGreaterStrategyNumber;
+
+ pk = make_canonical_pathkey(root, ec, gpk->pk_opfamily, revstr,
+ !gpk->pk_nulls_first);
+
+ result = lappend(result, pk);
+ }
+ return result;
+}
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index d129f8d..9433a40 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -312,14 +312,14 @@ set_cheapest(RelOptInfo *parent_rel) if (cmp > 0 || (cmp == 0 &&
compare_pathkeys(cheapest_startup_path->pathkeys,
- path->pathkeys) == PATHKEYS_BETTER2))
+ path->pathkeys, false) == PATHKEYS_BETTER2)) cheapest_startup_path =
path; cmp = compare_path_costs(cheapest_total_path, path, TOTAL_COST); if (cmp > 0 ||
(cmp == 0 && compare_pathkeys(cheapest_total_path->pathkeys,
- path->pathkeys) == PATHKEYS_BETTER2))
+ path->pathkeys, false) == PATHKEYS_BETTER2)) cheapest_total_path =
path; } }
@@ -455,7 +455,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) old_path_pathkeys =
old_path->param_info? NIL : old_path->pathkeys; keyscmp = compare_pathkeys(new_path_pathkeys,
- old_path_pathkeys);
+ old_path_pathkeys, false); if (keyscmp != PATHKEYS_DIFFERENT)
{ switch (costcmp)
@@ -653,7 +653,7 @@ add_path_precheck(RelOptInfo *parent_rel, old_path_pathkeys = old_path->param_info ?
NIL: old_path->pathkeys; keyscmp = compare_pathkeys(new_path_pathkeys,
- old_path_pathkeys);
+ old_path_pathkeys, false); if (keyscmp == PATHKEYS_EQUAL ||
keyscmp == PATHKEYS_BETTER2) {
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index b2becfa..1cebd2b 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -241,12 +241,28 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
info->reverse_sort= (bool *) palloc(sizeof(bool) * ncolumns); info->nulls_first = (bool *)
palloc(sizeof(bool)* ncolumns);
+ info->allnotnull = true; for (i = 0; i < ncolumns; i++) {
int16 opt = indexRelation->rd_indoption[i];
+ int16 attno = info->indexkeys[i]; info->reverse_sort[i] = (opt &
INDOPTION_DESC)!= 0; info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
+
+ if (!info->allnotnull) continue;
+
+ /* Check if there's no nullable key column */
+ if (attno > 0)
+ {
+ if (!relation->rd_att->attrs[attno - 1]->attnotnull)
+ info->allnotnull = false;
+ }
+ else if (attno != ObjectIdAttributeNumber)
+ {
+ /* OID is apparently not-null */
+ info->allnotnull = false;
+ } } } else if (indexRelation->rd_am->amcanorder)
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index dacbe9c..4855667 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -524,10 +524,13 @@ typedef struct IndexOptInfo List *indpred; /* predicate if a partial index, else
NIL*/ List *indextlist; /* targetlist representing index columns */
+ List *indfwpathkeys; /* index pathkeys for forward scan */
+ List *indbwpathkeys; /* index pathkeys for backwad scan */ bool predOK; /* true if
predicatematches query */ bool unique; /* true if a unique index */ bool immediate;
/* is uniqueness enforced immediately? */
+ bool allnotnull; /* all columns are "NOT NULL" ? */ bool hypothetical; /* true if index
doesn'treally exist */ bool canreturn; /* can index return IndexTuples? */ bool
amcanorderbyop;/* does AM support order by operator result? */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9b22fda..f637fc3 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -146,7 +146,10 @@ typedef enum PATHKEYS_DIFFERENT /* neither pathkey includes the other */}
PathKeysComparison;
-extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
+extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2,
+ bool ignore_strategy);
+extern PathKeysComparison compare_pathkeys_ignoring_strategy(List *keys1,
+ List *keys2);extern bool pathkeys_contained_in(List
*keys1,List *keys2);extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
Relids required_outer,
@@ -187,5 +190,8 @@ extern List *truncate_useless_pathkeys(PlannerInfo *root, RelOptInfo *rel,
List *pathkeys);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
+extern List *shorten_pathkeys_following(PlannerInfo *root,
+ List *pk_target, List *pk_guide,
+ bool allow_partial_flip);#endif /* PATHS_H */
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN
-Sort
- Sort Key: id, data
- -> Seq Scan on test_dc
- Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+ Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data
On Tue, Jul 22, 2014 at 5:19 AM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote: > # By the way, this style of calling a person is quite common > # among Japanese since the first-name basis implies very close > # relationship or it frequently conveys offensive shade. But I'm > # not sure what should I call others who're not Japases native. Typical usage on this mailing list is to refer to individuals by first name (e.g. Tom, Alvaro, Heikki) or by full name (e.g. Tom Lane, Alvaro Herrera, Heikki Linnakangas). The last name is typically included only when it might otherwise be confusing - for example, you will rarely see people use just "Greg" because there are several people by that name who are reasonably active, but Heikki's last name is almost never mentioned). That having been said, if you want to use the Japanese style, I don't think anyone here will mind. I am personally not totally familiar with it so please forgive me in turn if I should address you or anyone else in a manner that would be considered too familiar in another culture. I try not to do that, but I might make some mistakes. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company
On Tue, Jul 22, 2014 at 2:49 PM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
>
> Sorry , previous version has bugs. It stamps over the stack and
> crashesX( The attached is the bug fixed version, with no
> substantial changes.
>
> > On Tue, Jul 15, 2014 at 2:17 PM, Kyotaro HORIGUCHI <
> > horiguchi.kyotaro@lab.ntt.co.jp> wrote:
> > >
> > > Hi, the attached is the revised version.
> >
> > Thanks Horiguchi-San for the updated patch.
>
> # By the way, this style of calling a person is quite common
> # among Japanese since the first-name basis implies very close
> # relationship or it frequently conveys offensive shade.
>
> Sorry , previous version has bugs. It stamps over the stack and
> crashesX( The attached is the bug fixed version, with no
> substantial changes.
>
> > On Tue, Jul 15, 2014 at 2:17 PM, Kyotaro HORIGUCHI <
> > horiguchi.kyotaro@lab.ntt.co.jp> wrote:
> > >
> > > Hi, the attached is the revised version.
> >
> > Thanks Horiguchi-San for the updated patch.
>
> # By the way, this style of calling a person is quite common
> # among Japanese since the first-name basis implies very close
> # relationship or it frequently conveys offensive shade.
I don't know if I have ever offended you or any other Japanese
community member while interaction, but my intention was never
so. The reason for using this style for calling you is during my initial 4
years of work, I have worked very closely with Japanese, so I have
learned few things during that time and it was quite common to refer
the way I used above, however I am not sure I have always used
during communication, so if something I have used which is not common
in your culture, please feel free to let me know, I will surely not do that
again.
> > Today while looking into updated patch, I was wondering why can't
> > we eliminate useless keys in query_pathkeys when we actually build
> > the same in function standard_qp_callback(), basically somewhat
> > similar to what we do in
> > standard_qp_callback->make_pathkeys_for_sortclauses->pathkey_is_redundant().
>
> I agree that standard_qp_callback is basically more preferable.
>
> > We already have index information related to base_rels before building
> > query pathkeys. I noticed that you mentioned the below in your original
> > mail which indicates that information related to inheritance tables is built
> > only after set_base_rel_sizes()
> >
> > "These steps take place between set_base_rel_sizes() and
> > set_base_rel_pathlists() in make_one_rel(). The reason for the
> > position is that the step 2 above needs all inheritence tables to
> > be extended in PlannerInfo and set_base_rel_sizes (currently)
> > does that".
>
> Sorry, my memory had been worn down. After some reconfirmation,
> this description found to be a bit (quite?) wrong.
>
> collect_common_primary_pathkeys needs root->eq_classes to be set
> up beforehand, not appendrels. Bacause build_index_pathkeys
> doesn't work before every EC member for all relation involved is
> already registered.
>
> > we eliminate useless keys in query_pathkeys when we actually build
> > the same in function standard_qp_callback(), basically somewhat
> > similar to what we do in
> > standard_qp_callback->make_pathkeys_for_sortclauses->pathkey_is_redundant().
>
> I agree that standard_qp_callback is basically more preferable.
>
> > We already have index information related to base_rels before building
> > query pathkeys. I noticed that you mentioned the below in your original
> > mail which indicates that information related to inheritance tables is built
> > only after set_base_rel_sizes()
> >
> > "These steps take place between set_base_rel_sizes() and
> > set_base_rel_pathlists() in make_one_rel(). The reason for the
> > position is that the step 2 above needs all inheritence tables to
> > be extended in PlannerInfo and set_base_rel_sizes (currently)
> > does that".
>
> Sorry, my memory had been worn down. After some reconfirmation,
> this description found to be a bit (quite?) wrong.
>
> collect_common_primary_pathkeys needs root->eq_classes to be set
> up beforehand, not appendrels. Bacause build_index_pathkeys
> doesn't work before every EC member for all relation involved is
> already registered.
>
>
> standard_qp_callback registers EC members in the following path
> but only for the primary(?) tlist of the subquery, so EC members
> for the child relations are not registered at the time.
>
> .->make_pathekeys_sortclauses->make_pathkey_from_sortop
> ->make_pathkey_from_sortinfo->get_eclass_for_sort_expr
>
> EC members for the child rels are registered in
>
> set_base_rel_sizes->set_rel_size->set_append_rel_size
> ->add_child_rel_equivalences
>
> So trim_query_pathkeys (collect_common...) doesn't work before
> set_base_rel_sizes(). These EC members needed to be registered at
> least if root->query_pathkeys exists so this seems to be done in
> standard_qp_callback adding a separate inheritance tree walk.
Referring to above comment, I think we don't need it to eliminate
> standard_qp_callback registers EC members in the following path
> but only for the primary(?) tlist of the subquery, so EC members
> for the child relations are not registered at the time.
>
> .->make_pathekeys_sortclauses->make_pathkey_from_sortop
> ->make_pathkey_from_sortinfo->get_eclass_for_sort_expr
>
> EC members for the child rels are registered in
>
> set_base_rel_sizes->set_rel_size->set_append_rel_size
> ->add_child_rel_equivalences
>
> So trim_query_pathkeys (collect_common...) doesn't work before
> set_base_rel_sizes(). These EC members needed to be registered at
> least if root->query_pathkeys exists so this seems to be done in
> standard_qp_callback adding a separate inheritance tree walk.
Do we really need that information to eliminate useless keys from
query_pathkeys?
* We have to make child entries in the EquivalenceClass data
* structures as well. This is needed either if the parent
* participates in some eclass joins (because we will want to consider
* inner-indexscan joins on the individual children) or if the parent
* has useful pathkeys (because we should try to build MergeAppend
* paths that produce those sort orderings).
useless keys based on primary key info from query_pathkeys, but I
might be missing some case, could you please elaborate more to
let me know the case/cases where this would be useful.
I think there is one more disadvantage in the way current patch is
done which is that you need to collect index path keys for all relations
irrespective of whether they will be of any use to eliminate useless
pathkeys from query_pathkeys. One trivial case that comes to mind is
when there are multiple relations involved in query and ORDER BY is
base on columns of only part of the tables involved in query.
> # rel->has_elcass_joins seems not working but it is not the topic
> # here.
>
> > Could you please explain me why the index information built in above
> > path is not sufficient or is there any other case which I am missing?
>
> Is the description above enough to be the explaination for the
> place? Sorry for the inaccurate description.
> # here.
>
> > Could you please explain me why the index information built in above
> > path is not sufficient or is there any other case which I am missing?
>
> Is the description above enough to be the explaination for the
> place? Sorry for the inaccurate description.
No issues, above description is sufficient to explain why you have
written patch in its current form.
Hello. I've been cooled off and convinced that this patch has become quite useless by itself. It improves almost only UNIONs with ORDER BY on tables that have unioform primary keys, and needs my another patch to work. I'll try to reintegrate this patch into my 'another patch' as mentioned below and try next CF with it. I'll close this patch as 'Return with Feedback' by myself. Thank you for your thoughtful commnets. I learned a lot. ===== Thank you for the answers, Robert, Amit :) > > # By the way, this style of calling a person is quite common > > # among Japanese since the first-name basis implies very close > > # relationship or it frequently conveys offensive shade. > > I don't know if I have ever offended you or any other Japanese > community member while interaction, but my intention was never > so. The reason for using this style for calling you is during my initial 4 > years of work, I have worked very closely with Japanese, so I have > learned few things during that time and it was quite common to refer > the way I used above, however I am not sure I have always used > during communication, so if something I have used which is not common > in your culture, please feel free to let me know, I will surely not do that > again. I also don't mind at all and that's why I was anxious about it. Thank you for your answers. > > Sorry, my memory had been worn down. After some reconfirmation, > > this description found to be a bit (quite?) wrong. > > > > collect_common_primary_pathkeys needs root->eq_classes to be set > > up beforehand, not appendrels. Bacause build_index_pathkeys > > doesn't work before every EC member for all relation involved is > > already registered. > > > > > > standard_qp_callback registers EC members in the following path > > but only for the primary(?) tlist of the subquery, so EC members > > for the child relations are not registered at the time. > > > > .->make_pathekeys_sortclauses->make_pathkey_from_sortop > > ->make_pathkey_from_sortinfo->get_eclass_for_sort_expr > > > > EC members for the child rels are registered in > > > > set_base_rel_sizes->set_rel_size->set_append_rel_size > > ->add_child_rel_equivalences > > > > So trim_query_pathkeys (collect_common...) doesn't work before > > set_base_rel_sizes(). These EC members needed to be registered at > > least if root->query_pathkeys exists so this seems to be done in > > standard_qp_callback adding a separate inheritance tree walk. > > Do we really need that information to eliminate useless keys from > query_pathkeys? > > > * We have to make child entries in the EquivalenceClass data > * structures as well. This is needed either if the parent > * participates in some eclass joins (because we will want to consider > * inner-indexscan joins on the individual children) or if the parent > * has useful pathkeys (because we should try to build MergeAppend > * paths that produce those sort orderings). > > Referring to above comment, I think we don't need it to eliminate > useless keys based on primary key info from query_pathkeys, but I > might be missing some case, could you please elaborate more to > let me know the case/cases where this would be useful. As I said some time ago, It's not so useful for wide situation, especially for no transformation is done on the given query. If my memory is correct, there was more wider application before the EC fix for nested inheritance, but now this has rather narrow application:( Anyway, The most and almost only target of this patch is the situation that a DISTINCT is implicitly added for the query, that is UNION on tables with primary key, which is generated by my another patch which was proposed on last CF4 (or earlier). This patch is originally a part of it. https://commitfest.postgresql.org/action/patch_view?id=1279 Come to think of it, maybe I changed my mind. It's better to add a trimmed (minimum) DISTINCT ON clause directly for flattened simple UNION. Other examples are seemingly odd or unlikely as given queries. > I think there is one more disadvantage in the way current patch is > done which is that you need to collect index path keys for all relations > irrespective of whether they will be of any use to eliminate useless > pathkeys from query_pathkeys. One trivial case that comes to mind is > when there are multiple relations involved in query and ORDER BY is > base on columns of only part of the tables involved in query. Like this? select x.a, x.b, y.b from x, y where x.a = y.a order by x.a, x.b; Equivalent class consists of (x.a=y.a) and (x.b), so index pathkeys for i_y is (y.a.=x.a). As a result, no common primary pathkeys found. There seem to be no problem if I understand you correctly. > > # rel->has_elcass_joins seems not working but it is not the topic > > # here. > > > > > Could you please explain me why the index information built in above > > > path is not sufficient or is there any other case which I am missing? > > > > Is the description above enough to be the explaination for the > > place? Sorry for the inaccurate description. > > No issues, above description is sufficient to explain why you have > written patch in its current form. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
On Fri, Jul 25, 2014 at 12:48 PM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
> > I think there is one more disadvantage in the way current patch is
> > done which is that you need to collect index path keys for all relations
> > irrespective of whether they will be of any use to eliminate useless
> > pathkeys from query_pathkeys. One trivial case that comes to mind is
> > when there are multiple relations involved in query and ORDER BY is
> > base on columns of only part of the tables involved in query.
>
> Like this?
>
> select x.a, x.b, y.b from x, y where x.a = y.a order by x.a, x.b;
>
> Equivalent class consists of (x.a=y.a) and (x.b), so index
> pathkeys for i_y is (y.a.=x.a). As a result, no common primary
> pathkeys found.
> > I think there is one more disadvantage in the way current patch is
> > done which is that you need to collect index path keys for all relations
> > irrespective of whether they will be of any use to eliminate useless
> > pathkeys from query_pathkeys. One trivial case that comes to mind is
> > when there are multiple relations involved in query and ORDER BY is
> > base on columns of only part of the tables involved in query.
>
> Like this?
>
> select x.a, x.b, y.b from x, y where x.a = y.a order by x.a, x.b;
>
> Equivalent class consists of (x.a=y.a) and (x.b), so index
> pathkeys for i_y is (y.a.=x.a). As a result, no common primary
> pathkeys found.
I think it will find common pathkey incase you have an unique index
on x.a (please see the example below), but currently I am not clear
why there is a need for a common index path key in such a case to
eliminate useless keys in ORDER BY, why can't we do it based
on individual table's path key.
Example:
create table t (a int not null, b int not null, c int, d text);
create unique index i_t_pkey on t(a, b);
insert into t (select a % 10, a / 10, a, 't' from generate_series(0, 100000) a);
analyze;
create table t1 (a int not null, b int not null, c int, d text);
create unique index i_t1_pkey_1 on t1(a);
create unique index i_t1_pkey_2 on t1(a, b);
insert into t1 (select a * 2, a / 10, a, 't' from generate_series(0, 100000) a);
explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by t1.a,t1.b,t1.c,t1.d;
QUERY PLAN
------------------------------------------
Merge Join
Merge Cond: (t.a = t1.a)
-> Index Scan using i_t_pkey on t
-> Index Scan using i_t1_pkey_1 on t1
(4 rows)
Here we can notice that there is no separate sort key in plan.
Now drop the i_t1_pkey_1 and check the query plan again.
drop index i_t1_pkey_1;
explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by t1.a,t1.b,t1.c,t1.d;
QUERY PLAN
------------------------------------------------
Sort
Sort Key: t.a, t1.b, t1.c, t1.d
-> Merge Join
Merge Cond: (t.a = t1.a)
-> Index Scan using i_t_pkey on t
-> Index Scan using i_t1_pkey_2 on t1
(6 rows)
Can't above plan eliminate Sort Key even after dropping index
(i_t1_pkey_1)?
On Sat, Jul 26, 2014 at 11:53 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:
> On Fri, Jul 25, 2014 at 12:48 PM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
> > > I think there is one more disadvantage in the way current patch is
> > > done which is that you need to collect index path keys for all relations
> > > irrespective of whether they will be of any use to eliminate useless
> > > pathkeys from query_pathkeys. One trivial case that comes to mind is
> > > when there are multiple relations involved in query and ORDER BY is
> > > base on columns of only part of the tables involved in query.
> >
> > Like this?
> >
> > select x.a, x.b, y.b from x, y where x.a = y.a order by x.a, x.b;
> >
> > Equivalent class consists of (x.a=y.a) and (x.b), so index
> > pathkeys for i_y is (y.a.=x.a). As a result, no common primary
> > pathkeys found.
>
> I think it will find common pathkey incase you have an unique index
> on x.a (please see the example below), but currently I am not clear
> why there is a need for a common index path key in such a case to
> eliminate useless keys in ORDER BY, why can't we do it based
> on individual table's path key.
>
> Example:
>
> create table t (a int not null, b int not null, c int, d text);
> create unique index i_t_pkey on t(a, b);
> insert into t (select a % 10, a / 10, a, 't' from generate_series(0, 100000) a);
> analyze;
>
> create table t1 (a int not null, b int not null, c int, d text);
> create unique index i_t1_pkey_1 on t1(a);
> create unique index i_t1_pkey_2 on t1(a, b);
> insert into t1 (select a * 2, a / 10, a, 't' from generate_series(0, 100000) a);
> explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by t1.a,t1.b,t1.c,t1.d;
>
> QUERY PLAN
> ------------------------------------------
> Merge Join
> Merge Cond: (t.a = t1.a)
> -> Index Scan using i_t_pkey on t
> -> Index Scan using i_t1_pkey_1 on t1
> (4 rows)
>
> Here we can notice that there is no separate sort key in plan.
>
> Now drop the i_t1_pkey_1 and check the query plan again.
>
> drop index i_t1_pkey_1;
> explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by t1.a,t1.b,t1.c,t1.d;
> QUERY PLAN
> ------------------------------------------------
> Sort
> Sort Key: t.a, t1.b, t1.c, t1.d
> -> Merge Join
> Merge Cond: (t.a = t1.a)
> -> Index Scan using i_t_pkey on t
> -> Index Scan using i_t1_pkey_2 on t1
> (6 rows)
>
> Can't above plan eliminate Sort Key even after dropping index
> (i_t1_pkey_1)?
> On Fri, Jul 25, 2014 at 12:48 PM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
> > > I think there is one more disadvantage in the way current patch is
> > > done which is that you need to collect index path keys for all relations
> > > irrespective of whether they will be of any use to eliminate useless
> > > pathkeys from query_pathkeys. One trivial case that comes to mind is
> > > when there are multiple relations involved in query and ORDER BY is
> > > base on columns of only part of the tables involved in query.
> >
> > Like this?
> >
> > select x.a, x.b, y.b from x, y where x.a = y.a order by x.a, x.b;
> >
> > Equivalent class consists of (x.a=y.a) and (x.b), so index
> > pathkeys for i_y is (y.a.=x.a). As a result, no common primary
> > pathkeys found.
>
> I think it will find common pathkey incase you have an unique index
> on x.a (please see the example below), but currently I am not clear
> why there is a need for a common index path key in such a case to
> eliminate useless keys in ORDER BY, why can't we do it based
> on individual table's path key.
>
> Example:
>
> create table t (a int not null, b int not null, c int, d text);
> create unique index i_t_pkey on t(a, b);
> insert into t (select a % 10, a / 10, a, 't' from generate_series(0, 100000) a);
> analyze;
>
> create table t1 (a int not null, b int not null, c int, d text);
> create unique index i_t1_pkey_1 on t1(a);
> create unique index i_t1_pkey_2 on t1(a, b);
> insert into t1 (select a * 2, a / 10, a, 't' from generate_series(0, 100000) a);
> explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by t1.a,t1.b,t1.c,t1.d;
>
> QUERY PLAN
> ------------------------------------------
> Merge Join
> Merge Cond: (t.a = t1.a)
> -> Index Scan using i_t_pkey on t
> -> Index Scan using i_t1_pkey_1 on t1
> (4 rows)
>
> Here we can notice that there is no separate sort key in plan.
>
> Now drop the i_t1_pkey_1 and check the query plan again.
>
> drop index i_t1_pkey_1;
> explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by t1.a,t1.b,t1.c,t1.d;
> QUERY PLAN
> ------------------------------------------------
> Sort
> Sort Key: t.a, t1.b, t1.c, t1.d
> -> Merge Join
> Merge Cond: (t.a = t1.a)
> -> Index Scan using i_t_pkey on t
> -> Index Scan using i_t1_pkey_2 on t1
> (6 rows)
>
> Can't above plan eliminate Sort Key even after dropping index
> (i_t1_pkey_1)?
Here I have one additional thought which I would like to share with
you to see if this patch can be done in a simpler way. In function
standard_qp_callback(), can we directly trim the sortclause list based on index information in PlannerInfo. We have access to target list in
this function to know exactly the relation/column information of
sortclause.
Hello, > > > I think there is one more disadvantage in the way current patch is > > > done which is that you need to collect index path keys for all relations > > > irrespective of whether they will be of any use to eliminate useless > > > pathkeys from query_pathkeys. One trivial case that comes to mind is > > > when there are multiple relations involved in query and ORDER BY is > > > base on columns of only part of the tables involved in query. > > > > Like this? > > > > select x.a, x.b, y.b from x, y where x.a = y.a order by x.a, x.b; > > > > Equivalent class consists of (x.a=y.a) and (x.b), so index > > pathkeys for i_y is (y.a.=x.a). As a result, no common primary > > pathkeys found. > > I think it will find common pathkey incase you have an unique index > on x.a (please see the example below), but currently I am not clear > why there is a need for a common index path key in such a case to > eliminate useless keys in ORDER BY, why can't we do it based > on individual table's path key. > > Example: > > create table t (a int not null, b int not null, c int, d text); > create unique index i_t_pkey on t(a, b); > insert into t (select a % 10, a / 10, a, 't' from generate_series(0, > 100000) a); > analyze; > > create table t1 (a int not null, b int not null, c int, d text); > create unique index i_t1_pkey_1 on t1(a); > create unique index i_t1_pkey_2 on t1(a, b); > insert into t1 (select a * 2, a / 10, a, 't' from generate_series(0, > 100000) a); > explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by > t1.a,t1.b,t1.c,t1.d; > > QUERY PLAN > ------------------------------------------ > Merge Join > Merge Cond: (t.a = t1.a) > -> Index Scan using i_t_pkey on t > -> Index Scan using i_t1_pkey_1 on t1 > (4 rows) > > Here we can notice that there is no separate sort key in plan. Sure, > Now drop the i_t1_pkey_1 and check the query plan again. > > drop index i_t1_pkey_1; > explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by > t1.a,t1.b,t1.c,t1.d; > QUERY PLAN > ------------------------------------------------ > Sort > Sort Key: t.a, t1.b, t1.c, t1.d > -> Merge Join > Merge Cond: (t.a = t1.a) > -> Index Scan using i_t_pkey on t > -> Index Scan using i_t1_pkey_2 on t1 > (6 rows) > > Can't above plan eliminate Sort Key even after dropping index > (i_t1_pkey_1)? My patch doesn't so since there no longer a 'common primary pathkeys' in this query. Perhaps the query doesn't allow the sort eliminated. Since a is no more a pkey, t1 can have dulicate rows for the same a, so the joined relation also may have duplicte values in the column a. Therefore the joined relation may be half sorted only by the column a so the sort pathkeys cannot be trimmed. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
On Mon, Jul 28, 2014 at 3:17 PM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
>
> > Now drop the i_t1_pkey_1 and check the query plan again.
> >
> > drop index i_t1_pkey_1;
> > explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by
> > t1.a,t1.b,t1.c,t1.d;
> > QUERY PLAN
> > ------------------------------------------------
> > Sort
> > Sort Key: t.a, t1.b, t1.c, t1.d
> > -> Merge Join
> > Merge Cond: (t.a = t1.a)
> > -> Index Scan using i_t_pkey on t
> > -> Index Scan using i_t1_pkey_2 on t1
> > (6 rows)
> >
> > Can't above plan eliminate Sort Key even after dropping index
> > (i_t1_pkey_1)?
>
> My patch doesn't so since there no longer a 'common primary
> pathkeys' in this query. Perhaps the query doesn't allow the sort
> eliminated. Since a is no more a pkey, t1 can have dulicate rows
> for the same a, so the joined relation also may have duplicte
> values in the column a.
I think irrespective of that we can trim t1.c & t1.d as we have
primary key (unique and non column) for t1.a, t1.b. Basically
even if we don't use the primary key index, we can still trim
the keys in such a case. IIUC, then Tom has mentioned the
same in his message related to this issue.
I am referring to below text:
"If we have "ORDER BY a, b, c" and (a,b) is the
primary key, then including c in the ORDER BY list is semantically
redundant, *whether or not we use an indexscan on the pkey index at all*."
>
> > Now drop the i_t1_pkey_1 and check the query plan again.
> >
> > drop index i_t1_pkey_1;
> > explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by
> > t1.a,t1.b,t1.c,t1.d;
> > QUERY PLAN
> > ------------------------------------------------
> > Sort
> > Sort Key: t.a, t1.b, t1.c, t1.d
> > -> Merge Join
> > Merge Cond: (t.a = t1.a)
> > -> Index Scan using i_t_pkey on t
> > -> Index Scan using i_t1_pkey_2 on t1
> > (6 rows)
> >
> > Can't above plan eliminate Sort Key even after dropping index
> > (i_t1_pkey_1)?
>
> My patch doesn't so since there no longer a 'common primary
> pathkeys' in this query. Perhaps the query doesn't allow the sort
> eliminated. Since a is no more a pkey, t1 can have dulicate rows
> for the same a, so the joined relation also may have duplicte
> values in the column a.
I think irrespective of that we can trim t1.c & t1.d as we have
primary key (unique and non column) for t1.a, t1.b. Basically
even if we don't use the primary key index, we can still trim
the keys in such a case. IIUC, then Tom has mentioned the
same in his message related to this issue.
I am referring to below text:
"If we have "ORDER BY a, b, c" and (a,b) is the
primary key, then including c in the ORDER BY list is semantically
redundant, *whether or not we use an indexscan on the pkey index at all*."
http://www.postgresql.org/message-id/5212.1397599817@sss.pgh.pa.us
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com
Hello, > > > Now drop the i_t1_pkey_1 and check the query plan again. > > > > > > drop index i_t1_pkey_1; > > > explain (costs off, analyze off) select * from t,t1 where t.a=t1.a > order by > > > t1.a,t1.b,t1.c,t1.d; > > > QUERY PLAN > > > ------------------------------------------------ > > > Sort > > > Sort Key: t.a, t1.b, t1.c, t1.d > > > -> Merge Join > > > Merge Cond: (t.a = t1.a) > > > -> Index Scan using i_t_pkey on t > > > -> Index Scan using i_t1_pkey_2 on t1 > > > (6 rows) > > > > > > Can't above plan eliminate Sort Key even after dropping index > > > (i_t1_pkey_1)? > > > > My patch doesn't so since there no longer a 'common primary > > pathkeys' in this query. Perhaps the query doesn't allow the sort > > eliminated. Since a is no more a pkey, t1 can have dulicate rows > > for the same a, so the joined relation also may have duplicte > > values in the column a. Sorry, I may misunderstood you. The dropped index is t1(a) not t1(a,b) so the discussion abobe is on the wrong assumption. > I think irrespective of that we can trim t1.c & t1.d as we have > primary key (unique and non column) for t1.a, t1.b. Basically > even if we don't use the primary key index, we can still trim > the keys in such a case. IIUC, then Tom has mentioned the > same in his message related to this issue. Although, yes, you're right, irrespective of the "common something", and even if the dropped index was i_t1_pkey_2, which is on t1(a, b), the result tuples are sorted as expected only by the pathkey (t.a = t1.a, t1.b). It is because both t and t1 are still unique so the joined tuples are also unique, and the unique key of the result tuples is the merged pkey (t.a, t1.a, t1.b), which can be transformed to (t.a, t1.b) using the equiality between t.a and t1.a. And considering the inner relation (t1) is already sorted by (a, b), the sort itself could be elimited from the plan. The above could be described as below, - Join between relations with pkey yiels relation with the pkey containing the columns of both pkeys, this is createdby simply concatenate them. - The concatenated pkey can be transformed using equality operators, in other words, consulting equivelance classes. - If the projected joined relation(?) contains one of the transformed pkeys above, it is a pkey for the result. And in regards to MergeJoin and NestLoop, the result pathkeys can be composed by concatenating child pathkeys in outer-inner order. If the all ORDER BY pathkeys columns appear in the concatenated pathkeys in the same order , the sort itself can be eliminated. > I am referring to below text: > > "If we have "ORDER BY a, b, c" and (a,b) is the > primary key, then including c in the ORDER BY list is semantically > redundant, *whether or not we use an indexscan on the pkey index at all*." > > http://www.postgresql.org/message-id/5212.1397599817@sss.pgh.pa.us Yes, my point at that time was mainly union (all) and partitioned tables so the optimization for joins was the next step for me. Although, my previous implement of collect_common_primary_pathkeys seems to have been excessively heavyweighted and it could be integrated with join optimization. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
On Mon, Aug 4, 2014 at 1:22 PM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
>
> Hello,
>
> > I think irrespective of that we can trim t1.c & t1.d as we have
> > primary key (unique and non column) for t1.a, t1.b. Basically
> > even if we don't use the primary key index, we can still trim
> > the keys in such a case. IIUC, then Tom has mentioned the
> > same in his message related to this issue.
>
> Although, yes, you're right, irrespective of the "common
> something", and even if the dropped index was i_t1_pkey_2, which
> is on t1(a, b), the result tuples are sorted as expected only by
> the pathkey (t.a = t1.a, t1.b). It is because both t and t1 are
> still unique so the joined tuples are also unique, and the unique
> key of the result tuples is the merged pkey (t.a, t1.a, t1.b),
> which can be transformed to (t.a, t1.b) using the equiality
> between t.a and t1.a. And considering the inner relation (t1) is
> already sorted by (a, b), the sort itself could be elimited from
> the plan.
>
>
> > I am referring to below text:
> >
> > "If we have "ORDER BY a, b, c" and (a,b) is the
> > primary key, then including c in the ORDER BY list is semantically
> > redundant, *whether or not we use an indexscan on the pkey index at all*."
> >
> > http://www.postgresql.org/message-id/5212.1397599817@sss.pgh.pa.us
>
> Yes, my point at that time was mainly union (all) and partitioned
> tables so the optimization for joins was the next step for
> me.
>
> Hello,
>
> > I think irrespective of that we can trim t1.c & t1.d as we have
> > primary key (unique and non column) for t1.a, t1.b. Basically
> > even if we don't use the primary key index, we can still trim
> > the keys in such a case. IIUC, then Tom has mentioned the
> > same in his message related to this issue.
>
> Although, yes, you're right, irrespective of the "common
> something", and even if the dropped index was i_t1_pkey_2, which
> is on t1(a, b), the result tuples are sorted as expected only by
> the pathkey (t.a = t1.a, t1.b). It is because both t and t1 are
> still unique so the joined tuples are also unique, and the unique
> key of the result tuples is the merged pkey (t.a, t1.a, t1.b),
> which can be transformed to (t.a, t1.b) using the equiality
> between t.a and t1.a. And considering the inner relation (t1) is
> already sorted by (a, b), the sort itself could be elimited from
> the plan.
I think if we could eliminate t1.c,t1.d considering indexes on
individual relations (may be by using technique I have mentioned
upthread or some other way), then the current code itself will
eliminate the ORDER BY clause. I have tried that by using a query
without having t1.c,t1.d in ORDER BY clause
explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by t1.a,t1.b;
QUERY PLAN
------------------------------------------
Merge Join
Merge Cond: (t1.a = t.a)
-> Index Scan using i_t1_pkey_2 on t1
-> Index Scan using i_t_pkey on t
(4 rows)
>
>
> > I am referring to below text:
> >
> > "If we have "ORDER BY a, b, c" and (a,b) is the
> > primary key, then including c in the ORDER BY list is semantically
> > redundant, *whether or not we use an indexscan on the pkey index at all*."
> >
> > http://www.postgresql.org/message-id/5212.1397599817@sss.pgh.pa.us
>
> Yes, my point at that time was mainly union (all) and partitioned
> tables so the optimization for joins was the next step for
> me.
Okay, I think you want to handle the elimination of ORDER BY clauses
at a much broader level which might handle most of simple cases as
well. However I think eliminating clauses as mentioned above is itself
a good optimization for many cases and more so if that can be done in
a much simpler way.
Hello, > > Although, yes, you're right, irrespective of the "common > > something", and even if the dropped index was i_t1_pkey_2, which > > is on t1(a, b), the result tuples are sorted as expected only by > > the pathkey (t.a = t1.a, t1.b). It is because both t and t1 are > > still unique so the joined tuples are also unique, and the unique > > key of the result tuples is the merged pkey (t.a, t1.a, t1.b), > > which can be transformed to (t.a, t1.b) using the equiality > > between t.a and t1.a. And considering the inner relation (t1) is > > already sorted by (a, b), the sort itself could be elimited from > > the plan. > > I think if we could eliminate t1.c,t1.d considering indexes on > individual relations (may be by using technique I have mentioned > upthread or some other way), then the current code itself will > eliminate the ORDER BY clause. I have tried that by using a query > without having t1.c,t1.d in ORDER BY clause > > explain (costs off, analyze off) select * from t,t1 where t.a=t1.a order by > t1.a,t1.b; > QUERY PLAN > ------------------------------------------ > Merge Join > Merge Cond: (t1.a = t.a) > -> Index Scan using i_t1_pkey_2 on t1 > -> Index Scan using i_t_pkey on t > (4 rows) Ya, the elimination seems to me so fascinate:) > Okay, I think you want to handle the elimination of ORDER BY clauses > at a much broader level which might handle most of simple cases as > well. However I think eliminating clauses as mentioned above is itself > a good optimization for many cases and more so if that can be done in > a much simpler way. Yes, if can be done in "much" simpler way.. I guess that it could be looking from opposite side, that is, equivalence classes, anyway, I'll try it. regards, -- Kyotaro Horiguchi NTT Open Source Software Center