Opensource internals

ClickHouse Tokenizes SQL with a Hand-Written Lexer

14 min read Jay Hubbert

ClickHouse tokenizes SQL with a pointer-arithmetic lexer that never allocates, has no keyword table, and disambiguates dots from decimals by looking at the previous token.

TL;DR: ClickHouse’s SQL lexer is a single pass over the query buffer that produces Token { type, begin, end } — three machine words, no allocation, and no keyword table at all. SELECT and my_column are the same token type (BareWord); the 666 keywords live in a separate list that the lexer never looks at.

Every SQL database has a tokenizer, and most of them are the same boring thing: a switch over the current character, a hash map of keywords, and a std::string per token. That is fine for a table with a hundred columns. It is not fine for a database whose whole selling point is that a query is a stream: ClickHouse sends queries to a server over a binary protocol, keeps them in a query cache, and re-parses them on every replica.

ClickHouse’s lexer is written for that world. It never allocates, it never copies the query text, and it produces tokens that point directly into the original buffer. The interesting part is not the speed, it is the set of decisions the lexer has to make without any context except “what was the previous token”.

The token set

The token list is a macro, so that the same list generates the enum, the name table, and the error descriptions:

cpp 
// src/Parsers/Lexer.h:14
#define APPLY_FOR_TOKENS(M) \
    M(Whitespace) \
    M(Comment) \
    \
    M(BareWord)               /** Either keyword (SELECT) or identifier (column) */ \
    \
    M(Number)                 /** Always non-negative. No leading plus. 123 or something like 123.456e12, 0x123p12 */ \
    M(StringLiteral)          /** 'hello word', 'hello''word', 'hello\'word\\' */ \
    \
    M(QuotedIdentifier)       /** "x", `x` */ \
    \
    M(OpeningRoundBracket) \
    M(ClosingRoundBracket) \
    \
    M(OpeningSquareBracket) \
    M(ClosingSquareBracket) \
    \
    M(OpeningCurlyBrace) \
    M(ClosingCurlyBrace) \
    \
    M(Comma) \
    M(Semicolon) \
    M(VerticalDelimiter)      /** Vertical delimiter \G */ \
    M(Dot)                    /** Compound identifiers, like a.b or tuple access operator a.1, (x, y).2. */ \
                              /** Need to be distinguished from floating point number with omitted integer part: .1 */ \
    \
    M(Asterisk)               /** Could be used as multiplication operator or on it's own: "SELECT *" */ \
    \
    M(HereDoc) \
    \
    M(DollarSign) \

The rest of the list is the operator zoo: Plus, Minus, Slash, Percent, Arrow (->), QuestionMark, Colon, Caret, DoubleColon (::), Equals, NotEquals, Less, Greater, LessOrEquals, GreaterOrEquals, Spaceship (<=>), PipeMark, PipeOperator (|>), Concatenation (||), Tilde, TildeAsterisk, NotTilde, NotTildeAsterisk, At, DoubleAt.

That is 54 token types, and the enum that comes out of it is a single byte:

cpp 
// src/Parsers/Lexer.h:89
enum class TokenType : uint8_t
{
#define M(TOKEN) TOKEN,
APPLY_FOR_TOKENS(M)
#undef M
};

The ordering at the end of the list is load-bearing. EndOfStream sits after every real token, and every error token sits after EndOfStream:

cpp 
// src/Parsers/Lexer.h:72
    /** Order is important. EndOfStream goes after all usual tokens, and special error tokens goes after EndOfStream. */ \
    \
    M(EndOfStream) \
    \
    /** Something unrecognized. */ \
    M(Error) \
    /** Something is wrong and we have more information. */ \
    M(ErrorMultilineCommentIsNotClosed) \
    M(ErrorSingleQuoteIsNotClosed) \
    M(ErrorDoubleQuoteIsNotClosed) \
    M(ErrorBackQuoteIsNotClosed) \
    M(ErrorSingleExclamationMark) \
    M(ErrorSinglePipeMark) \
    M(ErrorWrongNumber) \
    M(ErrorMaxQuerySizeExceeded) \

which lets the Token type answer “is this a lexical error?” with a single comparison, no switch and no table:

cpp 
// src/Parsers/Lexer.h:102
struct Token
{
    TokenType type;
    const char * begin;
    const char * end;

    size_t size() const { return end - begin; }

    Token() = default;
    Token(TokenType type_, const char * begin_, const char * end_) : type(type_), begin(begin_), end(end_) {}

    bool isSignificant() const { return type != TokenType::Whitespace && type != TokenType::Comment; }
    bool isError() const { return type > TokenType::EndOfStream; }
    bool isEnd() const { return type == TokenType::EndOfStream; }
};

Note what is not in the token: the text. A token is a type and a half-open range into the query buffer. begin and end are const char * into memory that the caller owns and keeps alive; the lexer borrows, it does not own.

The lexer is a cursor

cpp 
// src/Parsers/Lexer.h:119
class Lexer
{
public:
    Lexer(const char * begin_, const char * end_, size_t max_query_size_ = 0)
        : begin(begin_), pos(begin_), end(end_),
        max_query_size(max_query_size_ <= max_query_size_limit ? max_query_size_ : max_query_size_limit)
    {
    }

    Token nextToken();

private:
    const char * const begin;
    const char * pos;
    const char * const end;

    const size_t max_query_size;

    /// Some reasonable size to at least avoid pointer overflows.
    static constexpr size_t max_query_size_limit = 1'000'000'000;

    Token nextTokenImpl();

    /// This is needed to disambiguate tuple access operator from floating point number (.1).
    TokenType prev_significant_token_type = TokenType::Whitespace;   /// No previous token.
};

Three pointers, one size_t, one byte of state. The max_query_size clamp is the only defensive arithmetic: it caps the limit at 1 GB so that begin + max_query_size cannot overflow a pointer on a 32-bit build.

The single byte of state — prev_significant_token_type — is what makes the lexer able to handle .5 versus t.1 without a symbol table. It is the entire “context” the lexer has.

Why there is no keyword table

The most surprising thing about this lexer is what it does not contain. There is no SELECT in it, no FROM, no ORDER BY. The keyword list lives in src/Parsers/CommonParsers.h, in a macro that expands to 666 entries (630 uppercase spellings plus 36 with underscores), and it is used for two things only:

  • the parser, when it wants to match a keyword — via ParserKeyword, which compares the current token’s text against the keyword;
  • the formatter, when it wants to re-quote an identifier that would otherwise be read back as a keyword.

That second use is the only one that consults a set:

cpp 
// src/Parsers/IAST.cpp:350
    if (identifier_quoting_rule == IdentifierQuotingRule::UserDisplay && !must_quote)
    {
        // Quote `name` if it is one of the keywords when `identifier_quoting_rule` is `IdentifierQuotingRule::UserDisplay`
        const auto & keyword_set = getKeyWordSet();
        must_quote = keyword_set.contains(Poco::toUpper(name));
    }

The consequence is a pleasant one: SELECT, select, and SeLeCt are all the same token, and the parser decides what they mean by comparing the token’s bytes against a keyword at the point where the keyword is expected. A column literally named select needs no special case in the lexer at all.

The dot problem

. is the token that makes SQL lexing genuinely hard, because it is three different things:

InputMeaning
a.bcompound identifier (qualifier)
t.1.1chained tuple access
.5a floating-point literal with no integer part (only where a float may appear)
(x, y).2tuple access on a parenthesized tuple

The lexer resolves this with the one byte of state. A . is a qualifier unless it is followed by a digit and the previous significant token was not something that can end an expression:

cpp 
// src/Parsers/Lexer.cpp:285
        case '.':   /// qualifier, tuple access operator or start of floating point number
        {
            /// Just after identifier or complex expression or number (for chained tuple access like x.1.1 to work properly).
            if (pos > begin
                && (!(pos + 1 < end && isNumericASCII(pos[1]))
                    || prev_significant_token_type == TokenType::ClosingRoundBracket
                    || prev_significant_token_type == TokenType::ClosingSquareBracket
                    || prev_significant_token_type == TokenType::BareWord
                    || prev_significant_token_type == TokenType::QuotedIdentifier
                    || prev_significant_token_type == TokenType::Number))
                return Token(TokenType::Dot, token_begin, ++pos);

Read it as: if the next character is a digit and the previous significant token cannot end an expression, then this . starts a number. Otherwise it is a qualifier.

The consequence is that SELECT .5 is a Dot followed by the number 5, not the number 0.5 — the previous token is SELECT, a BareWord, and a bare word can end an expression. Write 0.5. A leading-dot float only appears where a float can legally stand, e.g. SELECT x = .5, where the previous token is =.

And SELECT a.5 — the previous token is a, also a BareWord — is a qualifier followed by the integer 5, which is exactly what makes x.1.1 work as chained tuple access.

The number scanner has to agree, and it uses the same state. The trick is that after a ., a number may only be a simple integer:

sql 
-- What the lexer sees for these four lines:
SELECT t.1.1 FROM t;     -- BareWord Dot Number Dot Number
SELECT x = .5;          -- BareWord Equals Number   (the float 0.5)
SELECT x = 0.5;         -- BareWord Equals Number   (the float 0.5)
SELECT 'it''s', `a b`;  -- StringLiteral QuotedIdentifier
cpp 
// src/Parsers/Lexer.cpp:166
            /// The task is not to parse a number or check correctness, but only to skip it.

            /// Disambiguation: if previous token was dot, then we could parse only simple integer,
            ///  for chained tuple access operators (x.1.1) to work.
            //  Otherwise it will be tokenized as x . 1.1, not as x . 1 . 1
            if (prev_significant_token_type == TokenType::Dot)
            {
                ++pos;
                while (pos < end && (isNumericASCII(*pos) || isNumberSeparator(false, false, pos, end)))
                    ++pos;
            }

Note the comment: “The task is not to parse a number or check correctness, but only to skip it.” The lexer never converts text to a value. 12345678901234567890 and 1e999999 are both just a Number token with a range; the parser turns them into ASTLiterals later, and only then does the range check happen. This is why the lexer can be so small: it is a scanner, not a converter.

Strings and identifiers

The same scanner handles single-quoted strings, double-quoted identifiers and backquoted identifiers, because the escape rules are identical — a doubled quote or a backslash:

cpp 
// src/Parsers/Lexer.cpp:24
template <char quote>
Token quotedString(const char *& pos, const char * const token_begin, const char * const end,
    TokenType success_token, TokenType error_token)
{
    ++pos;
    while (true)
    {
        pos = find_first_symbols<quote, '\\'>(pos, end);
        if (pos >= end)
            return Token(error_token, token_begin, end);

        if (*pos == quote)
        {
            ++pos;
            if (pos < end && *pos == quote)
            {
                ++pos;
                continue;
            }
            return Token(success_token, token_begin, pos);
        }

        if (*pos == '\\')
        {
            ++pos;
            if (pos >= end)
                return Token(error_token, token_begin, end);
            ++pos;
            continue;
        }

        chassert(false);
    }
}

The interesting part is find_first_symbols<quote, '\\'>: instead of stepping one character at a time, it asks a SIMD routine to find the next quote or backslash. The scan of a long string literal is therefore a handful of 16-byte comparisons rather than a byte-at-a-time loop. (The same helper is what the CSV parser and the URL parser use.)

The three call sites differ only in the token type they produce:

cpp 
// src/Parsers/Lexer.cpp:261
        case '\'':
            return quotedString<'\''>(pos, token_begin, end, TokenType::StringLiteral, TokenType::ErrorSingleQuoteIsNotClosed);
        case '"':
            return quotedString<'"'>(pos, token_begin, end, TokenType::QuotedIdentifier, TokenType::ErrorDoubleQuoteIsNotClosed);
        case '`':
            return quotedString<'`'>(pos, token_begin, end, TokenType::QuotedIdentifier, TokenType::ErrorBackQuoteIsNotClosed);

Backquoted and double-quoted are the same token type — QuotedIdentifier. The lexer does not distinguish them; only the formatter does, because IdentifierQuotingStyle chooses which quoting to emit.

There is a fourth spelling: the Unicode typographic quotes ‘…’ and “…”, which arrive as three UTF-8 bytes and are handled by a separate scanner:

cpp 
// src/Parsers/Lexer.cpp:480
        case '\xE2':
        {
            /// Mathematical minus symbol, UTF-8
            if (pos + 3 <= end && pos[1] == '\x88' && pos[2] == '\x92')
            {
                pos += 3;
                return Token(TokenType::Minus, token_begin, pos);
            }
            /// Unicode quoted string, ‘Hello’ or “World”.
            if (pos + 5 < end && pos[0] == '\xE2' && pos[1] == '\x80' && (pos[2] == '\x98' || pos[2] == '\x9C'))
            {
                const char expected_end_byte = pos[2] + 1;
                TokenType success_token = pos[2] == '\x98' ? TokenType::StringLiteral : TokenType::QuotedIdentifier;
                TokenType error_token = pos[2] == '\x98' ? TokenType::ErrorSingleQuoteIsNotClosed : TokenType::ErrorDoubleQuoteIsNotClosed;
                pos += 3;
                return quotedStringWithUnicodeQuotes(pos, token_begin, end, expected_end_byte, success_token, error_token);
            }
            /// Other characters starting at E2 can be parsed, see skipWhitespacesUTF8
            [[fallthrough]];
        }

The E2 byte is a prefix of a large part of the UTF-8 range, so this branch has to be careful: it checks the second byte to decide whether the sequence is the mathematical minus − (U+2212), a Unicode quote, or something else that must fall through to the general path.

Comments

Four comment syntaxes, all folded into the single Comment token type:

cpp 
// src/Parsers/Lexer.cpp:344
        case '/':   /// division (/) or start of comment (//, /*)
        {
            ++pos;
            if (pos < end && (*pos == '/' || *pos == '*'))
            {
                if (*pos == '/')
                {
                    ++pos;
                    return comment_until_end_of_line();
                }

                ++pos;

                /// Nested multiline comments are supported according to the SQL standard.
                size_t nesting_level = 1;

                while (pos + 2 <= end)
                {
                    if (pos[0] == '/' && pos[1] == '*')
                    {
                        pos += 2;
                        ++nesting_level;
                    }
                    else if (pos[0] == '*' && pos[1] == '/')
                    {
                        pos += 2;
                        --nesting_level;

                        if (nesting_level == 0)
                            return Token(TokenType::Comment, token_begin, pos);
                    }
                    else
                        ++pos;
                }
                pos = end;
                return Token(TokenType::ErrorMultilineCommentIsNotClosed, token_begin, pos);
            }
            return Token(TokenType::Slash, token_begin, pos);
        }

-- and // run to the end of the line; /* … */ nests, per the SQL standard; and # is MySQL-style but only when followed by whitespace, because PostgreSQL uses # as an operator:

cpp 
// src/Parsers/Lexer.cpp:383
        case '#':   /// start of single line comment, MySQL style
        {           /// PostgreSQL has some operators using '#' character.
                    /// For less ambiguity, we will recognize a comment only if # is followed by whitespace.
                    /// or #! as a special case for "shebang".
                    /// #hello - not a comment
                    /// # hello - a comment
                    /// #!/usr/bin/clickhouse-local --queries-file - a comment
            ++pos;
            if (pos < end && (*pos == ' ' || *pos == '!'))
                return comment_until_end_of_line();
            return Token(TokenType::Error, token_begin, pos);
        }

The #hello case is a nice piece of design-by-ambiguity: ClickHouse has both a # operator (from PostgreSQL compatibility) and MySQL-style comments, and it resolves the collision with a single space of lookahead.

Words, dollars, and heredocs

The default: branch handles the tail of the character space: heredocs, dollar signs, hex and binary literals, and bare words. The heredoc scan is backwards-looking — it finds the closing $tag$ by searching the rest of the buffer:

cpp 
// src/Parsers/Lexer.cpp:520
                    if (is_valid_name)
                    {
                        size_t heredoc_end_position = std::string_view{tag_end + 1, end}.find(std::string_view{pos, heredoc_size});
                        if (heredoc_end_position != std::string::npos)
                        {
                            pos = tag_end + 1 + heredoc_end_position + heredoc_size;
                            return Token(TokenType::HereDoc, token_begin, pos);
                        }
                    }

A heredoc that is never closed is not a heredoc — the $ degrades into a DollarSign or the start of a bare word. Bare words themselves may contain $ ($1, param_$x):

cpp 
// src/Parsers/Lexer.cpp:543
            if (isWordCharASCII(*pos) || *pos == '$')
            {
                ++pos;
                while (pos < end && (isWordCharASCII(*pos) || *pos == '$'))
                    ++pos;
                return Token(TokenType::BareWord, token_begin, pos);
            }

Hex and binary literals (x'ABCD', b'1010') are detected by peeking at the byte after the current one: the default branch is entered with pos still pointing at the x or b, checks pos[1] == '\'', and hands the whole range to a dedicated scanner.

The size limit

Finally, the one place where the lexer is not a pure scanner:

cpp 
// src/Parsers/Lexer.cpp:116
Token Lexer::nextToken()
{
    Token res = nextTokenImpl();
    if (begin && max_query_size && res.end > begin + max_query_size)
        res.type = TokenType::ErrorMaxQuerySizeExceeded;
    if (res.isSignificant())
        prev_significant_token_type = res.type;
    return res;
}

Two things happen after every token. First, the query-size limit is enforced: any token that ends past max_query_size is turned into ErrorMaxQuerySizeExceeded, which is terminal for the parser. Second, the one byte of context is updated — but only for significant tokens, so whitespace and comments do not disturb the dot disambiguation.

Note that the check is res.end > begin + max_query_size: the limit is applied to the end of the token, so a query of exactly max_query_size bytes is accepted, and the check happens per token, not per character.

Numbers that are not numbers

The lexer has no error recovery, no modes and no context stack: it produces a stream of tokens and stops. Everything else — deciding whether a.b is a qualifier, whether x is a column or a function, whether the query is a SELECT or an INSERT — happens in the parser.

One exception lives in the number scanner, and it is a curiosity worth a paragraph: 1abc is lexically a bare word, provided every character in it is a word character or $:

cpp 
// src/Parsers/Lexer.cpp:242
            /// Try to parse it to a identifier(1identifier_name), otherwise it return ErrorWrongNumber
            if (pos < end && isWordCharASCII(*pos))
            {
                ++pos;
                while (pos < end && isWordCharASCII(*pos))
                    ++pos;

                for (const char * iterator = token_begin; iterator < pos; ++iterator)
                {
                    if (!isWordCharASCII(*iterator) && *iterator != '$')
                        return Token(TokenType::ErrorWrongNumber, token_begin, pos);
                }

                return Token(TokenType::BareWord, token_begin, pos);
            }

So 1abc lexes as BareWord and is a valid identifier, while 1.5abc is ErrorWrongNumber, because the . is not a word character. It is a small, deliberate exception that keeps the lexer from having to know about numeric literal syntax.

The cost

A SELECT with ten columns produces on the order of 30 tokens. Each token is 24 bytes (uint8_t type, two pointers, plus padding), and the token vector is a plain std::vector<Token> that grows once and is then reused for the whole query. The lexer itself allocates nothing at all: no std::string, no std::vector, no std::function.

That is the whole trick. A token is a range, a range is two pointers, and the parser can always go back and read the text again — because the text is still there, exactly where the user wrote it.

ClickhousePerformanceInternalsParserLexer