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.kyot...@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 print indextlist */ 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_am entry */ } 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); static void 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, Index rti, 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 assume the 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 need to keep looking */ } @@ -319,7 +338,7 @@ compare_pathkeys(List *keys1, List *keys2) bool pathkeys_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 be able 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 predicate matches 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'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..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 @@ Sort step 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
-- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers