* the nature and use of path keys.
*
*
- * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
* IDENTIFICATION
- * $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.56 2004/04/07 17:42:28 tgl Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.72 2005/08/27 22:13:43 tgl Exp $
*
*-------------------------------------------------------------------------
*/
static PathKeyItem *makePathKeyItem(Node *key, Oid sortop, bool checkType);
-static List *make_canonical_pathkey(Query *root, PathKeyItem *item);
-static Var *find_indexkey_var(Query *root, RelOptInfo *rel,
+static void generate_outer_join_implications(PlannerInfo *root,
+ List *equi_key_set,
+ Relids *relids);
+static void sub_generate_join_implications(PlannerInfo *root,
+ List *equi_key_set, Relids *relids,
+ Node *item1, Oid sortop1,
+ Relids item1_relids);
+static void process_implied_const_eq(PlannerInfo *root,
+ List *equi_key_set, Relids *relids,
+ Node *item1, Oid sortop1,
+ Relids item1_relids,
+ bool delete_it);
+static List *make_canonical_pathkey(PlannerInfo *root, PathKeyItem *item);
+static Var *find_indexkey_var(PlannerInfo *root, RelOptInfo *rel,
AttrNumber varattno);
/*
* Some callers pass expressions that are not necessarily of the same
- * type as the sort operator expects as input (for example when dealing
- * with an index that uses binary-compatible operators). We must relabel
- * these with the correct type so that the key expressions will be seen
- * as equal() to expressions that have been correctly labeled.
+ * type as the sort operator expects as input (for example when
+ * dealing with an index that uses binary-compatible operators). We
+ * must relabel these with the correct type so that the key
+ * expressions will be seen as equal() to expressions that have been
+ * correctly labeled.
*/
if (checkType)
{
* that involves an equijoined variable.
*/
void
-add_equijoined_keys(Query *root, RestrictInfo *restrictinfo)
+add_equijoined_keys(PlannerInfo *root, RestrictInfo *restrictinfo)
{
Expr *clause = restrictinfo->clause;
PathKeyItem *item1 = makePathKeyItem(get_leftop(clause),
PathKeyItem *item2 = makePathKeyItem(get_rightop(clause),
restrictinfo->right_sortop,
false);
- List *newset,
- *cursetlink;
+ List *newset;
+ ListCell *cursetlink;
/* We might see a clause X=X; don't make a single-element list from it */
if (equal(item1, item2))
newset = NIL;
/* cannot use foreach here because of possible lremove */
- cursetlink = root->equi_key_list;
+ cursetlink = list_head(root->equi_key_list);
while (cursetlink)
{
- List *curset = lfirst(cursetlink);
- bool item1here = member(item1, curset);
- bool item2here = member(item2, curset);
+ List *curset = (List *) lfirst(cursetlink);
+ bool item1here = list_member(curset, item1);
+ bool item2here = list_member(curset, item2);
/* must advance cursetlink before lremove possibly pfree's it */
cursetlink = lnext(cursetlink);
/* Build the new set only when we know we must */
if (newset == NIL)
- newset = makeList2(item1, item2);
+ newset = list_make2(item1, item2);
/* Found a set to merge into our new set */
- newset = set_union(newset, curset);
+ newset = list_concat_unique(newset, curset);
/*
* Remove old set from equi_key_list.
*/
- root->equi_key_list = lremove(curset, root->equi_key_list);
- freeList(curset); /* might as well recycle old cons cells */
+ root->equi_key_list = list_delete_ptr(root->equi_key_list, curset);
+ list_free(curset); /* might as well recycle old cons cells */
}
}
/* Build the new set only when we know we must */
if (newset == NIL)
- newset = makeList2(item1, item2);
+ newset = list_make2(item1, item2);
root->equi_key_list = lcons(newset, root->equi_key_list);
}
* functions; but we will never consider such an expression to be a pathkey
* at all, because check_mergejoinable() will reject it.)
*
+ * Also, when we have constants in an equi_key_list we can try to propagate
+ * the constants into outer joins; see generate_outer_join_implications
+ * for discussion.
+ *
* This routine just walks the equi_key_list to find all pairwise equalities.
* We call process_implied_equality (in plan/initsplan.c) to adjust the
* restrictinfo datastructures for each pair.
*/
void
-generate_implied_equalities(Query *root)
+generate_implied_equalities(PlannerInfo *root)
{
- List *cursetlink;
+ ListCell *cursetlink;
foreach(cursetlink, root->equi_key_list)
{
- List *curset = lfirst(cursetlink);
- int nitems = length(curset);
+ List *curset = (List *) lfirst(cursetlink);
+ int nitems = list_length(curset);
Relids *relids;
bool have_consts;
- List *ptr1;
+ ListCell *ptr1;
int i1;
/*
* A set containing only two items cannot imply any equalities
- * beyond the one that created the set, so we can skip it.
+ * beyond the one that created the set, so we can skip it ---
+ * unless outer joins appear in the query.
*/
- if (nitems < 3)
+ if (nitems < 3 && !root->hasOuterJoins)
continue;
/*
/*
* Match each item in the set with all that appear after it (it's
* sufficient to generate A=B, need not process B=A too).
+ *
+ * A set containing only two items cannot imply any equalities
+ * beyond the one that created the set, so we can skip this
+ * processing in that case.
*/
- i1 = 0;
- foreach(ptr1, curset)
+ if (nitems >= 3)
{
- PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
- bool i1_is_variable = !bms_is_empty(relids[i1]);
- List *ptr2;
- int i2 = i1 + 1;
-
- foreach(ptr2, lnext(ptr1))
+ i1 = 0;
+ foreach(ptr1, curset)
{
- PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
- bool i2_is_variable = !bms_is_empty(relids[i2]);
+ PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
+ bool i1_is_variable = !bms_is_empty(relids[i1]);
+ ListCell *ptr2;
+ int i2 = i1 + 1;
- /*
- * If it's "const = const" then just ignore it altogether.
- * There is no place in the restrictinfo structure to
- * store it. (If the two consts are in fact unequal, then
- * propagating the comparison to Vars will cause us to
- * produce zero rows out, as expected.)
- */
- if (i1_is_variable || i2_is_variable)
+ for_each_cell(ptr2, lnext(ptr1))
{
+ PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
+ bool i2_is_variable = !bms_is_empty(relids[i2]);
+
/*
- * Tell process_implied_equality to delete the clause,
- * not add it, if it's "var = var" and we have
- * constants present in the list.
+ * If it's "const = const" then just ignore it altogether.
+ * There is no place in the restrictinfo structure to
+ * store it. (If the two consts are in fact unequal, then
+ * propagating the comparison to Vars will cause us to
+ * produce zero rows out, as expected.)
*/
- bool delete_it = (have_consts &&
- i1_is_variable &&
- i2_is_variable);
-
- process_implied_equality(root,
- item1->key, item2->key,
- item1->sortop, item2->sortop,
- relids[i1], relids[i2],
- delete_it);
+ if (i1_is_variable || i2_is_variable)
+ {
+ /*
+ * Tell process_implied_equality to delete the clause,
+ * not add it, if it's "var = var" and we have
+ * constants present in the list.
+ */
+ bool delete_it = (have_consts &&
+ i1_is_variable &&
+ i2_is_variable);
+
+ process_implied_equality(root,
+ item1->key, item2->key,
+ item1->sortop, item2->sortop,
+ relids[i1], relids[i2],
+ delete_it);
+ }
+ i2++;
}
- i2++;
+ i1++;
}
- i1++;
}
+
+ /*
+ * If we have constant(s) and outer joins, try to propagate the
+ * constants through outer-join quals.
+ */
+ if (have_consts && root->hasOuterJoins)
+ generate_outer_join_implications(root, curset, relids);
+ }
+}
+
+/*
+ * generate_outer_join_implications
+ * Generate clauses that can be deduced in outer-join situations.
+ *
+ * When we have mergejoinable clauses A = B that are outer-join clauses,
+ * we can't blindly combine them with other clauses A = C to deduce B = C,
+ * since in fact the "equality" A = B won't necessarily hold above the
+ * outer join (one of the variables might be NULL instead). Nonetheless
+ * there are cases where we can add qual clauses using transitivity.
+ *
+ * One case that we look for here is an outer-join clause OUTERVAR = INNERVAR
+ * combined with a pushed-down (valid everywhere) clause OUTERVAR = CONSTANT.
+ * It is safe and useful to push a clause INNERVAR = CONSTANT into the
+ * evaluation of the inner (nullable) relation, because any inner rows not
+ * meeting this condition will not contribute to the outer-join result anyway.
+ * (Any outer rows they could join to will be eliminated by the pushed-down
+ * clause.)
+ *
+ * Note that the above rule does not work for full outer joins, nor for
+ * pushed-down restrictions on an inner-side variable; nor is it very
+ * interesting to consider cases where the pushed-down clause involves
+ * relations entirely outside the outer join, since such clauses couldn't
+ * be pushed into the inner side's scan anyway. So the restriction to
+ * outervar = pseudoconstant is not really giving up anything.
+ *
+ * For full-join cases, we can only do something useful if it's a FULL JOIN
+ * USING and a merged column has a restriction MERGEDVAR = CONSTANT. By
+ * the time it gets here, the restriction will look like
+ * COALESCE(LEFTVAR, RIGHTVAR) = CONSTANT
+ * and we will have a join clause LEFTVAR = RIGHTVAR that we can match the
+ * COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT
+ * and RIGHTVAR = CONSTANT into the input relations, since any rows not
+ * meeting these conditions cannot contribute to the join result.
+ *
+ * Again, there isn't any traction to be gained by trying to deal with
+ * clauses comparing a mergedvar to a non-pseudoconstant. So we can make
+ * use of the equi_key_lists to quickly find the interesting pushed-down
+ * clauses. The interesting outer-join clauses were accumulated for us by
+ * distribute_qual_to_rels.
+ *
+ * equi_key_set: a list of PathKeyItems that are known globally equivalent,
+ * at least one of which is a pseudoconstant.
+ * relids: an array of Relids sets showing the relation membership of each
+ * PathKeyItem in equi_key_set.
+ */
+static void
+generate_outer_join_implications(PlannerInfo *root,
+ List *equi_key_set,
+ Relids *relids)
+{
+ ListCell *l;
+ int i = 0;
+
+ /* Process each non-constant element of equi_key_set */
+ foreach(l, equi_key_set)
+ {
+ PathKeyItem *item1 = (PathKeyItem *) lfirst(l);
+
+ if (!bms_is_empty(relids[i]))
+ {
+ sub_generate_join_implications(root, equi_key_set, relids,
+ item1->key,
+ item1->sortop,
+ relids[i]);
+ }
+ i++;
+ }
+}
+
+/*
+ * sub_generate_join_implications
+ * Propagate a constant equality through outer join clauses.
+ *
+ * The item described by item1/sortop1/item1_relids has been determined
+ * to be equal to the constant(s) listed in equi_key_set. Recursively
+ * trace out the implications of this.
+ *
+ * equi_key_set and relids are as for generate_outer_join_implications.
+ */
+static void
+sub_generate_join_implications(PlannerInfo *root,
+ List *equi_key_set, Relids *relids,
+ Node *item1, Oid sortop1, Relids item1_relids)
+
+{
+ ListCell *l;
+
+ /*
+ * Examine each mergejoinable outer-join clause with OUTERVAR on left,
+ * looking for an OUTERVAR identical to item1
+ */
+ foreach(l, root->left_join_clauses)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+ Node *leftop = get_leftop(rinfo->clause);
+
+ if (equal(leftop, item1) && rinfo->left_sortop == sortop1)
+ {
+ /*
+ * Match, so find constant member(s) of set and generate
+ * implied INNERVAR = CONSTANT
+ */
+ Node *rightop = get_rightop(rinfo->clause);
+
+ process_implied_const_eq(root, equi_key_set, relids,
+ rightop,
+ rinfo->right_sortop,
+ rinfo->right_relids,
+ false);
+ /*
+ * We can remove explicit tests of this outer-join qual, too,
+ * since we now have tests forcing each of its sides
+ * to the same value.
+ */
+ process_implied_equality(root,
+ leftop, rightop,
+ rinfo->left_sortop, rinfo->right_sortop,
+ rinfo->left_relids, rinfo->right_relids,
+ true);
+ /*
+ * And recurse to see if we can deduce anything from
+ * INNERVAR = CONSTANT
+ */
+ sub_generate_join_implications(root, equi_key_set, relids,
+ rightop,
+ rinfo->right_sortop,
+ rinfo->right_relids);
+ }
+ }
+
+ /* The same, looking at clauses with OUTERVAR on right */
+ foreach(l, root->right_join_clauses)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+ Node *rightop = get_rightop(rinfo->clause);
+
+ if (equal(rightop, item1) && rinfo->right_sortop == sortop1)
+ {
+ /*
+ * Match, so find constant member(s) of set and generate
+ * implied INNERVAR = CONSTANT
+ */
+ Node *leftop = get_leftop(rinfo->clause);
+
+ process_implied_const_eq(root, equi_key_set, relids,
+ leftop,
+ rinfo->left_sortop,
+ rinfo->left_relids,
+ false);
+ /*
+ * We can remove explicit tests of this outer-join qual, too,
+ * since we now have tests forcing each of its sides
+ * to the same value.
+ */
+ process_implied_equality(root,
+ leftop, rightop,
+ rinfo->left_sortop, rinfo->right_sortop,
+ rinfo->left_relids, rinfo->right_relids,
+ true);
+ /*
+ * And recurse to see if we can deduce anything from
+ * INNERVAR = CONSTANT
+ */
+ sub_generate_join_implications(root, equi_key_set, relids,
+ leftop,
+ rinfo->left_sortop,
+ rinfo->left_relids);
+ }
+ }
+
+ /*
+ * Only COALESCE(x,y) items can possibly match full joins
+ */
+ if (IsA(item1, CoalesceExpr))
+ {
+ CoalesceExpr *cexpr = (CoalesceExpr *) item1;
+ Node *cfirst;
+ Node *csecond;
+
+ if (list_length(cexpr->args) != 2)
+ return;
+ cfirst = (Node *) linitial(cexpr->args);
+ csecond = (Node *) lsecond(cexpr->args);
+
+ /*
+ * Examine each mergejoinable full-join clause, looking for a
+ * clause of the form "x = y" matching the COALESCE(x,y) expression
+ */
+ foreach(l, root->full_join_clauses)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
+ Node *leftop = get_leftop(rinfo->clause);
+ Node *rightop = get_rightop(rinfo->clause);
+
+ /*
+ * We can assume the COALESCE() inputs are in the same order
+ * as the join clause, since both were automatically generated
+ * in the cases we care about.
+ *
+ * XXX currently this may fail to match in cross-type cases
+ * because the COALESCE will contain typecast operations while
+ * the join clause may not (if there is a cross-type mergejoin
+ * operator available for the two column types).
+ * Is it OK to strip implicit coercions from the COALESCE
+ * arguments? What of the sortops in such cases?
+ */
+ if (equal(leftop, cfirst) &&
+ equal(rightop, csecond) &&
+ rinfo->left_sortop == sortop1 &&
+ rinfo->right_sortop == sortop1)
+ {
+ /*
+ * Match, so find constant member(s) of set and generate
+ * implied LEFTVAR = CONSTANT
+ */
+ process_implied_const_eq(root, equi_key_set, relids,
+ leftop,
+ rinfo->left_sortop,
+ rinfo->left_relids,
+ false);
+ /* ... and RIGHTVAR = CONSTANT */
+ process_implied_const_eq(root, equi_key_set, relids,
+ rightop,
+ rinfo->right_sortop,
+ rinfo->right_relids,
+ false);
+ /* ... and remove COALESCE() = CONSTANT */
+ process_implied_const_eq(root, equi_key_set, relids,
+ item1,
+ sortop1,
+ item1_relids,
+ true);
+ /*
+ * We can remove explicit tests of this outer-join qual, too,
+ * since we now have tests forcing each of its sides
+ * to the same value.
+ */
+ process_implied_equality(root,
+ leftop, rightop,
+ rinfo->left_sortop,
+ rinfo->right_sortop,
+ rinfo->left_relids,
+ rinfo->right_relids,
+ true);
+ /*
+ * And recurse to see if we can deduce anything from
+ * LEFTVAR = CONSTANT
+ */
+ sub_generate_join_implications(root, equi_key_set, relids,
+ leftop,
+ rinfo->left_sortop,
+ rinfo->left_relids);
+ /* ... and RIGHTVAR = CONSTANT */
+ sub_generate_join_implications(root, equi_key_set, relids,
+ rightop,
+ rinfo->right_sortop,
+ rinfo->right_relids);
+
+ }
+ }
+ }
+}
+
+/*
+ * process_implied_const_eq
+ * Apply process_implied_equality with the given item and each
+ * pseudoconstant member of equi_key_set.
+ *
+ * equi_key_set and relids are as for generate_outer_join_implications,
+ * the other parameters as for process_implied_equality.
+ */
+static void
+process_implied_const_eq(PlannerInfo *root, List *equi_key_set, Relids *relids,
+ Node *item1, Oid sortop1, Relids item1_relids,
+ bool delete_it)
+{
+ ListCell *l;
+ bool found = false;
+ int i = 0;
+
+ foreach(l, equi_key_set)
+ {
+ PathKeyItem *item2 = (PathKeyItem *) lfirst(l);
+
+ if (bms_is_empty(relids[i]))
+ {
+ process_implied_equality(root,
+ item1, item2->key,
+ sortop1, item2->sortop,
+ item1_relids, NULL,
+ delete_it);
+ found = true;
+ }
+ i++;
}
+ /* Caller screwed up if no constants in list */
+ Assert(found);
}
/*
* check that case if it's possible to pass identical items.
*/
bool
-exprs_known_equal(Query *root, Node *item1, Node *item2)
+exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
{
- List *cursetlink;
+ ListCell *cursetlink;
foreach(cursetlink, root->equi_key_list)
{
- List *curset = lfirst(cursetlink);
+ List *curset = (List *) lfirst(cursetlink);
bool item1member = false;
bool item2member = false;
- List *ptr;
+ ListCell *ptr;
foreach(ptr, curset)
{
* scanning the WHERE clause for equijoin operators.
*/
static List *
-make_canonical_pathkey(Query *root, PathKeyItem *item)
+make_canonical_pathkey(PlannerInfo *root, PathKeyItem *item)
{
- List *cursetlink;
List *newset;
+ ListCell *cursetlink;
foreach(cursetlink, root->equi_key_list)
{
- List *curset = lfirst(cursetlink);
+ List *curset = (List *) lfirst(cursetlink);
- if (member(item, curset))
+ if (list_member(curset, item))
return curset;
}
- newset = makeList1(item);
+ newset = list_make1(item);
root->equi_key_list = lcons(newset, root->equi_key_list);
return newset;
}
* scanning the WHERE clause for equijoin operators.
*/
List *
-canonicalize_pathkeys(Query *root, List *pathkeys)
+canonicalize_pathkeys(PlannerInfo *root, List *pathkeys)
{
List *new_pathkeys = NIL;
- List *i;
+ ListCell *l;
- foreach(i, pathkeys)
+ foreach(l, pathkeys)
{
- List *pathkey = (List *) lfirst(i);
+ List *pathkey = (List *) lfirst(l);
PathKeyItem *item;
List *cpathkey;
* set by definition.
*/
Assert(pathkey != NIL);
- item = (PathKeyItem *) lfirst(pathkey);
+ item = (PathKeyItem *) linitial(pathkey);
cpathkey = make_canonical_pathkey(root, item);
/*
* canonicalized the keys, so that equivalent-key knowledge is
* used when deciding if an item is redundant.
*/
- if (!ptrMember(cpathkey, new_pathkeys))
- new_pathkeys = lappend(new_pathkeys, cpathkey);
+ new_pathkeys = list_append_unique_ptr(new_pathkeys, cpathkey);
}
return new_pathkeys;
}
* If not, return 0 (without actually adding it to our equi_key_list).
*
* This is a hack to support the rather bogus heuristics in
- * build_subquery_pathkeys.
+ * convert_subquery_pathkeys.
*/
static int
-count_canonical_peers(Query *root, PathKeyItem *item)
+count_canonical_peers(PlannerInfo *root, PathKeyItem *item)
{
- List *cursetlink;
+ ListCell *cursetlink;
foreach(cursetlink, root->equi_key_list)
{
- List *curset = lfirst(cursetlink);
+ List *curset = (List *) lfirst(cursetlink);
- if (member(item, curset))
- return length(curset) - 1;
+ if (list_member(curset, item))
+ return list_length(curset) - 1;
}
return 0;
}
PathKeysComparison
compare_pathkeys(List *keys1, List *keys2)
{
- List *key1,
+ ListCell *key1,
*key2;
- for (key1 = keys1, key2 = keys2;
- key1 != NIL && key2 != NIL;
- key1 = lnext(key1), key2 = lnext(key2))
+ forboth(key1, keys1, key2, keys2)
{
- List *subkey1 = lfirst(key1);
- List *subkey2 = lfirst(key2);
+ List *subkey1 = (List *) lfirst(key1);
+ List *subkey2 = (List *) lfirst(key2);
/*
* XXX would like to check that we've been given canonicalized
- * input, but query root not accessible here...
+ * input, but PlannerInfo not accessible here...
*/
#ifdef NOT_USED
- Assert(ptrMember(subkey1, root->equi_key_list));
- Assert(ptrMember(subkey2, root->equi_key_list));
+ Assert(list_member_ptr(root->equi_key_list, subkey1));
+ Assert(list_member_ptr(root->equi_key_list, subkey2));
#endif
/*
* the other list are not NIL --- no pathkey list should ever have a
* NIL sublist.)
*/
- if (key1 == NIL && key2 == NIL)
- return PATHKEYS_EQUAL;
- if (key1 != NIL)
- return PATHKEYS_BETTER1; /* key1 is longer */
- return PATHKEYS_BETTER2; /* key2 is longer */
-}
-
-/*
- * compare_noncanonical_pathkeys
- * Compare two pathkeys to see if they are equivalent, and if not whether
- * one is "better" than the other. This is used when we must compare
- * non-canonicalized pathkeys.
- *
- * A pathkey can be considered better than another if it is a superset:
- * it contains all the keys of the other plus more. For example, either
- * ((A) (B)) or ((A B)) is better than ((A)).
- *
- * Currently, the only user of this routine is grouping_planner(),
- * and it will only pass single-element sublists (from
- * make_pathkeys_for_sortclauses). Therefore we don't have to do the
- * full two-way-subset-inclusion test on each pair of sublists that is
- * implied by the above statement. Instead we just verify they are
- * singleton lists and then do an equal(). This could be improved if
- * necessary.
- */
-PathKeysComparison
-compare_noncanonical_pathkeys(List *keys1, List *keys2)
-{
- List *key1,
- *key2;
-
- for (key1 = keys1, key2 = keys2;
- key1 != NIL && key2 != NIL;
- key1 = lnext(key1), key2 = lnext(key2))
- {
- List *subkey1 = lfirst(key1);
- List *subkey2 = lfirst(key2);
-
- Assert(length(subkey1) == 1);
- Assert(length(subkey2) == 1);
- if (!equal(subkey1, subkey2))
- 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. (We assume the additional sublist(s) of
- * the other list are not NIL --- no pathkey list should ever have a
- * NIL sublist.)
- */
- if (key1 == NIL && key2 == NIL)
+ if (key1 == NULL && key2 == NULL)
return PATHKEYS_EQUAL;
- if (key1 != NIL)
+ if (key1 != NULL)
return PATHKEYS_BETTER1; /* key1 is longer */
return PATHKEYS_BETTER2; /* key2 is longer */
}
return false;
}
-/*
- * noncanonical_pathkeys_contained_in
- * The same, when we don't have canonical pathkeys.
- */
-bool
-noncanonical_pathkeys_contained_in(List *keys1, List *keys2)
-{
- switch (compare_noncanonical_pathkeys(keys1, keys2))
- {
- case PATHKEYS_EQUAL:
- case PATHKEYS_BETTER2:
- return true;
- default:
- break;
- }
- return false;
-}
-
/*
* get_cheapest_path_for_pathkeys
* Find the cheapest path (according to the specified criterion) that
CostSelector cost_criterion)
{
Path *matched_path = NULL;
- List *i;
+ ListCell *l;
- foreach(i, paths)
+ foreach(l, paths)
{
- Path *path = (Path *) lfirst(i);
+ Path *path = (Path *) lfirst(l);
/*
* Since cost comparison is a lot cheaper than pathkey comparison,
double fraction)
{
Path *matched_path = NULL;
- List *i;
+ ListCell *l;
- foreach(i, paths)
+ foreach(l, paths)
{
- Path *path = (Path *) lfirst(i);
+ Path *path = (Path *) lfirst(l);
/*
* Since cost comparison is a lot cheaper than pathkey comparison,
* current query. Caller should do truncate_useless_pathkeys().
*/
List *
-build_index_pathkeys(Query *root,
- RelOptInfo *rel,
+build_index_pathkeys(PlannerInfo *root,
IndexOptInfo *index,
ScanDirection scandir)
{
List *retval = NIL;
int *indexkeys = index->indexkeys;
Oid *ordering = index->ordering;
- List *indexprs = index->indexprs;
+ ListCell *indexprs_item = list_head(index->indexprs);
while (*ordering != InvalidOid)
{
if (*indexkeys != 0)
{
/* simple index column */
- indexkey = (Node *) find_indexkey_var(root, rel, *indexkeys);
+ indexkey = (Node *) find_indexkey_var(root, index->rel,
+ *indexkeys);
}
else
{
/* expression --- assume we need not copy it */
- if (indexprs == NIL)
+ if (indexprs_item == NULL)
elog(ERROR, "wrong number of index expressions");
- indexkey = (Node *) lfirst(indexprs);
- indexprs = lnext(indexprs);
+ indexkey = (Node *) lfirst(indexprs_item);
+ indexprs_item = lnext(indexprs_item);
}
/* OK, make a sublist for this sort key */
* Eliminate redundant ordering info; could happen if query is
* such that index keys are equijoined...
*/
- if (!ptrMember(cpathkey, retval))
- retval = lappend(retval, cpathkey);
+ retval = list_append_unique_ptr(retval, cpathkey);
indexkeys++;
ordering++;
* gin up a Var node the hard way.
*/
static Var *
-find_indexkey_var(Query *root, RelOptInfo *rel, AttrNumber varattno)
+find_indexkey_var(PlannerInfo *root, RelOptInfo *rel, AttrNumber varattno)
{
- List *temp;
+ ListCell *temp;
Index relid;
Oid reloid,
vartypeid;
int32 type_mod;
- foreach(temp, FastListValue(&rel->reltargetlist))
+ foreach(temp, rel->reltargetlist)
{
Var *var = (Var *) lfirst(temp);
}
relid = rel->relid;
- reloid = getrelid(relid, root->rtable);
+ reloid = getrelid(relid, root->parse->rtable);
get_atttypetypmod(reloid, varattno, &vartypeid, &type_mod);
return makeVar(relid, varattno, vartypeid, type_mod, 0);
}
/*
- * build_subquery_pathkeys
+ * convert_subquery_pathkeys
* Build a pathkeys list that describes the ordering of a subquery's
- * result (in the terms of the outer query). The subquery must already
- * have been planned, so that its query_pathkeys field has been set.
+ * result, in the terms of the outer query. This is essentially a
+ * task of conversion.
+ *
+ * 'rel': outer query's RelOptInfo for the subquery relation.
+ * 'subquery_pathkeys': the subquery's output pathkeys, in its terms.
*
* It is not necessary for caller to do truncate_useless_pathkeys(),
* because we select keys in a way that takes usefulness of the keys into
* account.
*/
List *
-build_subquery_pathkeys(Query *root, RelOptInfo *rel, Query *subquery)
+convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel,
+ List *subquery_pathkeys)
{
List *retval = NIL;
int retvallen = 0;
- int outer_query_keys = length(root->query_pathkeys);
+ int outer_query_keys = list_length(root->query_pathkeys);
List *sub_tlist = rel->subplan->targetlist;
- List *l;
+ ListCell *i;
- foreach(l, subquery->query_pathkeys)
+ foreach(i, subquery_pathkeys)
{
- List *sub_pathkey = (List *) lfirst(l);
- List *j;
+ List *sub_pathkey = (List *) lfirst(i);
+ ListCell *j;
PathKeyItem *best_item = NULL;
int best_score = 0;
List *cpathkey;
{
PathKeyItem *sub_item = (PathKeyItem *) lfirst(j);
Node *sub_key = sub_item->key;
- List *k;
+ ListCell *k;
foreach(k, sub_tlist)
{
TargetEntry *tle = (TargetEntry *) lfirst(k);
- if (!tle->resdom->resjunk &&
+ if (!tle->resjunk &&
equal(tle->expr, sub_key))
{
/* Found a representation for this sub_key */
int score;
outer_var = makeVar(rel->relid,
- tle->resdom->resno,
- tle->resdom->restype,
- tle->resdom->restypmod,
+ tle->resno,
+ exprType((Node *) tle->expr),
+ exprTypmod((Node *) tle->expr),
0);
outer_item = makePathKeyItem((Node *) outer_var,
sub_item->sortop,
score = count_canonical_peers(root, outer_item);
/* +1 if it matches the proper query_pathkeys item */
if (retvallen < outer_query_keys &&
- member(outer_item,
- nth(retvallen, root->query_pathkeys)))
+ list_member(list_nth(root->query_pathkeys, retvallen), outer_item))
score++;
if (score > best_score)
{
* Eliminate redundant ordering info; could happen if outer query
* equijoins subquery keys...
*/
- if (!ptrMember(cpathkey, retval))
+ if (!list_member_ptr(retval, cpathkey))
{
retval = lappend(retval, cpathkey);
retvallen++;
* vars they were joined with; furthermore, it doesn't matter what kind
* of join algorithm is actually used.
*
+ * EXCEPTION: in a FULL or RIGHT join, we cannot treat the result as
+ * having the outer path's path keys, because null lefthand rows may be
+ * inserted at random points. It must be treated as unsorted.
+ *
* 'joinrel' is the join relation that paths are being formed for
+ * 'jointype' is the join type (inner, left, full, etc)
* 'outer_pathkeys' is the list of the current outer path's path keys
*
* Returns the list of new path keys.
*/
List *
-build_join_pathkeys(Query *root,
+build_join_pathkeys(PlannerInfo *root,
RelOptInfo *joinrel,
+ JoinType jointype,
List *outer_pathkeys)
{
+ if (jointype == JOIN_FULL || jointype == JOIN_RIGHT)
+ return NIL;
+
/*
* This used to be quite a complex bit of code, but now that all
* pathkey sublists start out life canonicalized, we don't have to do
List *tlist)
{
List *pathkeys = NIL;
- List *i;
+ ListCell *l;
- foreach(i, sortclauses)
+ foreach(l, sortclauses)
{
- SortClause *sortcl = (SortClause *) lfirst(i);
+ SortClause *sortcl = (SortClause *) lfirst(l);
Node *sortkey;
PathKeyItem *pathkey;
* canonicalize_pathkeys() might replace it with a longer sublist
* later.
*/
- pathkeys = lappend(pathkeys, makeList1(pathkey));
+ pathkeys = lappend(pathkeys, list_make1(pathkey));
}
return pathkeys;
}
* problem for normal planning, but it is an issue for GEQO planning.
*/
void
-cache_mergeclause_pathkeys(Query *root, RestrictInfo *restrictinfo)
+cache_mergeclause_pathkeys(PlannerInfo *root, RestrictInfo *restrictinfo)
{
Node *key;
PathKeyItem *item;
* of the join.
*/
List *
-find_mergeclauses_for_pathkeys(Query *root,
+find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *pathkeys,
List *restrictinfos)
{
List *mergeclauses = NIL;
- List *i;
+ ListCell *i;
/* make sure we have pathkeys cached in the clauses */
foreach(i, restrictinfos)
{
- RestrictInfo *restrictinfo = lfirst(i);
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
cache_mergeclause_pathkeys(root, restrictinfo);
}
foreach(i, pathkeys)
{
- List *pathkey = lfirst(i);
+ List *pathkey = (List *) lfirst(i);
List *matched_restrictinfos = NIL;
- List *j;
+ ListCell *j;
/*
* We can match a pathkey against either left or right side of any
*/
foreach(j, restrictinfos)
{
- RestrictInfo *restrictinfo = lfirst(j);
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
/*
* We can compare canonical pathkey sublists by simple pointer
*/
if ((pathkey == restrictinfo->left_pathkey ||
pathkey == restrictinfo->right_pathkey) &&
- !ptrMember(restrictinfo, mergeclauses))
+ !list_member_ptr(mergeclauses, restrictinfo))
{
matched_restrictinfos = lappend(matched_restrictinfos,
restrictinfo);
* If we did find usable mergeclause(s) for this sort-key
* position, add them to result list.
*/
- mergeclauses = nconc(mergeclauses, matched_restrictinfos);
+ mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
}
return mergeclauses;
* just make the keys, eh?
*/
List *
-make_pathkeys_for_mergeclauses(Query *root,
+make_pathkeys_for_mergeclauses(PlannerInfo *root,
List *mergeclauses,
RelOptInfo *rel)
{
List *pathkeys = NIL;
- List *i;
+ ListCell *l;
- foreach(i, mergeclauses)
+ foreach(l, mergeclauses)
{
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
List *pathkey;
cache_mergeclause_pathkeys(root, restrictinfo);
* pathkey, a simple ptrMember test is sufficient to detect
* redundant keys.
*/
- if (!ptrMember(pathkey, pathkeys))
- pathkeys = lappend(pathkeys, pathkey);
+ pathkeys = list_append_unique_ptr(pathkeys, pathkey);
}
return pathkeys;
/*
* pathkeys_useful_for_merging
* Count the number of pathkeys that may be useful for mergejoins
- * above the given relation (by looking at its joininfo lists).
+ * above the given relation (by looking at its joininfo list).
*
* We consider a pathkey potentially useful if it corresponds to the merge
* ordering of either side of any joinclause for the rel. This might be
- * overoptimistic, since joinclauses that appear in different join lists
+ * overoptimistic, since joinclauses that require different other relations
* might never be usable at the same time, but trying to be exact is likely
* to be more trouble than it's worth.
*/
int
-pathkeys_useful_for_merging(Query *root, RelOptInfo *rel, List *pathkeys)
+pathkeys_useful_for_merging(PlannerInfo *root, RelOptInfo *rel, List *pathkeys)
{
int useful = 0;
- List *i;
+ ListCell *i;
foreach(i, pathkeys)
{
- List *pathkey = lfirst(i);
+ List *pathkey = (List *) lfirst(i);
bool matched = false;
- List *j;
+ ListCell *j;
foreach(j, rel->joininfo)
{
- JoinInfo *joininfo = (JoinInfo *) lfirst(j);
- List *k;
-
- foreach(k, joininfo->jinfo_restrictinfo)
- {
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(k);
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
- if (restrictinfo->mergejoinoperator == InvalidOid)
- continue;
- cache_mergeclause_pathkeys(root, restrictinfo);
+ if (restrictinfo->mergejoinoperator == InvalidOid)
+ continue;
+ cache_mergeclause_pathkeys(root, restrictinfo);
- /*
- * We can compare canonical pathkey sublists by simple
- * pointer equality; see compare_pathkeys.
- */
- if (pathkey == restrictinfo->left_pathkey ||
- pathkey == restrictinfo->right_pathkey)
- {
- matched = true;
- break;
- }
- }
-
- if (matched)
+ /*
+ * We can compare canonical pathkey sublists by simple
+ * pointer equality; see compare_pathkeys.
+ */
+ if (pathkey == restrictinfo->left_pathkey ||
+ pathkey == restrictinfo->right_pathkey)
+ {
+ matched = true;
break;
+ }
}
/*
*
* Unlike merge pathkeys, this is an all-or-nothing affair: it does us
* no good to order by just the first key(s) of the requested ordering.
- * So the result is always either 0 or length(root->query_pathkeys).
+ * So the result is always either 0 or list_length(root->query_pathkeys).
*/
int
-pathkeys_useful_for_ordering(Query *root, List *pathkeys)
+pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
{
if (root->query_pathkeys == NIL)
return 0; /* no special ordering requested */
if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
{
/* It's useful ... or at least the first N keys are */
- return length(root->query_pathkeys);
+ return list_length(root->query_pathkeys);
}
return 0; /* path ordering not useful */
* Shorten the given pathkey list to just the useful pathkeys.
*/
List *
-truncate_useless_pathkeys(Query *root,
+truncate_useless_pathkeys(PlannerInfo *root,
RelOptInfo *rel,
List *pathkeys)
{
* Note: not safe to modify input list destructively, but we can avoid
* copying the list if we're not actually going to change it
*/
- if (nuseful == length(pathkeys))
+ if (nuseful == list_length(pathkeys))
return pathkeys;
else
- return ltruncate(nuseful, listCopy(pathkeys));
+ return list_truncate(list_copy(pathkeys), nuseful);
}
projects / postgresql / blobdiff