Opensource internals

ClickHouse Shares One AST Between Threads

15 min read Jay Hubbert

The ClickHouse AST is a tree of intrusive-reference-counted nodes with 32-byte headers, a bit-packed flag word, and a destructor that unwinds iteratively instead of recursively.

TL;DR: Every ClickHouse AST node is an IAST with a 32-byte header: a vector of children, an atomic refcount, and a 32-bit flag word. Nodes are handed around as boost::intrusive_ptr, so the same subtree can be shared by the analyzer, the formatter and the query log at the same time — and freeing a 1000-deep tree does not recurse 1000 stack frames.

Parsing is the easy half of turning text into a query. The hard half is what happens to the result.

A parsed SELECT is not a private object. In a single server the AST is touched by at least half a dozen components: the analyzer rewrites it, the planner reads it, the formatter prints it back for EXPLAIN, the query log stores a rendering of it, the distributed-query rewriter clones a piece of it for every shard, and the INSERT path looks into it for the data payload. In a cluster, the same AST is then handed to the threads that execute the query, that log it, and that report the result to the client.

So the AST has to be:

  • shareable — several components hold references to the same subtree without copying it;
  • mutable — the analyzer rewrites it in place;
  • small — a query with 10 000 nodes should not cost 10 000 × 100 bytes of header;
  • safe to destroy — a query can nest 1000 levels deep, and the default max_parser_depth is exactly 1000.

ClickHouse gets all four with an intrusive refcount, a bitfield, and a destructor that is deliberately not recursive.

The node

cpp 
// src/Parsers/IAST.h:33
/** Element of the syntax tree (hereinafter - directed acyclic graph with elements of semantics)
  */
class IAST : public TypePromotion<IAST>
{
public:
    ASTs children;
private:
    /// We implement intrusive reference counting (based on boost::intrusive_ref_counter) to avoid the padding added by the ref_counter
    /// And we use the extra bytes to store flags_storage which can be used in derived classes.
    mutable std::atomic<UInt32> ref_counter{0};
    UInt32 flags_storage = 0;

    /// Helper to detect if a type has _parent_reserved member
    template <typename T>
    static consteval bool hasParentReserved()
    {
        if constexpr (requires { T::_parent_reserved; })
            return true;
        else
            return false;
    }

public:

    /// Bit 31 of `flags_storage` is reserved for the `parenthesized` flag — see accessors below.
    /// Derived `BitfieldStruct` definitions must keep `RESERVED_BITS <= 31`.
    static constexpr UInt32 PARENTHESIZED_BIT_MASK = UInt32{1} << 31;

    /// If the element has extra parentheses around it, e.g., in "a + (b)", b has extra parentheses.
    bool isParenthesized() const { return (flags_storage & PARENTHESIZED_BIT_MASK) != 0; }
    void setParenthesized(bool value)
    {
        flags_storage = (flags_storage & ~PARENTHESIZED_BIT_MASK) | (value ? PARENTHESIZED_BIT_MASK : 0);
    }

Three members, and the layout is asserted:

cpp 
// src/Parsers/IAST.cpp:26
/// Verify that we did not increase the size of IAST by accident.
static_assert(sizeof(IAST) <= 32);

32 bytes: 24 for the ASTs vector (three pointers), 4 for the refcount, 4 for the flag word. The static_assert is a tripwire — anyone who adds a member to IAST breaks the build rather than silently making every node 8 bytes bigger.

The comment on the class says “directed acyclic graph”, not “tree”, and that is not a typo. The same node can be referenced from two places. A WITH clause that is used twice, a subquery that the rewriter duplicates, an expression that the common-subexpression eliminator keeps in two slots — the AST is a DAG, and the refcount is what keeps the shared nodes alive.

The vector type is chosen for the same reason:

cpp 
// src/Parsers/IAST_fwd.h:18
using ASTPtr = boost::intrusive_ptr<IAST>;

/// Boost requires the stored size type to be either strictly smaller than `size_t` or the very same type.
/// On 32-bit platforms `size_t` is already 32-bit, so there is nothing to shrink.
using ASTsStoredSize = std::conditional_t<(sizeof(uint32_t) < sizeof(size_t)), uint32_t, size_t>;

/// Boost vector with smaller stored size to save memory for AST children vectors.
using ASTs = boost::container::vector<
    ASTPtr,
    boost::container::new_allocator<ASTPtr>,
    boost::container::vector_options<boost::container::stored_size<ASTsStoredSize>>::type>;

A std::vector stores its size in a size_t — 8 bytes on a 64-bit build. Every AST node has a children vector, and most of them have one or two children, so the size field is 4 bytes of pure waste in most nodes. The boost::container::vector with stored_size<uint32_t> shrinks it. The std::conditional_t keeps it correct on 32-bit platforms, where size_t is already 32 bits and shrinking would be impossible.

Reference counting

The refcount is intrusive, which means IAST implements the two free functions that boost::intrusive_ptr calls:

cpp 
// src/Parsers/IAST.cpp:29
void intrusive_ptr_add_ref(const IAST * p) noexcept
{
    p->ref_counter.fetch_add(1, std::memory_order_relaxed);
}

void intrusive_ptr_release(const IAST * p) noexcept
{
    if (p->ref_counter.fetch_sub(1, std::memory_order_acq_rel) == 1)
    {
        struct LinkedList
        {
            ASTs children;
            LinkedList * next = nullptr;

            static LinkedList * create(IAST * ptr)
            {
                if (ptr->children.empty())
                {
                    delete ptr;
                    return nullptr;
                }

                ASTs children;
                children.swap(ptr->children);
                ptr->~IAST();
                LinkedList * elem = new (dynamic_cast<void *>(ptr)) LinkedList;
                elem->children.swap(children);
                return elem;
            }
        };

        static_assert(sizeof(LinkedList) <= sizeof(IAST));

        const IAST * const_ptr = p;
        IAST * ptr = const_cast<IAST *>(const_ptr);

        LinkedList * list_head = LinkedList::create(ptr);

        while (list_head)
        {
            ASTs children;
            children.swap(list_head->children);
            {
                LinkedList * next = list_head->next;
                list_head->~LinkedList();
                operator delete(list_head);
                list_head = next;
            }

            for (auto & child : children)
            {
                if (child == nullptr || child->use_count() != 1)
                    continue;

                ptr = child.detach();
                chassert(ptr->ref_counter.fetch_sub(1, std::memory_order_acq_rel) == 1);

                LinkedList * elem = LinkedList::create(ptr);
                if (elem)
                {
                    elem->next = list_head;
                    list_head = elem;
                }
            }
        }
    }
}

Read this carefully, because it is the cleverest piece of the whole parser subtree.

A naive intrusive_ptr_release would be:

cpp 
if (--refcount == 0) delete this;   // ~IAST destroys children -> releases them -> recursion

That is recursive destruction: freeing a node releases its children, which releases their children, and a 1000-deep AST costs 1000 stack frames. With a default max_parser_depth of 1000, that is the difference between “works” and “stack overflow on a malicious query”.

The fix is to turn the recursion into an iteration, and it does it by reusing the node’s own memory:

  1. LinkedList::create(ptr) moves the node’s children vector out, destroys the node object in place (ptr->~IAST()), and then constructs a LinkedList in the same memory using placement new. Because static_assert(sizeof(LinkedList) <= sizeof(IAST)), the recycled node is big enough to hold the list link.
  2. The list of recycled nodes becomes a work queue. Each iteration takes one node off the queue, and for each of its children that is uniquely owned (use_count() != 1 means somebody else holds a reference — skip it), recycles that child the same way, and pushes it onto the queue.
  3. Nothing recurses. The stack depth is constant; the heap holds the work list.

The use_count() != 1 check is what makes the DAG safe: a node referenced from two places is not deleted when the first holder lets go.

chassert(ptr->ref_counter.fetch_sub(1, ...) == 1) is the delicate line. The child was detached from its parent’s vector, so the parent’s reference is gone; the refcount must now drop to zero, and the code asserts it. In a release build the assert compiles away and the value is discarded, but the invariant holds.

The flag word

flags_storage is 32 bits that every derived class can use for its own boolean flags, without adding a member and breaking the 32-byte budget. The accessor is a constrained reinterpret_cast:

cpp 
// src/Parsers/IAST.h:79
    template <typename BitfieldStruct>
    BitfieldStruct & flags()
    {
        static_assert(std::is_standard_layout_v<BitfieldStruct>);
        static_assert(sizeof(BitfieldStruct) == sizeof(flags_storage), "Bitfield struct must be the same size as flags_storage");
        static_assert(BitfieldStruct::RESERVED_BITS <= 31, "RESERVED_BITS exceeds 31 (bit 31 is reserved for parenthesized)");

        if constexpr (!std::is_void_v<typename BitfieldStruct::ParentFlags>)
        {
            static_assert(hasParentReserved<BitfieldStruct>(), "Derived flags struct must have _parent_reserved field");
            static_assert(
                BitfieldStruct::ParentFlags::RESERVED_BITS < BitfieldStruct::RESERVED_BITS,
                "Derived RESERVED_BITS must be greater than parent's");
        }

        return *reinterpret_cast<BitfieldStruct *>(&flags_storage);
    }

The rules are enforced by the compiler, not by comments:

  • the bitfield struct must be exactly the size of the flag word;
  • it may use at most 31 bits, because bit 31 belongs to IAST itself (parenthesized);
  • a derived struct must reserve the bits its parent already uses, so the ParentFlags chain is checked at compile time.

A derived class declares its flags like this:

cpp 
// src/Parsers/ASTWithAlias.h:16
    struct ASTWithAliasFlags
    {
        using ParentFlags = void;
        static constexpr UInt32 RESERVED_BITS = 1;

        UInt32 prefer_alias_to_column_name : 1;
        UInt32 unused : 31;
    };

ASTWithAlias has no parent flags (void), so it may use all 32 bits minus the one IAST reserved — hence unused : 31 and RESERVED_BITS = 1. A subclass of ASTWithAlias would declare ParentFlags = ASTWithAliasFlags and RESERVED_BITS = 2, and the static asserts would catch it if it tried to overlap bit 0.

Children and aliases

The children vector owns the child nodes. But most AST classes also want a typed pointer to a particular child — ASTSelectQuery wants ASTExpressionList * select_expression_list, not ASTPtr. So there are two representations, and the invariant is that the vector owns and the member pointer observes.

cpp 
// src/Parsers/IAST.h:220
    template <typename T>
    void set(T * & field, const ASTPtr & child)
    {
        if (!child)
            return;

        T * cast = dynamic_cast<T *>(child.get());
        if (!cast)
            throw Exception(ErrorCodes::LOGICAL_ERROR, "Could not cast AST subtree");

        children.push_back(child);
        field = cast;
    }

    template <typename T>
    void replace(T * & field, const ASTPtr & child)
    {
        if (!child)
            throw Exception(ErrorCodes::LOGICAL_ERROR, "Trying to replace AST subtree with nullptr");

        T * cast = dynamic_cast<T *>(child.get());
        if (!cast)
            throw Exception(ErrorCodes::LOGICAL_ERROR, "Could not cast AST subtree");

        for (ASTPtr & current_child : children)
        {
            if (current_child.get() == field)
            {
                current_child = child;
                field = cast;
                return;
            }
        }

        throw Exception(ErrorCodes::LOGICAL_ERROR, "AST subtree not found in children");
    }

set appends to children and points the member at the same object. replace finds the old child in children (by pointer identity — it compares the raw pointers, not the values) and swaps it. setOrReplace and reset complete the set.

The danger of this scheme is obvious: if somebody assigns to the member pointer directly, the children vector and the member disagree, and the refcount leaks. updatePointerToChild exists for the case where a child is replaced behind the class’s back:

cpp 
// src/Parsers/IAST.h:344
    /// After changing one of `children` elements, update the corresponding member pointer if needed.
    void updatePointerToChild(const IAST * old_ptr, const ASTPtr & new_ptr)
    {
        std::function<void(IAST **, boost::intrusive_ptr<IAST> *)> f = [old_ptr, new_ptr](IAST ** raw, boost::intrusive_ptr<IAST> * smart)
        {
            if (raw && *raw == old_ptr)
                *raw = new_ptr.get();
            else if (smart && smart->get() == old_ptr)
                *smart = new_ptr;
        };
        forEachPointerToChild(f);
    }

forEachPointerToChild is a virtual hook that each class overrides to list its naked pointers, so the base class can repair them after a rewrite.

Copying

Because the tree is shared, “copy” has to be explicit. clone() is a deep copy, and every class implements it:

cpp 
// src/Parsers/IAST.h:155
    /** Get a deep copy of the tree. Cloned object must have the same range. */
    virtual ASTPtr clone() const = 0;

and the helper that most implementations use is:

cpp 
// src/Parsers/IAST.cpp:319
void IAST::cloneChildren()
{
    checkStackSize();
    for (auto & child : children)
        child = child->clone();
}

Note the checkStackSize(): clone() recurses, so cloning a 1000-deep tree does use 1000 stack frames. The recursion is bounded by the depth limit that the parser enforced, so it is safe — and the stack check catches the case where an AST was built by a rewriter that did not go through the parser.

Hashing

The tree hash identifies an expression structurally. It is what the query cache keys on, and what common-subexpression elimination compares.

cpp 
// src/Parsers/IAST.cpp:148
IASTHash IAST::getTreeHash(bool ignore_aliases) const
{
    SipHash hash_state;
    updateTreeHash(hash_state, ignore_aliases);
    return getSipHash128AsPair(hash_state);
}


void IAST::updateTreeHash(SipHash & hash_state, bool ignore_aliases) const
{
    checkStackSize();
    updateTreeHashImpl(hash_state, ignore_aliases);
    hash_state.update(children.size());
    for (const auto & child : children)
        child->updateTreeHash(hash_state, ignore_aliases);
}

The hash is a 128-bit SipHash, computed over the node identifiers and the child count, recursively. ignore_aliases makes SELECT a AS x and SELECT a AS y hash the same, which is what you want for subexpression elimination but not for a query cache key.

The updateTreeHashImpl hook lets a class add its own members to the hash. The base implementation hashes only the getID() string, and the header is explicit about the trap:

cpp 
// src/Parsers/IAST.h:158
    /** Get hash code, identifying this element and its subtree.
     *  Hashing by default ignores aliases (e.g. identifier aliases, function aliases, literal aliases) which is
     *  useful for common subexpression elimination. Set 'ignore_aliases = false' if you don't want that behavior.
     *
     *  The default implementation only hashes `getID` and `children`. When adding a member that is
     *  not a child and is part of the element's meaning, hash it here as well, otherwise two
     *  elements that differ only in that member get the same hash, and the callers that use the
     *  hash as an identity of the expression treat them as the same expression.
     */

That last paragraph is a trap documented in the source: add a member to ASTFunction, forget to hash it, and two different functions become “the same expression” for the optimizer.

Limits

The parser bounds the recursion depth of the parse, but the AST can end up deeper than the parse was:

cpp 
// src/Parsers/parseQuery.cpp:569
    /// Also check on the AST level, because the generated AST depth can be greater than the recursion depth of the parser.
    if (res && max_parser_depth)
        res->checkDepth(max_parser_depth);

The check is iterative, not recursive, for the same reason the destructor is:

cpp 
// src/Parsers/IAST.cpp:173
size_t IAST::checkDepthImpl(size_t max_depth) const
{
    std::vector<std::pair<ASTPtr, size_t>> stack;
    stack.reserve(children.size());

    for (const auto & i: children)
        stack.push_back({i, 1});

    size_t res = 0;

    while (!stack.empty())
    {
        auto top = stack.back();
        stack.pop_back();

        if (top.second >= max_depth)
            throw Exception(ErrorCodes::TOO_DEEP_AST, "AST is too deep. Maximum: {}", max_depth);

        res = std::max(res, top.second);

        for (const auto & i: top.first->children)
            stack.push_back({i, top.second + 1});
    }

    return res;
}

An explicit stack of (node, depth) pairs, allocated on the heap. The same pattern — recursion in the builder, iteration in the checker and the destructor — appears throughout the AST code.

Printing it back

The AST can be turned back into SQL, which is what EXPLAIN, SHOW CREATE TABLE, the query log and the distributed-query rewriter all need. The formatter is a virtual formatImpl on every node, driven by a FormatStateStacked frame that carries the nesting level and a handful of flags:

cpp 
// src/Parsers/IAST.h:404
    /// The state that is copied when each node is formatted. For example, nesting level.
    struct FormatStateStacked
    {
        UInt16 indent = 0;
        bool need_parens = false;
        bool expression_list_always_start_on_new_line = false;  /// Line feed and indent before expression list even if it's of single element.
        bool expression_list_prepend_whitespace = false; /// Prepend whitespace (if it is required)
        bool surround_each_list_element_with_parens = false;
        bool allow_operators = true; /// Format some functions, such as "plus", "in", etc. as operators.
        bool allow_moving_operators_before_parens = true; /// Allow moving operators like "-" before parens: (-...) -> -(...)
        size_t list_element_index = 0;
        std::string create_engine_name;
        const IAST * current_select = nullptr;
        const IAST * current_function = nullptr;  /// Pointer to the function whose arguments are being formatted
        bool parent_has_trailing_settings = false; /// A parent ASTQueryWithOutput will append SETTINGS after this node's output.
        bool has_trailing_output_options = false; /// A parent ASTQueryWithOutput has trailing output options (SETTINGS, FORMAT, INTO OUTFILE).
        bool disable_from_first_syntax = false; /// Disable FROM-first syntax for SELECTs inside INSERT (to avoid parsing ambiguity).
        /// Set by a parent formatter that has explicitly emitted `(` around this child to indicate
        /// that the child should not emit its own `parenthesized` parens (which would duplicate the parent's).
        /// Consumed (cleared) by `IAST::format` so it only applies one level deep.
        bool wrapped_in_parens = false;
        /// Set by `IAST::format` when the node has both `isParenthesized()` and a non-empty alias,
        /// to tell `ASTWithAlias::formatImpl` to emit `(expr) AS alias` instead of `(expr AS alias)`.
        /// This keeps the format-parse-format round-trip stable: `(expr) AS alias` re-parses with
        /// `parenthesized=true` on the aliased node, which formats back to `(expr) AS alias`.
        bool parenthesize_alias_inner_only = false;
    };

That is 20-odd flags, all of them one bit or one small integer, all living in a struct that is copied down the tree rather than passed by reference. The copying is the point: a node’s formatter can change the flags for its children without disturbing its siblings.

The parenthesized bit in flags_storage is a good example of why the flag word exists at all. ClickHouse remembers that the user wrote (a + b) rather than a + b, so that the query can be printed back exactly as it was written — but the parentheses carry no meaning for the analyzer, and the storage engine’s table definitions want them gone. Hence a separate formatIgnoringRedundantParentheses() entry point.

Dumping the tree

For debugging, dumpTree prints the tree with indentation and the address of every node:

cpp 
// src/Parsers/IAST.cpp:424
void IAST::dumpTree(WriteBuffer & ostr, size_t indent) const
{
    checkStackSize();
    String indent_str(indent, '-');
    ostr << indent_str << getID() << ", ";
    writePointerHex(this, ostr);
    writeChar('\n', ostr);
    for (const auto & child : children)
    {
        if (!child)
            throw Exception(ErrorCodes::UNKNOWN_ELEMENT_IN_AST, "Can't dump a nullptr child");
        child->dumpTree(ostr, indent + 1);
    }
}

The indentation is a run of - characters, one per level, and the node’s getID() names it. This is what EXPLAIN AST=1 produces:

sql 
EXPLAIN AST = 1 SELECT a + 1 FROM t;
text 
SelectWithUnionQuery, 0x55f1c0a4e2d0
-ExpressionList, 0x55f1c0a4e330
--Function_plus, 0x55f1c0a4e580
---Identifier_a, 0x55f1c0a4e710
---Literal_1, 0x55f1c0a4e8a0
-ASTTableIdentifier_t, 0x55f1c0a4e940

Each line is the indentation, the node’s getID() (which is the class name plus the node’s own name, joined with an underscore), and the node’s address. The address is how you spot the DAG: the same address appearing twice means the subtree is shared.

The shape of the thing

text 
              ASTSelectQuery
              (refcount 1)
                   |
        +----------+----------+
        |                     |
 ASTExpressionList     ASTTableExpression
 (refcount 1)          (refcount 1)
     |                       |
     |            +----------+----------+
     |            |                     |
 ASTIdentifier  ASTFunction        ASTIdentifier
 (refcount 2)  (refcount 1)        (refcount 1)
     ^               |
     |               |
     +-------+-------+
             |
     shared by two slots

An ASTIdentifier reached from two places has a refcount of 2. When one holder is dropped, the count goes to 1 and nothing happens. When the last one goes, the node is recycled — and, if it has children, its children are recycled too, iteratively.

The cost

Per node: 32 bytes of header, plus the children vector’s heap block (which is one allocation per node that has children), plus the node’s own payload. A SELECT with 10 columns produces on the order of 100 nodes, so a typical query’s AST is a few kilobytes — and it is allocated once and shared everywhere afterwards.

The price is that IAST is a base class with a virtual destructor, a virtual formatImpl, a virtual clone, a virtual getID, a virtual updateTreeHashImpl, a virtual writeJSON/readJSON, and a virtual forEachPointerToChild. That is at least six vtable slots and an indirect call on every operation, on a structure that is traversed constantly.

ClickHouse pays that deliberately: the AST is the interface between the parser, the analyzer, the planner, the formatter, the rewriters and the logs, and all of them are in different translation units and different libraries. A flat struct-of-arrays would be faster and would couple them together. The tree of polymorphic nodes keeps them apart, and the 32-byte header keeps the cost of that decision small.

ClickhousePerformanceInternalsAstParser