tlist.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * tlist.c
 *    Target list manipulation routines
 *
 * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *    src/backend/optimizer/util/tlist.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/tlist.h"


/*****************************************************************************
 *      Target list creation and searching utilities
 *****************************************************************************/

/*
 * tlist_member
 *    Finds the (first) member of the given tlist whose expression is
 *    equal() to the given expression.  Result is NULL if no such member.
 */
TargetEntry *
tlist_member(Node *node, List *targetlist)
{
    ListCell   *temp;

    foreach(temp, targetlist)
    {
        TargetEntry *tlentry = (TargetEntry *) lfirst(temp);

        if (equal(node, tlentry->expr))
            return tlentry;
    }
    return NULL;
}

/*
 * tlist_member_ignore_relabel
 *    Same as above, except that we ignore top-level RelabelType nodes
 *    while checking for a match.  This is needed for some scenarios
 *    involving binary-compatible sort operations.
 */
TargetEntry *
tlist_member_ignore_relabel(Node *node, List *targetlist)
{
    ListCell   *temp;

    while (node && IsA(node, RelabelType))
        node = (Node *) ((RelabelType *) node)->arg;

    foreach(temp, targetlist)
    {
        TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
        Expr       *tlexpr = tlentry->expr;

        while (tlexpr && IsA(tlexpr, RelabelType))
            tlexpr = ((RelabelType *) tlexpr)->arg;

        if (equal(node, tlexpr))
            return tlentry;
    }
    return NULL;
}

/*
 * flatten_tlist
 *    Create a target list that only contains unique variables.
 *
 * Aggrefs and PlaceHolderVars in the input are treated according to
 * aggbehavior and phbehavior, for which see pull_var_clause().
 *
 * 'tlist' is the current target list
 *
 * Returns the "flattened" new target list.
 *
 * The result is entirely new structure sharing no nodes with the original.
 * Copying the Var nodes is probably overkill, but be safe for now.
 */
List *
flatten_tlist(List *tlist, PVCAggregateBehavior aggbehavior,
              PVCPlaceHolderBehavior phbehavior)
{
    List       *vlist = pull_var_clause((Node *) tlist,
                                        aggbehavior,
                                        phbehavior);
    List       *new_tlist;

    new_tlist = add_to_flat_tlist(NIL, vlist);
    list_free(vlist);
    return new_tlist;
}

/*
 * add_to_flat_tlist
 *      Add more items to a flattened tlist (if they're not already in it)
 *
 * 'tlist' is the flattened tlist
 * 'exprs' is a list of expressions (usually, but not necessarily, Vars)
 *
 * Returns the extended tlist.
 */
List *
add_to_flat_tlist(List *tlist, List *exprs)
{
    int         next_resno = list_length(tlist) + 1;
    ListCell   *lc;

    foreach(lc, exprs)
    {
        Node       *expr = (Node *) lfirst(lc);

        if (!tlist_member(expr, tlist))
        {
            TargetEntry *tle;

            tle = makeTargetEntry(copyObject(expr),     /* copy needed?? */
                                  next_resno++,
                                  NULL,
                                  false);
            tlist = lappend(tlist, tle);
        }
    }
    return tlist;
}


/*
 * get_tlist_exprs
 *      Get just the expression subtrees of a tlist
 *
 * Resjunk columns are ignored unless includeJunk is true
 */
List *
get_tlist_exprs(List *tlist, bool includeJunk)
{
    List       *result = NIL;
    ListCell   *l;

    foreach(l, tlist)
    {
        TargetEntry *tle = (TargetEntry *) lfirst(l);

        if (tle->resjunk && !includeJunk)
            continue;

        result = lappend(result, tle->expr);
    }
    return result;
}


/*
 * tlist_same_exprs
 *      Check whether two target lists contain the same expressions
 *
 * Note: this function is used to decide whether it's safe to jam a new tlist
 * into a non-projection-capable plan node.  Obviously we can't do that unless
 * the node's tlist shows it already returns the column values we want.
 * However, we can ignore the TargetEntry attributes resname, ressortgroupref,
 * resorigtbl, resorigcol, and resjunk, because those are only labelings that
 * don't affect the row values computed by the node.  (Moreover, if we didn't
 * ignore them, we'd frequently fail to make the desired optimization, since
 * the planner tends to not bother to make resname etc. valid in intermediate
 * plan nodes.)  Note that on success, the caller must still jam the desired
 * tlist into the plan node, else it won't have the desired labeling fields.
 */
bool
tlist_same_exprs(List *tlist1, List *tlist2)
{
    ListCell   *lc1,
               *lc2;

    if (list_length(tlist1) != list_length(tlist2))
        return false;           /* not same length, so can't match */

    forboth(lc1, tlist1, lc2, tlist2)
    {
        TargetEntry *tle1 = (TargetEntry *) lfirst(lc1);
        TargetEntry *tle2 = (TargetEntry *) lfirst(lc2);

        if (!equal(tle1->expr, tle2->expr))
            return false;
    }

    return true;
}


/*
 * Does tlist have same output datatypes as listed in colTypes?
 *
 * Resjunk columns are ignored if junkOK is true; otherwise presence of
 * a resjunk column will always cause a 'false' result.
 *
 * Note: currently no callers care about comparing typmods.
 */
bool
tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
{
    ListCell   *l;
    ListCell   *curColType = list_head(colTypes);

    foreach(l, tlist)
    {
        TargetEntry *tle = (TargetEntry *) lfirst(l);

        if (tle->resjunk)
        {
            if (!junkOK)
                return false;
        }
        else
        {
            if (curColType == NULL)
                return false;   /* tlist longer than colTypes */
            if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
                return false;
            curColType = lnext(curColType);
        }
    }
    if (curColType != NULL)
        return false;           /* tlist shorter than colTypes */
    return true;
}

/*
 * Does tlist have same exposed collations as listed in colCollations?
 *
 * Identical logic to the above, but for collations.
 */
bool
tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
{
    ListCell   *l;
    ListCell   *curColColl = list_head(colCollations);

    foreach(l, tlist)
    {
        TargetEntry *tle = (TargetEntry *) lfirst(l);

        if (tle->resjunk)
        {
            if (!junkOK)
                return false;
        }
        else
        {
            if (curColColl == NULL)
                return false;   /* tlist longer than colCollations */
            if (exprCollation((Node *) tle->expr) != lfirst_oid(curColColl))
                return false;
            curColColl = lnext(curColColl);
        }
    }
    if (curColColl != NULL)
        return false;           /* tlist shorter than colCollations */
    return true;
}


/*
 * get_sortgroupref_tle
 *      Find the targetlist entry matching the given SortGroupRef index,
 *      and return it.
 */
TargetEntry *
get_sortgroupref_tle(Index sortref, List *targetList)
{
    ListCell   *l;

    foreach(l, targetList)
    {
        TargetEntry *tle = (TargetEntry *) lfirst(l);

        if (tle->ressortgroupref == sortref)
            return tle;
    }

    elog(ERROR, "ORDER/GROUP BY expression not found in targetlist");
    return NULL;                /* keep compiler quiet */
}

/*
 * get_sortgroupclause_tle
 *      Find the targetlist entry matching the given SortGroupClause
 *      by ressortgroupref, and return it.
 */
TargetEntry *
get_sortgroupclause_tle(SortGroupClause *sgClause,
                        List *targetList)
{
    return get_sortgroupref_tle(sgClause->tleSortGroupRef, targetList);
}

/*
 * get_sortgroupclause_expr
 *      Find the targetlist entry matching the given SortGroupClause
 *      by ressortgroupref, and return its expression.
 */
Node *
get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
{
    TargetEntry *tle = get_sortgroupclause_tle(sgClause, targetList);

    return (Node *) tle->expr;
}

/*
 * get_sortgrouplist_exprs
 *      Given a list of SortGroupClauses, build a list
 *      of the referenced targetlist expressions.
 */
List *
get_sortgrouplist_exprs(List *sgClauses, List *targetList)
{
    List       *result = NIL;
    ListCell   *l;

    foreach(l, sgClauses)
    {
        SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
        Node       *sortexpr;

        sortexpr = get_sortgroupclause_expr(sortcl, targetList);
        result = lappend(result, sortexpr);
    }
    return result;
}


/*****************************************************************************
 *      Functions to extract data from a list of SortGroupClauses
 *
 * These don't really belong in tlist.c, but they are sort of related to the
 * functions just above, and they don't seem to deserve their own file.
 *****************************************************************************/

/*
 * extract_grouping_ops - make an array of the equality operator OIDs
 *      for a SortGroupClause list
 */
Oid *
extract_grouping_ops(List *groupClause)
{
    int         numCols = list_length(groupClause);
    int         colno = 0;
    Oid        *groupOperators;
    ListCell   *glitem;

    groupOperators = (Oid *) palloc(sizeof(Oid) * numCols);

    foreach(glitem, groupClause)
    {
        SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);

        groupOperators[colno] = groupcl->eqop;
        Assert(OidIsValid(groupOperators[colno]));
        colno++;
    }

    return groupOperators;
}

/*
 * extract_grouping_cols - make an array of the grouping column resnos
 *      for a SortGroupClause list
 */
AttrNumber *
extract_grouping_cols(List *groupClause, List *tlist)
{
    AttrNumber *grpColIdx;
    int         numCols = list_length(groupClause);
    int         colno = 0;
    ListCell   *glitem;

    grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);

    foreach(glitem, groupClause)
    {
        SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
        TargetEntry *tle = get_sortgroupclause_tle(groupcl, tlist);

        grpColIdx[colno++] = tle->resno;
    }

    return grpColIdx;
}

/*
 * grouping_is_sortable - is it possible to implement grouping list by sorting?
 *
 * This is easy since the parser will have included a sortop if one exists.
 */
bool
grouping_is_sortable(List *groupClause)
{
    ListCell   *glitem;

    foreach(glitem, groupClause)
    {
        SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);

        if (!OidIsValid(groupcl->sortop))
            return false;
    }
    return true;
}

/*
 * grouping_is_hashable - is it possible to implement grouping list by hashing?
 *
 * We rely on the parser to have set the hashable flag correctly.
 */
bool
grouping_is_hashable(List *groupClause)
{
    ListCell   *glitem;

    foreach(glitem, groupClause)
    {
        SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);

        if (!groupcl->hashable)
            return false;
    }
    return true;
}