PostgreSQL Node 数据结构详解

摘要

PostgreSQL 使用一种优雅而强大的树形节点系统来表示 SQL 语句、查询计划、表达式等所有内部数据结构。本文基于 PostgreSQL 源码,详细剖析其核心 Node 系统的设计原理、数据结构、操作函数和使用模式,帮助读者深入理解 PostgreSQL 的内部表示机制。

1. Node 系统概述

1.1 设计原则

PostgreSQL 的 Node 系统遵循一个简单而强大的设计原则:

每种节点的第一个字段必定是 NodeTag 类型标识符。

// src/include/nodes/nodes.h
typedef struct Node
{
    NodeTag     type;           // 节点类型标识符
} Node;

这个设计使得:

任意节点都可以通过强制转换为 Node* 来识别类型
IsA() 宏可以安全地检查任意节点类型
节点树可以统一遍历和处理

1.2 Node 类型分类

类别	示例	说明
表达式节点	`Const`, `Var`, `FuncExpr`	表示表达式
查询节点	`Query`, `SelectStmt`	表示完整查询
计划节点	`SeqScan`, `HashJoin`, `Sort`	执行计划
路径节点	`IndexPath`, `NestPath`	优化器内部路径
列表节点	`List`, `IntList`	容器类型
值节点	`Integer`, `String`, `Float`	原始数据类型

2. NodeTag 枚举详解

2.1 NodeTag 定义

NodeTag 是一个枚举类型,定义了所有可能的节点类型:

// src/include/nodes/nodetags.h (自动生成)
typedef enum NodeTag
{
    T_Invalid = 0,
    
    /* 列表和别名节点 */
    T_List = 1,
    T_Alias = 2,
    T_RangeVar = 3,
    
    /* 表达式节点 (5-61) */
    T_Var = 5,
    T_Const = 6,
    T_Param = 7,
    T_Aggref = 8,
    T_WindowFunc = 9,
    T_SubLink = 10,
    T_FuncExpr = 11,
    T_OpExpr = 12,
    T_BoolExpr = 13,
    T_FieldSelect = 14,
    /* ... 更多表达式类型 ... */
    
    /* 解析树节点 (67-140) */
    T_RawStmt = 67,
    T_SelectStmt = 68,
    T_InsertStmt = 69,
    T_UpdateStmt = 70,
    T_DeleteStmt = 71,
    T_CreateStmt = 72,      // CREATE TABLE
    T_Constraint = 73,
    /* ... 更多 DDL 节点 ... */
    
    /* 计划节点 (341-430) */
    T_Result = 341,
    T_SeqScan = 342,
    T_IndexScan = 343,
    T_HashJoin = 344,
    T_Sort = 345,
    T_Agg = 346,
    T_Material = 347,
    /* ... 更多执行计划节点 ... */
    
    /* 值节点 */
    T_Integer = 459,
    T_Float = 460,
    T_Boolean = 461,
    T_String = 462
} NodeTag;

2.2 按功能组织的 NodeTag

T_Invalid (0)
    │
    ├── 基础类型 (1-4)
    │       T_List, T_Alias, T_RangeVar, T_TableFunc
    │
    ├── 表达式节点 (5-61)
    │       ├── 变量/常量: T_Var, T_Const, T_Param
    │       ├── 函数调用: T_Aggref, T_WindowFunc, T_FuncExpr, T_OpExpr
    │       ├── 逻辑表达式: T_BoolExpr (AND/OR/NOT)
    │       ├── 比较表达式: T_SubLink, T_NullIfExpr, T_CoalesceExpr
    │       ├── 类型转换: T_RelabelType, T_CoerceViaIO
    │       └── 其他: T_CaseExpr, T_ArrayExpr, T_RowExpr
    │
    ├── 查询结构节点 (62-66)
    │       T_TargetEntry, T_RangeTblRef, T_JoinExpr, T_FromExpr, T_Query
    │
    ├── 解析树节点 (67-140)
    │       ├── 语句: T_InsertStmt, T_UpdateStmt, T_DeleteStmt
    │       ├── DDL: T_CreateStmt, T_AlterTableStmt, T_DropStmt
    │       └── 其他: T_TypeName, T_ColumnDef, T_IndexElem
    │
    ├── 优化器节点 (262-340)
    │       ├── 关系信息: T_RelOptInfo, T_IndexOptInfo
    │       └── 路径: T_Path, T_IndexPath, T_HashPath, T_NestPath
    │
    ├── 执行计划节点 (341-430)
    │       ├── 扫描: T_SeqScan, T_IndexScan, T_BitmapScan
    │       ├── 连接: T_NestLoop, T_MergeJoin, T_HashJoin
    │       ├── 操作: T_Sort, T_Agg, T_Group, T_Limit
    │       └── 修改: T_ModifyTable, T_Append
    │
    └── 值节点 (459-463)
            T_Integer, T_Float, T_Boolean, T_String

3. 类型检查与转换

3.1 IsA 宏

// src/include/nodes/nodes.h
#define nodeTag(nodeptr)     (((const Node*)(nodeptr))->type)

#define IsA(nodeptr, _type_) (nodeTag(nodeptr) == T_##_type_)

使用示例:

Node *node;

if (IsA(node, Query))
{
    // node 是 Query 类型
    Query *query = (Query *) node;
}

if (IsA(node, Const))
{
    // node 是 Const 类型
    Const *con = (Const *) node;
}

// 检查多个类型
if (IsA(node, SelectStmt) || IsA(node, InsertStmt))
{
    // 处理的 DML 语句
}

3.2 castNode 宏 (类型安全转换)

// src/include/nodes/nodes.h
#ifdef USE_ASSERT_CHECKING
static inline Node *
castNodeImpl(NodeTag type, void *ptr)
{
    // 仅在断言模式下检查类型
    Assert(ptr == NULL || nodeTag(ptr) == type);
    return (Node *) ptr;
}
#define castNode(_type_, nodeptr) \
    ((_type_ *) castNodeImpl(T_##_type_, nodeptr))
#else
#define castNode(_type_, nodeptr) ((_type_ *) (nodeptr))
#endif

使用示例:

// 类型安全的节点转换,带断言检查
Query *query = castNode(Query, rawStmt->stmt);

// 如果类型不匹配,会触发断言失败
// 仅在 debug 模式下启用检查,生产环境零开销

3.3 is_node_like Macro

// 检查节点类型是否匹配模式
#define is_node_like(nodeptr, pattern) \
    (nodeTag(nodeptr) == T_##pattern || \
     nodeTag(nodeptr) == T_##pattern##2 || ...)

4. 节点创建与内存管理

4.1 makeNode 宏

// src/include/nodes/nodes.h

// 内部分配器 - 使用 palloc0 分配并清零内存
static inline Node *
newNode(Size size, NodeTag tag)
{
    Node *result;
    Assert(size >= sizeof(Node));      // 确保足够容纳 Node 结构
    result = (Node *) palloc0(size);   // 分配并清零
    result->type = tag;
    return result;
}

// 推荐使用的节点创建宏
#define makeNode(_type_) \
    ((_type_ *) newNode(sizeof(_type_), T_##_type_))

使用示例:

// 创建一个 Query 节点
Query *query = makeNode(Query);

// 创建一个常量表达式
Const *c = makeNode(Const);

// 创建一个 RangeVar (表引用)
RangeVar *rv = makeNode(RangeVar);
rv->catalogname = NULL;
rv->schemaname = "public";
rv->relname = "users";

4.2 makeNode 示例函数

// src/backend/nodes/makefuncs.c

// 创建 Var 节点 (变量引用)
Var *
makeVar(int varno, AttrNumber varattno, Oid vartype, 
        int32 vartypmod, Oid varcollid, Index varlevelsup)
{
    Var *var = makeNode(Var);
    var->varno = varno;
    var->varattno = varattno;
    var->vartype = vartype;
    var->vartypmod = vartypmod;
    var->varcollid = varcollid;
    var->varlevelsup = varlevelsup;
    var->varnosyn = (Index) varno;
    var->varattnosyn = varattno;
    var->location = -1;
    var->varnullingrels = NULL;
    return var;
}

// 创建常量节点
Const *
makeConst(Oid consttype, int32 consttypmod, Oid constcollid,
          int constlen, Datum constvalue, 
          bool constisnull, bool constbyval)
{
    Const *cnst = makeNode(Const);
    cnst->consttype = consttype;
    cnst->consttypmod = consttypmod;
    cnst->constcollid = constcollid;
    cnst->constlen = constlen;
    cnst->constvalue = constvalue;
    cnst->constisnull = constisnull;
    cnst->constbyval = constbyval;
    cnst->location = -1;
    return cnst;
}

// 创建目标项 (SELECT 列)
TargetEntry *
makeTargetEntry(Expr *expr, AttrNumber resno, 
                char *resname, bool resjunk)
{
    TargetEntry *tle = makeNode(TargetEntry);
    tle->expr = expr;
    tle->resno = resno;
    tle->resname = resname;
    tle->ressortgroupref = 0;
    tle->resorigtbl = InvalidOid;
    tle->resorigcol = 0;
    tle->resjunk = resjunk;
    return tle;
}

4.3 节点内存上下文

节点分配在当前内存上下文中,通常使用 CurrentMemoryContext:

// 节点在当前上下文中分配
Node *node = makeNode(Query);

// 切换到特定上下文创建节点
MemoryContext old = MemoryContextSwitchTo(QueryContext);
Node *node = makeNode(Query);
MemoryContextSwitchTo(old);

5. List 结构详解

5.1 List 数据结构

PostgreSQL 的 List 是可扩展数组,不是传统的 Lisp 链表:

// src/include/nodes/list.h
typedef struct List
{
    NodeTag     type;           // T_List, T_IntList, T_OidList, T_XidList
    int         length;        // 当前元素数量
    int         max_length;    // 已分配的元素数组长度
    ListCell   *elements;      // 可重分配的数组指针
    ListCell    initial_elements[];  // 内联存储
} List;

// 空列表表示
#define NIL ((List *) NULL)

5.2 ListCell 联合体

typedef union ListCell
{
    void       *ptr_value;         // T_List 使用
    int         int_value;        // T_IntList 使用
    Oid         oid_value;        // T_OidList 使用
    TransactionId xid_value;      // T_XidList 使用
} ListCell;

5.3 List 类型

类型	NodeTag	元素类型	示例用途
`T_List`	通用列表	`void *`	节点树、语句列表
`T_IntList`	整数列表	`int`	列号、偏移量
`T_OidList`	OID 列表	`Oid`	表 OID、类型 OID
`T_XidList`	事务 ID 列表	`TransactionId`	事务列表

5.4 ListCell 访问宏

// 获取元素值
#define lfirst(lc)              ((lc)->ptr_value)
#define lfirst_int(lc)          ((lc)->int_value)
#define lfirst_oid(lc)          ((lc)->oid_value)
#define lfirst_node(type, lc)   castNode(type, lfirst(lc))

// 按索引访问
#define linitial(l)             lfirst(list_nth_cell(l, 0))
#define lsecond(l)              lfirst(list_nth_cell(l, 1))
#define lthird(l)               lfirst(list_nth_cell(l, 2))
#define llast(l)                lfirst(list_last_cell(l))

// 安全的整数/OID 访问
#define linitial_int(l)         lfirst_int(list_nth_cell(l, 0))
#define llast_int(l)            lfirst_int(list_last_cell(l))

5.5 List 创建宏

// 创建指针列表 (T_List)
#define list_make1(x1)          list_make1_impl(T_List, list_make_ptr_cell(x1))
#define list_make2(x1, x2)      ...
#define list_make3(x1, x2, x3)  ...
#define list_make4(x1, x2, x3, x4) ...
#define list_make5(x1, x2, x3, x4, x5) ...

// 创建整数列表 (T_IntList)
#define list_make1_int(x1)      list_make1_impl(T_IntList, list_make_int_cell(x1))
#define list_make2_int(x1, x2)  ...

// 创建 OID 列表 (T_OidList)
#define list_make1_oid(x1)      list_make1_impl(T_OidList, list_make_oid_cell(x1))

// 便捷创建函数
List *list_make1_impl(NodeTag type, ListCell c1);
List *list_make2_impl(NodeTag type, ListCell c1, ListCell c2);

5.6 List 遍历

// 基础遍历
ListCell *cell;
foreach (cell, myList)
{
    Node *node = lfirst(cell);
    // 处理 node
}

// 使用指针遍历 (更简洁)
Node *node;
foreach_ptr (Node, node, myList)
{
    // 处理 node
}

// 带索引遍历
int i = 0;
for (ListCell *cell = list_head(myList); 
     cell != NULL; 
     cell = lnext(myList, cell), i++)
{
    Node *node = lfirst(cell);
    // 处理 node, i 是索引
}

5.7 List 操作函数

// 追加元素
List *lappend(List *list, void *datum);
List *lappend_int(List *list, int datum);
List *lappend_oid(List *list, Oid datum);

// 前置元素
List *lcons(void *datum, List *list);
List *lcons_int(int datum, List *list);

// 连接列表
List *list_concat(List *list1, const List *list2);

// 删除元素
List *list_delete(List *list, const void *datum);
List *list_delete_first(List *list);

// 成员检查
bool list_member(const List *list, const void *datum);
bool list_member_int(const List *list, int datum);
bool list_member_oid(const List *list, Oid datum);

// 列表长度
int list_length(const List *list);

// 列表复制
List *list_copy(const List *oldlist);          // 浅复制
List *list_copy_deep(const List *oldlist);    // 深复制

// 列表切片
List *list_truncate(List *list, int n);       // 保留前 n 个元素

5.8 List 使用示例

// 构建整数列表
List *colNums = list_make2_int(1, 2);
colNums = lappend_int(colNums, 3);
// 结果: [1, 2, 3]

// 构建节点列表
List *exprList = list_make1(makeConst(INT4OID, -1, 0, 
                                       sizeof(int32), Int32GetDatum(1),
                                       false, true));
exprList = lappend(exprList, makeConst(INT4OID, -1, 0,
                                       sizeof(int32), Int32GetDatum(2),
                                       false, true));

// 遍历处理
foreach (cell, exprList)
{
    Const *c = lfirst_node(Const, cell);
    Datum val = c->constvalue;
    // 处理常量值
}

// OID 列表 (表引用)
List *tableOids = list_make1_oid(MyTableRelationId);
tableOids = list_concat(tableOids, list_make1_oid(OtherTableId));

6. 值节点 (Value Nodes)

6.1 原始值类型定义

// src/include/nodes/value.h

typedef struct Integer
{
    NodeTag     type;           // T_Integer = 459
    int         ival;          // 整数值
} Integer;

typedef struct Float
{
    NodeTag     type;           // T_Float = 460
    char       *fval;          // 存储为字符串以保持精度
} Float;

typedef struct Boolean
{
    NodeTag     type;           // T_Boolean = 461
    bool        boolval;
} Boolean;

typedef struct String
{
    NodeTag     type;           // T_String = 462
    char       *sval;          // 字符串值
} String;

6.2 值访问宏

#define intVal(v)      (castNode(Integer, v)->ival)
#define floatVal(v)    (atof(castNode(Float, v)->fval))
#define boolVal(v)    (castNode(Boolean, v)->boolval)
#define strVal(v)     (castNode(String, v)->sval)

6.3 值节点使用示例

// 在表达式中使用值节点
Node *make_int_node(int i)
{
    Integer *n = makeNode(Integer);
    n->ival = i;
    return (Node *) n;
}

Node *make_string_node(const char *s)
{
    String *n = makeNode(String);
    n->sval = pstrdup(s);
    return (Node *) n;
}

// 在解析中使用
Node *parse_value = make_int_node(42);
if (IsA(parse_value, Integer))
{
    int val = intVal(parse_value);
    printf("Integer value: %d\n", val);
}

7. 表达式节点详解

7.1 Const 节点 (常量)

// src/include/nodes/primnodes.h
typedef struct Const
{
    Expr        xpr;
    Oid         consttype;      // 数据类型 OID
    int32       consttypmod;   // 类型修饰符
    Oid         constcollid;   // 排序规则 OID
    int         constlen;      // 常量长度 (-1 表示变长)
    Datum       constvalue;     // 实际值
    bool        constisnull;   // 是否为 NULL
    bool        constbyval;    // 是否按值传递
    bool        constisarray;  // 是否为数组类型
    int         location;      // 解析位置
} Const;

7.2 Var 节点 (变量引用)

// src/include/nodes/primnodes.h
typedef struct Var
{
    Expr        xpr;
    Index       varno;         // 范围表索引
    AttrNumber  varattno;      // 属性编号 (1-based)
    Oid         vartype;       // 数据类型
    int32       vartypmod;     // 类型修饰符
    Oid         varcollid;     // 排序规则
    Index       varlevelsup;   // 上层嵌套级别 (用于子查询)
    Index       varnosyn;      // 同步索引
    AttrNumber  varattnosyn;   // 同步属性编号
    int         location;      // 位置
    Bitmapset   *varnullingrels;  // 可为空的列
} Var;

7.3 FuncExpr 节点 (函数调用)

// src/include/nodes/primnodes.h
typedef struct FuncExpr
{
    Expr        xpr;
    Oid         funcid;         // 函数 OID
    Oid         funcresulttype; // 返回类型
    bool        funcretset;    // 是否返回集合
    bool        funcvariadic;  // 是否有可变参数
    Oid        *funccoltypes;  // 返回列类型
    int32      *funccoltypmods; // 返回列类型修饰符
    int         funcformat;    // 格式 (刚量/IO 转换)
    List       *args;          // 参数列表
    int         location;      // 位置
} FuncExpr;

7.4 表达式节点示例

// 构建表达式: users.age + 1 > 18
FuncExpr *
build_age_check_expr(void)
{
    // Var: users.age
    Var *age = makeVar(1, 2, INT4OID, -1, InvalidOid, 0);
    
    // Const: 1
    Const *one = makeConst(INT4OID, -1, InvalidOid, 
                           sizeof(int32), Int32GetDatum(1),
                           false, true);
    
    // Const: 18
    Const *eighteen = makeConst(INT4OID, -1, InvalidOid,
                                 sizeof(int32), Int32GetDatum(18),
                                 false, true);
    
    // age + 1
    OpExpr *plus = makeNode(OpExpr);
    plus->opno = Int4EqualOperator;  // 或实际的操作符 OID
    plus->args = list_make2(age, one);
    plus->opfuncid = F_INT4PL;
    
    // (age + 1) > 18
    OpExpr *gt = makeNode(OpExpr);
    gt->opno = Int4GreaterOperator;
    gt->args = list_make2(plus, eighteen);
    gt->opfuncid = F_INT4GT;
    
    return gt;
}

8. 查询计划节点

8.1 Plan 基结构

// src/include/nodes/plannodes.h
typedef struct Plan
{
    NodeTag     type;
    
    // 成本估算
    Cost        startup_cost;   // 开始获取元组前的成本
    Cost        total_cost;     // 总成本
    Cardinality plan_rows;      // 估算行数
    int         plan_width;     // 平均行宽 (字节)
    
    // 并行相关
    bool        parallel_aware;
    bool        parallel_safe;
    bool        async_capable;
    
    // 通用字段
    int         plan_node_id;   // 计划树中的唯一 ID
    List       *targetlist;     // 输出列 (TargetEntry 列表)
    List       *qual;           // 过滤条件 (AND 列表)
    Plan       *lefttree;       // 左子节点 (外层)
    Plan       *righttree;      // 右子节点 (内层)
    List       *initPlan;       // InitPlan 节点
    
    // 参数追踪
    Bitmapset  *extParam;       // 影响此节点的外部参数
    Bitmapset  *allParam;       // 影响此节点的所有参数
} Plan;

// 子节点访问宏
#define outerPlan(node)   (((Plan *)(node))->lefttree)
#define innerPlan(node)   (((Plan *)(node))->righttree)

8.2 TargetEntry 结构

// src/include/nodes/primnodes.h
typedef struct TargetEntry
{
    Expr        xpr;            // 内嵌的 Expr (用于内存管理)
    Expr       *expr;          // 要计算的表达式
    AttrNumber  resno;         // 属性编号 (输出列号)
    char       *resname;       // 列名 (用于显示)
    Index       ressortgroupref; // 排序/分组引用
    Oid         resorigtbl;    // 源表 OID
    AttrNumber  resorigcol;    // 源表中的列号
    bool        resjunk;       // true = 从最终输出中移除
} TargetEntry;

8.3 常见计划节点

shell

PlannedStmt (根节点)
    │
    └── Plan (基类)
          │
          ├── Scan (扫描)
          │     ├── SeqScan      - 顺序扫描
          │     ├── IndexScan    - 索引扫描
          │     ├── IndexOnlyScan - 仅索引扫描
          │     ├── BitmapScan   - 位图扫描
          │     └── TidScan      - CTID 扫描
          │
          ├── Join (连接)
          │     ├── NestLoop     - 嵌套循环连接
          │     ├── MergeJoin    - 归并连接
          │     └── HashJoin     - 哈希连接
          │
          ├── 操作符
          │     ├── Sort         - 排序
          │     ├── Agg          - 聚合
          │     ├── WindowAgg    - 窗口函数
          │     ├── Group        - 分组
          │     ├── Unique       - 去重
          │     ├── Limit        - 限制
          │     └── Material     - 物化
          │
          └── 修改
                └── ModifyTable - INSERT/UPDATE/DELETE

8.4 计划树构建示例

// 构建简单查询: SELECT name FROM users WHERE id = 1 ORDER BY name

// 1. 创建扫描计划 (叶子节点)
SeqScan *scan = makeNode(SeqScan);
scan->plan.plan_node_id = 1;
scan->scanrelid = 1;  // 范围表索引

// 2. 创建目标列表
TargetEntry *tle1 = makeTargetEntry(
    makeVar(1, 2, TEXTOID, -1, InvalidOid, 0),  // name 列
    1,                                           // resno = 1
    "name",                                      // 列名
    false                                        // 不是 junk
);
scan->plan.targetlist = list_make1(tle1);

// 3. 创建过滤条件: id = 1
Var *id_var = makeVar(1, 1, INT4OID, -1, InvalidOid, 0);
Const *one = makeConst(INT4OID, -1, InvalidOid, 
                       sizeof(int32), Int32GetDatum(1), false, true);
OpExpr *id_eq = makeNode(OpExpr);
id_eq->opno = Int4EqualOperator;
id_eq->args = list_make2(id_var, one);
scan->plan.qual = list_make1(id_eq);

// 4. 创建排序
Sort *sort = makeNode(Sort);
sort->plan.plan_node_id = 2;
sort->plan.lefttree = (Plan *)scan;
sort->plan.targetlist = scan->plan.targetlist;
sort->numCols = 1;
sort->sortColIdx = list_make1_int(1);  // 按第1列排序
sort->sortOperators = list_make1_oid(bttextcmp);

// 5. 包装为 PlannedStmt
PlannedStmt *stmt = makeNode(PlannedStmt);
stmt->commandType = CMD_SELECT;
stmt->planTree = (Plan *)sort;
stmt->rtable = list_of_range_table_entries;

9. 节点树操作

9.1 节点复制 (copyfuncs.c)

// 深度复制整个节点树
void *copyObjectImpl(const void *from);

#define copyObject(obj) \
    ((typeof(obj)) copyObjectImpl(obj))

// 使用示例
Query *original = parseQuery();
Query *copy = copyObject(original);
// 复制整个节点树,包括所有子节点

9.2 节点比较 (equalfuncs.c)

// 比较两个节点树是否结构相等
bool equal(const void *a, const void *b);

// 使用示例
Query *q1 = ...;
Query *q2 = ...;
if (equal(q1, q2))
{
    // 两个查询结构相同
}

9.3 节点序列化 (outfuncs.c)

// 将节点树转换为字符串表示
char *nodeToString(const void *obj);

// 使用示例
char *str = nodeToString(myQuery);
elog(DEBUG1, "Query plan: %s", str);
pfree(str);

9.4 节点反序列化 (readfuncs.c)

// 从字符串恢复节点树
void *stringToNode(const char *str);

// 使用示例
Node *restored = stringToNode(str);

9.5 表达式类型信息 (nodeFuncs.c)

// 获取表达式类型
Oid exprType(const Node *expr);
int32 exprTypmod(const Node *expr);
Oid exprCollation(const Node *expr);

// 检查表达式属性
bool exprIsLengthCoercion(const Node *expr, int32 *coercedTypmod);
bool exprIsLengthCoercion(const Node *expr, ...);

// 剥离隐式强制转换
Node *strip_implicit_coercions(Node *node);

// 获取位置信息
int exprLocation(const Node *expr);

10. 节点系统使用模式

10.1 遍历节点树

// 递归遍历节点树
void
walk_node_tree(Node *node, void *context)
{
    if (node == NULL)
        return;
    
    switch (nodeTag(node))
    {
        case T_Query:
            walk_query((Query *) node, context);
            break;
        case T_SelectStmt:
            walk_select((SelectStmt *) node, context);
            break;
        case T_Const:
            // 处理常量
            break;
        case T_List:
            {
                List *list = (List *) node;
                ListCell *cell;
                foreach (cell, list)
                    walk_node_tree(lfirst(cell), context);
            }
            break;
        default:
            // 递归处理所有子节点
            if (IsA(node, Expr))
                walk_expr((Expr *) node, context);
            break;
    }
}

10.2 统计节点数量

// 统计计划树中的节点数
int
count_plan_nodes(Plan *plan)
{
    int count = 1;  // 当前节点
    ListCell *lc;
    
    // 遍历目标列表
    foreach (lc, plan->targetlist)
    {
        TargetEntry *tle = lfirst_node(TargetEntry, lc);
        count += count_expr_nodes((Node *) tle->expr);
    }
    
    // 遍历过滤条件
    foreach (lc, plan->qual)
        count += count_expr_nodes(lfirst(lc));
    
    // 递归处理子节点
    if (outerPlan(plan))
        count += count_plan_nodes(outerPlan(plan));
    if (innerPlan(plan))
        count += count_plan_nodes(innerPlan(plan));
    
    return count;
}

10.3 修改节点树

// 替换节点树中的子节点
Node *
replace_var_in_targetlist(Plan *plan, Var *old_var, Var *new_var)
{
    List *new_tlist = NULL;
    ListCell *lc;
    
    foreach (lc, plan->targetlist)
    {
        TargetEntry *tle = lfirst_node(TargetEntry, lc);
        Expr *new_expr = (Expr *) replace_var_in_expr(tle->expr, 
                                                      (Node *) old_var, 
                                                      (Node *) new_var);
        TargetEntry *new_tle = makeTargetEntry(new_expr, tle->resno,
                                               tle->resname, tle->resjunk);
        new_tlist = lappend(new_tlist, new_tle);
    }
    
    plan->targetlist = new_tlist;
    return (Node *) plan;
}

11. 源码文件索引

文件路径	功能描述
`src/include/nodes/nodes.h`	Node 基结构、IsA 宏、makeNode
`src/include/nodes/nodetags.h`	NodeTag 枚举定义
`src/include/nodes/list.h`	List 数据结构、ListCell
`src/include/nodes/value.h`	Integer、Float、String、Boolean 值节点
`src/include/nodes/primnodes.h`	Var、Const、FuncExpr、TargetEntry
`src/include/nodes/parsenodes.h`	CreateStmt、SelectStmt 等解析节点
`src/include/nodes/plannodes.h`	Plan、SeqScan、HashJoin 等执行计划节点
`src/include/nodes/pathnodes.h`	Path、IndexPath 等优化器路径节点
`src/backend/nodes/makefuncs.c`	makeVar、makeConst、makeTargetEntry 等创建函数
`src/backend/nodes/copyfuncs.c`	copyObject 深度复制实现
`src/backend/nodes/equalfuncs.c`	equal 节点比较实现
`src/backend/nodes/outfuncs.c`	nodeToString 序列化实现
`src/backend/nodes/readfuncs.c`	stringToNode 反序列化实现
`src/backend/nodes/list.c`	List 操作函数实现

12. 总结

核心要点

统一标识: 所有节点都以 NodeTag 开头,实现统一的类型识别
IsA 模式: 通过简单的标签比较实现类型检查,零运行时开销
makeNode 模式: 使用 palloc0 分配并清零内存的节点创建模式
List 容器: 使用可扩展数组实现的通用容器,支持指针、整数、OID 等类型
节点树: SQL 语句和查询计划都表示为树形节点结构
函数式操作: 通过 copyObject、equal、nodeToString 等函数实现通用的节点树操作

设计优势

类型安全: 通过 IsA 和 castNode 实现类型检查
内存管理: 与 MemoryContext 集成,便于统一释放
树形表示: 自然地表示 SQL 语句和执行计划的层次结构
可扩展性: 新增节点类型只需添加新的结构体和 NodeTag 值
通用操作: 复制、比较、序列化等操作适用于所有节点类型

本文档基于 PostgreSQL 源码分析编写,详细阐述了 PostgreSQL 核心 Node 数据结构的设计、实现和使用方法。

PostgreSQL Node 数据结构详解 ​

摘要 ​

1. Node 系统概述 ​

1.1 设计原则 ​

1.2 Node 类型分类 ​

2. NodeTag 枚举详解 ​

2.1 NodeTag 定义 ​

2.2 按功能组织的 NodeTag ​

3. 类型检查与转换 ​

3.1 IsA 宏 ​

3.2 castNode 宏 (类型安全转换) ​

3.3 is_node_like Macro ​

4. 节点创建与内存管理 ​

4.1 makeNode 宏 ​

4.2 makeNode 示例函数 ​

4.3 节点内存上下文 ​

5. List 结构详解 ​

5.1 List 数据结构 ​

5.2 ListCell 联合体 ​

5.3 List 类型 ​

5.4 ListCell 访问宏 ​

5.5 List 创建宏 ​

5.6 List 遍历 ​

5.7 List 操作函数 ​

5.8 List 使用示例 ​

6. 值节点 (Value Nodes) ​

6.1 原始值类型定义 ​

6.2 值访问宏 ​

6.3 值节点使用示例 ​

7. 表达式节点详解 ​

7.1 Const 节点 (常量) ​

7.2 Var 节点 (变量引用) ​

7.3 FuncExpr 节点 (函数调用) ​

7.4 表达式节点示例 ​

8. 查询计划节点 ​

8.1 Plan 基结构 ​

8.2 TargetEntry 结构 ​

8.3 常见计划节点 ​

8.4 计划树构建示例 ​

9. 节点树操作 ​

9.1 节点复制 (copyfuncs.c) ​

9.2 节点比较 (equalfuncs.c) ​

9.3 节点序列化 (outfuncs.c) ​

9.4 节点反序列化 (readfuncs.c) ​

9.5 表达式类型信息 (nodeFuncs.c) ​

10. 节点系统使用模式 ​

10.1 遍历节点树 ​

10.2 统计节点数量 ​

10.3 修改节点树 ​

11. 源码文件索引 ​

12. 总结 ​

核心要点 ​

设计优势 ​

PostgreSQL Node 数据结构详解

摘要

1. Node 系统概述

1.1 设计原则

1.2 Node 类型分类

2. NodeTag 枚举详解

2.1 NodeTag 定义

2.2 按功能组织的 NodeTag

3. 类型检查与转换

3.1 IsA 宏

3.2 castNode 宏 (类型安全转换)

3.3 is_node_like Macro

4. 节点创建与内存管理

4.1 makeNode 宏

4.2 makeNode 示例函数

4.3 节点内存上下文

5. List 结构详解

5.1 List 数据结构

5.2 ListCell 联合体

5.3 List 类型

5.4 ListCell 访问宏

5.5 List 创建宏

5.6 List 遍历

5.7 List 操作函数

5.8 List 使用示例

6. 值节点 (Value Nodes)

6.1 原始值类型定义

6.2 值访问宏

6.3 值节点使用示例

7. 表达式节点详解

7.1 Const 节点 (常量)

7.2 Var 节点 (变量引用)

7.3 FuncExpr 节点 (函数调用)

7.4 表达式节点示例

8. 查询计划节点

8.1 Plan 基结构

8.2 TargetEntry 结构

8.3 常见计划节点

8.4 计划树构建示例

9. 节点树操作

9.1 节点复制 (copyfuncs.c)

9.2 节点比较 (equalfuncs.c)

9.3 节点序列化 (outfuncs.c)

9.4 节点反序列化 (readfuncs.c)

9.5 表达式类型信息 (nodeFuncs.c)

10. 节点系统使用模式

10.1 遍历节点树

10.2 统计节点数量

10.3 修改节点树

11. 源码文件索引

12. 总结

核心要点

设计优势