* the nature and use of path keys.
*
*
- * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2007, 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.69 2005/07/02 23:00:40 tgl Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/path/pathkeys.c,v 1.82 2007/01/20 20:45:39 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
+#include "access/skey.h"
#include "nodes/makefuncs.h"
+#include "nodes/plannodes.h"
#include "optimizer/clauses.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
-#include "optimizer/planmain.h"
#include "optimizer/tlist.h"
-#include "optimizer/var.h"
#include "parser/parsetree.h"
#include "parser/parse_expr.h"
-#include "parser/parse_func.h"
#include "utils/lsyscache.h"
-#include "utils/memutils.h"
-
-
-static PathKeyItem *makePathKeyItem(Node *key, Oid sortop, bool checkType);
-static void generate_outer_join_implications(PlannerInfo *root,
- List *equi_key_set,
- Relids *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);
/*
- * makePathKeyItem
- * create a PathKeyItem node
+ * If an EC contains a const and isn't below-outer-join, any PathKey depending
+ * on it must be redundant, since there's only one possible value of the key.
*/
-static PathKeyItem *
-makePathKeyItem(Node *key, Oid sortop, bool checkType)
-{
- PathKeyItem *item = makeNode(PathKeyItem);
+#define MUST_BE_REDUNDANT(eclass) \
+ ((eclass)->ec_has_const && !(eclass)->ec_below_outer_join)
+
+static PathKey *makePathKey(EquivalenceClass *eclass, Oid opfamily,
+ int strategy, bool nulls_first);
+static PathKey *make_canonical_pathkey(PlannerInfo *root,
+ EquivalenceClass *eclass, Oid opfamily,
+ int strategy, bool nulls_first);
+static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
+static PathKey *make_pathkey_from_sortinfo(PlannerInfo *root,
+ Expr *expr, Oid ordering_op,
+ bool nulls_first,
+ bool canonicalize);
+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.
- */
- if (checkType)
- {
- Oid lefttype,
- righttype;
- op_input_types(sortop, &lefttype, &righttype);
- if (exprType(key) != lefttype)
- key = (Node *) makeRelabelType((Expr *) key,
- lefttype, -1,
- COERCE_DONTCARE);
- }
-
- item->key = key;
- item->sortop = sortop;
- return item;
-}
+/****************************************************************************
+ * PATHKEY CONSTRUCTION AND REDUNDANCY TESTING
+ ****************************************************************************/
/*
- * add_equijoined_keys
- * The given clause has a mergejoinable operator, so its two sides
- * can be considered equal after restriction clause application; in
- * particular, any pathkey mentioning one side (with the correct sortop)
- * can be expanded to include the other as well. Record the exprs and
- * associated sortops in the query's equi_key_list for future use.
+ * makePathKey
+ * create a PathKey node
*
- * The query's equi_key_list field points to a list of sublists of PathKeyItem
- * nodes, where each sublist is a set of two or more exprs+sortops that have
- * been identified as logically equivalent (and, therefore, we may consider
- * any two in a set to be equal). As described above, we will subsequently
- * use direct pointers to one of these sublists to represent any pathkey
- * that involves an equijoined variable.
+ * This does not promise to create a canonical PathKey, it's merely a
+ * convenience routine to build the specified node.
*/
-void
-add_equijoined_keys(PlannerInfo *root, RestrictInfo *restrictinfo)
+static PathKey *
+makePathKey(EquivalenceClass *eclass, Oid opfamily,
+ int strategy, bool nulls_first)
{
- Expr *clause = restrictinfo->clause;
- PathKeyItem *item1 = makePathKeyItem(get_leftop(clause),
- restrictinfo->left_sortop,
- false);
- PathKeyItem *item2 = makePathKeyItem(get_rightop(clause),
- restrictinfo->right_sortop,
- false);
- List *newset;
- ListCell *cursetlink;
-
- /* We might see a clause X=X; don't make a single-element list from it */
- if (equal(item1, item2))
- return;
-
- /*
- * Our plan is to make a two-element set, then sweep through the
- * existing equijoin sets looking for matches to item1 or item2. When
- * we find one, we remove that set from equi_key_list and union it
- * into our new set. When done, we add the new set to the front of
- * equi_key_list.
- *
- * It may well be that the two items we're given are already known to be
- * equijoin-equivalent, in which case we don't need to change our data
- * structure. If we find both of them in the same equivalence set to
- * start with, we can quit immediately.
- *
- * This is a standard UNION-FIND problem, for which there exist better
- * data structures than simple lists. If this code ever proves to be
- * a bottleneck then it could be sped up --- but for now, simple is
- * beautiful.
- */
- newset = NIL;
-
- /* cannot use foreach here because of possible lremove */
- cursetlink = list_head(root->equi_key_list);
- while (cursetlink)
- {
- 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);
+ PathKey *pk = makeNode(PathKey);
- if (item1here || item2here)
- {
- /*
- * If find both in same equivalence set, no need to do any
- * more
- */
- if (item1here && item2here)
- {
- /* Better not have seen only one in an earlier set... */
- Assert(newset == NIL);
- return;
- }
+ pk->pk_eclass = eclass;
+ pk->pk_opfamily = opfamily;
+ pk->pk_strategy = strategy;
+ pk->pk_nulls_first = nulls_first;
- /* Build the new set only when we know we must */
- if (newset == NIL)
- newset = list_make2(item1, item2);
-
- /* Found a set to merge into our new set */
- newset = list_union(newset, curset);
-
- /*
- * Remove old set from equi_key_list.
- */
- 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 = list_make2(item1, item2);
-
- root->equi_key_list = lcons(newset, root->equi_key_list);
+ return pk;
}
/*
- * generate_implied_equalities
- * Scan the completed equi_key_list for the query, and generate explicit
- * qualifications (WHERE clauses) for all the pairwise equalities not
- * already mentioned in the quals; or remove qualifications found to be
- * redundant.
- *
- * Adding deduced equalities is useful because the additional clauses help
- * the selectivity-estimation code and may allow better joins to be chosen;
- * and in fact it's *necessary* to ensure that sort keys we think are
- * equivalent really are (see src/backend/optimizer/README for more info).
- *
- * If an equi_key_list set includes any constants then we adopt a different
- * strategy: we record all the "var = const" deductions we can make, and
- * actively remove all the "var = var" clauses that are implied by the set
- * (including the clauses that originally gave rise to the set!). The reason
- * is that given input like "a = b AND b = 42", once we have deduced "a = 42"
- * there is no longer any need to apply the clause "a = b"; not only is
- * it a waste of time to check it, but we will misestimate selectivity if the
- * clause is left in. So we must remove it. For this purpose, any pathkey
- * item that mentions no Vars of the current level can be taken as a constant.
- * (The only case where this would be risky is if the item contains volatile
- * 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.
+ * make_canonical_pathkey
+ * Given the parameters for a PathKey, find any pre-existing matching
+ * pathkey in the query's list of "canonical" pathkeys. Make a new
+ * entry if there's not one already.
*
- * 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.
+ * Note that this function must not be used until after we have completed
+ * merging EquivalenceClasses.
*/
-void
-generate_implied_equalities(PlannerInfo *root)
+static PathKey *
+make_canonical_pathkey(PlannerInfo *root,
+ EquivalenceClass *eclass, Oid opfamily,
+ int strategy, bool nulls_first)
{
- ListCell *cursetlink;
-
- foreach(cursetlink, root->equi_key_list)
- {
- List *curset = (List *) lfirst(cursetlink);
- int nitems = list_length(curset);
- Relids *relids;
- bool have_consts;
- ListCell *ptr1;
- int i1;
+ PathKey *pk;
+ ListCell *lc;
+ MemoryContext oldcontext;
- /*
- * A set containing only two items cannot imply any equalities
- * beyond the one that created the set, so we can skip it ---
- * unless outer joins appear in the query.
- */
- if (nitems < 3 && !root->hasOuterJoins)
- continue;
+ /* The passed eclass might be non-canonical, so chase up to the top */
+ while (eclass->ec_merged)
+ eclass = eclass->ec_merged;
- /*
- * Collect info about relids mentioned in each item. For this
- * routine we only really care whether there are any at all in
- * each item, but process_implied_equality() needs the exact sets,
- * so we may as well pull them here.
- */
- relids = (Relids *) palloc(nitems * sizeof(Relids));
- have_consts = false;
- i1 = 0;
- foreach(ptr1, curset)
- {
- PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
-
- relids[i1] = pull_varnos(item1->key);
- if (bms_is_empty(relids[i1]))
- have_consts = true;
- i1++;
- }
+ foreach(lc, root->canon_pathkeys)
+ {
+ pk = (PathKey *) lfirst(lc);
+ if (eclass == pk->pk_eclass &&
+ opfamily == pk->pk_opfamily &&
+ strategy == pk->pk_strategy &&
+ nulls_first == pk->pk_nulls_first)
+ return pk;
+ }
- /*
- * 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);
+ /*
+ * Be sure canonical pathkeys are allocated in the main planning context.
+ * Not an issue in normal planning, but it is for GEQO.
+ */
+ oldcontext = MemoryContextSwitchTo(root->planner_cxt);
- /*
- * A set containing only two items cannot imply any equalities
- * beyond the one that created the set, so we can skip it.
- */
- if (nitems < 3)
- continue;
+ pk = makePathKey(eclass, opfamily, strategy, nulls_first);
+ root->canon_pathkeys = lappend(root->canon_pathkeys, pk);
- /*
- * 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).
- */
- i1 = 0;
- foreach(ptr1, curset)
- {
- PathKeyItem *item1 = (PathKeyItem *) lfirst(ptr1);
- bool i1_is_variable = !bms_is_empty(relids[i1]);
- ListCell *ptr2;
- int i2 = i1 + 1;
+ MemoryContextSwitchTo(oldcontext);
- for_each_cell(ptr2, lnext(ptr1))
- {
- PathKeyItem *item2 = (PathKeyItem *) lfirst(ptr2);
- bool i2_is_variable = !bms_is_empty(relids[i2]);
-
- /*
- * 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)
- {
- /*
- * 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++;
- }
- i1++;
- }
- }
+ return pk;
}
/*
- * 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.)
+ * pathkey_is_redundant
+ * Is a pathkey redundant with one already in the given list?
*
- * 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.
+ * Both the given pathkey and the list members must be canonical for this
+ * to work properly. We detect two cases:
*
- * 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.
+ * 1. If the new pathkey's equivalence class contains a constant, and isn't
+ * below an outer join, then we can disregard it as a sort key. An example:
+ * SELECT ... WHERE x = 42 ORDER BY x, y;
+ * We may as well just sort by y. Note that because of opfamily matching,
+ * this is semantically correct: we know that the equality constraint is one
+ * that actually binds the variable to a single value in the terms of any
+ * ordering operator that might go with the eclass. This rule not only lets
+ * us simplify (or even skip) explicit sorts, but also allows matching index
+ * sort orders to a query when there are don't-care index columns.
*
- * 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.
+ * 2. If the new pathkey's equivalence class is the same as that of any
+ * existing member of the pathkey list, then it is redundant. Some examples:
+ * SELECT ... ORDER BY x, x;
+ * SELECT ... ORDER BY x, x DESC;
+ * SELECT ... WHERE x = y ORDER BY x, y;
+ * In all these cases the second sort key cannot distinguish values that are
+ * considered equal by the first, and so there's no point in using it.
+ * Note in particular that we need not compare opfamily (all the opfamilies
+ * of the EC have the same notion of equality) nor sort direction.
*
- * 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.
+ * Because the equivclass.c machinery forms only one copy of any EC per query,
+ * pointer comparison is enough to decide whether canonical ECs are the same.
*/
-static void
-generate_outer_join_implications(PlannerInfo *root,
- List *equi_key_set,
- Relids *relids)
+static bool
+pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys)
{
- ListCell *l1;
-
- /* Examine each mergejoinable outer-join clause with OUTERVAR on left */
- foreach(l1, root->left_join_clauses)
- {
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(l1);
- Node *leftop = get_leftop(rinfo->clause);
- Node *rightop = get_rightop(rinfo->clause);
- ListCell *l2;
-
- /* Scan to see if it matches any element of equi_key_set */
- foreach(l2, equi_key_set)
- {
- PathKeyItem *item1 = (PathKeyItem *) lfirst(l2);
-
- if (equal(leftop, item1->key) &&
- rinfo->left_sortop == item1->sortop)
- {
- /*
- * Yes, so find constant member(s) of set and generate
- * implied INNERVAR = CONSTANT
- */
- process_implied_const_eq(root, equi_key_set, relids,
- rightop,
- rinfo->right_sortop,
- rinfo->right_relids,
- false);
- /*
- * We can remove the explicit 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);
-
- /* No need to match against remaining set members */
- break;
- }
- }
- }
+ EquivalenceClass *new_ec = new_pathkey->pk_eclass;
+ ListCell *lc;
- /* Examine each mergejoinable outer-join clause with OUTERVAR on right */
- foreach(l1, root->right_join_clauses)
- {
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(l1);
- Node *leftop = get_leftop(rinfo->clause);
- Node *rightop = get_rightop(rinfo->clause);
- ListCell *l2;
+ /* Assert we've been given canonical pathkeys */
+ Assert(!new_ec->ec_merged);
- /* Scan to see if it matches any element of equi_key_set */
- foreach(l2, equi_key_set)
- {
- PathKeyItem *item1 = (PathKeyItem *) lfirst(l2);
+ /* Check for EC containing a constant --- unconditionally redundant */
+ if (MUST_BE_REDUNDANT(new_ec))
+ return true;
- if (equal(rightop, item1->key) &&
- rinfo->right_sortop == item1->sortop)
- {
- /*
- * Yes, so find constant member(s) of set and generate
- * implied INNERVAR = CONSTANT
- */
- process_implied_const_eq(root, equi_key_set, relids,
- leftop,
- rinfo->left_sortop,
- rinfo->left_relids,
- false);
- /*
- * We can remove the explicit 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);
-
- /* No need to match against remaining set members */
- break;
- }
- }
- }
-
- /* Examine each mergejoinable full-join clause */
- foreach(l1, root->full_join_clauses)
+ /* If same EC already used in list, then redundant */
+ foreach(lc, pathkeys)
{
- RestrictInfo *rinfo = (RestrictInfo *) lfirst(l1);
- Node *leftop = get_leftop(rinfo->clause);
- Node *rightop = get_rightop(rinfo->clause);
- int i1 = 0;
- ListCell *l2;
-
- /* Scan to see if it matches any element of equi_key_set */
- foreach(l2, equi_key_set)
- {
- PathKeyItem *item1 = (PathKeyItem *) lfirst(l2);
- CoalesceExpr *cexpr = (CoalesceExpr *) item1->key;
-
- /*
- * Try to match a pathkey containing a COALESCE() expression
- * to the join 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 (IsA(cexpr, CoalesceExpr) &&
- list_length(cexpr->args) == 2 &&
- equal(leftop, (Node *) linitial(cexpr->args)) &&
- equal(rightop, (Node *) lsecond(cexpr->args)) &&
- rinfo->left_sortop == item1->sortop &&
- rinfo->right_sortop == item1->sortop)
- {
- /*
- * Yes, 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->key,
- item1->sortop,
- relids[i1],
- true);
- /*
- * We can remove the explicit 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);
-
- /* No need to match against remaining set members */
- break;
- }
- i1++;
- }
- }
-}
+ PathKey *old_pathkey = (PathKey *) lfirst(lc);
-/*
- * process_implied_const_eq
- * Apply process_implied_equality with the given item and each
- * pseudoconstant member of equi_key_set.
- *
- * This is just a subroutine to save some cruft in
- * generate_outer_join_implications. equi_key_set and relids are as in
- * 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);
+ /* Assert we've been given canonical pathkeys */
+ Assert(!old_pathkey->pk_eclass->ec_merged);
- if (bms_is_empty(relids[i]))
- {
- process_implied_equality(root,
- item1, item2->key,
- sortop1, item2->sortop,
- item1_relids, NULL,
- delete_it);
- found = true;
- }
- i++;
+ if (new_ec == old_pathkey->pk_eclass)
+ return true;
}
- /* Caller screwed up if no constants in list */
- Assert(found);
-}
-
-/*
- * exprs_known_equal
- * Detect whether two expressions are known equal due to equijoin clauses.
- *
- * Note: does not bother to check for "equal(item1, item2)"; caller must
- * check that case if it's possible to pass identical items.
- */
-bool
-exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
-{
- ListCell *cursetlink;
- foreach(cursetlink, root->equi_key_list)
- {
- List *curset = (List *) lfirst(cursetlink);
- bool item1member = false;
- bool item2member = false;
- ListCell *ptr;
-
- foreach(ptr, curset)
- {
- PathKeyItem *pitem = (PathKeyItem *) lfirst(ptr);
-
- if (equal(item1, pitem->key))
- item1member = true;
- else if (equal(item2, pitem->key))
- item2member = true;
- /* Exit as soon as equality is proven */
- if (item1member && item2member)
- return true;
- }
- }
return false;
}
-
-/*
- * make_canonical_pathkey
- * Given a PathKeyItem, find the equi_key_list subset it is a member of,
- * if any. If so, return a pointer to that sublist, which is the
- * canonical representation (for this query) of that PathKeyItem's
- * equivalence set. If it is not found, add a singleton "equivalence set"
- * to the equi_key_list and return that --- see compare_pathkeys.
- *
- * Note that this function must not be used until after we have completed
- * scanning the WHERE clause for equijoin operators.
- */
-static List *
-make_canonical_pathkey(PlannerInfo *root, PathKeyItem *item)
-{
- List *newset;
- ListCell *cursetlink;
-
- foreach(cursetlink, root->equi_key_list)
- {
- List *curset = (List *) lfirst(cursetlink);
-
- if (list_member(curset, item))
- return curset;
- }
- newset = list_make1(item);
- root->equi_key_list = lcons(newset, root->equi_key_list);
- return newset;
-}
-
/*
* canonicalize_pathkeys
* Convert a not-necessarily-canonical pathkeys list to canonical form.
*
* Note that this function must not be used until after we have completed
- * scanning the WHERE clause for equijoin operators.
+ * merging EquivalenceClasses.
*/
List *
canonicalize_pathkeys(PlannerInfo *root, List *pathkeys)
foreach(l, pathkeys)
{
- List *pathkey = (List *) lfirst(l);
- PathKeyItem *item;
- List *cpathkey;
+ PathKey *pathkey = (PathKey *) lfirst(l);
+ EquivalenceClass *eclass;
+ PathKey *cpathkey;
- /*
- * It's sufficient to look at the first entry in the sublist; if
- * there are more entries, they're already part of an equivalence
- * set by definition.
- */
- Assert(pathkey != NIL);
- item = (PathKeyItem *) linitial(pathkey);
- cpathkey = make_canonical_pathkey(root, item);
+ /* Find the canonical (merged) EquivalenceClass */
+ eclass = pathkey->pk_eclass;
+ while (eclass->ec_merged)
+ eclass = eclass->ec_merged;
/*
- * Eliminate redundant ordering requests --- ORDER BY A,A is the
- * same as ORDER BY A. We want to check this only after we have
- * canonicalized the keys, so that equivalent-key knowledge is
- * used when deciding if an item is redundant.
+ * If we can tell it's redundant just from the EC, skip.
+ * pathkey_is_redundant would notice that, but we needn't even bother
+ * constructing the node...
*/
- if (!list_member_ptr(new_pathkeys, cpathkey))
+ if (MUST_BE_REDUNDANT(eclass))
+ continue;
+
+ /* OK, build a canonicalized PathKey struct */
+ cpathkey = make_canonical_pathkey(root,
+ eclass,
+ pathkey->pk_opfamily,
+ pathkey->pk_strategy,
+ pathkey->pk_nulls_first);
+
+ /* Add to list unless redundant */
+ if (!pathkey_is_redundant(cpathkey, new_pathkeys))
new_pathkeys = lappend(new_pathkeys, cpathkey);
}
return new_pathkeys;
}
-
/*
- * count_canonical_peers
- * Given a PathKeyItem, find the equi_key_list subset it is a member of,
- * if any. If so, return the number of other members of the set.
- * If not, return 0 (without actually adding it to our equi_key_list).
+ * make_pathkey_from_sortinfo
+ * Given an expression, a sortop, and a nulls-first flag, create
+ * a PathKey. If canonicalize = true, the result is a "canonical"
+ * PathKey, otherwise not. (But note it might be redundant anyway.)
*
- * This is a hack to support the rather bogus heuristics in
- * convert_subquery_pathkeys.
+ * canonicalize should always be TRUE after EquivalenceClass merging has
+ * been performed, but FALSE if we haven't done EquivalenceClass merging yet.
*/
-static int
-count_canonical_peers(PlannerInfo *root, PathKeyItem *item)
+static PathKey *
+make_pathkey_from_sortinfo(PlannerInfo *root,
+ Expr *expr, Oid ordering_op,
+ bool nulls_first,
+ bool canonicalize)
{
- ListCell *cursetlink;
+ Oid equality_op;
+ List *opfamilies;
+ Oid opfamily,
+ lefttype,
+ righttype;
+ int strategy;
+ ListCell *lc;
+ EquivalenceClass *eclass;
- foreach(cursetlink, root->equi_key_list)
- {
- List *curset = (List *) lfirst(cursetlink);
+ /*
+ * An ordering operator fully determines the behavior of its opfamily,
+ * so could only meaningfully appear in one family --- or perhaps two
+ * if one builds a reverse-sort opfamily, but there's not much point in
+ * that anymore. But EquivalenceClasses need to contain opfamily lists
+ * based on the family membership of equality operators, which could
+ * easily be bigger. So, look up the equality operator that goes with
+ * the ordering operator (this should be unique) and get its membership.
+ */
+ equality_op = get_equality_op_for_ordering_op(ordering_op);
+ if (!OidIsValid(equality_op)) /* shouldn't happen */
+ elog(ERROR, "could not find equality operator for ordering operator %u",
+ ordering_op);
+ opfamilies = get_mergejoin_opfamilies(equality_op);
+ if (!opfamilies) /* certainly should find some */
+ elog(ERROR, "could not find opfamilies for ordering operator %u",
+ ordering_op);
- if (list_member(curset, item))
- return list_length(curset) - 1;
+ /*
+ * Next we have to determine the strategy number to put into the pathkey.
+ * In the presence of reverse-sort opclasses there might be two answers.
+ * We prefer the one associated with the first opfamilies member that
+ * this ordering_op appears in (this will be consistently defined in
+ * normal system operation; see comments for get_mergejoin_opfamilies()).
+ */
+ opfamily = InvalidOid;
+ strategy = 0;
+ foreach(lc, opfamilies)
+ {
+ opfamily = lfirst_oid(lc);
+ strategy = get_op_opfamily_strategy(ordering_op, opfamily);
+ if (strategy)
+ break;
}
- return 0;
+ if (!(strategy == BTLessStrategyNumber ||
+ strategy == BTGreaterStrategyNumber))
+ elog(ERROR, "ordering operator %u is has wrong strategy number %d",
+ ordering_op, strategy);
+
+ /* Need the declared input type of the operator, too */
+ op_input_types(ordering_op, &lefttype, &righttype);
+ Assert(lefttype == righttype);
+
+ /* Now find or create a matching EquivalenceClass */
+ eclass = get_eclass_for_sort_expr(root, expr, lefttype, opfamilies);
+
+ /* And finally we can find or create a PathKey node */
+ if (canonicalize)
+ return make_canonical_pathkey(root, eclass, opfamily,
+ strategy, nulls_first);
+ else
+ return makePathKey(eclass, opfamily, strategy, nulls_first);
}
+
/****************************************************************************
* PATHKEY COMPARISONS
****************************************************************************/
* one is "better" than the other.
*
* This function may only be applied to canonicalized pathkey lists.
- * In the canonical representation, sublists can be checked for equality
+ * In the canonical representation, pathkeys can be checked for equality
* by simple pointer comparison.
*/
PathKeysComparison
forboth(key1, keys1, key2, keys2)
{
- List *subkey1 = (List *) lfirst(key1);
- List *subkey2 = (List *) lfirst(key2);
+ PathKey *pathkey1 = (PathKey *) lfirst(key1);
+ PathKey *pathkey2 = (PathKey *) lfirst(key2);
/*
- * XXX would like to check that we've been given canonicalized
- * input, but PlannerInfo not accessible here...
+ * XXX would like to check that we've been given canonicalized input,
+ * but PlannerInfo not accessible here...
*/
#ifdef NOT_USED
- Assert(list_member_ptr(root->equi_key_list, subkey1));
- Assert(list_member_ptr(root->equi_key_list, subkey2));
+ Assert(list_member_ptr(root->canon_pathkeys, pathkey1));
+ Assert(list_member_ptr(root->canon_pathkeys, pathkey2));
#endif
- /*
- * We will never have two subkeys where one is a subset of the
- * other, because of the canonicalization process. Either they
- * are equal or they ain't. Furthermore, we only need pointer
- * comparison to detect equality.
- */
- if (subkey1 != subkey2)
+ if (pathkey1 != pathkey2)
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 == NULL && key2 == NULL)
- return PATHKEYS_EQUAL;
- if (key1 != NULL)
- 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)
-{
- ListCell *key1,
- *key2;
-
- forboth(key1, keys1, key2, keys2)
- {
- List *subkey1 = (List *) lfirst(key1);
- List *subkey2 = (List *) lfirst(key2);
-
- Assert(list_length(subkey1) == 1);
- Assert(list_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.)
+ * therefore not a subset.
*/
if (key1 == NULL && key2 == NULL)
return PATHKEYS_EQUAL;
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
Path *path = (Path *) lfirst(l);
/*
- * Since cost comparison is a lot cheaper than pathkey comparison,
- * do that first. (XXX is that still true?)
+ * Since cost comparison is a lot cheaper than pathkey comparison, do
+ * that first. (XXX is that still true?)
*/
if (matched_path != NULL &&
compare_path_costs(matched_path, path, cost_criterion) <= 0)
Path *path = (Path *) lfirst(l);
/*
- * Since cost comparison is a lot cheaper than pathkey comparison,
- * do that first.
+ * Since cost comparison is a lot cheaper than pathkey comparison, do
+ * that first.
*/
if (matched_path != NULL &&
- compare_fractional_path_costs(matched_path, path, fraction) <= 0)
+ compare_fractional_path_costs(matched_path, path, fraction) <= 0)
continue;
if (pathkeys_contained_in(pathkeys, path->pathkeys))
* Build a pathkeys list that describes the ordering induced by an index
* scan using the given index. (Note that an unordered index doesn't
* induce any ordering; such an index will have no sortop OIDS in
- * its "ordering" field, and we will return NIL.)
+ * its sortops arrays, and we will return NIL.)
*
* If 'scandir' is BackwardScanDirection, attempt to build pathkeys
* representing a backwards scan of the index. Return NIL if can't do it.
*
+ * The result is canonical, meaning that redundant pathkeys are removed;
+ * it may therefore have fewer entries than there are index columns.
+ *
* We generate the full pathkeys list whether or not all are useful for the
* current query. Caller should do truncate_useless_pathkeys().
*/
ScanDirection scandir)
{
List *retval = NIL;
- int *indexkeys = index->indexkeys;
- Oid *ordering = index->ordering;
ListCell *indexprs_item = list_head(index->indexprs);
+ int i;
- while (*ordering != InvalidOid)
+ for (i = 0; i < index->ncolumns; i++)
{
- PathKeyItem *item;
Oid sortop;
- Node *indexkey;
- List *cpathkey;
+ bool nulls_first;
+ int ikey;
+ Expr *indexkey;
+ PathKey *cpathkey;
- sortop = *ordering;
if (ScanDirectionIsBackward(scandir))
{
- sortop = get_commutator(sortop);
- if (sortop == InvalidOid)
- break; /* oops, no reverse sort operator? */
+ sortop = index->revsortop[i];
+ nulls_first = !index->nulls_first[i];
+ }
+ else
+ {
+ sortop = index->fwdsortop[i];
+ nulls_first = index->nulls_first[i];
}
- if (*indexkeys != 0)
+ if (!OidIsValid(sortop))
+ break; /* no more orderable columns */
+
+ ikey = index->indexkeys[i];
+ if (ikey != 0)
{
/* simple index column */
- indexkey = (Node *) find_indexkey_var(root, index->rel,
- *indexkeys);
+ indexkey = (Expr *) find_indexkey_var(root, index->rel, ikey);
}
else
{
/* expression --- assume we need not copy it */
if (indexprs_item == NULL)
elog(ERROR, "wrong number of index expressions");
- indexkey = (Node *) lfirst(indexprs_item);
+ indexkey = (Expr *) lfirst(indexprs_item);
indexprs_item = lnext(indexprs_item);
}
- /* OK, make a sublist for this sort key */
- item = makePathKeyItem(indexkey, sortop, true);
- cpathkey = make_canonical_pathkey(root, item);
+ /* OK, make a canonical pathkey for this sort key */
+ cpathkey = make_pathkey_from_sortinfo(root,
+ indexkey,
+ sortop,
+ nulls_first,
+ true);
- /*
- * Eliminate redundant ordering info; could happen if query is
- * such that index keys are equijoined...
- */
- if (!list_member_ptr(retval, cpathkey))
+ /* Add to list unless redundant */
+ if (!pathkey_is_redundant(cpathkey, retval))
retval = lappend(retval, cpathkey);
-
- indexkeys++;
- ordering++;
}
return retval;
/*
* convert_subquery_pathkeys
* Build a pathkeys list that describes the ordering of a subquery's
- * result, in the terms of the outer query. This is essentially a
+ * result, in the terms of the outer query. This is essentially a
* task of conversion.
*
* 'rel': outer query's RelOptInfo for the subquery relation.
foreach(i, subquery_pathkeys)
{
- List *sub_pathkey = (List *) lfirst(i);
+ PathKey *sub_pathkey = (PathKey *) lfirst(i);
+ EquivalenceClass *sub_eclass = sub_pathkey->pk_eclass;
+ PathKey *best_pathkey = NULL;
+ int best_score = -1;
ListCell *j;
- PathKeyItem *best_item = NULL;
- int best_score = 0;
- List *cpathkey;
/*
- * The sub_pathkey could contain multiple elements (representing
- * knowledge that multiple items are effectively equal). Each
- * element might match none, one, or more of the output columns
- * that are visible to the outer query. This means we may have
- * multiple possible representations of the sub_pathkey in the
- * context of the outer query. Ideally we would generate them all
- * and put them all into a pathkey list of the outer query,
- * thereby propagating equality knowledge up to the outer query.
- * Right now we cannot do so, because the outer query's canonical
- * pathkey sets are already frozen when this is called. Instead
- * we prefer the one that has the highest "score" (number of
- * canonical pathkey peers, plus one if it matches the outer
- * query_pathkeys). This is the most likely to be useful in the
- * outer query.
+ * The sub_pathkey's EquivalenceClass could contain multiple elements
+ * (representing knowledge that multiple items are effectively equal).
+ * Each element might match none, one, or more of the output columns
+ * that are visible to the outer query. This means we may have
+ * multiple possible representations of the sub_pathkey in the context
+ * of the outer query. Ideally we would generate them all and put
+ * them all into an EC of the outer query, thereby propagating
+ * equality knowledge up to the outer query. Right now we cannot do
+ * so, because the outer query's EquivalenceClasses are already frozen
+ * when this is called. Instead we prefer the one that has the highest
+ * "score" (number of EC peers, plus one if it matches the outer
+ * query_pathkeys). This is the most likely to be useful in the outer
+ * query.
*/
- foreach(j, sub_pathkey)
+ foreach(j, sub_eclass->ec_members)
{
- PathKeyItem *sub_item = (PathKeyItem *) lfirst(j);
- Node *sub_key = sub_item->key;
+ EquivalenceMember *sub_member = (EquivalenceMember *) lfirst(j);
+ Expr *sub_expr = sub_member->em_expr;
+ Expr *rtarg;
ListCell *k;
+ /*
+ * We handle two cases: the sub_pathkey key can be either an exact
+ * match for a targetlist entry, or a RelabelType of a targetlist
+ * entry. (The latter case is worth extra code because it arises
+ * frequently in connection with varchar fields.)
+ */
+ if (IsA(sub_expr, RelabelType))
+ rtarg = ((RelabelType *) sub_expr)->arg;
+ else
+ rtarg = NULL;
+
foreach(k, sub_tlist)
{
TargetEntry *tle = (TargetEntry *) lfirst(k);
+ Expr *outer_expr;
+ EquivalenceClass *outer_ec;
+ PathKey *outer_pk;
+ int score;
+
+ /* resjunk items aren't visible to outer query */
+ if (tle->resjunk)
+ continue;
- if (!tle->resjunk &&
- equal(tle->expr, sub_key))
+ if (equal(tle->expr, sub_expr))
{
- /* Found a representation for this sub_key */
- Var *outer_var;
- PathKeyItem *outer_item;
- int score;
-
- outer_var = makeVar(rel->relid,
- tle->resno,
- exprType((Node *) tle->expr),
- exprTypmod((Node *) tle->expr),
- 0);
- outer_item = makePathKeyItem((Node *) outer_var,
- sub_item->sortop,
- true);
- /* score = # of mergejoin peers */
- score = count_canonical_peers(root, outer_item);
- /* +1 if it matches the proper query_pathkeys item */
- if (retvallen < outer_query_keys &&
- list_member(list_nth(root->query_pathkeys, retvallen), outer_item))
- score++;
- if (score > best_score)
- {
- best_item = outer_item;
- best_score = score;
- }
+ /* Exact match */
+ outer_expr = (Expr *)
+ makeVar(rel->relid,
+ tle->resno,
+ exprType((Node *) tle->expr),
+ exprTypmod((Node *) tle->expr),
+ 0);
+ }
+ else if (rtarg && equal(tle->expr, rtarg))
+ {
+ /* Match after discarding RelabelType */
+ outer_expr = (Expr *)
+ makeVar(rel->relid,
+ tle->resno,
+ exprType((Node *) tle->expr),
+ exprTypmod((Node *) tle->expr),
+ 0);
+ outer_expr = (Expr *)
+ makeRelabelType((Expr *) outer_expr,
+ ((RelabelType *) sub_expr)->resulttype,
+ ((RelabelType *) sub_expr)->resulttypmod,
+ ((RelabelType *) sub_expr)->relabelformat);
+ }
+ else
+ continue;
+
+ /* Found a representation for this sub_pathkey */
+ outer_ec = get_eclass_for_sort_expr(root,
+ outer_expr,
+ sub_member->em_datatype,
+ sub_eclass->ec_opfamilies);
+ outer_pk = make_canonical_pathkey(root,
+ outer_ec,
+ sub_pathkey->pk_opfamily,
+ sub_pathkey->pk_strategy,
+ sub_pathkey->pk_nulls_first);
+ /* score = # of equivalence peers */
+ score = list_length(outer_ec->ec_members) - 1;
+ /* +1 if it matches the proper query_pathkeys item */
+ if (retvallen < outer_query_keys &&
+ list_nth(root->query_pathkeys, retvallen) == outer_pk)
+ score++;
+ if (score > best_score)
+ {
+ best_pathkey = outer_pk;
+ best_score = score;
}
}
}
* If we couldn't find a representation of this sub_pathkey, we're
* done (we can't use the ones to its right, either).
*/
- if (!best_item)
+ if (!best_pathkey)
break;
- /* Canonicalize the chosen item (we did not before) */
- cpathkey = make_canonical_pathkey(root, best_item);
-
/*
* Eliminate redundant ordering info; could happen if outer query
- * equijoins subquery keys...
+ * equivalences subquery keys...
*/
- if (!list_member_ptr(retval, cpathkey))
+ if (!pathkey_is_redundant(best_pathkey, retval))
{
- retval = lappend(retval, cpathkey);
+ retval = lappend(retval, best_pathkey);
retvallen++;
}
}
/*
* build_join_pathkeys
* Build the path keys for a join relation constructed by mergejoin or
- * nestloop join. These keys should include all the path key vars of the
- * outer path (since the join will retain the ordering of the outer path)
- * plus any vars of the inner path that are equijoined to the outer vars.
- *
- * Per the discussion in backend/optimizer/README, equijoined inner vars
- * can be considered path keys of the result, just the same as the outer
- * vars they were joined with; furthermore, it doesn't matter what kind
- * of join algorithm is actually used.
+ * nestloop join. This is normally the same as the outer path's keys.
*
* 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.
*
+ * We truncate away any pathkeys that are uninteresting for higher joins.
+ *
* '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
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
- * a darn thing here! The inner-rel vars we used to need to add are
- * *already* part of the outer pathkey!
+ * 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 a darn thing
+ * here!
*
* We do, however, need to truncate the pathkeys list, since it may
* contain pathkeys that were useful for forming this joinrel but are
* Generate a pathkeys list that represents the sort order specified
* by a list of SortClauses (GroupClauses will work too!)
*
- * NB: the result is NOT in canonical form, but must be passed through
- * canonicalize_pathkeys() before it can be used for comparisons or
- * labeling relation sort orders. (We do things this way because
- * grouping_planner needs to be able to construct requested pathkeys
- * before the pathkey equivalence sets have been created for the query.)
+ * If canonicalize is TRUE, the resulting PathKeys are all in canonical form;
+ * otherwise not. canonicalize should always be TRUE after EquivalenceClass
+ * merging has been performed, but FALSE if we haven't done EquivalenceClass
+ * merging yet. (We provide this option because grouping_planner() needs to
+ * be able to represent requested pathkeys before the equivalence classes have
+ * been created for the query.)
*
* 'sortclauses' is a list of SortClause or GroupClause nodes
* 'tlist' is the targetlist to find the referenced tlist entries in
*/
List *
-make_pathkeys_for_sortclauses(List *sortclauses,
- List *tlist)
+make_pathkeys_for_sortclauses(PlannerInfo *root,
+ List *sortclauses,
+ List *tlist,
+ bool canonicalize)
{
List *pathkeys = NIL;
ListCell *l;
foreach(l, sortclauses)
{
SortClause *sortcl = (SortClause *) lfirst(l);
- Node *sortkey;
- PathKeyItem *pathkey;
-
- sortkey = get_sortgroupclause_expr(sortcl, tlist);
- pathkey = makePathKeyItem(sortkey, sortcl->sortop, true);
-
- /*
- * The pathkey becomes a one-element sublist, for now;
- * canonicalize_pathkeys() might replace it with a longer sublist
- * later.
- */
- pathkeys = lappend(pathkeys, list_make1(pathkey));
+ Expr *sortkey;
+ PathKey *pathkey;
+
+ sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist);
+ pathkey = make_pathkey_from_sortinfo(root,
+ sortkey,
+ sortcl->sortop,
+ sortcl->nulls_first,
+ canonicalize);
+
+ /* Canonical form eliminates redundant ordering keys */
+ if (canonicalize)
+ {
+ if (!pathkey_is_redundant(pathkey, pathkeys))
+ pathkeys = lappend(pathkeys, pathkey);
+ }
+ else
+ pathkeys = lappend(pathkeys, pathkey);
}
return pathkeys;
}
****************************************************************************/
/*
- * cache_mergeclause_pathkeys
- * Make the cached pathkeys valid in a mergeclause restrictinfo.
+ * cache_mergeclause_eclasses
+ * Make the cached EquivalenceClass links valid in a mergeclause
+ * restrictinfo.
*
- * RestrictInfo contains fields in which we may cache the result
- * of looking up the canonical pathkeys for the left and right sides
- * of the mergeclause. (Note that in normal cases they will be the
- * same, but not if the mergeclause appears above an OUTER JOIN.)
- * This is a worthwhile savings because these routines will be invoked
- * many times when dealing with a many-relation query.
- *
- * We have to be careful that the cached values are palloc'd in the same
- * context the RestrictInfo node itself is in. This is not currently a
- * problem for normal planning, but it is an issue for GEQO planning.
+ * RestrictInfo contains fields in which we may cache pointers to
+ * EquivalenceClasses for the left and right inputs of the mergeclause.
+ * (If the mergeclause is a true equivalence clause these will be the
+ * same EquivalenceClass, otherwise not.)
*/
void
-cache_mergeclause_pathkeys(PlannerInfo *root, RestrictInfo *restrictinfo)
+cache_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo)
{
- Node *key;
- PathKeyItem *item;
- MemoryContext oldcontext;
-
- Assert(restrictinfo->mergejoinoperator != InvalidOid);
+ Assert(restrictinfo->mergeopfamilies != NIL);
- if (restrictinfo->left_pathkey == NIL)
+ /* the cached values should be either both set or both not */
+ if (restrictinfo->left_ec == NULL)
{
- oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(restrictinfo));
- key = get_leftop(restrictinfo->clause);
- item = makePathKeyItem(key, restrictinfo->left_sortop, false);
- restrictinfo->left_pathkey = make_canonical_pathkey(root, item);
- MemoryContextSwitchTo(oldcontext);
- }
- if (restrictinfo->right_pathkey == NIL)
- {
- oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(restrictinfo));
- key = get_rightop(restrictinfo->clause);
- item = makePathKeyItem(key, restrictinfo->right_sortop, false);
- restrictinfo->right_pathkey = make_canonical_pathkey(root, item);
- MemoryContextSwitchTo(oldcontext);
+ Expr *clause = restrictinfo->clause;
+ Oid lefttype,
+ righttype;
+
+ /* Need the declared input types of the operator */
+ op_input_types(((OpExpr *) clause)->opno, &lefttype, &righttype);
+
+ /* Find or create a matching EquivalenceClass for each side */
+ restrictinfo->left_ec =
+ get_eclass_for_sort_expr(root,
+ (Expr *) get_leftop(clause),
+ lefttype,
+ restrictinfo->mergeopfamilies);
+ restrictinfo->right_ec =
+ get_eclass_for_sort_expr(root,
+ (Expr *) get_rightop(clause),
+ righttype,
+ restrictinfo->mergeopfamilies);
}
+ else
+ Assert(restrictinfo->right_ec != NULL);
}
/*
* If successful, it returns a list of mergeclauses.
*
* 'pathkeys' is a pathkeys list showing the ordering of an input path.
- * It doesn't matter whether it is for the inner or outer path.
+ * 'outer_keys' is TRUE if these keys are for the outer input path,
+ * FALSE if for inner.
* 'restrictinfos' is a list of mergejoinable restriction clauses for the
* join relation being formed.
*
+ * The restrictinfos must be marked (via outer_is_left) to show which side
+ * of each clause is associated with the current outer path. (See
+ * select_mergejoin_clauses())
+ *
* The result is NIL if no merge can be done, else a maximal list of
* usable mergeclauses (represented as a list of their restrictinfo nodes).
- *
- * XXX Ideally we ought to be considering context, ie what path orderings
- * are available on the other side of the join, rather than just making
- * an arbitrary choice among the mergeclauses that will work for this side
- * of the join.
*/
List *
find_mergeclauses_for_pathkeys(PlannerInfo *root,
List *pathkeys,
+ bool outer_keys,
List *restrictinfos)
{
List *mergeclauses = NIL;
ListCell *i;
- /* make sure we have pathkeys cached in the clauses */
+ /* make sure we have eclasses cached in the clauses */
foreach(i, restrictinfos)
{
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(i);
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(i);
- cache_mergeclause_pathkeys(root, restrictinfo);
+ cache_mergeclause_eclasses(root, rinfo);
}
foreach(i, pathkeys)
{
- List *pathkey = (List *) lfirst(i);
+ PathKey *pathkey = (PathKey *) lfirst(i);
+ EquivalenceClass *pathkey_ec = pathkey->pk_eclass;
List *matched_restrictinfos = NIL;
ListCell *j;
- /*
- * We can match a pathkey against either left or right side of any
- * mergejoin clause. (We examine both sides since we aren't told
- * if the given pathkeys are for inner or outer input path; no
- * confusion is possible.) Furthermore, if there are multiple
- * matching clauses, take them all. In plain inner-join scenarios
- * we expect only one match, because redundant-mergeclause
- * elimination will have removed any redundant mergeclauses from
- * the input list. However, in outer-join scenarios there might be
- * multiple matches. An example is
+ /*----------
+ * A mergejoin clause matches a pathkey if it has the same EC.
+ * If there are multiple matching clauses, take them all. In plain
+ * inner-join scenarios we expect only one match, because
+ * equivalence-class processing will have removed any redundant
+ * mergeclauses. However, in outer-join scenarios there might be
+ * multiple matches. An example is
+ *
+ * select * from a full join b
+ * on a.v1 = b.v1 and a.v2 = b.v2 and a.v1 = b.v2;
+ *
+ * Given the pathkeys ({a.v1}, {a.v2}) it is okay to return all three
+ * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and indeed
+ * we *must* do so or we will be unable to form a valid plan.
*
- * select * from a full join b on a.v1 = b.v1 and a.v2 = b.v2 and
- * a.v1 = b.v2;
+ * We expect that the given pathkeys list is canonical, which means
+ * no two members have the same EC, so it's not possible for this
+ * code to enter the same mergeclause into the result list twice.
*
- * Given the pathkeys ((a.v1), (a.v2)) it is okay to return all three
- * clauses (in the order a.v1=b.v1, a.v1=b.v2, a.v2=b.v2) and
- * indeed we *must* do so or we will be unable to form a valid
- * plan.
+ * XXX it's possible that multiple matching clauses might have
+ * different ECs on the other side, in which case the order we put
+ * them into our result makes a difference in the pathkeys required
+ * for the other input path. However this routine hasn't got any info
+ * about which order would be best, so for now we disregard that case
+ * (which is probably a corner case anyway).
+ *----------
*/
foreach(j, restrictinfos)
{
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
-
- /*
- * We can compare canonical pathkey sublists by simple pointer
- * equality; see compare_pathkeys.
- */
- if ((pathkey == restrictinfo->left_pathkey ||
- pathkey == restrictinfo->right_pathkey) &&
- !list_member_ptr(mergeclauses, restrictinfo))
- {
- matched_restrictinfos = lappend(matched_restrictinfos,
- restrictinfo);
- }
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(j);
+ EquivalenceClass *clause_ec;
+
+ if (outer_keys)
+ clause_ec = rinfo->outer_is_left ?
+ rinfo->left_ec : rinfo->right_ec;
+ else
+ clause_ec = rinfo->outer_is_left ?
+ rinfo->right_ec : rinfo->left_ec;
+ if (clause_ec == pathkey_ec)
+ matched_restrictinfos = lappend(matched_restrictinfos, rinfo);
}
/*
* If we didn't find a mergeclause, we're done --- any additional
- * sort-key positions in the pathkeys are useless. (But we can
- * still mergejoin if we found at least one mergeclause.)
+ * sort-key positions in the pathkeys are useless. (But we can still
+ * mergejoin if we found at least one mergeclause.)
*/
if (matched_restrictinfos == NIL)
break;
/*
- * If we did find usable mergeclause(s) for this sort-key
- * position, add them to result list.
+ * If we did find usable mergeclause(s) for this sort-key position,
+ * add them to result list.
*/
mergeclauses = list_concat(mergeclauses, matched_restrictinfos);
}
}
/*
- * make_pathkeys_for_mergeclauses
+ * select_outer_pathkeys_for_merge
+ * Builds a pathkey list representing a possible sort ordering
+ * that can be used with the given mergeclauses.
+ *
+ * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
+ * that will be used in a merge join.
+ * 'joinrel' is the join relation we are trying to construct.
+ *
+ * The restrictinfos must be marked (via outer_is_left) to show which side
+ * of each clause is associated with the current outer path. (See
+ * select_mergejoin_clauses())
+ *
+ * Returns a pathkeys list that can be applied to the outer relation.
+ *
+ * Since we assume here that a sort is required, there is no particular use
+ * in matching any available ordering of the outerrel. (joinpath.c has an
+ * entirely separate code path for considering sort-free mergejoins.) Rather,
+ * it's interesting to try to match the requested query_pathkeys so that a
+ * second output sort may be avoided; and failing that, we try to list "more
+ * popular" keys (those with the most unmatched EquivalenceClass peers)
+ * earlier, in hopes of making the resulting ordering useful for as many
+ * higher-level mergejoins as possible.
+ */
+List *
+select_outer_pathkeys_for_merge(PlannerInfo *root,
+ List *mergeclauses,
+ RelOptInfo *joinrel)
+{
+ List *pathkeys = NIL;
+ int nClauses = list_length(mergeclauses);
+ EquivalenceClass **ecs;
+ int *scores;
+ int necs;
+ ListCell *lc;
+ int j;
+
+ /* Might have no mergeclauses */
+ if (nClauses == 0)
+ return NIL;
+
+ /*
+ * Make arrays of the ECs used by the mergeclauses (dropping any
+ * duplicates) and their "popularity" scores.
+ */
+ ecs = (EquivalenceClass **) palloc(nClauses * sizeof(EquivalenceClass *));
+ scores = (int *) palloc(nClauses * sizeof(int));
+ necs = 0;
+
+ foreach(lc, mergeclauses)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ EquivalenceClass *oeclass;
+ int score;
+ ListCell *lc2;
+
+ /* get the outer eclass */
+ cache_mergeclause_eclasses(root, rinfo);
+
+ if (rinfo->outer_is_left)
+ oeclass = rinfo->left_ec;
+ else
+ oeclass = rinfo->right_ec;
+
+ /* reject duplicates */
+ for (j = 0; j < necs; j++)
+ {
+ if (ecs[j] == oeclass)
+ break;
+ }
+ if (j < necs)
+ continue;
+
+ /* compute score */
+ score = 0;
+ foreach(lc2, oeclass->ec_members)
+ {
+ EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+
+ /* Potential future join partner? */
+ if (!em->em_is_const && !em->em_is_child &&
+ !bms_overlap(em->em_relids, joinrel->relids))
+ score++;
+ }
+
+ ecs[necs] = oeclass;
+ scores[necs] = score;
+ necs++;
+ }
+
+ /*
+ * Find out if we have all the ECs mentioned in query_pathkeys; if so
+ * we can generate a sort order that's also useful for final output.
+ * There is no percentage in a partial match, though, so we have to
+ * have 'em all.
+ */
+ if (root->query_pathkeys)
+ {
+ foreach(lc, root->query_pathkeys)
+ {
+ PathKey *query_pathkey = (PathKey *) lfirst(lc);
+ EquivalenceClass *query_ec = query_pathkey->pk_eclass;
+
+ for (j = 0; j < necs; j++)
+ {
+ if (ecs[j] == query_ec)
+ break; /* found match */
+ }
+ if (j >= necs)
+ break; /* didn't find match */
+ }
+ /* if we got to the end of the list, we have them all */
+ if (lc == NULL)
+ {
+ /* copy query_pathkeys as starting point for our output */
+ pathkeys = list_copy(root->query_pathkeys);
+ /* mark their ECs as already-emitted */
+ foreach(lc, root->query_pathkeys)
+ {
+ PathKey *query_pathkey = (PathKey *) lfirst(lc);
+ EquivalenceClass *query_ec = query_pathkey->pk_eclass;
+
+ for (j = 0; j < necs; j++)
+ {
+ if (ecs[j] == query_ec)
+ {
+ scores[j] = -1;
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ /*
+ * Add remaining ECs to the list in popularity order, using a default
+ * sort ordering. (We could use qsort() here, but the list length is
+ * usually so small it's not worth it.)
+ */
+ for (;;)
+ {
+ int best_j;
+ int best_score;
+ EquivalenceClass *ec;
+ PathKey *pathkey;
+
+ best_j = 0;
+ best_score = scores[0];
+ for (j = 1; j < necs; j++)
+ {
+ if (scores[j] > best_score)
+ {
+ best_j = j;
+ best_score = scores[j];
+ }
+ }
+ if (best_score < 0)
+ break; /* all done */
+ ec = ecs[best_j];
+ scores[best_j] = -1;
+ pathkey = make_canonical_pathkey(root,
+ ec,
+ linitial_oid(ec->ec_opfamilies),
+ BTLessStrategyNumber,
+ false);
+ /* can't be redundant because no duplicate ECs */
+ Assert(!pathkey_is_redundant(pathkey, pathkeys));
+ pathkeys = lappend(pathkeys, pathkey);
+ }
+
+ pfree(ecs);
+ pfree(scores);
+
+ return pathkeys;
+}
+
+/*
+ * make_inner_pathkeys_for_merge
* Builds a pathkey list representing the explicit sort order that
- * must be applied to a path in order to make it usable for the
+ * must be applied to an inner path to make it usable with the
* given mergeclauses.
*
* 'mergeclauses' is a list of RestrictInfos for mergejoin clauses
* that will be used in a merge join.
- * 'rel' is the relation the pathkeys will apply to (ie, either the inner
- * or outer side of the proposed join rel).
+ * 'outer_pathkeys' are the already-known canonical pathkeys for the outer
+ * side of the join.
*
- * Returns a pathkeys list that can be applied to the indicated relation.
+ * The restrictinfos must be marked (via outer_is_left) to show which side
+ * of each clause is associated with the current outer path. (See
+ * select_mergejoin_clauses())
+ *
+ * Returns a pathkeys list that can be applied to the inner relation.
*
* Note that it is not this routine's job to decide whether sorting is
* actually needed for a particular input path. Assume a sort is necessary;
* just make the keys, eh?
*/
List *
-make_pathkeys_for_mergeclauses(PlannerInfo *root,
- List *mergeclauses,
- RelOptInfo *rel)
+make_inner_pathkeys_for_merge(PlannerInfo *root,
+ List *mergeclauses,
+ List *outer_pathkeys)
{
List *pathkeys = NIL;
- ListCell *l;
+ EquivalenceClass *lastoeclass;
+ PathKey *opathkey;
+ ListCell *lc;
+ ListCell *lop;
+
+ lastoeclass = NULL;
+ opathkey = NULL;
+ lop = list_head(outer_pathkeys);
- foreach(l, mergeclauses)
+ foreach(lc, mergeclauses)
{
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
- List *pathkey;
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ EquivalenceClass *oeclass;
+ EquivalenceClass *ieclass;
+ PathKey *pathkey;
- cache_mergeclause_pathkeys(root, restrictinfo);
+ cache_mergeclause_eclasses(root, rinfo);
- if (bms_is_subset(restrictinfo->left_relids, rel->relids))
+ if (rinfo->outer_is_left)
{
- /* Rel is left side of mergeclause */
- pathkey = restrictinfo->left_pathkey;
+ oeclass = rinfo->left_ec;
+ ieclass = rinfo->right_ec;
}
- else if (bms_is_subset(restrictinfo->right_relids, rel->relids))
+ else
{
- /* Rel is right side of mergeclause */
- pathkey = restrictinfo->right_pathkey;
+ oeclass = rinfo->right_ec;
+ ieclass = rinfo->left_ec;
}
- else
+
+ /* outer eclass should match current or next pathkeys */
+ /* we check this carefully for debugging reasons */
+ if (oeclass != lastoeclass)
{
- elog(ERROR, "could not identify which side of mergeclause to use");
- pathkey = NIL; /* keep compiler quiet */
+ if (!lop)
+ elog(ERROR, "too few pathkeys for mergeclauses");
+ opathkey = (PathKey *) lfirst(lop);
+ lop = lnext(lop);
+ lastoeclass = opathkey->pk_eclass;
+ if (oeclass != lastoeclass)
+ elog(ERROR, "outer pathkeys do not match mergeclause");
}
/*
- * When we are given multiple merge clauses, it's possible that
- * some clauses refer to the same vars as earlier clauses. There's
- * no reason for us to specify sort keys like (A,B,A) when (A,B)
- * will do --- and adding redundant sort keys makes add_path think
- * that this sort order is different from ones that are really the
- * same, so don't do it. Since we now have a canonicalized
- * pathkey, a simple ptrMember test is sufficient to detect
- * redundant keys.
+ * Often, we'll have same EC on both sides, in which case the outer
+ * pathkey is also canonical for the inner side, and we can skip a
+ * useless search.
+ */
+ if (ieclass == oeclass)
+ pathkey = opathkey;
+ else
+ pathkey = make_canonical_pathkey(root,
+ ieclass,
+ opathkey->pk_opfamily,
+ opathkey->pk_strategy,
+ opathkey->pk_nulls_first);
+
+ /*
+ * Don't generate redundant pathkeys (can happen if multiple
+ * mergeclauses refer to same EC).
*/
- if (!list_member_ptr(pathkeys, pathkey))
+ if (!pathkey_is_redundant(pathkey, pathkeys))
pathkeys = lappend(pathkeys, pathkey);
}
/*
* pathkeys_useful_for_merging
* Count the number of pathkeys that may be useful for mergejoins
- * above the given relation (by looking at its joininfo list).
+ * above the given relation.
*
* 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
foreach(i, pathkeys)
{
- List *pathkey = (List *) lfirst(i);
+ PathKey *pathkey = (PathKey *) lfirst(i);
bool matched = false;
ListCell *j;
- foreach(j, rel->joininfo)
+ /*
+ * First look into the EquivalenceClass of the pathkey, to see if
+ * there are any members not yet joined to the rel. If so, it's
+ * surely possible to generate a mergejoin clause using them.
+ */
+ if (rel->has_eclass_joins &&
+ eclass_useful_for_merging(pathkey->pk_eclass, rel))
+ matched = true;
+ else
{
- RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
-
- if (restrictinfo->mergejoinoperator == InvalidOid)
- continue;
- cache_mergeclause_pathkeys(root, restrictinfo);
-
/*
- * We can compare canonical pathkey sublists by simple
- * pointer equality; see compare_pathkeys.
+ * Otherwise search the rel's joininfo list, which contains
+ * non-EquivalenceClass-derivable join clauses that might
+ * nonetheless be mergejoinable.
*/
- if (pathkey == restrictinfo->left_pathkey ||
- pathkey == restrictinfo->right_pathkey)
+ foreach(j, rel->joininfo)
{
- matched = true;
- break;
+ RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(j);
+
+ if (restrictinfo->mergeopfamilies == NIL)
+ continue;
+ cache_mergeclause_eclasses(root, restrictinfo);
+
+ if (pathkey->pk_eclass == restrictinfo->left_ec ||
+ pathkey->pk_eclass == restrictinfo->right_ec)
+ {
+ matched = true;
+ break;
+ }
}
}
/*
* If we didn't find a mergeclause, we're done --- any additional
- * sort-key positions in the pathkeys are useless. (But we can
- * still mergejoin if we found at least one mergeclause.)
+ * sort-key positions in the pathkeys are useless. (But we can still
+ * mergejoin if we found at least one mergeclause.)
*/
if (matched)
useful++;