PostgreSQL Query Tree

在PostgreSQL中，Parser将SQL语句解析成ParseTree，ParseTree只是简单记录SQL语句中的信息，并不保证信息的正确性。因此，在进行查询优化之前先要检验SQL语义的正确性。

Analyzer负责对ParseTree进行语义分析，并将ParseTree转换成QueryTree，QueryTree是优化器的输入参数。

这里我们只关注查询语句的QueryTree。对于查询语句，它的ParseTree实际是通过SelectStmt的数据结构来表示的。QueryTree则通过Query的数据结构来表示。我们将通过分析从SelectStmt到Query的转换过程来揭示Query的组成结构。

Query

/*
 * Query -
 *    Parse analysis turns all statements into a Query tree
 *    for further processing by the rewriter and planner.
 *
 *    Utility statements (i.e. non-optimizable statements) have the
 *    utilityStmt field set, and the rest of the Query is mostly dummy.
 *
 *    Planning converts a Query tree into a Plan tree headed by a PlannedStmt
 *    node --- the Query structure is not used by the executor.
 */
typedef struct Query
{
    NodeTag     type;

    CmdType     commandType;    /* select|insert|update|delete|utility */

    QuerySource querySource;    /* where did I come from? */

    uint64      queryId;        /* query identifier (can be set by plugins) */

    bool        canSetTag;      /* do I set the command result tag? */

    Node       *utilityStmt;    /* non-null if commandType == CMD_UTILITY */

    int         resultRelation; /* rtable index of target relation for
                                 * INSERT/UPDATE/DELETE; 0 for SELECT */

    bool        hasAggs;        /* has aggregates in tlist or havingQual */
    bool        hasWindowFuncs; /* has window functions in tlist */
    bool        hasTargetSRFs;  /* has set-returning functions in tlist */
    bool        hasSubLinks;    /* has subquery SubLink */
    bool        hasDistinctOn;  /* distinctClause is from DISTINCT ON */
    bool        hasRecursive;   /* WITH RECURSIVE was specified */
    bool        hasModifyingCTE;    /* has INSERT/UPDATE/DELETE in WITH */
    bool        hasForUpdate;   /* FOR [KEY] UPDATE/SHARE was specified */
    bool        hasRowSecurity; /* rewriter has applied some RLS policy */

    List       *cteList;        /* WITH list (of CommonTableExpr's) */

    List       *rtable;         /* list of range table entries */
    FromExpr   *jointree;       /* table join tree (FROM and WHERE clauses) */

    List       *targetList;     /* target list (of TargetEntry) */

    OverridingKind override;    /* OVERRIDING clause */

    OnConflictExpr *onConflict; /* ON CONFLICT DO [NOTHING | UPDATE] */

    List       *returningList;  /* return-values list (of TargetEntry) */

    List       *groupClause;    /* a list of SortGroupClause's */

    List       *groupingSets;   /* a list of GroupingSet's if present */

    Node       *havingQual;     /* qualifications applied to groups */

    List       *windowClause;   /* a list of WindowClause's */

    List       *distinctClause; /* a list of SortGroupClause's */

    List       *sortClause;     /* a list of SortGroupClause's */

    Node       *limitOffset;    /* # of result tuples to skip (int8 expr) */
    Node       *limitCount;     /* # of result tuples to return (int8 expr) */

    List       *rowMarks;       /* a list of RowMarkClause's */

    Node       *setOperations;  /* set-operation tree if this is top level of
                                 * a UNION/INTERSECT/EXCEPT query */

    List       *constraintDeps; /* a list of pg_constraint OIDs that the query
                                 * depends on to be semantically valid */

    List       *withCheckOptions;   /* a list of WithCheckOption's, which are
                                     * only added during rewrite and therefore
                                     * are not written out as part of Query. */

    /*
     * The following two fields identify the portion of the source text string
     * containing this query.  They are typically only populated in top-level
     * Queries, not in sub-queries.  When not set, they might both be zero, or
     * both be -1 meaning "unknown".
     */
    int         stmt_location;  /* start location, or -1 if unknown */
    int         stmt_len;       /* length in bytes; 0 means "rest of string" */
} Query;

ParseState

ParseState数据结构用于保存在分析阶段使用的状态信息。

当存在子查询时，ParseState通过parentParseState指针指向外层查询的ParseState。

struct ParseState
{
    struct ParseState *parentParseState;    /* stack link */
    const char *p_sourcetext;   /* source text, or NULL if not available */
    List       *p_rtable;       /* range table so far */
    List       *p_joinexprs;    /* JoinExprs for RTE_JOIN p_rtable entries */
    List       *p_joinlist;     /* join items so far (will become FromExpr
                                 * node's fromlist) */
    List       *p_namespace;    /* currently-referenceable RTEs (List of
                                 * ParseNamespaceItem) */
    bool        p_lateral_active;   /* p_lateral_only items visible? */
    List       *p_ctenamespace; /* current namespace for common table exprs */
    List       *p_future_ctes;  /* common table exprs not yet in namespace */
    CommonTableExpr *p_parent_cte;  /* this query's containing CTE */
    Relation    p_target_relation;  /* INSERT/UPDATE/DELETE target rel */
    RangeTblEntry *p_target_rangetblentry;  /* target rel's RTE */
    bool        p_is_insert;    /* process assignment like INSERT not UPDATE */
    List       *p_windowdefs;   /* raw representations of window clauses */
    ParseExprKind p_expr_kind;  /* what kind of expression we're parsing */
    int         p_next_resno;   /* next targetlist resno to assign */
    List       *p_multiassign_exprs;    /* junk tlist entries for multiassign */
    List       *p_locking_clause;   /* raw FOR UPDATE/FOR SHARE info */
    bool        p_locked_from_parent;   /* parent has marked this subquery
                                         * with FOR UPDATE/FOR SHARE */
    bool        p_resolve_unknowns; /* resolve unknown-type SELECT outputs as
                                     * type text */

    QueryEnvironment *p_queryEnv;   /* curr env, incl refs to enclosing env */

    /* Flags telling about things found in the query: */
    bool        p_hasAggs;
    bool        p_hasWindowFuncs;
    bool        p_hasTargetSRFs;
    bool        p_hasSubLinks;
    bool        p_hasModifyingCTE;

    Node       *p_last_srf;     /* most recent set-returning func/op found */

    /*
     * Optional hook functions for parser callbacks.  These are null unless
     * set up by the caller of make_parsestate.
     */
    PreParseColumnRefHook p_pre_columnref_hook;
    PostParseColumnRefHook p_post_columnref_hook;
    ParseParamRefHook p_paramref_hook;
    CoerceParamHook p_coerce_param_hook;
    void       *p_ref_hook_state;   /* common passthrough link for above */
};

parse_analyze

SelectStmt转换为Query的过程通过函数parse_analyze实现，位于src/backend/parser/analyze.c中。

函数parse_analyze首先生成一个ParseState用于记录分析时的中间信息，然后调用transformTopLevelStmt函数来完成语义分析。

transformTopLevelStmt函数调用transformOptionalSelectInto函数对SELECT ... INTO进行处理。transformOptionalSelectInto先将SELECT ... INTO语句转换为CREATE TABLE AS语句，然后调用transformStmt函数对语句进行处理。

transformStmt函数根据不同的查询类型调用相应的函数进行处理，其主要作用是将分析树转换为查询树。这里我们主要关注对SELECT语句进行转换的函数transformSelectStmt函数，不考虑集合操作。

transformValuesClause

VALUES子句可以通过值表达式生成一个记录集，通常用于生成一个“常量表”。

关于VALUES的具体说明可参考https://www.postgresql.org/docs/current/sql-values.html，其语法如下所示：

VALUES ( expression [, ...] ) [, ...]
    [ ORDER BY sort_expression [ ASC | DESC | USING operator ] [, ...] ]
    [ LIMIT { count | ALL } ]
    [ OFFSET start [ ROW | ROWS ] ]
    [ FETCH { FIRST | NEXT } [ count ] { ROW | ROWS } ONLY ]

Parser会将VALUES子句封装成一个单独的子查询SelectStmt，此时SelectStmt::valuesLists保存的是值表达式的链表，链表中每一个节点是一个常量表达式。

transformValuesClause函数用于转换VALUES子句，将VALUES子句所在的SelectStmt转换成一个Query。值表达式链表被转换成常量节点链表，通过addRangeTableEntryForValues函数向子查询的ParseState::p_rtable增加RTE_VALUES类型的RTE。

transformValuesClause函数对with子句、sort子句、limit子句的处理与transformSelectStmt函数一致，不再赘叙。

在外层，VALUES子句转换成的Query被包装成RET_SUBQUERY类型的RTE添加到外层的ParseState::p_rtable中。

transformSelectStmt

transformSelectStmt函数根据SelectStmt数据结构生成一个查询树，其主要处理操作如下：

  1. With clause
  2. From clause
  3. Target list
  4. Where clause
  5. Having clause
  6. Sort clause
  7. Group clause
  8. Distinct clause
  9. Limit clause
  10. Window clause
  11. Locking clause

With clause

With子句包含的是CTE(Common Table Expressions)的链表，链表中的每个CTE是一个CommonTableExpr数据结构。

transformWithClause函数对with子句进行处理，处理流程如下：

  1. 检查CTE名称有没有重复；
  2. 检查CTE是否有数据修改语句（INSERT/UPDATE/DELETE）；
  3. 如果CTE是递归的，检查CTE之间的依赖关系，根据依赖关系重新排序；
  4. 分析每一个CTE：
    • 调用transformStmt函数对CTE中的子查询进行转换
    • 计算输出列的名称和类型

From clause

transformFromClause函数负责处理From子句，并且向Query的range table、joinlist和namespace中增加项。

SelectStmt的fromClause是一个链表，链表中的节点可能是RangeVar、RangeSubselect、RangeFunction、RangeTableFunc、RangeTableSample、JoinExpr。

transformFromClause函数主要调用transformFromClauseItem函数对fromClause链表中的每一个节点进行处理。处理完节点之后会检查该节点表示的范围表是否有重名。

transformFromClauseItem函数转换fromClause链表中的节点，向ParseState的p_rtable链表字段添加生成的RangeTableEntry结构，每一个RangeTableEntry结构表示一个范围表，最终生成的Query的rtable字段也指向该链表。

transformFromClause函数将transformFromClauseItem函数返回的Node添加到ParseState::p_joinlist中，将ParseNamespaceItem添加到pstate->p_namespace中。

RangeTblRef实际保存的是RTE在ParseState::p_rtable链表中的位置。

在transformSelectStmt函数的最后会将ParseState::p_rtable指向的链表赋值给QUery::rtable。

下面依次分析transformFromClauseItem函数对不同节点类型的处理。

RangeVar

  1. 首先检查节点是不是一个CTE或者EphemeralNamedRelation，如果是则通过addRangeTableEntryForCTE函数或addRangeTableEntryForENR函数向ParseState::p_rtable添加RTE，RTE的类型为RTE_CTE或RTE_NAMEDTUPLESTORE。

  2. 如果是普通表，则通过addRangeTableEntry函数向ParseState::p_rtable添加RTE_RELATION类型的RTE。

RangeSubselect

transformRangeSubselect函数用来转换FROM子句中的子查询。

首先通过parse_sub_analyze函数解析子查询，生成子查询的Query。parse_sub_analyze函数递归调用transformStmt函数实现对子查询的分析。

最后通过addRangeTableEntryForSubquery函数将子查询作为RTE_SUBQUERY类型的RTE加入到ParseState::p_rtable中。

返回RangeTblRef。

RangeFunction

transformRangeFunction函数用来转换FROM子句中的函数。

RangeFunction中保存的是函数表达式的链表，需要对每个函数表达式进行分析。通过transformExpr对函数表达式进行分析转换。

最后通过addRangeTableEntryForFunction函数向ParseState::p_rtable添加RTE_FUNCTION类型的RTE。

返回RangeTblRef。

RangeTableFunc

表函数是能够产生记录集的函数，可以在FROM子句中像表、视图或子查询一样使用。

transformRangeTableFunc函数用来转换FROM子句的表函数。目前只支持XMLTABLE。

最后通过addRangeTableEntryForTableFunc函数向ParseState::p_rtable添加RTE_TABLEFUNC类型的RTE。

返回RangeTblRef。

RangeTableSample

表采样对表使用采样方法进行采样。

首先递归调用transformFromClauseItem函数对RangeTableSample中的relation进行转换。

然后调用transformRangeTableSample函数将RangeTableSample转换为TableSampleClause。这里会分析采样方法是否有效，转换参数表达式和REPEATABLE表达式。

返回RangeTblRef。

JoinExpr

JoinExpr是连接表达式，有左右子树并且有不同的连接类型。主要处理流程如下：

  1. 递归调用transformFromClauseItem函数对JoinExpr的左右子树进行分析。
  2. 检查命名空间是否冲突（重名检查）。
  3. 从左右子树中抽取出列。
  4. 如果是自然连接，则转换成using子句。
  5. 如果存在using子句，则检查其中的连接条件，并通过transformJoinUsingClause函数生成“=”表达式加入到JoinExpr的quals字段中。
  6. 如果不存在using子句，但是quals不为空，则通过transformJoinOnClause函数处理ON给出的连接条件。
  7. 通过addRangeTableEntryForJoin函数向ParseState::p_rtable添加RTE_JOIN类型的RTE。

Target list

SelectStmt::targetList是由ResTarget组成的链表，由函数transformTargetList进行转换。通过transformTargetEntry函数将每一个ResTarget转换成TargetEntry。如果ResTarget::val会通过transformExpr函数转换成表达式。例如，ColumnRef结构会转换成Var结构。

最终，转换后的TargetEntry链表会保存到Query::targetList字段上。

Where clause

通过transformWhereClause函数处理where子句，在内部通过transformExpr函数转换成条件表达式树。

在transformSelectStmt函数的后面将生成的条件表达式树和ParseState::p_joinlist包装成FromExpr结构保存到Query::jointree字段上。

Having clause

通过transformWhereClause函数处理having子句，并将生成的条件表达式树保存到Query::havingQual字段上。

Sort clause

通过transformSortClause函数处理sort子句。

首先对排序链表中的每一个元素分别到targetList中查找是否由匹配的TLE。如果不存在，则将其加入到Query::targetList中，并标记为"resjunk"节点。

然后根据排序顺序和排序字段类型确定排序操作符、相等比较操作符，并生成SortGroupClause结构加入到sortList中，并为对应的TLE的TargetEntry::ressortgroupref字段分配值，并将该值赋给SortGroupClause::tleSortGroupRef。

最后将sortList保存到Query::sortClause字段上。

Group clause

通过transformGroupClause函数处理group子句。

首先将groupList中的grouping set扁平化，然后对groupList中的每一个元素进行转换。与sort子句类似，转换过程中会到targetList中查找是否由匹配的TLE。如果不存在，则将其加入到Query::targetList中，并标记为"resjunk"节点。

如果group字段已经在sortList中，则直接复制对应的SortGroupClause结构并将其加入到groupList中。
如果group字段不在sortList中，则需要生成SortGroupClause结构并为其确定排序操作符、相等比较操作符，并为对应的TLE的TargetEntry::ressortgroupref字段分配值，并将该值赋给SortGroupClause::tleSortGroupRef，最后将SortGroupClause加入到groupList中。

最后将groupList保存到Query::groupClause字段上。

Distinct clause

对于SELECT DISTINCT，通过transformDistinctClause函数处理distinct子句。此时，如果由sort子句，则要求sort字段必需出现在targetList中且不能是resjunk。

对于SELECT DISTINCT ON，通过transformDistinctOnClause函数处理distinct on子句。

对于上面两种情况的处理是相似的。如果sort子句中由distinct子句中的字段，则直接复制sort子句中的SortGroupClause结构并加入到distinctList中。最后通过addTargetToGroupList将所有未出现在sort子句中的字段添加到distinctList中。

最后将distinctList保存到Query::distinctClause字段上。

Limit clause

通过transformLimitClause函数处理offset和count。

首先通过transformExpr函数转换表达式，然后确保表达式是bigint类型，最后检查不能是当前查询中的变量（可以是子查询）。

最后将offset和count表达式保存到Query::limitOffset和Query::limitCount上。

Window clause

通过transformWindowDefinitions函数处理将WindowDef转换为WindowClause。

对WindowDef中的orderClause调用transformSortClause函数进行处理（会将涉及的TLE添加到Query的targetList中）。

对WindowDef中的partitionClause调用transformGroupClause函数进行处理（会将涉及的TLE添加到Query的targetList中）。

对WindowDef中的startOffset和endOffset调用transformFrameOffset函数进行处理。

最后将WindowClause的链表保存到Query::windowClause字段上。

Locking clause

通过transformLockingClause函数处理locking子句链表中的每一项，只支持表和子查询两种类型。

对每一个需要加锁的表生成RowMarkClause并增加到Query::rowMarks中。对于子查询需要递归处理。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • DPDK编程指南（翻译）（ 八）
    8.通用流API 8.1.概述 此API提供了一种通用的方式来配置硬件以匹配特定的Ingress或Egress流量...
    半天妖阅读 11,046评论 0赞 7
  • mysql
    什么是数据库？ 数据库是存储数据的集合的单独的应用程序。每个数据库具有一个或多个不同的API，用于创建，访问，管理...
    chen_000阅读 9,467评论 0赞 19
  • Django查询集 API
    原文：https://my.oschina.net/liuyuantao/blog/751438 查询集API 参...
    阳光小镇少爷阅读 9,248评论 0赞 8
  • 信（中）
    寄出去的信，退了回来。这是铃的最后一个办法，将信寄去梁成的发信地址，但结果是令人失望的。退后来的原因是，查无此地址...
    刘月霞snow阅读 3,008评论 0赞 0
  • 迎接挑战
    今天是沃尔玛扎堆，楼上楼下全部都是我们的小伙伴，被我们围攻了。上午加了十个资源后就松懈了，别人加自己不着急，到后面...
    4c65e162c403阅读 949评论 0赞 0