Opensource internals

ClickHouse Parses SQL with a Backtracking Recursive-Descent Parser

14 min read Jay Hubbert

ClickHouse's SQL parser is a set of small combinator objects that share one mutable position, rewind it on failure, and count every rewind against a hard backtrack budget.

TL;DR: ClickHouse’s parser is not a generated LL(k) table. It is a set of ~200 small IParser objects, each of which is handed a mutable position into a token stream, tries to consume something, and rewinds the position if it fails. Every rewind is counted, and a query that rewinds more than 1 000 000 times is rejected.

SQL is a language designed by committee, and it is not LL(1). SELECT a FROM t and SELECT a FROM t WHERE x differ only in what follows FROM, and the parser cannot know until it has looked. A column may be followed by an alias, a table may be followed by a join or by a WHERE, and ( may open a subquery, a tuple, a function argument list, or a parenthesised expression.

Two classic answers:

  • Backtracking (recursive descent). Try to parse the alternative; if it fails, put the input back and try the next one. Simple to write, exponential in the worst case, and needs a hard budget to stay safe.
  • Table-driven (yacc/bison). Precompute the decision table. Fast and linear, but you need a grammar compiler, and the grammar of a language like ClickHouse’s SQL is large enough that the tables get big.

ClickHouse takes the first route, and the interesting engineering is not in the grammar — it is in making “put the input back” cheap, and in making “this query is trying too many things” detectable.

The token stream

The parser never sees the query text. It sees a lazily-produced vector of tokens:

cpp 
// src/Parsers/TokenIterator.h:35
    const Token & operator[] (size_t index)
    {
        while (true)
        {
            if (index < data.size())
            {
                max_pos = std::max(max_pos, index);
                return data[index];
            }

            if (!data.empty() && data.back().isEnd())
            {
                max_pos = data.size() - 1;
                return data.back();
            }

            Token token = lexer.nextToken();

            if (!skip_insignificant || token.isSignificant())
                data.emplace_back(token);
        }
    }

    const Token & max()
    {
        if (data.empty())
            return (*this)[0];
        return data[max_pos];
    }

operator[] is a pull on demand: asking for token 40 lexes tokens 0..40 and stops. Since a failed parse rewinds, the same tokens are re-read rather than re-lexed — the lexer runs at most once per token of the query.

max_pos is the rightmost token anybody has looked at. It is what tryParseQuery uses to decide where the error is:

cpp 
// src/Parsers/parseQuery.cpp:564
    ASTPtr res;
    const bool parse_res = parser.parse(token_iterator, res, expected);
    const auto last_token = token_iterator.max();
    _out_query_end = last_token.end;

Tokens::reset() exists for the one case where the parser has to be restarted from scratch: the fast path in tryParseQuery that scans for lexical errors before attempting a real parse, and then throws the scan away.

On top of Tokens sits a cursor:

cpp 
// src/Parsers/TokenIterator.h:82
    ALWAYS_INLINE const Token & get() { return (*tokens)[index]; }
    ALWAYS_INLINE const Token & operator*() { return get(); }
    ALWAYS_INLINE const Token * operator->() { return &get(); }

    ALWAYS_INLINE TokenIterator & operator++()
    {
        ++index;
        return *this;
    }
    ALWAYS_INLINE TokenIterator & operator--()
    {
        --index;
        return *this;
    }

The class is a Tokens * and a size_t index, plus the five comparison operators that compare indices, isValid() (which stops at EndOfStream) and max() (the rightmost token anybody looked at).

A TokenIterator is a Tokens* and a size_t. Copying it is copying 16 bytes, which is what makes “save the position” cheap.

The position is the parser’s state

IParser::Pos is a TokenIterator plus four counters. This is the heart of the whole design:

cpp 
// src/Parsers/IParser.h:120
    struct Pos : TokenIterator
    {
        uint32_t depth = 0;
        uint32_t max_depth = 0;

        uint32_t backtracks = 0;
        uint32_t max_backtracks = 0;

        Pos(Tokens & tokens_, uint32_t max_depth_, uint32_t max_backtracks_)
            : TokenIterator(tokens_), max_depth(max_depth_), max_backtracks(max_backtracks_)
        {
        }

        Pos(TokenIterator token_iterator_, uint32_t max_depth_, uint32_t max_backtracks_)
            : TokenIterator(token_iterator_), max_depth(max_depth_), max_backtracks(max_backtracks_)
        {
        }

Two budgets, one for each way a recursive-descent parser can go wrong:

  • depth counts nesting — a subquery inside a subquery inside an expression. The limit is max_parser_depth, default 1000.
  • backtracks counts rewinds — how many times the parser has said “that alternative did not work, let me try another”. The limit is max_parser_backtracks, default 1 000 000.
cpp 
// src/Core/Defines.h:91
/// Default limit on recursion depth of recursive descend parser.
static constexpr auto DBMS_DEFAULT_MAX_PARSER_DEPTH = 1000;
/// Default limit on the amount of backtracking of recursive descend parser.
static constexpr auto DBMS_DEFAULT_MAX_PARSER_BACKTRACKS = 1000000;

How a rewind is detected

Here is the part I like. The parser never declares that it is about to backtrack. There is no try_parse helper, no mark()/reset() pair. Instead, the position notices that it is being moved backwards:

cpp 
// src/Parsers/IParser.cpp:14
/// NOLINTBEGIN(cert-oop54-cpp)
IParser::Pos & IParser::Pos::operator=(const IParser::Pos & rhs)
{
    depth = rhs.depth;
    max_depth = rhs.max_depth;
    backtracks = std::max(backtracks, rhs.backtracks);
    max_backtracks = rhs.max_backtracks;

    if (rhs < *this)
    {
        ++backtracks;
        if (max_backtracks && backtracks > max_backtracks)
            throw Exception(ErrorCodes::TOO_SLOW_PARSING, "Maximum amount of backtracking ({}) exceeded in the parser. "
                "Consider rising max_parser_backtracks parameter.", max_backtracks);
    }

    TokenIterator::operator=(rhs);

    return *this;
}
/// NOLINTEND(cert-oop54-cpp)

rhs < *this is rhs.index < this.index: the new position is behind the old one. That is a rewind, so the counter goes up by one, and if it exceeds the budget the parser throws TOO_SLOW_PARSING.

The consequences are elegant:

  • Every rewind is counted, including ones nobody thought to instrument. If a new parser is added that rewinds in a loop, it is caught for free.
  • The counter is monotonic: backtracks = std::max(backtracks, rhs.backtracks) means restoring an old snapshot cannot lower the count.
  • The check is max_backtracks && ..., so a limit of 0 means “unlimited” — which is how max_parser_depth is documented (“0 — Recursion depth is unlimited”).

The budget is therefore not a property of any one parser; it is a property of the position, and it is shared by the whole tree of parsers.

The same Pos also carries the depth counter, and enforces it:

cpp 
// src/Parsers/IParser.h:150
        ALWAYS_INLINE void increaseDepth()
        {
            ++depth;
            if (unlikely(max_depth > 0 && depth > max_depth))
                throw Exception(ErrorCodes::TOO_DEEP_RECURSION, "Maximum parse depth ({}) exceeded. "
                    "Consider rising max_parser_depth parameter.", max_depth);

and, further down in the same function, a checkStackSize() every 8192 frames (128 under sanitizers or musl, where the frames are bigger):

cpp 
// src/Parsers/IParser.h:157
            /** Sometimes the maximum parser depth can be set to a high value by the user,
              * but we still want to avoid stack overflow.
              * For this purpose, we can use the checkStackSize function, but it is too heavy.
              * The solution is to check not too frequently.
              * The frequency is arbitrary, but not too large, not too small,
              * and a power of two to simplify the division.
              */
#if defined(USE_MUSL) || defined(SANITIZER) || !defined(NDEBUG)
            static constexpr uint32_t check_frequency = 128;
#else
            static constexpr uint32_t check_frequency = 8192;
#endif
            if (depth % check_frequency == 0)
                checkStackSize();
        }

That call is a guard against the other failure mode: a user who sets max_parser_depth to 100 000 and sends a query with 100 000 nested parentheses will overflow the C++ stack before the counter trips.

The rewind idiom

Now the actual parser code. Every parser that can fail does the same thing:

cpp 
// src/Parsers/IParserBase.h:17
    template <typename F>
    ALWAYS_INLINE static bool wrapParseImpl(Pos & pos, const F & func)
    {
        Pos begin = pos;
        bool res = func();
        if (!res)
            pos = begin;
        return res;
    }

    struct IncreaseDepthTag {};

    template <typename F>
    ALWAYS_INLINE static bool wrapParseImpl(Pos & pos, IncreaseDepthTag, const F & func)
    {
        Pos begin = pos;
        pos.increaseDepth();
        bool res = func();
        pos.decreaseDepth();
        if (!res)
            pos = begin;
        return res;
    }

Pos begin = pos; is a 32-byte copy (a 16-byte cursor plus four counters). pos = begin; is the rewind, and the operator= above notices it and charges it to the budget. There is no exception handling, no RAII guard, no std::optional — the failure path is one assignment.

The second overload is the depth-tracking one. IParserBase::parse uses it:

cpp 
// src/Parsers/IParserBase.cpp:7
bool IParserBase::parse(Pos & pos, ASTPtr & node, Expected & expected)
{
    expected.add(pos, getName());

    return wrapParseImpl(pos, IncreaseDepthTag{}, [&]
    {
        const char * begin = pos->begin;
        bool res = parseImpl(pos, node, expected);

and on failure it clears the node:

cpp 
// src/Parsers/IParserBase.cpp:31
        else
            node = nullptr;
        return res;
    });
}

Three things happen in the wrapper, and every parser in the codebase gets them for free:

  1. expected.add(pos, getName()) — before trying, tell the error machinery what this parser was hoping for, and where.
  2. increaseDepth() / decreaseDepth() — the nesting budget.
  3. On failure, node = nullptr — a failed parse must not leave a half-built AST behind.

The Highlight block records the byte range a keyword or identifier parser consumed, so the query editor can colour the original text; the range is recovered from the token stream, not from the AST.

The interface

IParser is deliberately tiny:

cpp 
// src/Parsers/IParser.h:196
    virtual bool parse(Pos & pos, ASTPtr & node, Expected & expected) = 0;

    bool ignore(Pos & pos, Expected & expected)
    {
        ASTPtr ignore_node;
        return parse(pos, ignore_node, expected);
    }

The contract, in the source’s own words: parse piece of text from position pos, move pointer pos to the maximum position to which it was possible to parse, in case of success return true and the result in node if it is needed, otherwise false, in expected write what was expected in the maximum position.

The convenience wrappers are what parsers actually call: ignore throws the AST away, and check is the lookahead primitive — parse, but restore the position even on success:

cpp 
// src/Parsers/IParser.h:212
    bool check(Pos & pos, Expected & expected)
    {
        Pos begin = pos;
        ASTPtr node;
        if (!parse(pos, node, expected))
        {
            pos = begin;
            return false;
        }
        return true;
    }

check answers “does the next thing match this parser?”. Its sibling checkWithoutMoving takes the position by value, so the caller’s cursor is never touched at all — which is why it does not need to restore anything.

Error messages: the rightmost failure wins

A backtracking parser has a problem: it fails in many places, and the user only cares about the last one — the one furthest along the query.

Expected solves this with a simple rule: a failure at a position further right than any previous failure wipes the list of alternatives and starts a new one. The struct holds an InlineVector<const char *, 7> variants (seven const char * fit inline, with a heap fallback beyond that) and a max_parsed_pos pointer into the query text:

cpp 
// src/Parsers/IParser.h:90
    /// 'description' should be statically allocated string.
    ALWAYS_INLINE void add(const char * current_pos, const char * description)
    {
        if (!max_parsed_pos || current_pos > max_parsed_pos)
        {
            variants.clear();
            max_parsed_pos = current_pos;
            variants.push_back(description);
            return;
        }

        if ((current_pos == max_parsed_pos) && (std::find(variants.begin(), variants.end(), description) == variants.end()))
            variants.push_back(description);
    }

The strings are static literals, so there is nothing to own.

Because every parser calls expected.add(pos, getName()) before it tries, the “expected” list at the end of a failed parse is exactly the set of alternatives that were live at the furthest position reached. SELECT a FROM fails with “expected: table identifier, subquery, function” rather than with the fifty things that were expected three tokens earlier.

Keywords are matched by text

A keyword is not a token type. ParserKeyword matches a word against a string, case-insensitively, and it supports compound keywords with anything in between:

cpp 
// src/Parsers/CommonParsers.cpp:103
    while (true)
    {
        expected.add(pos, current_word);

        if (pos->type != TokenType::BareWord)
            return false;

        const char * const next_whitespace = find_first_symbols<' ', '\0'>(current_word, s.data() + s.size());
        const size_t word_length = next_whitespace - current_word;

        if (word_length != pos->size())
            return false;

        if (0 != strncasecmp(pos->begin, current_word, word_length))
            return false;

        ++pos;

        if (!*next_whitespace)
            break;

        current_word = next_whitespace + 1;
    }

The while loop is what makes ORDER BY a single keyword: the keyword string is "ORDER BY", and the loop walks the space-separated words one at a time, requiring a BareWord token of exactly the right length for each. Since the lexer throws away whitespace and comments by default, ORDER/*x*/BY matches too.

The keyword itself is one of the 666 entries in the Keyword enum, generated from a macro in src/Parsers/CommonParsers.h:

cpp 
// src/Parsers/CommonParsers.h:688
enum class Keyword : size_t
{
#define DECLARE_PARSER_KEYWORD_ENUM(identifier, name) identifier,

    APPLY_FOR_PARSER_KEYWORDS(DECLARE_PARSER_KEYWORD_ENUM) APPLY_FOR_PARSER_KEYWORDS_WITH_UNDERSCORES(DECLARE_PARSER_KEYWORD_ENUM)
#undef DECLARE_PARSER_KEYWORD_ENUM
};

Trying the alternatives

With all those pieces in place, the top-level statement parser is just a long chain of alternatives, tried in order:

cpp 
// src/Parsers/ParserQuery.cpp:132
    bool res = query_with_output_p.parse(pos, node, expected)
        || insert_p.parse(pos, node, expected)
        || use_p.parse(pos, node, expected)
        || parseSetRoleQuery(pos, node, expected)
        || set_p.parse(pos, node, expected)
        || system_p.parse(pos, node, expected)
        || parseCreateAccessEntityQuery(pos, node, expected)
        || create_function_p.parse(pos, node, expected)
        || drop_function_p.parse(pos, node, expected)
        || create_workload_p.parse(pos, node, expected)

… and then fifteen more: named collections, handlers, indexes, hypothetical objects, grants, transactions, DELETE, UPDATE and COPY.

Twenty-six alternatives, each of which must fail cheaply if it is not the right one. ParserInsertQuery starts by matching INSERT; if the token is not INSERT it fails after touching one token. The whole chain is O(number of statement kinds) in the common case.

The order matters, and the source says so:

cpp 
// src/Parsers/ParserQuery.cpp:51
/** The DCL statements: access management, in three groups because each has to keep its place among
  * the other alternatives. `SET ROLE` has to be tried before `SET`, which would otherwise read it
  * as the shorthand for a `Bool` setting named `ROLE`.
  *
  * A `CLICKHOUSE_PARSER_NO_DCL` build has none of them, and the linker then drops
  * `src/Parsers/Access` and `src/Access/Common` along with them. See `utils/wasm-parser`.
  */

That is a genuine ambiguity, resolved by ordering rather than by lookahead: SET ROLE must be tried before SET, because SET alone also accepts a bareword setting name.

What backtracking costs, and what it buys

The failure mode of a backtracking parser is a query that makes it try an enormous number of alternatives. ClickHouse’s answer is the budget in Pos::operator=, and the error it produces:

sql 
-- SET max_parser_backtracks = 100;
-- SELECT ...;   -- a query crafted to explore many alternatives
-- Code: 407, DB::Exception: Maximum amount of backtracking (100) exceeded in the parser.
-- Consider rising max_parser_backtracks parameter. (TOO_SLOW_PARSING)

The cost of the design is that the worst case is exponential in the nesting depth, and ClickHouse pays for that with a limit rather than with an algorithm. The benefit is that a new SQL feature is a new IParser subclass and nothing else — no grammar file, no generated tables, no build-time codegen. src/Parsers/ contains about 200 of them.

The other benefit is error messages. Because every alternative records what it expected at the position it reached, the error can say “one of: table identifier, subquery, function” — and, since the alternatives are keywords from the language, it can also find the typo:

cpp 
// src/Parsers/parseQuery.cpp:208
    for (const char * variant : expected.variants)
    {
        /// Only a description that is a keyword itself can be meant literally: the parser also adds prose
        /// such as `SELECT query, possibly with UNION`. A single word cannot be a typo of a multi-word
        /// keyword either, so anything with a space is not a candidate.
        const std::string_view variant_view(variant);
        if (variant_view.size() + max_distance < token.size() || token.size() + max_distance < variant_view.size())
            continue;
        if (!std::all_of(variant_view.begin(), variant_view.end(), [](char c) { return isUpperAlphaASCII(c) || c == '_'; }))
            continue;

        const size_t distance = levenshteinDistanceCaseInsensitive(token, String(variant_view));
        /// Zero distance means the token is that keyword, so it cannot be the reason of the failure.
        if (distance > 0 && distance < best_distance)
        {
            best_distance = distance;
            best_variant = variant_view;
        }
    }

    return best_variant;
}

The thresholds are deliberately tight — one edit for short words, two for longer ones — because the candidate list is keywords, not identifiers from the query. Almost every short word is within a small distance of some keyword, so a loose threshold would suggest nonsense. The comment says it outright: “a wrong guess is worse than no guess”.

The whole picture

text 
        query text
            |
            v
      +-----------+        +-------------+      +-------------+
      |   Lexer   | -----> |    Tokens   | ---> | TokenIterator|
      | (no alloc)|        | (lazy vec)  |      |  (index)     |
      +-----------+        +-------------+      +------+------+
                                                         |
                                                         v
                                              +-----------------+
                                              |      Pos        |
                                              |  index          |
                                              |  depth    <= 1000
                                              |  backtracks<=1e6 |
                                              +--------+--------+
                                                       |
        +----------------------------------------------+-------------+
        |                      |                       |             |
   parse() succeeds      parse() fails            ignore()      check()
        |                      |                       |          (rewind)
        v                      v                       v
   AST subtree          pos = begin  ----------->  rewind charged
   (ASTPtr)              (charged)                    to budget

The design in one sentence: the parser has exactly one piece of mutable state, and every failure is a rewind of that state.

That is what makes the two budgets meaningful. The depth budget bounds the C++ stack, and the backtrack budget bounds the work. Both are enforced in one place, and both are enforced for every parser in the codebase without any of them opting in.

ClickhousePerformanceInternalsParserAst