(KO) PostgreSQL 노드 시스템 — NodeTag, copyObject, gen_node_support 코드 생성

목차

• 이론적 배경
• DBMS 공통 설계
• PostgreSQL의 접근법
• 소스 탐방
• 소스 검증 (2026-06-05 기준)
• PostgreSQL 너머 — 비교 설계와 연구 프런티어
• 출처

이론적 배경

SQL 구문 하나는 백엔드를 통과하면서 여러 번 다른 형태로 다시 태어난다. 처음에는 텍스트를 충실히 옮긴 **파스 트리(parse tree)**가 되고, 다음에는 재작성된 **쿼리 트리(query tree)**가 되며, 최적화된 플랜 트리(plan tree)(물리 연산자들의 트리)가 된 뒤, 마지막으로 엔진이 행을 생산하기 위해 순회하는 **실행 상태 트리(execution state tree)**가 된다. Database System Concepts(Silberschatz, 7판, 15–16장)는 이 파이프라인을 일련의 *중간 표현(intermediate representation)*으로 설명한다. 각 표현은 관계대수 스타일 연산자들의 트리이며, 반복되는 공학적 질문은 트리 노드를 메모리에서 어떻게 표현하고 범용 알고리즘이 어떻게 순회하는가이다.

이 질문에 대한 고전적인 두 가지 답이 경쟁한다.

• 객체지향 방식. 각 노드 타입을 클래스로 만들고, 복사·비교·직렬화를 가상 메서드로 구현하며, 컴파일러의 vtable이 디스패치를 담당한다. 설계는 깔끔하지만 C++(또는 Java) 객체 모델을 코어에 끌어들이고, 병렬 워커에 플랜을 전송할 때 필요한 프로세스 경계를 넘는 직렬화는 클래스별로 작성하거나 생성해야 한다는 점에서 문제가 남는다.
• 태그 유니온 방식. 모든 노드가 구체적인 타입을 식별하는 작은 정수 **태그(tag)**를 가진다. 범용 루틴이 태그를 읽고 switch로 타입별 코드로 분기한다. 이것은 Lisp 전통이다. s-표현식은 태그가 붙은 셀이고, copy·equal·print·read는 태그를 따라 재귀하는 범용 함수다. PostgreSQL은 Lisp 전통에서 직접 유래했다(POSTGRES는 부분적으로 Lisp으로 프로토타입됐다). 노드 시스템은 그 계보의 화석 기록이다.

태그 방식에는 잘 알려진 비용이 있다. 태그에 대한 switch와 타입별 복사·비교·직렬화 코드를 구조체 정의와 항상 동기화해야 한다. 복사 루틴에서 필드를 빠뜨리면 공유 하위 구조를 별명(alias)으로 가리키는 얕은 복사본이 생기고, 비교 루틴에서 빠뜨리면 리라이터가 서로 다른 두 표현식을 동일하다고 판단한다. 이런 동기화를 손으로 유지하는 일은 코드 생성기가 맡아야 할 기계적이고 오류 유발성 높은 작업이다. 이 문서의 주제가 바로 그것이다. PostgreSQL은 태그 유니온 표현을 유지하되, 구조체 정의 자체에서 타입별 기반 코드를 파생시킨다.

두 가지 이론적 기반이 더 있다.

1. 리스트의 표현. 관계 플랜에는 가변 길이 시퀀스가 많다. 대상 목록(target list), 조건 목록(qual list), 조인의 자식 목록이 그 예다. 교과서는 이것들을 집합/시퀀스로 추상적으로 다루지만, 구현에는 빠른 추가(append)와 인덱스 접근이 가능한 구체적인 컨테이너가 필요하다. 순진한 Lisp 방식은 cons 셀의 연결 리스트이고, 캐시 친화적인 방식은 확장 가능 배열이다. PostgreSQL은 v13에서 전자에서 후자로 이전했다. Lisp 스타일 API(lappend, lfirst, foreach)는 유지했다. 이것은 표현 방식을 바꾸면서 인터페이스를 보존한 교과서적 사례다.

2. 깊은 복사와 구조적 동등성. 하위 구조를 공유하는 트리는 변경하기 위험하다. 플래너는 Query를 재작성하기 전에 복사하고, 규칙 적용은 표현식을 다른 곳에 이어 붙이기 전에 복사한다. 여기서 “복사”는 도달 가능한 전체 하위 그래프를 복제하는 **깊은 복사(deep copy)**여야 하고, “동등”은 포인터 동일성이 아닌 필드별 재귀 검사인 **구조적 동등성(structural equality)**이어야 한다. 노드 시스템이 제공해야 하는 두 범용 재귀 연산이 바로 이것이며, 둘 다 태그로 디스패치된다.

DBMS 공통 설계

태그 노드 트리 시스템이라면 어떤 DBMS든 핵심 설계 결정들을 반복한다.

판별자(discriminator) 필드는 항상 첫 번째 자리에

타입 없는 포인터만 가진 루틴이 구체적인 타입을 모르는 상태에서도 태그를 읽을 수 있으려면, 태그가 고정된 알려진 오프셋에 있어야 한다. 보편적인 관례는 오프셋 0이다. 태그를 모든 노드의 첫 번째 필드로 두면 *(Tag *) ptr은 항상 타입을 돌려준다. PostgreSQL의 Node는 문자 그대로 struct { NodeTag type; }이며, nodeTag(p)는 그 첫 번째 워드를 캐스트해서 읽는다.

구조체 접두사로 구현하는 상속

C에는 클래스가 없으므로 “B는 A다”는 B의 첫 번째 필드를 A로 만드는 방식으로 표현한다. A의 첫 번째 필드가 태그이므로, B의 첫 번째 필드도 재귀적으로 태그가 된다. B*를 A*나 Node*로 캐스트해도 올바른 판별자를 가리킨다. PostgreSQL은 전체 플랜 계층 구조에 이 방식을 사용한다. SeqScan은 Scan을 내장하고, Scan은 Plan을 내장하며, Plan은 NodeTag를 내장한다.

할당-후-태그 도장 찍기 방식의 생성자

생성자는 (a) 올바른 바이트 수를 할당하고 (b) 올바른 태그를 기록해야 한다. PostgreSQL의 makeNode(T)는 newNode(sizeof(T), T_T)로 확장되는 매크로다. palloc0(0으로 채우기)을 하고 태그를 설정한다. 0 채우기는 중요하다. 설정되지 않은 모든 필드가 깨끗한 NULL/0이므로, 범용 깊은 복사와 직렬화 루틴이 쓰레기 값을 읽지 않는다.

태그로 구동하는 범용 순회

복사, 비교, 직렬화, 역직렬화, 표현식 순회, 표현식 변환은 모두 같은 형태다. 태그를 읽고, switch하고, 타입별 작업을 수행하고, 자식 노드를 재귀한다. 모든 구현이 직면하는 열린 질문은 타입별 작업이 손으로 작성되는가 아니면 생성되는가이다. 손 작성은 읽기 쉽지만 부패하고, 생성은 빌드 시점 도구가 필요하지만 구조상 올바름을 보장한다.

가변 개수 자식을 담는 리스트 타입

가변 개수 자식을 가진 연산자(Append, N개 조건의 AND)는 리스트를 사용한다. 리스트 자체가 보통 노드 타입이어서 범용 복사/비교가 균일하게 재귀할 수 있다. PostgreSQL의 List는 노드(T_List)이며, copyObject/equal은 요소별 코드를 생성하는 대신 List를 특수 처리한다.

이론 ↔ PostgreSQL 대응 관계

개념 (DSC 15–16장 / Lisp 전통)	PostgreSQL 구현
태그된 셀 / 판별자	NodeTag type — 모든 노드의 첫 번째 필드 (nodes.h)
cons/car/cdr 리스트, 이후 배열	List 노드 + ListCell 유니온; lappend/lfirst/foreach (pg_list.h, list.c)
단일 상속	구조체 접두사 내장: SeqScan ⊃ Scan ⊃ Plan ⊃ NodeTag (plannodes.h)
생성자	makeNode(T) → newNode (palloc0 + 태그) (nodes.h)
범용 깊은 복사	copyObject() → copyObjectImpl → 태그 switch (copyfuncs.c)
범용 구조적 동등성	equal() → 태그 switch (equalfuncs.c)
직렬화 / 역직렬화	nodeToString/outNode, stringToNode/nodeRead (outfuncs.c, readfuncs.c)
구조체와 기반 코드의 동기화 유지	gen_node_support.pl이 헤더에서 _copyT/_equalT/_outT/_readT를 생성

PostgreSQL의 접근법

PostgreSQL 노드 시스템은 하나의 불변 규칙과 하나의 코드 생성기로 읽는 것이 가장 명확하다. 태그는 SQL 구문의 모든 표현을 백엔드 전체에 걸쳐 꿰뚫고, 생성된 지원 함수들이 각 단계가 트리를 범용적으로 다음 단계로 넘기는 일을 가능하게 한다.

flowchart LR
    SQL["SQL 텍스트"] -->|gram.y / 원시 파스| RAW["RawStmt<br/>SelectStmt, A_Expr, ColumnRef ..."]
    RAW -->|분석| Q["Query 노드<br/>rtable, jointree, targetList"]
    Q -->|리라이터: copyObject + equal| Q2["Query (재작성됨)"]
    Q2 -->|플래너| PLAN["PlannedStmt<br/>플랜 트리: SeqScan / NestLoop / Agg"]
    PLAN -->|nodeToString| WIRE["직렬화 텍스트<br/>병렬 워커로 전송"]
    WIRE -->|stringToNode| PLAN2["플랜 트리 (워커 복사본)"]
    PLAN -->|ExecInitNode| EST["PlanState 트리<br/>실행기 상태 (nodetag_only)"]
    classDef gen fill:#eef,stroke:#446;
    class Q,Q2,PLAN,PLAN2 gen;

위 다이어그램의 모든 박스는 노드 트리이고, 복사·비교·직렬화가 일어나는 모든 화살표는 네 가지 생성된 패스 중 하나다.

불변 규칙은 다음과 같다. 모든 노드의 첫 번째 필드는 NodeTag이다. 캐스팅, 디스패치, 상속, 생성 모두 이 규칙의 귀결이다. nodes.h에서:

// Node, nodeTag, makeNode — src/include/nodes/nodes.h
typedef struct Node
{
    NodeTag     type;
} Node;

#define nodeTag(nodeptr)    (((const Node*)(nodeptr))->type)

static inline Node *
newNode(size_t size, NodeTag tag)
{
    Node       *result;

    Assert(size >= sizeof(Node));   /* need the tag, at least */
    result = (Node *) palloc0(size);
    result->type = tag;
    return result;
}

#define makeNode(_type_)    ((_type_ *) newNode(sizeof(_type_),T_##_type_))
#define IsA(nodeptr,_type_) (nodeTag(nodeptr) == T_##_type_)

makeNode(Query)는 sizeof(Query) 바이트를 할당하고 0으로 채운 뒤 첫 번째 워드에 T_Query를 기록한다. IsA(p, Query)는 정수 비교 한 번이다. castNode(Query, p)는 그 비교를 Assert로 감싼 것이다(assert 활성화 빌드에서만). 디버그 빌드에서 추가 비용 없이 타입 검사가 이루어진다.

NodeTag 열거형은 생성되고 ABI가 고정된 목록

NodeTag는 손으로 관리하지 않는다. nodes.h는 열거형을 열고 생성된 파일을 #include한다.

// NodeTag — src/include/nodes/nodes.h
typedef enum NodeTag
{
    T_Invalid = 0,

#include "nodes/nodetags.h"
} NodeTag;

nodetags.h는 gen_node_support.pl이 생성한다. 모든 태그의 숫자 값이 목록에서의 위치로 결정되므로, 노드 타입을 하나 추가하거나 제거하면 그 뒤의 모든 번호가 바뀐다. 플랜 노드는 번호가 디스크에 기록되지 않으므로 개발 중에는 문제없지만, 릴리스된 브랜치에서는 익스텐션의 ABI를 깨는 일이다. 그래서 생성기는 안정 브랜치 가드를 가진다. REL_18에서는 자동 번호 할당된 마지막 태그가 WindowObjectData이고 번호가 479임을 assert한다. pg_node_attr(nodetag_number(N))은 백포트된 노드가 기존 번호를 밀지 않고 새 번호를 확보하기 위해 존재한다.

상속: 구조체 접두사로 구성된 플랜 계층 구조

전체 플랜 노드 계열은 내장(embedding) 방식으로 구성된다. Plan이 추상 기반이고, Scan이 Plan을 내장하고, SeqScan이 Scan을 내장한다. Join은 Plan을 내장하고, NestLoop은 Join을 내장한다.

// Plan, Scan, SeqScan, Join, NestLoop — src/include/nodes/plannodes.h
typedef struct Plan
{
    pg_node_attr(abstract, no_equal, no_query_jumble)
    NodeTag     type;
    int         disabled_nodes;
    Cost        startup_cost;
    /* ... total_cost, plan_rows, targetlist, qual, lefttree, righttree ... */
} Plan;

typedef struct Scan
{
    pg_node_attr(abstract)
    Plan        plan;
    Index       scanrelid;      /* index into the range table */
} Scan;

typedef struct SeqScan
{
    Scan        scan;
} SeqScan;

typedef struct Join
{
    pg_node_attr(abstract)
    Plan        plan;
    JoinType    jointype;
    bool        inner_unique;
    List       *joinqual;
} Join;

SeqScan *는 Scan *, Plan *, Node *로 캐스트할 수 있다. NodeTag가 체인 전체에서 오프셋 0을 유지하므로, 어느 캐스트도 올바른 첫 번째 필드를 본다. pg_node_attr(abstract) 마커는 생성기에게 T_Scan/T_Plan/T_Join 태그를 생성하지 말라고 지시한다. 이것들은 인스턴스화할 수 없는 슈퍼타입이고, 상속만 가능하다. Plan은 추가로 no_equal, no_query_jumble을 가진다. 플랜 노드는 복사되고 직렬화되지만(병렬 워커로 전송), equal()로 비교되지 않는다. 생성기는 전체 계층 구조에서 equal 지원을 건너뛴다.

파스 트리의 루트인 Query는 단순 노드다(태그가 첫 번째이고 내장 없음).

// Query — src/include/nodes/parsenodes.h
typedef struct Query
{
    NodeTag     type;
    CmdType     commandType;    /* select|insert|update|delete|merge|utility */
    QuerySource querySource pg_node_attr(query_jumble_ignore);
    /* ... rtable, jointree, targetList, ... */
} Query;

pg_node_attr(query_jumble_ignore)가 필드 수준에 붙어 있다. 속성은 구조체에(여는 중괄호 뒤에) 붙거나 단일 필드에(해당 줄 끝에) 붙는다. 정확히 네 가지 생성된 패스 중 하나만 조정한다.

List는 연결 리스트가 아닌 태그된 확장 가능 배열

이름 “List”와 API(lappend, lcons, lfirst, foreach)는 Lisp 유산이지만, v13부터 표현은 평탄한 확장 가능 배열이다. pg_list.h의 헤더 주석은 이것이 의도적인 인터페이스 보존 재작성임을 명시한다. 구조체:

// ListCell, List — src/include/nodes/pg_list.h
typedef union ListCell
{
    void       *ptr_value;
    int         int_value;
    Oid         oid_value;
    TransactionId xid_value;
} ListCell;

typedef struct List
{
    NodeTag     type;           /* T_List, T_IntList, T_OidList, or T_XidList */
    int         length;         /* number of elements currently present */
    int         max_length;     /* allocated length of elements[] */
    ListCell   *elements;       /* re-allocatable array of cells */
    ListCell    initial_elements[FLEXIBLE_ARRAY_MEMBER];
} List;

#define NIL ((List *) NULL)

네 가지 사실이 전체 설계를 요약한다.

• List는 노드다. 첫 번째 필드가 NodeTag이므로 copyObject/equal 경로에서 다른 노드와 동일하게 디스패치된다.
• 빈 리스트는 NIL == NULL이다. NIL이 아닌 리스트는 항상 length >= 1이다. 비어 있지만 NULL이 아닌 유효한 리스트는 없다. cons 셀 시대에서 유지된 하나의 양보다.
• 하나의 유니온, 네 가지 형태. 셀은 포인터, int, Oid, Xid 중 하나를 담는다. type 필드가 어느 것인지 알려준다. 포인터 리스트(T_List)는 주로 Node*를 담지만, 셀은 void *로 선언되어 호출자가 캐스트할 필요가 없다.
• 헤더와 첫 번째 셀들이 하나의 palloc을 공유한다. initial_elements[]는 헤더와 함께 할당되는 유연한 배열 멤버다. 짧은 리스트는 할당이 하나뿐이고, elements는 리스트가 이 초기 공간을 넘기 전까지 헤더 블록 안을 가리킨다.

foreach가 정식 순회 방법이며, 이제 배열에 대한 인덱스 워크다. 포인터 체이싱이 아니다.

// foreach — src/include/nodes/pg_list.h
#define foreach(cell, lst)  \
    for (ForEachState cell##__state = {(lst), 0}; \
         (cell##__state.l != NIL && \
          cell##__state.i < cell##__state.l->length) ? \
         (cell = &cell##__state.l->elements[cell##__state.i], true) : \
         (cell = NULL, false); \
         cell##__state.i++)

lfirst(cell)은 cell->ptr_value를 읽는다. lfirst_int/lfirst_oid는 다른 유니온 멤버를 읽는다. list_length(l)은 l ? l->length : 0으로 NIL에 안전하다. 배열 재작성으로 인덱스 접근이 O(1)이 되고 순회가 캐시 친화적이 됐다. 호출자는 매크로 API만 사용했으므로 호출 지점은 거의 바뀌지 않았다.

소스 탐방

심볼 이름에 닻을 내려라. 줄 번호가 아니라. git grep -n '<심볼>' src/backend/nodes/로 현재 위치를 찾는다. 이 절 끝의 위치 힌트 표는 커밋 273fe94 (REL_18_STABLE) 기준으로 관찰한 줄 번호를 빠른 힌트로 기록한다.

범용 깊은 복사: copyObject와 태그 switch

copyObject()는 copyObjectImpl 위의 타입 보존 매크로다. copyObjectImpl은 단일 범용 진입점이다. 손으로 작성한 copyfuncs.c 전체는 필드 복사 매크로들, 몇 가지 custom_copy_equal 루틴, 그리고 이 디스패치다.

// copyObjectImpl — src/backend/nodes/copyfuncs.c
void *
copyObjectImpl(const void *from)
{
    void       *retval;

    if (from == NULL)
        return NULL;

    /* Guard against stack overflow due to overly complex expressions */
    check_stack_depth();

    switch (nodeTag(from))
    {
#include "copyfuncs.switch.c"          /* generated: case T_Foo: ... _copyFoo(from) */

        case T_List:
            retval = list_copy_deep(from);
            break;

        case T_IntList:
        case T_OidList:
        case T_XidList:
            retval = list_copy(from);   /* scalar cells: shallow is enough */
            break;

        default:
            elog(ERROR, "unrecognized node type: %d", (int) nodeTag(from));
            retval = 0;             /* keep compiler quiet */
            break;
    }
    return retval;
}

주목할 세 가지가 있다. 첫째, NULL은 NULL로 복사된다. 선택적 자식을 가드 없이 복사할 수 있는 이유다. makeNode에서 palloc0으로 0을 채우는 것이 의미를 갖는 이유다. 둘째, 큰 switch 본문이 생성된 파일 copyfuncs.switch.c에서 #include된다. 복사를 지원하는 노드마다 case T_Foo: retval = _copyFoo(from); break; 한 줄이 있다. 셋째, List는 특수 처리된다. 포인터 리스트는 각 요소를 깊이 복사하고(자체도 copyObjectImpl 호출), int/Oid/Xid 리스트는 셀이 포인터가 아닌 값을 담으므로 얕은 memcpy로 충분하다.

노드별 복사 루틴은 copyfuncs.funcs.c(역시 생성됨)에 있으며 필드 매크로를 사용한다. 매크로는 지역 이름 newnode와 from을 고정한다.

// field-copy macros — src/backend/nodes/copyfuncs.c
#define COPY_SCALAR_FIELD(fldname) \
    (newnode->fldname = from->fldname)

#define COPY_NODE_FIELD(fldname) \
    (newnode->fldname = copyObjectImpl(from->fldname))   /* recurse */

#define COPY_STRING_FIELD(fldname) \
    (newnode->fldname = from->fldname ? pstrdup(from->fldname) : NULL)

#define COPY_BITMAPSET_FIELD(fldname) \
    (newnode->fldname = bms_copy(from->fldname))

#define COPY_POINTER_FIELD(fldname, sz) \
    do { \
        Size    _size = (sz); \
        if (_size > 0) \
        { \
            newnode->fldname = palloc(_size); \
            memcpy(newnode->fldname, from->fldname, _size); \
        } \
    } while (0)

스칼라 필드는 값으로 복사된다. 노드 포인터 필드는 copyObjectImpl로 재귀한다(복사를 깊게 만드는 부분이다). 문자열은 pstrdup로 복사된다. Bitmapset은 bms_copy로, 크기가 있는 버퍼는 palloc + memcpy로 복사된다. 생성기의 역할은 각 필드의 C 타입으로부터 적절한 매크로를 선택하는 것뿐이다.

단일 copyObject(query) 호출이 태그 디스패치와 List 특수 처리를 거쳐 재귀하는 과정:

flowchart TD
    A["copyObject(node)"] --> B["copyObjectImpl(from)"]
    B --> C{"from == NULL?"}
    C -->|yes| D["return NULL"]
    C -->|no| E["switch nodeTag(from)"]
    E -->|T_Query, T_SeqScan, ...| F["_copyFoo(from)<br/>generated, field by field"]
    E -->|T_List| G["list_copy_deep"]
    E -->|T_IntList / T_OidList / T_XidList| H["list_copy<br/>shallow memcpy of cells"]
    E -->|unknown| I["elog ERROR unrecognized node type"]
    F -->|COPY_NODE_FIELD on each child| B
    G -->|copyObjectImpl on each element| B

두 개의 역방향 에지(COPY_NODE_FIELD와 list_copy_deep의 요소별 루프)가 복사를 깊게 만드는 재귀다.

커스텀 복사: 생성 코드로 부족한 경우

소수의 노드 타입은 필드별 복사로 처리할 수 없어 pg_node_attr(custom_copy_equal)을 가진다. 이 마커는 생성기에게 case만 생성하고 손으로 작성한 루틴을 호출하게 한다. Const가 전형적 사례다. 참조에 의한(by-reference) datum은 포인터 복사가 아닌 진짜 값 복사가 필요하기 때문이다.

// _copyConst — src/backend/nodes/copyfuncs.c
static Const *
_copyConst(const Const *from)
{
    Const      *newnode = makeNode(Const);

    COPY_SCALAR_FIELD(consttype);
    COPY_SCALAR_FIELD(consttypmod);
    COPY_SCALAR_FIELD(constcollid);
    COPY_SCALAR_FIELD(constlen);

    if (from->constbyval || from->constisnull)
        newnode->constvalue = from->constvalue;     /* by value: just copy */
    else
        newnode->constvalue = datumCopy(from->constvalue,   /* by ref: clone */
                                        from->constbyval,
                                        from->constlen);

    COPY_SCALAR_FIELD(constisnull);
    COPY_SCALAR_FIELD(constbyval);
    COPY_LOCATION_FIELD(location);
    return newnode;
}

ExtensibleNode도 교훈적인 커스텀 사례다. 등록된 ExtensibleNodeMethods vtable(methods->nodeCopy)로 디스패치한다. 노드 시스템이 가상 메서드 스타일 디스패치로 후퇴하는 유일한 지점이다. 빌드 시점 생성기가 볼 수 없는 익스텐션 정의 노드 타입을 위한 장치다.

범용 구조적 비교: equal

equal()은 copyObjectImpl을 정확히 거울처럼 반영하지만, 불리언을 반환하고 할당을 하지 않는다. 디스패치:

// equal — src/backend/nodes/equalfuncs.c
bool
equal(const void *a, const void *b)
{
    bool        retval;

    if (a == b)
        return true;            /* same pointer (covers NULL==NULL) */
    if (a == NULL || b == NULL)
        return false;           /* exactly one NULL */
    if (nodeTag(a) != nodeTag(b))
        return false;           /* different concrete types */

    check_stack_depth();

    switch (nodeTag(a))
    {
#include "equalfuncs.switch.c"       /* generated: case T_Foo: _equalFoo(a,b) */

        case T_List:
        case T_IntList:
        case T_OidList:
        case T_XidList:
            retval = _equalList(a, b);
            break;

        default:
            elog(ERROR, "unrecognized node type: %d", (int) nodeTag(a));
            retval = false;
            break;
    }
    return retval;
}

비교 매크로는 복사 매크로와 대응한다. COMPARE_SCALAR_FIELD, COMPARE_NODE_FIELD(equal로 재귀), COMPARE_STRING_FIELD(strcmp, NULL 인식), COMPARE_BITMAPSET_FIELD(bms_equal)가 있으며, 첫 번째 불일치에서 false를 반환한다. 가장 중요한 매크로는 아무것도 하지 않는 것이다.

// COMPARE_LOCATION_FIELD — src/backend/nodes/equalfuncs.c
/* Compare a parse location field (this is a no-op, per note above) */
#define COMPARE_LOCATION_FIELD(fldname) \
    ((void) 0)

파스 위치 필드(소스 텍스트에서의 바이트 오프셋)는 의도적으로 비교하지 않는다. 쿼리 문자열의 서로 다른 위치에 나타나는 열 x에 대한 두 참조도 equal()로는 같다. ParseLoc이 별도의 typedef이고, location이라는 이름의 정수 필드가 생성기에서 특별 처리되는 이유가 이것이다. 위치는 메타데이터이지 동일성을 결정하는 요소가 아니다.

List는 복사와 마찬가지로 특수 처리된다. _equalList는 먼저 type이나 length가 다르면 거부한다(저렴한 스칼라 검사). 그 뒤 두 배열을 forboth로 나란히 순회하며 포인터 셀은 equal()로, 스칼라 셀은 !=로 비교한다.

// _equalList (pointer-list arm) — src/backend/nodes/equalfuncs.c
COMPARE_SCALAR_FIELD(type);
COMPARE_SCALAR_FIELD(length);
switch (a->type)
{
    case T_List:
        forboth(item_a, a, item_b, b)
        {
            if (!equal(lfirst(item_a), lfirst(item_b)))
                return false;
        }
        break;
    case T_IntList:
        forboth(item_a, a, item_b, b)
        {
            if (lfirst_int(item_a) != lfirst_int(item_b))
                return false;
        }
        break;
    /* ... T_OidList, T_XidList ... */
}

List 내부: 여유를 두는 할당, 확장, 깊은 복사

new_list에 공동 할당 트릭이 있다. 셀 수를 2의 거듭제곱으로 올림해서 palloc이 어차피 2의 거듭제곱으로 올림하는 점을 활용해 사용 가능한 여유 공간을 확보한다. elements를 인라인 initial_elements[]를 가리키게 한다.

// new_list — src/backend/nodes/list.c
static List *
new_list(NodeTag type, int min_size)
{
    List       *newlist;
    int         max_size;

    Assert(min_size > 0);

    /* round the allocation up to a power of two for free slack */
    max_size = pg_nextpower2_32(Max(8, min_size + LIST_HEADER_OVERHEAD));
    max_size -= LIST_HEADER_OVERHEAD;

    newlist = (List *) palloc(offsetof(List, initial_elements) +
                              max_size * sizeof(ListCell));
    newlist->type = type;
    newlist->length = min_size;
    newlist->max_length = max_size;
    newlist->elements = newlist->initial_elements;   /* still inline */
    return newlist;
}

lappend가 핵심 함수다. NIL에서 시작하면 한 셀짜리 리스트를 새로 만든다. 그렇지 않으면 마지막에 셀 하나를 추가할 공간을 만들고(용량 초과 시 확장) 데이터를 마지막 셀에 기록한다. 반환값을 항상 사용해야 한다는 규율이 있다. 확장 시 셀 배열이 이동할 수 있기 때문이다.

// lappend — src/backend/nodes/list.c
List *
lappend(List *list, void *datum)
{
    Assert(IsPointerList(list));

    if (list == NIL)
        list = new_list(T_List, 1);
    else
        new_tail_cell(list);        /* enlarge_list() if length == max_length */

    llast(list) = datum;
    check_list_invariants(list);
    return list;
}

인라인 셀이 소진되면 enlarge_list가 공동 할당된 initial_elements[]에서 별도의 MemoryContextAlloc 배열로 이전하거나(이미 분리된 경우 repalloc), 다음 2의 거듭제곱으로 크기를 키운다. 그 이후로는 헤더는 제자리에 있으므로 보유 중인 List*는 여전히 유효하지만, 셀 배열은 이동했으므로 보유 중인 ListCell* 포인터는 유효하지 않다. list_concat은 하나의 배열을 다른 배열에 memcpy 한 번으로 추가하고, list_copy는 모든 셀의 얕은 memcpy다. list_copy_deep은 copyObjectImpl이 T_List를 처리할 때 호출하는 포인터 리스트 깊은 복사다.

// list_copy_deep — src/backend/nodes/list.c
List *
list_copy_deep(const List *oldlist)
{
    List       *newlist;

    if (oldlist == NIL)
        return NIL;

    Assert(IsA(oldlist, List));     /* only sensible for pointer Lists */

    newlist = new_list(oldlist->type, oldlist->length);
    for (int i = 0; i < newlist->length; i++)
        lfirst(&newlist->elements[i]) =
            copyObjectImpl(lfirst(&oldlist->elements[i]));   /* recurse */

    check_list_invariants(newlist);
    return newlist;
}

이로써 재귀가 완결된다. 노드의 COPY_NODE_FIELD가 List* 인수로 copyObjectImpl을 호출하면, T_List가 list_copy_deep으로 라우팅되고, list_copy_deep이 모든 요소에 copyObjectImpl을 호출한다. 표현식 하위 트리를 담은 TargetEntry 노드들의 대상 목록도 최상위 copyObject(query) 호출 하나로 완전히 복제된다.

기반 코드 생성 방법: gen_node_support.pl

노드별 _copyT/_equalT 본문과 switch.c 파일들은 빌드 시점에 gen_node_support.pl이 생성한다. 스크립트는 고정된 순서로 정렬된 노드 헤더 파일 목록을 파싱한다.

# canonical, order-stable input list — src/backend/nodes/gen_node_support.pl
my @all_input_files = qw(
  nodes/nodes.h
  nodes/primnodes.h
  nodes/parsenodes.h
  nodes/pathnodes.h
  nodes/plannodes.h
  nodes/execnodes.h
  # ... access/*, commands/*, executor/tuptable.h, foreign/fdwapi.h, nodes/value.h ...
);

순서가 의미를 가진다. NodeTag 번호를 고정하며, 스크립트는 이를 안정 브랜치 ABI 가드로 보강한다.

# ABI stability guard (REL_18) — src/backend/nodes/gen_node_support.pl
my $last_nodetag = 'WindowObjectData';
my $last_nodetag_no = 479;

구조체마다 생성기는 필드를 순회하며 필드의 C 타입에서 복사/비교 매크로를 선택한다. pg_node_attr로 조정한다. 타입 디스패치의 핵심:

# field-type → macro selection (abridged) — gen_node_support.pl
if ($t eq 'char*') {
    print $cff "\tCOPY_STRING_FIELD($f);\n"  unless $copy_ignore;
    print $eff "\tCOMPARE_STRING_FIELD($f);\n" unless $equal_ignore;
}
elsif ($t eq 'Bitmapset*' || $t eq 'Relids') {
    print $cff "\tCOPY_BITMAPSET_FIELD($f);\n"  unless $copy_ignore;
    print $eff "\tCOMPARE_BITMAPSET_FIELD($f);\n" unless $equal_ignore;
}
elsif ($t eq 'ParseLoc') {
    print $cff "\tCOPY_LOCATION_FIELD($f);\n"  unless $copy_ignore;
    print $eff "\tCOMPARE_LOCATION_FIELD($f);\n" unless $equal_ignore;
}
elsif (elem $t, @scalar_types or elem $t, @enum_types) {
    print $cff "\tCOPY_SCALAR_FIELD($f);\n" unless $copy_ignore;
    # ... COMPARE_SCALAR_FIELD, or equal_ignore_if_zero handling ...
}
# node type: pointer to a known node → recurse
elsif (($t =~ /^(\w+)\*$/ or $t =~ /^struct\s+(\w+)\*$/) and elem $1, @node_types) {
    print $cff "\tCOPY_NODE_FIELD($f);\n" unless $copy_ignore;
    print $eff "\tCOMPARE_NODE_FIELD($f);\n" unless $equal_ignore;
}

char *는 COPY_STRING_FIELD가 된다. ParseLoc은 no-op 위치 처리가 된다. 알려진 노드를 가리키는 포인터는 재귀하는 COPY_NODE_FIELD가 된다. 일반 스칼라/열거형은 COPY_SCALAR_FIELD가 된다. 필드 수준에서 pg_node_attr로 조정할 수 있다. copy_as_scalar는 포인터를 얕게 복사하게 한다. equal_ignore는 필드를 비교에서 제외한다. equal_ignore_if_zero는 0일 때만 무시한다. array_size(other)는 “이것은 길이가 필드 other에 있는 palloc 배열이다”라고 알려줘서 생성기가 그 동반 필드로 크기를 결정하는 COPY_POINTER_FIELD를 생성한다. 구조체 수준에서 no_copy/no_equal/nodetag_only/custom_copy_equal은 본문 자체를 생성할지 여부를 결정한다. 디스패치 case도 같은 방식으로 제어된다.

# emit the switch case unless the struct opts out — gen_node_support.pl
print $cfs "\t\tcase T_${n}:\n"
  . "\t\t\tretval = _copy${n}(from);\n"
  . "\t\t\tbreak;\n"
  unless $struct_no_copy;

생성된 _copySeqScan은 다음과 같은 형태다(실제 파일 copyfuncs.funcs.c는 빌드된 트리에서만 존재하므로 생성기 규칙을 바탕으로 재구성한 형태다). 상속은 단순히 생성기가 평탄화하는 접두사다.

// _copySeqScan (generated form) — copyfuncs.funcs.c
static SeqScan *
_copySeqScan(const SeqScan *from)
{
    SeqScan    *newnode = makeNode(SeqScan);

    /* fields flattened from Plan, then Scan */
    COPY_SCALAR_FIELD(scan.plan.disabled_nodes);
    COPY_SCALAR_FIELD(scan.plan.startup_cost);
    /* ... total_cost, plan_rows, plan_width ... */
    COPY_NODE_FIELD(scan.plan.targetlist);
    COPY_NODE_FIELD(scan.plan.qual);
    COPY_NODE_FIELD(scan.plan.lefttree);
    COPY_NODE_FIELD(scan.plan.righttree);
    COPY_SCALAR_FIELD(scan.scanrelid);

    return newnode;
}

위치 힌트 (2026-06-05 기준, REL_18 273fe94)

심볼 이름이 안정적인 기준이다. 줄 번호는 릴리스마다 바뀐다. git grep -n '<심볼>' src/backend/nodes/로 현재 위치를 확인하라. 아래 줄 번호는 커밋 273fe94 (REL_18_STABLE) 기준으로 관찰한 빠른 힌트다.

심볼	파일	줄
typedef enum NodeTag	src/include/nodes/nodes.h	26
typedef struct Node	src/include/nodes/nodes.h	134
newNode	src/include/nodes/nodes.h	150
makeNode (매크로)	src/include/nodes/nodes.h	161
IsA (매크로)	src/include/nodes/nodes.h	164
castNode (매크로)	src/include/nodes/nodes.h	180
copyObject (매크로)	src/include/nodes/nodes.h	228
extern bool equal	src/include/nodes/nodes.h	236
typedef int ParseLoc	src/include/nodes/nodes.h	246
typedef enum CmdType	src/include/nodes/nodes.h	268
typedef union ListCell	src/include/nodes/pg_list.h	45
typedef struct List	src/include/nodes/pg_list.h	53
#define NIL	src/include/nodes/pg_list.h	68
#define lfirst	src/include/nodes/pg_list.h	172
#define list_make1	src/include/nodes/pg_list.h	212
#define foreach	src/include/nodes/pg_list.h	373
new_list	src/backend/nodes/list.c	91
enlarge_list	src/backend/nodes/list.c	155
list_make1_impl	src/backend/nodes/list.c	236
lappend	src/backend/nodes/list.c	339
lcons	src/backend/nodes/list.c	495
list_concat	src/backend/nodes/list.c	561
list_member	src/backend/nodes/list.c	661
list_copy	src/backend/nodes/list.c	1573
list_copy_deep	src/backend/nodes/list.c	1639
#include "copyfuncs.funcs.c"	src/backend/nodes/copyfuncs.c	65
_copyConst	src/backend/nodes/copyfuncs.c	73
_copyExtensibleNode	src/backend/nodes/copyfuncs.c	147
copyObjectImpl	src/backend/nodes/copyfuncs.c	177
#include "copyfuncs.switch.c"	src/backend/nodes/copyfuncs.c	189
#include "equalfuncs.funcs.c"	src/backend/nodes/equalfuncs.c	88
_equalConst	src/backend/nodes/equalfuncs.c	96
_equalList	src/backend/nodes/equalfuncs.c	156
equal	src/backend/nodes/equalfuncs.c	223
#include "equalfuncs.switch.c"	src/backend/nodes/equalfuncs.c	247
@all_input_files	src/backend/nodes/gen_node_support.pl	53
$last_nodetag (ABI 가드)	src/backend/nodes/gen_node_support.pl	110
typedef struct PlannedStmt	src/include/nodes/plannodes.h	46
typedef struct Plan	src/include/nodes/plannodes.h	158
typedef struct Scan	src/include/nodes/plannodes.h	470
typedef struct Join	src/include/nodes/plannodes.h	916
typedef struct Query	src/include/nodes/parsenodes.h	117

소스 검증 (2026-06-05 기준)

커밋 273fe94 (REL_18_STABLE)의 /data/hgryoo/references/postgres에서 검증했다. 방법: 인용된 각 파일을 직접 읽고, grep -n으로 심볼 줄 번호를 확인했다.

• NodeTag 우선 불변 규칙. nodes.h의 struct Node는 정확히 { NodeTag type; }이다. nodeTag()는 const Node *로 캐스트해 ->type을 읽는다. makeNode는 palloc0을 하고 태그를 찍는 newNode(sizeof(T), T_T)로 확장된다. 그대로 확인됐다.
• NodeTag는 생성되고 ABI가 보호된다. nodes.h 30번 줄이 열거형 안에서 #include "nodes/nodetags.h"를 한다. gen_node_support.pl은 REL_18에서 $last_nodetag = 'WindowObjectData' / $last_nodetag_no = 479를 고정한다. 태스크 범위에서 금지된 T_XLOG2 rmgr과 B_DATACHECKSUMSWORKER_* 심볼은 여기에 나타나지 않는다. 확인됐다.
• 접두사 내장에 의한 상속. Plan은 NodeTag type을 첫 번째로 두고 pg_node_attr(abstract, no_equal, no_query_jumble)을 가진다. Scan은 Plan을 내장하고 abstract다. SeqScan은 Scan을 내장한다. Join은 Plan을 내장하고, NestLoop은 Join을 내장한다. plannodes.h에서 확인됐다.
• List 표현. ListCell이 네 멤버 유니온이고, List가 { NodeTag; int length; int max_length; ListCell *elements; ListCell initial_elements[FLEXIBLE_ARRAY_MEMBER]; }이며, NIL이 ((List *) NULL)이다. foreach가 인덱스 워크다. pg_list.h에서 확인됐다.
• 디스패치 형태. copyObjectImpl과 equal 모두 생성된 *.switch.c를 #include하고, 네 가지 리스트 태그를 특수 처리하며, 기본 아암에서 elog(ERROR, "unrecognized node type")을 한다. copyfuncs.c / equalfuncs.c에서 확인됐다.
• 커스텀 복사/동등. _copyConst는 참조에 의한 datum에 datumCopy를 사용한다. _copyExtensibleNode/_equalExtensibleNode는 ExtensibleNodeMethods로 디스패치한다. _equalConst는 datumIsEqual을 사용한다. 확인됐다.
• 위치 no-op. COMPARE_LOCATION_FIELD(fldname)이 ((void) 0)이다. 파일 헤더 주석에 이유가 설명돼 있다(x가 x와 같게 하기 위해). 확인됐다.
• List 내부. new_list가 pg_nextpower2_32로 올림하고 elements를 initial_elements로 가리킨다. lappend가 이동 가능한 리스트를 반환한다. enlarge_list가 인라인에서 분리 할당으로 이전한다. list_copy가 얕은 memcpy다. list_copy_deep이 copyObjectImpl로 재귀한다. list.c에서 확인됐다.
• 코드 생성. @all_input_files가 헤더를 고정 순서로 나열한다. 필드 타입에서 매크로로의 디스패치와 case T_${n} 생성이 인용한 대로다. gen_node_support.pl에서 확인됐다.
• 주의 — 생성된 아티팩트. copyfuncs.funcs.c, copyfuncs.switch.c, equalfuncs.funcs.c, equalfuncs.switch.c, nodetags.h는 빌드된 트리에서만 존재한다. 참조 체크아웃은 클린 상태이므로 _copySeqScan 발췌는 생성기의 문서화된 규칙에서 파생한 재구성된 생성 형태로 제시됐다. 바이트 단위 파일 캡처가 아니다. 손으로 작성된 모든 발췌는 원문 그대로다.

PostgreSQL 너머 — 비교 설계와 연구 프런티어

노드 시스템의 백엔드 위치. 이 문서는 표현과 범용 기반 코드에서 의도적으로 멈춘다. 이 트리들의 생산자와 소비자는 다른 곳에서 다룬다. 원시 파스와 분석 단계는 postgres-parser.md에 있다. Query를 PlannedStmt로 변환하는 경로·플랜 구성은 postgres-planner-overview.md와 postgres-path-generation.md에 있다. ExecInitNode가 Plan 트리에서 구성하는 PlanState 트리 — 첫 번째 다이어그램의 네 번째 트리로, 복사/동등/직렬화가 필요 없어 nodetag_only로 표시됨 — 는 postgres-executor.md에 있다. 표현식 노드(Var, OpExpr, Const)와 컴파일된 평가는 postgres-expression-eval.md에 있다.

코드 생성 대 손 관리. PostgreSQL의 선택 — 태그 유니온 표현을 유지하되 복사/동등/출력/읽기 패스를 생성한다 — 이 흥미로운 설계 지점이다. v15 이전에는 이 파일들이 손으로 작성됐고 “새 필드 복사 누락” 버그의 반복되는 원천이었다. gen_node_support.pl로 전환하면서 구조체 정의가 단일 정보 원천이 됐고, 잠재적 별명 버그 유형 하나가 컴파일 오류로 바뀌었다. 대가는 Perl 빌드 의존성과 간접성이다(생성기와 pg_node_attr 마커를 읽어야 하고, 생성된 코드는 볼 수 없다). 다른 시스템은 다른 선택을 한다.

• C++ 엔진(DuckDB, ClickHouse). 가상 Copy()/Equals()/Serialize() 메서드를 가진 실제 클래스 계층 구조를 사용한다. 컴파일러 vtable이 태그 switch를 대체하고, RTTI/dynamic_cast가 IsA를 대체한다. 분산/병렬 실행을 위한 직렬화는 여전히 클래스별로 작성하거나 생성해야 한다. PostgreSQL의 코드 생성이 해결하는 근본 문제는 사라지지 않고 직렬화 프레임워크로 이동한다.
• Apache Calcite (JVM). 관계 연산자를 RelNode 객체로, 불변 RexNode 표현식으로 표현한다. “다이제스트”를 통한 구조적 동등성과 복사-후-변환 규칙을 사용한다. 불변성 덕분에 PostgreSQL이 copyObject로 수동 강제하는 변환 전 깊은 복사 규율이 필요 없다.
• Substrait / protobuf 플랜 IR. 현대의 크로스 엔진 트렌드는 플랜 트리를 스키마 언어(protobuf)로 정의하고 직렬화기/역직렬화기를 스키마에서 생성하게 하는 것이다. 이것은 PostgreSQL의 gen_node_support.pl 아이디어를 이식 가능한 언어 중립 IR로 일반화한 것이다. 한 엔진이 생성한 플랜을 다른 엔진이 실행할 수 있다.

List 재작성의 사례 연구. v13의 cons 셀에서 확장 가능 배열로의 이전 — 이 코드에서 initial_elements[], enlarge_list, 인덱스 기반 foreach로 나타남 — 은 캐시 지역성을 위해 안정적인 API 아래 데이터 구조의 표현을 변경한 사례로 자주 인용된다. 부과하는 비용 — 배열 성장 시 ListCell 포인터가 무효화되므로 코드베이스 전체에서 보유 셀 가정을 감사해야 했다(DEBUG_LIST_MEMORY_USAGE가 정확히 그것을 찾아내기 위해 존재한다) — 은 배열 기반 시퀀스의 반복되는 세금이다. lappend/lcons가 호출자에게 반환값을 사용하도록 요구하는 이유가 그것이다.

프런티어. (1) ABI 안정적 노드 진화 — nodetag_number(VALUE) 속성과 $last_nodetag 가드는 “마이너 릴리스에서 익스텐션을 깨지 않고 노드 타입을 추가하라”에 대한 실용적인 답이다. 더 깔끔한 답(태그 정체성을 열거형 위치에서 분리하는 것)은 열려 있다. (2) 전체 트리 인터닝 / 구조적 공유 — equal()이 O(트리 크기)이고 플래너가 자주 호출한다. 하위 표현식을 해시-cons나 인턴하는 엔진은 전역 테이블의 비용으로 O(1) 동등성을 얻는다. PostgreSQL은 메모리 컨텍스트 단순성을 위해 지금까지 이를 거부했다. (3) 스키마 주도 IR — 미래의 PostgreSQL 플랜 형식이 현재 노드 시스템을 빠르게 만드는 palloc/메모리 컨텍스트 결합을 잃지 않고 이식 가능한 IR로 생성될 수 있는가라는 질문이다.

출처

• src/backend/nodes/README — 정식 개요: 노드 개념, 관례에 의한 상속, 각 노드 클래스에 필요한 지원 함수들, “노드 추가 절차” 체크리스트.
• src/include/nodes/nodes.h — NodeTag, Node, newNode, makeNode, IsA, castNode, copyObject/equal 선언, pg_node_attr 문서화, ParseLoc.
• src/include/nodes/pg_list.h — List/ListCell, NIL, lfirst/linitial/llast 접근자, foreach 계열.
• src/backend/nodes/list.c — new_list, enlarge_list, lappend/lcons, list_concat, list_copy, list_copy_deep, list_member.
• src/backend/nodes/copyfuncs.c — 복사 매크로, copyObjectImpl 디스패치, _copyConst/_copyExtensibleNode 커스텀 루틴.
• src/backend/nodes/equalfuncs.c — 비교 매크로(위치/강제 변환 형식 no-op 포함), equal 디스패치, _equalList, _equalConst.
• src/backend/nodes/gen_node_support.pl — 빌드 시점 생성기: 입력 파일 순서, ABI 가드, 필드 타입에서 매크로로의 디스패치, switch 생성.
• src/include/nodes/plannodes.h, src/include/nodes/parsenodes.h — Plan/Scan/SeqScan/Join/NestLoop 상속 체인, PlannedStmt, Query.
• Database System Concepts, Silberschatz 외, 7판, 15–16장 — 쿼리 표현과 중간 트리 파이프라인 (이론적 기반; .omc/plans/postgres-paper-bibliography.md 참고).
• 교차 참조: postgres-parser.md, postgres-planner-overview.md, postgres-executor.md, postgres-expression-eval.md.