Opensource internals

ClickHouse Resolves Identifiers While It Parses

15 min read Jay Hubbert

ClickHouse's parser unquotes identifiers, splits compound names into parts, guesses the table qualifier, and turns {name:Type} into a parameter node before the analyzer ever runs.

TL;DR: An identifier is not just a string. db.tbl.col is a qualified reference, col might be a column or an alias or a table, and {id:UInt32} is not a name at all — it is a hole to be filled in later. ClickHouse’s parser resolves all of that eagerly, at parse time: it unquotes the name, splits it into parts, guesses which part is the table qualifier, and builds a parameter node for a placeholder.

Most parsers treat an identifier as an opaque string. The lexer produces QuotedIdentifier or BareWord, the parser copies the bytes into a string, and everything else — is this a column, an alias, a table? which table? — is deferred to the analyzer, which is allowed to ask the catalog.

sql 
-- Four spellings, four different shapes of node:
SELECT a, `a`, "a", {a:Identifier} FROM db.tbl;
--    ^     ^    ^         ^
--    |     |    |         +-- ASTIdentifier("", [ASTQueryParameter])
--    |     |    +------------ ASTIdentifier("a")   (quoting is forgotten)
--    |     +----------------- ASTIdentifier("a")
--    +----------------------- ASTIdentifier("a")

ClickHouse does part of that work in the parser, and the reason is practical: the AST is shared between the parser, the analyzer, the rewriters, the formatter and the query log, and a node that has already resolved its own spelling needs no further interpretation. The price is a set of deliberate approximations, several of which the source marks with FIXME.

One node, three spellings

ParserIdentifier accepts a backquoted name, a double-quoted name, a Unicode-quoted name, a bare word, and — optionally — a query parameter:

cpp 
// src/Parsers/ExpressionElementParsers.cpp:344
bool ParserIdentifier::parseImpl(Pos & pos, ASTPtr & node, Expected & expected)
{
    /// Identifier in backquotes or in double quotes or in English-style Unicode double quotes
    if (pos->type == TokenType::QuotedIdentifier)
    {
        /// The case of Unicode quotes. No escaping is supported. Assuming UTF-8.
        if (*pos->begin == '\xE2' && pos->size() >= 6)
        {
            if (pos->size() == 6) /// Empty Unicode-quoted identifiers are not allowed.
                return false;
            node = make_intrusive<ASTIdentifier>(String(pos->begin + 3, pos->end - 3));
            ++pos;
            return true;
        }

        ReadBufferFromMemory buf(pos->begin, pos->size());
        String s;

        if (*pos->begin == '`')
            readBackQuotedStringWithSQLStyle(s, buf);
        else
            readDoubleQuotedStringWithSQLStyle(s, buf);

        if (s.empty())    /// Identifiers "empty string" are not allowed.
            return false;

        node = make_intrusive<ASTIdentifier>(s);
        ++pos;
        return true;
    }
    if (pos->type == TokenType::BareWord)
    {
        node = make_intrusive<ASTIdentifier>(String(pos->begin, pos->end));
        ++pos;
        return true;
    }

The unquoting happens here, in the parser, not in the lexer. The lexer hands over a token range; readBackQuotedStringWithSQLStyle turns `ab`` intoab and readDoubleQuotedStringWithSQLStyle turns "a\"b" into a"b. By the time the ASTIdentifier exists, the name is the name, not the spelling.

The price is that the spelling is gone. The source is explicit about it:

cpp 
// src/Parsers/IdentifierQuotingStyle.h:43
    /// A name that the user wrote quoted solely to preserve a mixed-case spelling (`(SELECT "Foo" FROM t)`)
    /// therefore comes out unquoted and is folded to `foo` as well. That is not a property of this rule:
    /// `ParserIdentifier` does not record whether an identifier was quoted, so `"Foo"` and `Foo` are the very
    /// same parsed identifier, and every rule that does not quote unconditionally - `WhenNecessary`, which
    /// this one replaced, included - emits it the same way. Only the `query('...')` form, which is passed to
    /// the external database verbatim, can express a case-sensitive mixed-case identifier.
    AlwaysUnlessUpperCase,

"Foo" and Foo parse to the same AST node. Only the formatter’s quoting rule can put the quotes back, and it decides to do so based on the name’s content (does it contain upper case? is it a keyword?), not on what the user typed.

Compound names

ParserCompoundIdentifier handles a.b.c, and it is where the eager resolution starts. It parses the parts one at a time, and each part may be separated by a dot, or by one of three special two-character delimiters:

cpp 
// src/Parsers/ExpressionElementParsers.cpp:502
    auto element_parser = std::make_unique<ParserIdentifier>(allow_query_parameter, highlight_type);
    std::vector<std::pair<ParserPtr, SpecialDelimiter>> delimiter_parsers;
    delimiter_parsers.emplace_back(std::make_unique<ParserTokenSequence>(std::vector<TokenType>{TokenType::Dot, TokenType::Colon}), SpecialDelimiter::JSON_PATH_DYNAMIC_TYPE);
    delimiter_parsers.emplace_back(std::make_unique<ParserTokenSequence>(std::vector<TokenType>{TokenType::Dot, TokenType::Caret}), SpecialDelimiter::JSON_PATH_PREFIX);
    delimiter_parsers.emplace_back(std::make_unique<ParserTokenSequence>(std::vector<TokenType>{TokenType::Dot, TokenType::At}), SpecialDelimiter::JSON_PATH_COMBINED);
    delimiter_parsers.emplace_back(std::make_unique<ParserToken>(TokenType::Dot), SpecialDelimiter::NONE);

The three special delimiters exist because of ClickHouse’s JSON column type: json.a.b.:UInt32 is the dynamic type of the subcolumn a.b, json.a.^path is a path prefix, and json.a.@path is a combined one. The parser encodes the delimiter by gluing it to the front of the part and back-quoting the rest:

cpp 
// src/Parsers/ExpressionElementParsers.cpp:527
        if (last_special_delimiter != SpecialDelimiter::NONE)
        {
            parts.push_back(static_cast<char>(last_special_delimiter) + backQuote(getIdentifierName(element)));
        }
        else
        {
            parts.push_back(getIdentifierName(element));
            /// Check if we have Array of JSON subcolumn additioon after identifier
            /// and replace it with corresponding type subcolumn.
            if (!is_first && array_of_json_identifier_addition.check(pos, expected))
                parts.push_back(array_of_json_identifier_addition.getLastArrayOfJSONSubcolumnIdentifier());
        }

So the part : + `UInt32` is stored as the string :`UInt32`, and the formatter can tell it apart from a part that happens to be spelled UInt32 with a backquote in it. The split is done later, by splitSpecialDelimiterAndIdentifierIfAny, when the node is formatted.

The eager guess

Now the interesting part. The compound constructor stores the parts and guesses which one is the table qualifier:

cpp 
// src/Parsers/ASTIdentifier.cpp:33
ASTIdentifier::ASTIdentifier(std::vector<String> && name_parts_, bool special, ASTs && name_params)
    : name_parts(name_parts_), semantic(std::make_shared<IdentifierSemanticImpl>())
{
    chassert(!name_parts.empty());
    semantic->special = special;
    semantic->legacy_compound = true;
    if (!name_params.empty())
    {
        [[maybe_unused]] size_t params = 0;
        for (const auto & part [[maybe_unused]] : name_parts)
        {
            if (part.empty())
                ++params;
        }
        chassert(params == name_params.size());
        children = std::move(name_params);
    }
    else
    {
        for (const auto & part [[maybe_unused]] : name_parts)
            chassert(!part.empty());

        if (!special && name_parts.size() >= 2)
            semantic->table = name_parts.end()[-2];

        resetFullName();
    }
}

semantic->table = name_parts.end()[-2]; — the second to last part is declared to be the table qualifier, at construction time, long before the FROM clause has been parsed. For db.tbl.col the guess is tbl; for tbl.col it is tbl.

This is the “resolve eagerly” trick in its purest form, and it is a guess, not a resolution. The parser does not know whether a.b is table.column or alias.column or two parts of a database name; it records the hypothesis, and the analyzer corrects it later using the actual FROM clause. The IdentifierSemantic machinery in src/Interpreters/IdentifierSemantic.h is the corrector: it has setColumnShortName, setColumnLongName, chooseTable, canReferColumnToTable, and a ColumnMatch enum that distinguishes ColumnName, AliasedTableName, TableName, DBAndTable, TableAlias and Ambiguous.

The same constructor also flattens the parts into the dotted name:

cpp 
// src/Parsers/ASTIdentifier.cpp:283
void ASTIdentifier::resetFullName()
{
    full_name = name_parts[0];
    for (size_t i = 1; i < name_parts.size(); ++i)
        full_name += '.' + name_parts[i];
}

so ASTIdentifier carries both the parts and the joined name. The joined name is what getID() and the tree hash use; the parts are what the analyzer uses.

The semantic is a pimpl

cpp 
// src/Parsers/ASTIdentifier.h:60
    String full_name;
    std::vector<String> name_parts;

protected:
    std::shared_ptr<IdentifierSemanticImpl> semantic; /// pimpl

IdentifierSemanticImpl lives in src/Interpreters/, not in src/Parsers/. Putting it behind a shared_ptr keeps the parser library independent of the analyzer library — the parser can be built standalone for WebAssembly (utils/wasm-parser), and the whole src/Interpreters tree does not have to come along.

The shared_ptr (rather than a value) has a second purpose. clone() copies the semantic by value:

cpp 
// src/Parsers/ASTIdentifier.cpp:169
ASTPtr ASTIdentifier::clone() const
{
    auto ret = make_intrusive<ASTIdentifier>(*this);
    ret->semantic = std::make_shared<IdentifierSemanticImpl>(*ret->semantic);
    ret->cloneChildren();
    return ret;
}

A clone must not share its semantic with the original, because the analyzer mutates the semantic in place (setting the table membership, covering the name with an alias, and so on). If the semantic were shared, resolving one copy would resolve the other.

Tables are a different node

ASTTableIdentifier derives from ASTIdentifier and is what the parser builds for a table reference:

cpp 
// src/Parsers/ASTIdentifier.h:80
class ASTTableIdentifier : public ASTIdentifier
{
public:
    explicit ASTTableIdentifier(const String & table_name, ASTs && name_params = {});
    explicit ASTTableIdentifier(const StorageID & table_id, ASTs && name_params = {});
    ASTTableIdentifier(const String & database_name, const String & table_name, ASTs && name_params = {});

    String getID(char delim) const override { return "TableIdentifier" + (delim + name()); }
    ASTPtr clone() const override;
    void writeJSON(WriteBuffer & out) const override;
    void readJSON(const Poco::JSON::Object & json) override;

    UUID uuid = UUIDHelpers::Nil;  // FIXME(ilezhankin): make private
    /// True iff the parser saw an explicit `UUID '...'` clause, set even when the parsed value is `Nil`.
    /// Use this (not `uuid != UUIDHelpers::Nil`) when you need to distinguish "user wrote `UUID '...'`"
    /// from "no UUID clause": explicit `UUID '00000000-0000-0000-0000-000000000000'` parses to `Nil`.
    bool has_uuid = false;

The distinction matters: a table reference may carry a UUID clause, and the has_uuid flag distinguishes “the user wrote UUID '...'” from “there was no UUID clause” even when the UUID is the nil UUID. The parser decides which node to build:

cpp 
// src/Parsers/ExpressionElementParsers.cpp:563
    ParserKeyword s_uuid(Keyword::UUID);
    UUID uuid = UUIDHelpers::Nil;
    bool has_uuid_clause = false;

    if (table_name_with_optional_uuid)
    {
        if (parts.size() > 2)
            return false;

        if (s_uuid.ignore(pos, expected))
        {
            ParserStringLiteral uuid_p;
            ASTPtr ast_uuid;
            if (!uuid_p.parse(pos, ast_uuid, expected))
                return false;
            uuid = parseFromString<UUID>(ast_uuid->as<ASTLiteral>()->value.safeGet<String>());
            has_uuid_clause = true;
        }

        if (parts.size() == 1) node = make_intrusive<ASTTableIdentifier>(parts[0], std::move(params));
        else node = make_intrusive<ASTTableIdentifier>(parts[0], parts[1], std::move(params));

A table reference may have at most two parts — table or database.table — and the parser rejects a third. The UUID is parsed by the parser, not by the analyzer, and the string is converted to a UUID right there.

Query parameters

Now the interesting case: {name:Type}. The parser accepts it as an identifier, but it is not a name — it is a placeholder.

cpp 
// src/Parsers/ExpressionElementParsers.cpp:380
    if (allow_query_parameter && pos->type == TokenType::OpeningCurlyBrace)
    {
        ++pos;
        if (pos->type != TokenType::BareWord)
        {
            expected.add(pos, "substitution name (identifier)");
            return false;
        }

        String name(pos->begin, pos->end);
        ++pos;

        if (pos->type != TokenType::Colon)
        {
            expected.add(pos, "colon between name and type");
            return false;
        }

        ++pos;

        if (pos->type != TokenType::BareWord)
        {
            expected.add(pos, "substitution type (identifier)");
            return false;
        }

        String type(pos->begin, pos->end);
        ++pos;

        if (type != "Identifier")
        {
            expected.add(pos, "substitution type (identifier)");
            return false;
        }

Note the last check: the only type accepted in the identifier position is the literal word Identifier. {id:UInt32} is not an identifier — it is a value of a known type, and the value parsers handle it. The identifier parser only handles the case where the whole name is unknown:

cpp 
// src/Parsers/ExpressionElementParsers.cpp:422
        node = make_intrusive<ASTIdentifier>("", make_intrusive<ASTQueryParameter>(name, type));
        return true;
    }
    return false;
}

An ASTIdentifier with an empty name and one child, which is an ASTQueryParameter:

cpp 
// src/Parsers/ASTQueryParameter.h:9
/// Parameter in query with name and type of substitution ({name:type}).
/// Example: SELECT * FROM table WHERE id = {pid:UInt16}.
class ASTQueryParameter : public ASTWithAlias
{
public:
    String name;
    String type;

    ASTQueryParameter(const String & name_, const String & type_) : name(name_), type(type_) {}

    /** Get the text that identifies this element. */
    String getID(char delim) const override { return String("QueryParameter") + delim + name + ':' + type; }

For a compound name with a parameter in it — {db}.tbl.col — the same trick is used per part: the part is stored as an empty string in name_parts, and the parameter node is stored as a child. The compound constructor’s chassert(params == name_params.size()) is what keeps the two in step, and the formatter walks them together:

cpp 
// src/Parsers/ASTIdentifier.cpp:228
    if (compound())
    {
        for (size_t i = 0, j = 0, size = name_parts.size(); i < size; ++i)
        {
            if (i != 0)
                ostr << '.';

            /// Some AST rewriting code, like IdentifierSemantic::setColumnLongName,
            /// does not respect children of identifier.
            /// Here we also ignore children if they are empty.
            if (name_parts[i].empty() && j < children.size())
            {
                children[j]->format(ostr, settings, state, frame);
                ++j;
            }
            else
                format_element(name_parts[i]);
        }
    }

The empty part is a placeholder in the name_parts vector, and the child list is walked in parallel. The comment is a warning from the author: some rewriting code does not respect the children of an identifier, so the formatter has to cope with a part that is empty and has no corresponding child.

The whole mechanism carries a FIXME in the header:

cpp 
// src/Parsers/ASTIdentifier.h:19
/// FIXME: rewrite code about params - they should be substituted at the parsing stage,
///        or parsed as a separate AST entity.

The parameters are resolved after parsing, by a visitor, and the author thinks the whole approach is wrong. It is still there, and it works, but the source says what it thinks of it.

SETTINGS

SET and the SETTINGS clause of a SELECT share one parser. The parse_only_internals flag is what distinguishes them:

cpp 
// src/Parsers/ParserSetQuery.cpp:339
bool ParserSetQuery::parseImpl(Pos & pos, ASTPtr & node, Expected & expected)
{
    ParserToken s_comma(TokenType::Comma);

    if (!parse_only_internals)
    {
        ParserKeyword s_set(Keyword::SET);

        if (!s_set.ignore(pos, expected))
            return false;

        /// Parse SET TRANSACTION ... queries using ParserTransactionControl
        if (ParserKeyword{Keyword::TRANSACTION}.check(pos, expected))
            return false;

        /// Parse SET TIME ZONE 'tz' as an alias for SET session_timezone = 'tz'
        if (ParserKeyword{Keyword::TIME_ZONE}.ignore(pos, expected))
        {
            ParserToken eq(TokenType::Equals);
            eq.ignore(pos, expected); // optional, for PostgreSQL compatibility
            ASTPtr value_node;
            ParserLiteralOrMap literal_parser;

            if (!literal_parser.parse(pos, value_node, expected))
                return false;

            auto query = make_intrusive<ASTSetQuery>();
            node = query;

            query->is_standalone = !parse_only_internals;

            SettingChange change;
            change.name = "session_timezone";
            change.value = value_node->as<ASTLiteral &>().value;
            query->changes.push_back(std::move(change));

            return true;
        }
    }

SET TIME ZONE 'UTC' is rewritten by the parser into a session_timezone change — a PostgreSQL compatibility alias that never reaches the analyzer as a SET TIME ZONE.

The SETTINGS clause of a SELECT uses the same parser with parse_only_internals = true:

cpp 
// src/Parsers/ParserSelectQuery.cpp:875
    /// SETTINGS key1 = value1, key2 = value2, ...
    if (s_settings.ignore(pos, expected))
    {
        ParserSetQuery parser_settings(true);

        if (!parser_settings.parse(pos, settings, expected))
            return false;
    }

so SELECT 1 SETTINGS max_threads = 8 and SET max_threads = 8 produce the same ASTSetQuery, differing only in the is_standalone flag.

The pair parser is where the setting values are decided:

cpp 
// src/Parsers/ParserSetQuery.cpp:239
bool ParserSetQuery::parseNameValuePairWithParameterOrDefault(
    SettingChange & change, String & default_settings, ParserSetQuery::Parameter & parameter, IParser::Pos & pos, Expected & expected, bool enable_shorthand_syntax)
{
    ParserCompoundIdentifier name_p;
    ParserLiteralOrMap value_p;
    ParserToken s_eq(TokenType::Equals);
    ParserFunction function_p;

    ASTPtr node;
    String name;
    ASTPtr function_ast;
    bool have_eq = false;

    if (!name_p.parse(pos, node, expected))
        return false;

    have_eq = s_eq.ignore(pos, expected);

    if (!enable_shorthand_syntax && !have_eq)
        return false;

    tryGetIdentifierNameInto(node, name);

Three things can follow a setting name:

  • param_ — a query parameter, not a setting:
cpp 
// src/Parsers/ParserSetQuery.cpp:262
    /// Parameter
    if (name.starts_with(QUERY_PARAMETER_NAME_PREFIX))
    {
        if (!have_eq)
            return false;

        name = name.substr(strlen(QUERY_PARAMETER_NAME_PREFIX));

        if (name.empty())
            throw Exception(ErrorCodes::BAD_ARGUMENTS, "Parameter name cannot be empty");

        String value;

        if (!parseParameterValueIntoString(pos, value, expected))
            return false;

        parameter = {std::move(name), std::move(value)};
        return true;
    }
  • DEFAULT — reset to the default value;
  • a value — a literal, a map, a disk(...) call, or a {name:Type} parameter.

And there is the shorthand: a setting name with no value at all means = true.

cpp 
// src/Parsers/ParserSetQuery.cpp:323
    else
    {
        /// A setting name with no value is shorthand for `= true`. Only a Bool setting can be
        /// written this way, but the parser does not know the settings schema, so it records that
        /// the value was omitted and leaves the check to `BaseSettings::applyChange`.
        node = make_intrusive<ASTLiteral>(Field(true));
    }

    change.name = name;
    change.value = node->as<ASTLiteral &>().value;
    change.shorthand = !have_eq;

The parser records that the value was omitted (change.shorthand = true) rather than pretending it knows the value. The settings schema check happens later, in BaseSettings::applyChange. That is the right division of labour: the parser does not know the list of settings, and there are hundreds of them with dozens of types.

A SET statement and a SETTINGS clause produce the same node:

sql 
SET max_threads = 8, force_index_by_date;   -- shorthand: = true
SET param_rows = 1000;                      -- a query parameter, not a setting
SELECT 1 SETTINGS max_threads = 8;          -- the same ASTSetQuery, is_standalone = false

The result is a small, flat structure:

cpp 
// src/Parsers/ASTSetQuery.h:17
/** SET query
  */
class ASTSetQuery : public IAST
{
public:
    /// If false, this AST is a part of another query, such as SELECT.
    bool is_standalone = true;

    SettingsChanges changes;
    /// settings that will be reset to default value
    std::vector<String> default_settings;
    NameToNameVector query_parameters;

    /** Get the text that identifies this element. */
    String getID(char) const override { return "Set"; }

Three vectors: the changes, the settings to reset, and the parameters. Note that ASTSetQuery has no children — the settings are not AST nodes at all, they are SettingChange structs with a name and a Field value. The parser decided the value’s type at parse time, so there is nothing left to resolve.

Filling the holes

The parameters are resolved after parsing, by a visitor:

cpp 
// src/Interpreters/ReplaceQueryParameterVisitor.h:17
class ReplaceQueryParameterVisitor
{
public:
    explicit ReplaceQueryParameterVisitor(const NameToNameMap & parameters)
        : query_parameters(parameters)
    {}

    void visit(ASTPtr & ast);

    /// Resolve query parameters used as setting values (e.g. `max_threads = {threads:UInt64}`)
    /// directly in a SettingsChanges list. Used when settings from a query are applied to a
    /// context outside of the full AST traversal (e.g. on the client side).
    void visitSettingsChanges(SettingsChanges & changes);

Two entry points, because a setting value can hold a parameter without the setting living in the AST: SET max_threads = {threads:UInt64} is a SettingsChanges entry, and the client applies it to a context without walking the AST. visitSettingsChanges handles that case.

The visitor rebuilds the identifiers whose parts were parameters:

text 
    {db}.tbl.col
      |
      v
    ASTIdentifier(name_parts = ["", "tbl", "col"], children = [ASTQueryParameter("db", "Identifier")])
      |
      |  ReplaceQueryParameterVisitor, with db = "mydb"
      v
    ASTIdentifier(name_parts = ["mydb", "tbl", "col"], children = [])

The placeholder is replaced by the value, and the empty part is filled in.

What this buys, and what it costs

The eager resolution buys three things:

  • the AST is self-describing — ASTIdentifier knows its own parts, its joined name, and its hypothesis about the table qualifier, so the formatter, the tree hash and the log do not need the catalog;
  • the parser does the work once — the unescaping, the splitting and the joining are done at parse time and never repeated;
  • the UUID clause and the SET TIME ZONE alias are resolved at parse time, where the surrounding syntax is still known.

The costs are visible in the source:

  • the FIXME about parameters — a placeholder is encoded as an empty string in a vector of names, and every consumer of name_parts has to know that;
  • the semantic->table guess — the second-to-last part is assumed to be a table, and the analyzer has to correct it, which means the parser’s answer is sometimes wrong until then;
  • the loss of the quoting — "Foo" and Foo are the same node, so the formatter cannot reproduce the user’s spelling;
  • the TODO(ilezhankin) markers on restoreTable, setShortName and createTable, which are the code that patches up the parser’s guesses after the fact.

The pattern is consistent: the parser resolves everything it can resolve without the catalog, and leaves everything that needs the catalog — which column is this, which table does it belong to — to the analyzer, but leaves behind a hypothesis in the node so the analyzer has a starting point.

ClickhousePerformanceInternalsParserAstQuery parameters