Header And Logo

PostgreSQL
| The world's most advanced open source database.

Functions

analyzejoins.c File Reference

#include "postgres.h"
#include "optimizer/joininfo.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/var.h"
Include dependency graph for analyzejoins.c:

Go to the source code of this file.

Functions

static bool join_is_removable (PlannerInfo *root, SpecialJoinInfo *sjinfo)
static void remove_rel_from_query (PlannerInfo *root, int relid, Relids joinrelids)
static Listremove_rel_from_joinlist (List *joinlist, int relid, int *nremoved)
Listremove_useless_joins (PlannerInfo *root, List *joinlist)
static bool clause_sides_match_join (RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)

Function Documentation

static bool clause_sides_match_join ( RestrictInfo rinfo,
Relids  outerrelids,
Relids  innerrelids 
) [inline, static]

Definition at line 114 of file analyzejoins.c.

References bms_is_subset(), RestrictInfo::left_relids, RestrictInfo::outer_is_left, and RestrictInfo::right_relids.

Referenced by join_is_removable().

{
    if (bms_is_subset(rinfo->left_relids, outerrelids) &&
        bms_is_subset(rinfo->right_relids, innerrelids))
    {
        /* lefthand side is outer */
        rinfo->outer_is_left = true;
        return true;
    }
    else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
             bms_is_subset(rinfo->right_relids, outerrelids))
    {
        /* righthand side is outer */
        rinfo->outer_is_left = false;
        return true;
    }
    return false;               /* no good for these input relations */
}

static bool join_is_removable ( PlannerInfo root,
SpecialJoinInfo sjinfo 
) [static]

Definition at line 146 of file analyzejoins.c.

References RelOptInfo::attr_needed, bms_equal(), bms_is_member(), bms_is_subset(), bms_membership(), bms_overlap(), BMS_SINGLETON, bms_singleton_member(), bms_union(), RestrictInfo::can_join, RestrictInfo::clause_relids, clause_sides_match_join(), SpecialJoinInfo::delay_upper_joins, find_base_rel(), RelOptInfo::indexlist, RestrictInfo::is_pushed_down, JOIN_LEFT, RelOptInfo::joininfo, SpecialJoinInfo::jointype, lappend(), lfirst, RelOptInfo::max_attr, RestrictInfo::mergeopfamilies, RelOptInfo::min_attr, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NIL, PlaceHolderInfo::ph_eval_at, PlaceHolderInfo::ph_needed, PlaceHolderInfo::ph_var, PlannerInfo::placeholder_list, pull_varnos(), relation_has_unique_index_for(), RelOptInfo::relids, RELOPT_BASEREL, RelOptInfo::reloptkind, RestrictInfo::required_relids, RTE_RELATION, and RelOptInfo::rtekind.

Referenced by remove_useless_joins().

{
    int         innerrelid;
    RelOptInfo *innerrel;
    Relids      joinrelids;
    List       *clause_list = NIL;
    ListCell   *l;
    int         attroff;

    /*
     * Currently, we only know how to remove left joins to a baserel with
     * unique indexes.  We can check most of these criteria pretty trivially
     * to avoid doing useless extra work.  But checking whether any of the
     * indexes are unique would require iterating over the indexlist, so for
     * now we just make sure there are indexes of some sort or other.  If none
     * of them are unique, join removal will still fail, just slightly later.
     */
    if (sjinfo->jointype != JOIN_LEFT ||
        sjinfo->delay_upper_joins ||
        bms_membership(sjinfo->min_righthand) != BMS_SINGLETON)
        return false;

    innerrelid = bms_singleton_member(sjinfo->min_righthand);
    innerrel = find_base_rel(root, innerrelid);

    if (innerrel->reloptkind != RELOPT_BASEREL ||
        innerrel->rtekind != RTE_RELATION ||
        innerrel->indexlist == NIL)
        return false;

    /* Compute the relid set for the join we are considering */
    joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);

    /*
     * We can't remove the join if any inner-rel attributes are used above the
     * join.
     *
     * Note that this test only detects use of inner-rel attributes in higher
     * join conditions and the target list.  There might be such attributes in
     * pushed-down conditions at this join, too.  We check that case below.
     *
     * As a micro-optimization, it seems better to start with max_attr and
     * count down rather than starting with min_attr and counting up, on the
     * theory that the system attributes are somewhat less likely to be wanted
     * and should be tested last.
     */
    for (attroff = innerrel->max_attr - innerrel->min_attr;
         attroff >= 0;
         attroff--)
    {
        if (!bms_is_subset(innerrel->attr_needed[attroff], joinrelids))
            return false;
    }

    /*
     * Similarly check that the inner rel isn't needed by any PlaceHolderVars
     * that will be used above the join.  We only need to fail if such a PHV
     * actually references some inner-rel attributes; but the correct check
     * for that is relatively expensive, so we first check against ph_eval_at,
     * which must mention the inner rel if the PHV uses any inner-rel attrs.
     */
    foreach(l, root->placeholder_list)
    {
        PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);

        if (bms_is_subset(phinfo->ph_needed, joinrelids))
            continue;           /* PHV is not used above the join */
        if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
            continue;           /* it definitely doesn't reference innerrel */
        if (bms_overlap(pull_varnos((Node *) phinfo->ph_var),
                        innerrel->relids))
            return false;       /* it does reference innerrel */
    }

    /*
     * Search for mergejoinable clauses that constrain the inner rel against
     * either the outer rel or a pseudoconstant.  If an operator is
     * mergejoinable then it behaves like equality for some btree opclass, so
     * it's what we want.  The mergejoinability test also eliminates clauses
     * containing volatile functions, which we couldn't depend on.
     */
    foreach(l, innerrel->joininfo)
    {
        RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);

        /*
         * If it's not a join clause for this outer join, we can't use it.
         * Note that if the clause is pushed-down, then it is logically from
         * above the outer join, even if it references no other rels (it might
         * be from WHERE, for example).
         */
        if (restrictinfo->is_pushed_down ||
            !bms_equal(restrictinfo->required_relids, joinrelids))
        {
            /*
             * If such a clause actually references the inner rel then join
             * removal has to be disallowed.  We have to check this despite
             * the previous attr_needed checks because of the possibility of
             * pushed-down clauses referencing the rel.
             */
            if (bms_is_member(innerrelid, restrictinfo->clause_relids))
                return false;
            continue;           /* else, ignore; not useful here */
        }

        /* Ignore if it's not a mergejoinable clause */
        if (!restrictinfo->can_join ||
            restrictinfo->mergeopfamilies == NIL)
            continue;           /* not mergejoinable */

        /*
         * Check if clause has the form "outer op inner" or "inner op outer".
         */
        if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
                                     innerrel->relids))
            continue;           /* no good for these input relations */

        /* OK, add to list */
        clause_list = lappend(clause_list, restrictinfo);
    }

    /*
     * relation_has_unique_index_for automatically adds any usable restriction
     * clauses for the innerrel, so we needn't do that here.
     */

    /* Now examine the indexes to see if we have a matching unique index */
    if (relation_has_unique_index_for(root, innerrel, clause_list, NIL, NIL))
        return true;

    /*
     * Some day it would be nice to check for other methods of establishing
     * distinctness.
     */
    return false;
}

static List * remove_rel_from_joinlist ( List joinlist,
int  relid,
int *  nremoved 
) [static]

Definition at line 444 of file analyzejoins.c.

References elog, ERROR, IsA, lappend(), lfirst, and nodeTag.

Referenced by remove_useless_joins().

{
    List       *result = NIL;
    ListCell   *jl;

    foreach(jl, joinlist)
    {
        Node       *jlnode = (Node *) lfirst(jl);

        if (IsA(jlnode, RangeTblRef))
        {
            int         varno = ((RangeTblRef *) jlnode)->rtindex;

            if (varno == relid)
                (*nremoved)++;
            else
                result = lappend(result, jlnode);
        }
        else if (IsA(jlnode, List))
        {
            /* Recurse to handle subproblem */
            List       *sublist;

            sublist = remove_rel_from_joinlist((List *) jlnode,
                                               relid, nremoved);
            /* Avoid including empty sub-lists in the result */
            if (sublist)
                result = lappend(result, sublist);
        }
        else
        {
            elog(ERROR, "unrecognized joinlist node type: %d",
                 (int) nodeTag(jlnode));
        }
    }

    return result;
}

static void remove_rel_from_query ( PlannerInfo root,
int  relid,
Relids  joinrelids 
) [static]

Definition at line 295 of file analyzejoins.c.

References Assert, RelOptInfo::attr_needed, bms_add_member(), bms_copy(), bms_del_member(), bms_equal(), bms_is_empty(), bms_is_member(), RestrictInfo::clause_relids, distribute_restrictinfo_to_rels(), find_base_rel(), RestrictInfo::is_pushed_down, PlannerInfo::join_info_list, RelOptInfo::joininfo, PlannerInfo::lateral_info_list, LateralJoinInfo::lateral_lhs, LateralJoinInfo::lateral_rhs, lfirst, list_copy(), list_delete_ptr(), list_head(), lnext, RelOptInfo::max_attr, RelOptInfo::min_attr, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, NULL, PlaceHolderInfo::ph_eval_at, PlaceHolderInfo::ph_may_need, PlaceHolderInfo::ph_needed, PlannerInfo::placeholder_list, RelOptInfo::relid, RelOptInfo::reloptkind, remove_join_clause_from_rels(), RestrictInfo::required_relids, PlannerInfo::simple_rel_array, PlannerInfo::simple_rel_array_size, SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

Referenced by remove_useless_joins().

{
    RelOptInfo *rel = find_base_rel(root, relid);
    List       *joininfos;
    Index       rti;
    ListCell   *l;
    ListCell   *nextl;

    /*
     * Mark the rel as "dead" to show it is no longer part of the join tree.
     * (Removing it from the baserel array altogether seems too risky.)
     */
    rel->reloptkind = RELOPT_DEADREL;

    /*
     * Remove references to the rel from other baserels' attr_needed arrays.
     */
    for (rti = 1; rti < root->simple_rel_array_size; rti++)
    {
        RelOptInfo *otherrel = root->simple_rel_array[rti];
        int         attroff;

        /* there may be empty slots corresponding to non-baserel RTEs */
        if (otherrel == NULL)
            continue;

        Assert(otherrel->relid == rti); /* sanity check on array */

        /* no point in processing target rel itself */
        if (otherrel == rel)
            continue;

        for (attroff = otherrel->max_attr - otherrel->min_attr;
             attroff >= 0;
             attroff--)
        {
            otherrel->attr_needed[attroff] =
                bms_del_member(otherrel->attr_needed[attroff], relid);
        }
    }

    /*
     * Likewise remove references from SpecialJoinInfo data structures.
     *
     * This is relevant in case the outer join we're deleting is nested inside
     * other outer joins: the upper joins' relid sets have to be adjusted. The
     * RHS of the target outer join will be made empty here, but that's OK
     * since caller will delete that SpecialJoinInfo entirely.
     */
    foreach(l, root->join_info_list)
    {
        SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);

        sjinfo->min_lefthand = bms_del_member(sjinfo->min_lefthand, relid);
        sjinfo->min_righthand = bms_del_member(sjinfo->min_righthand, relid);
        sjinfo->syn_lefthand = bms_del_member(sjinfo->syn_lefthand, relid);
        sjinfo->syn_righthand = bms_del_member(sjinfo->syn_righthand, relid);
    }

    /*
     * Likewise remove references from LateralJoinInfo data structures.
     *
     * If we are deleting a LATERAL subquery, we can forget its
     * LateralJoinInfo altogether.  Otherwise, make sure the target is not
     * included in any lateral_lhs set.  (It probably can't be, since that
     * should have precluded deciding to remove it; but let's cope anyway.)
     */
    for (l = list_head(root->lateral_info_list); l != NULL; l = nextl)
    {
        LateralJoinInfo *ljinfo = (LateralJoinInfo *) lfirst(l);

        nextl = lnext(l);
        if (ljinfo->lateral_rhs == relid)
            root->lateral_info_list = list_delete_ptr(root->lateral_info_list,
                                                      ljinfo);
        else
            ljinfo->lateral_lhs = bms_del_member(ljinfo->lateral_lhs, relid);
    }

    /*
     * Likewise remove references from PlaceHolderVar data structures.
     *
     * Here we have a special case: if a PHV's eval_at set is just the target
     * relid, we want to leave it that way instead of reducing it to the empty
     * set.  An empty eval_at set would confuse later processing since it
     * would match every possible eval placement.
     */
    foreach(l, root->placeholder_list)
    {
        PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);

        phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
        if (bms_is_empty(phinfo->ph_eval_at))   /* oops, belay that */
            phinfo->ph_eval_at = bms_add_member(phinfo->ph_eval_at, relid);

        phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
        /* ph_may_need probably isn't used after this, but fix it anyway */
        phinfo->ph_may_need = bms_del_member(phinfo->ph_may_need, relid);
    }

    /*
     * Remove any joinquals referencing the rel from the joininfo lists.
     *
     * In some cases, a joinqual has to be put back after deleting its
     * reference to the target rel.  This can occur for pseudoconstant and
     * outerjoin-delayed quals, which can get marked as requiring the rel in
     * order to force them to be evaluated at or above the join.  We can't
     * just discard them, though.  Only quals that logically belonged to the
     * outer join being discarded should be removed from the query.
     *
     * We must make a copy of the rel's old joininfo list before starting the
     * loop, because otherwise remove_join_clause_from_rels would destroy the
     * list while we're scanning it.
     */
    joininfos = list_copy(rel->joininfo);
    foreach(l, joininfos)
    {
        RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

        remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);

        if (rinfo->is_pushed_down ||
            !bms_equal(rinfo->required_relids, joinrelids))
        {
            /* Recheck that qual doesn't actually reference the target rel */
            Assert(!bms_is_member(relid, rinfo->clause_relids));

            /*
             * The required_relids probably aren't shared with anything else,
             * but let's copy them just to be sure.
             */
            rinfo->required_relids = bms_copy(rinfo->required_relids);
            rinfo->required_relids = bms_del_member(rinfo->required_relids,
                                                    relid);
            distribute_restrictinfo_to_rels(root, rinfo);
        }
    }
}

List* remove_useless_joins ( PlannerInfo root,
List joinlist 
)

Definition at line 47 of file analyzejoins.c.

References bms_singleton_member(), bms_union(), elog, ERROR, PlannerInfo::join_info_list, join_is_removable(), lfirst, list_delete_ptr(), SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, remove_rel_from_joinlist(), and remove_rel_from_query().

Referenced by query_planner().

{
    ListCell   *lc;

    /*
     * We are only interested in relations that are left-joined to, so we can
     * scan the join_info_list to find them easily.
     */
restart:
    foreach(lc, root->join_info_list)
    {
        SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
        int         innerrelid;
        int         nremoved;

        /* Skip if not removable */
        if (!join_is_removable(root, sjinfo))
            continue;

        /*
         * Currently, join_is_removable can only succeed when the sjinfo's
         * righthand is a single baserel.  Remove that rel from the query and
         * joinlist.
         */
        innerrelid = bms_singleton_member(sjinfo->min_righthand);

        remove_rel_from_query(root, innerrelid,
                              bms_union(sjinfo->min_lefthand,
                                        sjinfo->min_righthand));

        /* We verify that exactly one reference gets removed from joinlist */
        nremoved = 0;
        joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
        if (nremoved != 1)
            elog(ERROR, "failed to find relation %d in joinlist", innerrelid);

        /*
         * We can delete this SpecialJoinInfo from the list too, since it's no
         * longer of interest.
         */
        root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);

        /*
         * Restart the scan.  This is necessary to ensure we find all
         * removable joins independently of ordering of the join_info_list
         * (note that removal of attr_needed bits may make a join appear
         * removable that did not before).  Also, since we just deleted the
         * current list cell, we'd have to have some kluge to continue the
         * list scan anyway.
         */
        goto restart;
    }

    return joinlist;
}