Opensource internals

ClickHouse Parses URLs with a Hand-Written State Machine

24 min read Jay Hubbert

ClickHouse's 27 URL functions share one hand-rolled byte scanner that walks scheme, authority and path with SIMD find_first_symbols instead of a regex engine.

TL;DR: ClickHouse has 27 registered URL functions and none of them uses a regular expression. They share a hand-written byte scanner built on a SIMD find_first_symbols, plus a token-generator protocol (set() / get()) that lets one state machine serve URLHierarchy, URLPathHierarchy, splitByString and friends.

Web analytics is a common ClickHouse workload: a table of request logs, and you want to slice it by host, by path, by query parameter. So ClickHouse ships a family of URL functions:

sql 
SELECT domain(url), path(url), queryString(url), topLevelDomain(url),
       firstSignificantSubdomain(url), extractURLParameter(url, 'utm_source')
FROM hits;

The obvious way to implement those is with a regular expression. domain would be ^https?://([^/:?#]+), path would be ^[^:]+://[^/]+(/[^?#]*)?, and so on. Every one of them, plus a dozen variants. That approach has two problems.

First, regexes are slow in bulk. RE2 is not a slow engine, but it is a general-purpose one: it compiles the pattern to a program, runs a finite automaton over the input, and pays for capture-group bookkeeping that most of these functions do not need. A domain() call that just needs to find the third / pays for a full regexp engine.

Second, and more subtly, the semantics are wrong. A regex expresses “find a substring shaped like this”. A URL parser has to express “this is the host of this URL”, which means dealing with userinfo (user@host), port separators, IPv6 literals in brackets ([::1]:8080), and the fact that @ can appear in a userinfo section and that a second @ invalidates the first one’s interpretation. Those are not regular in the regex sense.

ClickHouse’s answer is to write the scanner by hand. Here is what that looks like.

The shape of the family

The functions live in src/Functions/URL/. The directory listing is essentially the API surface:

text 
src/Functions/URL/
├── URLHierarchy.cpp            URLHierarchy(url)         -> Array(String)
├── URLPathHierarchy.cpp        URLPathHierarchy(url)     -> Array(String)
├── basename.cpp                basename(path)            -> String

├── cutFragment.cpp             cutFragment(url)          -> String
├── cutQueryString.cpp          cutQueryString(url)       -> String
├── cutQueryStringAndFragment.cpp
├── cutToFirstSignificantSubdomain.cpp
├── cutToFirstSignificantSubdomainCustom.cpp
├── cutURLParameter.cpp         cutURLParameter(url, name) -> String
├── cutWWW.cpp                  cutWWW(url)               -> String
├── decodeURLComponent.cpp      decodeURLComponent(s)     -> String
├── domain.cpp                  domain(url)               -> String
├── domainWithoutWWW.cpp
├── extractURLParameter.cpp     extractURLParameter(url, name) -> String
├── extractURLParameterNames.cpp
├── extractURLParameters.cpp
├── firstSignificantSubdomain.cpp
├── firstSignificantSubdomainCustom.cpp
├── fragment.cpp                fragment(url)             -> String
├── netloc.cpp                  netloc(url)               -> String
├── path.cpp                    path(url)                 -> String
├── pathFull.cpp
├── port.cpp                    port(url)                 -> String
├── protocol.cpp                protocol(url)             -> String
├── queryString.cpp             queryString(url)          -> String
├── queryStringAndFragment.cpp
├── topLevelDomain.cpp          topLevelDomain(url)       -> String
└── tldLookup.generated.cpp     (gperf-generated TLD table)

Note that only a few of these have a .cpp with the implementation in it. Most of the logic is in headers, shared between functions. The reason is that almost all of them are the same function with different parameters: domain and domainWithoutWWW are one template; queryString and queryStringAndFragment are one template; topLevelDomain and topLevelDomainRFC are one template.

One warning before quoting any of it: in this tree the two hierarchy implementation files have swapped contents relative to their names. src/Functions/URL/URLHierarchy.cpp contains URLPathHierarchyImpl and registers URLPathHierarchy; src/Functions/URL/URLPathHierarchy.cpp contains URLHierarchyImpl and registers URLHierarchy. The line numbers below follow the files, not the function names.

The template parameters are bools, and the whole family is generated from a handful of Extractor structs with a execute(data, size, res_data, res_size) signature.

The extraction protocol

Every extractor implements the same four static members:

cpp 
// src/Functions/URL/path.h:10
template <bool with_query_string>
struct ExtractPath
{
    static size_t getReserveLengthForElement() { return 25; }

    static void execute(Pos data, size_t size, Pos & res_data, size_t & res_size)
    {
        res_data = data;
        res_size = 0;

        Pos pos = data;
        Pos end = pos + size;

        /// We support URLs with and without schema:
        /// 1. http://host/path
        /// 2. host/path
        /// We search for first slash and if there is subsequent slash, then skip and repeat search for the next slash.

        pos = find_first_symbols<'/'>(pos, end);
        if (end == pos)
            return;

        bool has_subsequent_slash = pos + 1 < end && pos[1] == '/';
        if (has_subsequent_slash)
        {
            /// Search for next slash.
            pos = find_first_symbols<'/'>(pos + 2, end);
            if (end == pos)
                return;
        }

        res_data = pos;

        if constexpr (with_query_string)
        {
            res_size = end - res_data;
        }
        else
        {
            Pos query_string_or_fragment = find_first_symbols<'?', '#'>(pos, end);
            res_size = query_string_or_fragment - res_data;
        }
    }
};

Three things to notice.

res_data / res_size is an out-parameter pair, not a string_view. The extractor returns a pointer into the input buffer and a length. No allocation, no copy. The caller (ExtractSubstringImpl) then does the copy into the result column.

The if constexpr (with_query_string) branch. path() and pathFull() are the same scanner with a different answer for the tail. pathFull includes the query string, path does not. if constexpr means the dead branch is not even instantiated — no runtime flag, no branch in the inner loop.

The “first slash, and if the next one is a slash, skip two” rule. This is the entire scheme-vs-no-scheme discrimination, in four lines:

  • http://host/path — the first / is at index 5, the next char is /, so we skip to index 7 and find the next /, which is the start of the path.
  • host/path — the first / is at index 4, the next char is p, not /, so the first slash is the path.

That is a heuristic, not a parser — but it is a heuristic on a problem where a heuristic is what the users actually want, and it is exactly the kind of thing a regex would also get “wrong” in the same way.

The SIMD primitive

The scanning primitive is find_first_symbols, which lives in base/base/find_symbols.h. It is the URL functions’ whole performance story:

cpp 
// base/base/find_symbols.h:19
/** find_first_symbols<c1, c2, ...>(begin, end):
  *
  * Allow to search for next character from the set of 'symbols...' in a string.
  * It is similar to 'strpbrk', 'strcspn' (and 'strchr', 'memchr' in the case of one symbol and '\0'),
  * but with the following differences:
  * - works with any memory ranges, including containing zero bytes;
  * - doesn't require terminating zero byte: end of memory range is passed explicitly;
  * - if not found, returns pointer to end instead of nullptr;
  * - maximum number of symbols to search is 16.
  *
  * Uses SSE 2 in case of small number of symbols for search and SSE 4.2 in the case of large number of symbols,
  *  that have more than 2x performance advantage over trivial loop
  *  in the case of parsing tab-separated dump with (probably escaped) string fields.
  * In the case of parsing tab separated dump with short strings, there is no performance degradation over trivial loop.
  *
  * Note: the optimal threshold to choose between SSE 2 and SSE 4.2 may depend on CPU model.

Three properties matter for the URL use case:

  • No terminating NUL required. URL strings in a ColumnString are length-prefixed slices of one big buffer; there is no NUL at the end of the slice.
  • Returns end rather than nullptr when not found. This makes the caller’s “did I find it” check a single pointer comparison, and it removes the need for a separate “found” flag.
  • Up to 16 symbols at once. So find_first_symbols<'?', '#'> finds the start of the query string or the fragment in one pass — the two characters that can end a path.

And it is SIMD: SSE2 on x86, NEON on aarch64.

The vectorised driver

The extractors are called from a shared driver that handles the column-at-a-time plumbing. Here is the whole of ExtractSubstringImpl::vector:

cpp 
// src/Functions/StringHelpers.h:62
template <typename Extractor>
struct ExtractSubstringImpl
{
    static void vector(
        const ColumnString::Chars & data, const ColumnString::Offsets & offsets,
        ColumnString::Chars & res_data, ColumnString::Offsets & res_offsets,
        size_t input_rows_count)
    {
        res_offsets.resize(input_rows_count);
        res_data.reserve(input_rows_count * Extractor::getReserveLengthForElement());

        size_t prev_offset = 0;
        size_t res_offset = 0;

        /// Matched part.
        Pos start = nullptr;
        size_t length = 0;

        for (size_t i = 0; i < input_rows_count; ++i)
        {
            Extractor::execute(reinterpret_cast<const char *>(&data[prev_offset]), offsets[i] - prev_offset, start, length);

            res_data.resize(res_data.size() + length);
            memcpySmallAllowReadWriteOverflow15(&res_data[res_offset], start, length);
            res_offset += length;
            res_offsets[i] = res_offset;
            prev_offset = offsets[i];
        }
    }

The getReserveLengthForElement() call is a per-extractor hint about the typical output length — 25 for a path, 15 for a domain, 10 for a query string, 5 for a top-level domain, 10 for a fragment. It is used to size the reserve() on the result buffer, which avoids repeated reallocation.

The memcpySmallAllowReadWriteOverflow15 is ClickHouse’s small-copy helper: for lengths up to 15 bytes it uses a branchy inline copy, and otherwise it calls memcpy. Since a typical extracted URL part is short, the inline path dominates.

Note also that the loop maintains prev_offset rather than reading offsets[i-1]: the offsets array is monotonically increasing, so the previous offset is the current start.

The authority: the hard part

path is easy — find a slash. domain is where it gets interesting, because the host of a URL is delimited by several different characters depending on the context, and the RFC has a specific grammar for it.

ClickHouse provides two variants. getURLHost is the legacy one, and getURLHostRFC is the RFC-3986-conformant one. They differ substantially. Here is the RFC one’s opening:

cpp 
// src/Functions/URL/domain.h:59
inline std::string_view getURLHostRFC(const char * data, size_t size)
{
    if (size < 2)
        return std::string_view{};

    Pos pos = data;
    Pos end = data + size;

    if (*pos == '/' && *(pos + 1) == '/')
    {
        pos += 2;
    }
    else if (isAlphaASCII(*pos))
    {
        Pos scheme_end = data + std::min(size, 16UL);
        for (++pos; pos < scheme_end; ++pos)
        {
            if (!isAlphaNumericASCII(*pos))
            {
                switch (*pos)
                {
                case '.':
                case '-':
                case '+':
                    break;
                case ' ': /// restricted symbols
                case '\t':
                case '<':
                case '>':
                case '%':
                case '{':
                case '}':
                case '|':
                case '\\':
                case '^':
                case '~':
                case ']':
                case ';':
                case '=':
                case '&':
                    return std::string_view{};
                default:
                    goto exloop;
                }
            }
        }
exloop: if ((scheme_end - pos) > 2 && *pos == ':' && *(pos + 1) == '/' && *(pos + 2) == '/')
            pos += 3;
        else
            pos = data;
    }

The goto exloop is a deliberate escape from the nested loop: the scheme scan finds the first character that cannot be part of a scheme, and if that character is : followed by //, we have a scheme and skip past it; otherwise the whole thing is reset to data (i.e. “there was no scheme, the host starts at the beginning”).

Note std::min(size, 16UL): the scheme scan is bounded at 16 bytes. An RFC scheme can be longer, but capping it keeps a malformed input like aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.com/x from costing a long scan, and because the fallback is “no scheme”, the cap is safe.

Then the authority scan proper — this is the state machine:

cpp 
// src/Functions/URL/domain.h:111
    bool has_open_bracket = false;
    bool has_end_bracket = false;
    if (pos < end && *pos == '[') /// IPv6 [2001:db8::1]:80
    {
        has_open_bracket = true;
        ++pos;
    }
    Pos bracket_close_pos = nullptr;
    Pos dot_pos = nullptr;
    Pos colon_pos = nullptr;
    bool has_sub_delims = false;
    bool has_at_symbol = false;
    bool has_terminator_after_colon = false;
    const auto * start_of_host = pos;
    for (; pos < end; ++pos)
    {
        switch (*pos) /// NOLINT(bugprone-switch-missing-default-case)
        {
        case '.':
            if (has_open_bracket)
                continue; /// part of a mixed IPv6/IPv4 tail, e.g. "::ffff:192.0.2.128"; parseIPv6Whole validates it below
            /// Once colon_pos is set (whether or not '@' has been seen), a dot afterward is past
            /// the host, in what would be the port - it must not count as a dot within the host,
            /// e.g. the '.' in "user@foo:80.bar" must not make checkAndReturnHost think "foo" has
            /// a valid dot of its own.
            if (colon_pos == nullptr)
                dot_pos = pos;
            break;
        case ':':
            if (has_open_bracket)
                continue;
            /// Whether or not '@' has been seen yet, this ':' might still turn out to be
            /// followed by a later '@' (e.g. "user@host:[email protected]"), which would mean it was
            /// never the port separator at all - keep only the first one as a fallback and keep
            /// scanning, instead of stopping the scan here.
            if (colon_pos == nullptr)
                colon_pos = pos;
            break;
        case '/': /// end symbols
        case '?':
        case '#':
            goto done;
        case '@': /// [email protected]
            /// Inside an IP-literal there is no userinfo: `@` is not allowed there at all.
            if (has_open_bracket) return std::string_view{};
            /// A bracket that already closed before this '@' would have to become part of
            /// userinfo now that '@' turned up - but raw '[' / ']' can never legally appear
            /// there, so an authority like "[::1]:[email protected]" is invalid, not "host evil.com".
            if (has_end_bracket) return std::string_view{};
            if (has_terminator_after_colon) return std::string_view{};
            if (has_at_symbol) return std::string_view{};
            has_sub_delims = false;
            has_at_symbol = true;
            start_of_host = pos + 1;
            colon_pos = nullptr;
            dot_pos = nullptr;
            has_terminator_after_colon = false;

The state is six booleans plus three remembered positions. The interesting invariant is the has_at_symbol one: a second @ invalidates the authority entirely. The URL http://user@[email protected]/ is not a URL with userinfo user and host [email protected]; it is malformed. The scanner detects this and returns an empty host.

That check exists because of a security consideration. A naive parser that takes the last @ as the separator would report evil.com as the host of http://[email protected]/ — the classic userinfo-confusion vulnerability. Taking the first @ would report [email protected] as the host, which is also wrong but less dangerous. Refusing outright is the safe answer.

The IPv6 handling is the other interesting part. A host can be an IP-literal in brackets: [2001:db8::1]:8080. Inside the brackets, : is part of the address, not a port separator, so the scanner flips into has_open_bracket mode and ignores colons and dots. It also tracks whether the bracket has closed, because after ] a : is an ordinary port separator again.

And it supports RFC 3986’s IPvFuture form, [v1.a], via a helper:

cpp 
// src/Functions/URL/domain.h:15
inline bool isIPvFuture(const char * begin, const char * end)
{
    if (begin >= end || (*begin != 'v' && *begin != 'V'))
        return false;

    const char * pos = begin + 1;
    const char * version_start = pos;
    while (pos < end && isHexDigit(*pos))
        ++pos;
    if (pos == version_start)
        return false;

    if (pos >= end || *pos != '.')
        return false;
    ++pos;

    const char * address_start = pos;
    for (; pos < end; ++pos)
    {
        char c = *pos;
        bool is_unreserved = isAlphaNumericASCII(c) || c == '-' || c == '.' || c == '_' || c == '~';
        bool is_sub_delim = c == '!' || c == '$' || c == '&' || c == '\'' || c == '(' || c == ')'
            || c == '*' || c == '+' || c == ',' || c == ';' || c == '=';
        if (!is_unreserved && !is_sub_delim && c != ':')
            return false;
    }
    return pos > address_start;
}

Finally, the host is only accepted if it has a dot and a character after it:

cpp 
// src/Functions/URL/domain.h:44
inline std::string_view checkAndReturnHost(const Pos & pos, const Pos & dot_pos, const Pos & start_of_host)
{
    if (!dot_pos || start_of_host >= pos || pos - dot_pos == 1 || *start_of_host == '.')
        return std::string_view{};

    auto after_dot = *(dot_pos + 1);
    if (after_dot == ':' || after_dot == '/' || after_dot == '?' || after_dot == '#')
        return std::string_view{};

    return std::string_view(start_of_host, pos - start_of_host);
}

“Has a dot, has something after the dot, and does not start with a dot” — the classic rule for “this looks like a hostname, not a bare word”. This is why domain('localhost') returns an empty string: localhost has no dot, so it is not a domain by this definition.

Note the after_dot check: foo.:8080 is rejected because the character after the dot is :. And foo. (dot at the end) is rejected by the pos - dot_pos == 1 check.

The token generator: URLHierarchy

URLHierarchy is the odd one out. It does not extract a single substring — it returns an array of progressively longer prefixes:

sql 
SELECT URLHierarchy('https://example.com/a/b?c=1');
-- ['https://example.com/','https://example.com/a/','https://example.com/a/b?','https://example.com/a/b?c=1']

Producing an array of N substrings means the result is an Array(String), and the implementation cannot use the ExtractSubstringImpl driver (which produces one substring per row). So ClickHouse invented a generator protocol to share the scanning logic.

The protocol is: init() once, then set(begin, end) per input string, then repeated get(token_begin, token_end) calls that yield one token at a time and return false when exhausted. URLPathHierarchyImpl implements it:

cpp 
// src/Functions/URL/URLHierarchy.cpp:51
    /// Get the next token, if any, or return false.
    bool get(Pos & token_begin, Pos & token_end)
    {
        /// Code from URLParser.

        if (pos == end)
            return false;

        if (pos == begin)
        {
            /// Let's parse everything that goes before the path

            /// Assume that the protocol has already been changed to lowercase.
            while (pos < end && ((*pos >= 'a' && *pos <= 'z') || (*pos >= '0' && *pos <= '9')))
                ++pos;

            /** We will calculate the hierarchy only for URLs in which there is a protocol, and after it there are two slashes.
             * (http, file - fit, mailto, magnet - do not fit), and after two slashes still at least something is there.
             * For the rest, just return an empty array.
             */
            if (pos == begin || pos == end || !(pos + 3 < end && pos[0] == ':' && pos[1] == '/' && pos[2] == '/'))
            {
                pos = end;
                return false;
            }
            pos += 3;

            /// The domain for simplicity is everything that after the protocol and the two slashes, until the next slash or `?` or `#`
            while (pos < end && !(*pos == '/' || *pos == '?' || *pos == '#'))
                ++pos;

            start = pos;

            if (pos != end)
                ++pos;
        }

        /// We go to the next `/` or `?` or `#`, skipping all those at the beginning.
        while (pos < end && (*pos == '/' || *pos == '?' || *pos == '#'))
            ++pos;
        if (pos == end)
            return false;
        while (pos < end && !(*pos == '/' || *pos == '?' || *pos == '#'))
            ++pos;

        if (pos != end)
            ++pos;

        token_begin = start;
        token_end = pos;

        return true;
    }

The state machine has two phases. The first get() call (when pos == begin) consumes the scheme and the authority and sets start to the beginning of the path. Subsequent calls walk the path, emitting one token per segment.

And URLHierarchy is the same protocol with one difference — it emits the scheme+authority as the first token:

cpp 
// src/Functions/URL/URLPathHierarchy.cpp:83
            token_begin = begin;
            token_end = pos;

            return true;
        }

Compare with URLPathHierarchy, which sets start = pos (the path) and leaves token_begin = start. Two nearly-identical 50-line state machines, differing in three lines, because the protocol is data, not code.

The protocol is generic enough that FunctionTokens — the shared higher-order driver in src/Functions/FunctionTokens.h — implements the column-at-a-time loop for any generator:

cpp 
// src/Functions/FunctionTokens.h:107
    ColumnPtr executeImpl(const ColumnsWithTypeAndName & arguments, const DataTypePtr & result_type, size_t input_rows_count) const override
    {
        Generator generator{};
        /// Only generators that opt in (currently `ExtractAllImpl`) take the JIT compile-count threshold.
        if constexpr (requires { generator.init(arguments, max_substrings_includes_remaining_string, regexp_jit_min_count); })
            generator.init(arguments, max_substrings_includes_remaining_string, regexp_jit_min_count);
        else
            generator.init(arguments, max_substrings_includes_remaining_string);

        const auto & array_argument = arguments[generator.strings_argument_position];
cpp 
// src/Functions/FunctionTokens.h:145
            for (size_t i = 0; i < input_rows_count; ++i)
            {
                Pos pos = reinterpret_cast<Pos>(&src_chars[current_src_offset]);
                current_src_offset = src_offsets[i];
                Pos end = reinterpret_cast<Pos>(&src_chars[current_src_offset]);

                generator.set(pos, end);
                size_t j = 0;
                while (generator.get(token_begin, token_end))
                {
                    chassert(token_begin >= pos && token_end >= token_begin);
                    chassert(token_end <= end);
                    size_t token_size = token_end - token_begin;

                    res_strings_chars.resize(res_strings_chars.size() + token_size);
                    memcpySmallAllowReadWriteOverflow15(&res_strings_chars[current_dst_strings_offset], token_begin, token_size);

                    current_dst_strings_offset += token_size;
                    res_strings_offsets.push_back(current_dst_strings_offset);
                    ++j;
                }

                current_dst_offset += j;
                res_offsets.push_back(current_dst_offset);
            }

So FunctionTokens<Generator> is a higher-order function over the generator protocol, and it serves:

  • URLHierarchy
  • URLPathHierarchy
  • splitByString, splitByChar, splitByWhitespace, splitByNonAlpha
  • alphaTokens
  • extractAll (which is a regexp generator, and which also opts into the regexp JIT threshold)

That is a genuine framework abstraction, not a copy-paste: the token plumbing, the offsets arithmetic, the small-copy helper, and the constant column fast path are all written once.

extractURLParameter: a different problem

Not every URL function fits the “find a delimiter” shape. extractURLParameter(url, 'utm_source') has to find a named parameter in the query string, which means a substring search plus a boundary check. It is implemented separately:

cpp 
// src/Functions/URL/extractURLParameter.cpp:9
struct ExtractURLParameterImpl
{
    static void vector(const ColumnString::Chars & data,
        const ColumnString::Offsets & offsets,
        std::string pattern,
        ColumnString::Chars & res_data, ColumnString::Offsets & res_offsets,
        size_t input_rows_count)
    {
        res_data.reserve(data.size() / 5);
        res_offsets.resize(input_rows_count);

        pattern += '=';
        const char * param_str = pattern.data();
        size_t param_len = pattern.size();

        ColumnString::Offset prev_offset = 0;
        ColumnString::Offset res_offset = 0;

        for (size_t i = 0; i < input_rows_count; ++i)
        {
            ColumnString::Offset cur_offset = offsets[i];

            const char * str = reinterpret_cast<const char *>(&data[prev_offset]);
            const char * end = reinterpret_cast<const char *>(&data[cur_offset]);

            /// Find query string or fragment identifier.
            /// Note that we support parameters in fragment identifier in the same way as in query string.

            const char * const query_string_begin = find_first_symbols<'?', '#'>(str, end);

            /// Will point to the beginning of "name=value" pair. Then it will be reassigned to the beginning of "value".
            const char * param_begin = nullptr;

            if (query_string_begin + 1 < end)
            {
                param_begin = query_string_begin + 1;

                while (true)
                {
                    param_begin = static_cast<const char *>(memmem(param_begin, end - param_begin, param_str, param_len));

                    if (!param_begin)
                        break;

                    char prev_char = param_begin[-1];
                    if (prev_char != '?' && prev_char != '#' && prev_char != '&')
                    {
                        /// Parameter name is different but has the same suffix.
                        param_begin += param_len;
                        continue;
                    }

                    param_begin += param_len;
                    break;
                }
            }

The trick is that the parameter name is turned into a search key by appending =: the code searches for "utm_source=" with memmem (which is itself SIMD-optimised in glibc), and then checks the preceding character to make sure it is a real parameter boundary (?, #, or &) and not the tail of a longer name like notutm_source=.

So the same find_first_symbols primitive handles the delimiter case and memmem handles the substring case, and the boundary check is the extra logic that a regex like [?&]utm_source=([^&#]*) would have given for free.

firstSignificantSubdomain and the TLD table

firstSignificantSubdomain needs to know what a top-level domain is, which means a table. ClickHouse generates one with gperf:

bash 
# src/Functions/URL/tldLookup.sh
#!/usr/bin/env bash

[ ! -f public_suffix_list.dat ] && wget -nv -O public_suffix_list.dat https://publicsuffix.org/list/public_suffix_list.dat

echo '%language=C++
%define lookup-function-name isValid
%define class-name TopLevelDomainLookupHash
%readonly-tables
%includes
%compare-strncmp
%{
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
#pragma GCC diagnostic ignored "-Wzero-as-null-pointer-constant"
#pragma GCC diagnostic ignored "-Wunused-macros"
// NOLINTBEGIN(modernize-macro-to-enum)
%}
# List generated using https://publicsuffix.org/list/public_suffix_list.dat
%%' > tldLookup.gperf
grep -v "//" public_suffix_list.dat | grep . | grep "\." | grep -ve "\..*\..*" >> tldLookup.gperf
echo "%%" >> tldLookup.gperf
echo '// NOLINTEND(modernize-macro-to-enum)' >> tldLookup.gperf

gperf turns the public suffix list into a perfect hash — a static array with no runtime search. The generated file is 110 742 lines, which is why it is checked in rather than built.

The lookup then drives the subdomain extraction:

cpp 
// src/Functions/URL/ExtractFirstSignificantSubdomain.h:30
    template <class Lookup>
    static void execute(const Lookup & lookup, const Pos data, const size_t size, Pos & res_data, size_t & res_size, Pos * out_domain_end = nullptr)
    {
        res_data = data;
        res_size = 0;

        Pos tmp = nullptr;
        size_t domain_length = 0;
        ExtractDomain<without_www, conform_rfc>::execute(data, size, tmp, domain_length);

        if (domain_length == 0)
            return;

The algorithm walks backwards through the last three dots, and asks the TLD lookup whether the candidate is a registered suffix:

cpp 
// src/Functions/URL/ExtractFirstSignificantSubdomain.h:84
        const auto * end_of_level_domain = find_first_symbols<'/'>(last_periods[0], end);
        if (!end_of_level_domain)
        {
            end_of_level_domain = end;
        }

        size_t host_len = static_cast<size_t>(end_of_level_domain - last_periods[1] - 1);
        std::string_view host{last_periods[1] + 1, host_len};
        if (lookup(host))
        {
            res_data += last_periods[2] + 1 - begin;
            res_size = last_periods[1] - last_periods[2] - 1;
        }
        else
        {
            res_data += last_periods[1] + 1 - begin;
            res_size = last_periods[0] - last_periods[1] - 1;
        }

For www.foo.example.co.uk, the last three periods bracket example.co.uk; if that is a registered suffix, the significant subdomain is foo, otherwise it is example.

The custom variant (firstSignificantSubdomainCustom) is different because a user-supplied TLD list can have records at any level, so the lookup returns a type rather than a boolean and the scan has to handle TLD_NONE, TLD_REGULAR, TLD_ANY and TLD_EXCLUDE:

cpp 
// src/Functions/URL/ExtractFirstSignificantSubdomain.h:150
            TLDType tld_type = lookup(host);
            switch (tld_type)
            {
                case TLDType::TLD_NONE:
                    break;
                case TLDType::TLD_REGULAR:
                    res_data += last_periods[0] + 1 - begin;
                    res_size = end - 1 - last_periods[0];
                    return;
                case TLDType::TLD_ANY:
                {
                    std::string_view regular_host{last_periods[0] + 1, static_cast<size_t>(end - 1 - last_periods[0])};
                    if (last_periods[1] && excluded_host != regular_host)
                    {
                        /// Return TLD_REGULAR + 1
                        res_data += last_periods[1] + 1 - begin;
                        res_size = end - 1 - last_periods[1];
                    }
                    else
                    {
                        /// Same as TLD_REGULAR
                        res_data += last_periods[0] + 1 - begin;
                        res_size = end - 1 - last_periods[0];
                    }
                    return;
                }
                case TLDType::TLD_EXCLUDE:
                    excluded_host = host;
                    break;
            }

TLD_ANY and TLD_EXCLUDE come from the public suffix list’s wildcard and exception rules (*.ck, !www.ck). This is the public suffix list model implemented as a state machine over a suffix hash.

Two host parsers, two behaviours

One last detail worth calling out, because it explains why there are two domain functions. The legacy getURLHost is much simpler — it does not understand userinfo or IPv6:

cpp 
// src/Functions/URL/domain.h:250
inline std::string_view getURLHost(const char * data, size_t size)
{
    Pos pos = data;
    Pos end = data + size;

    if (size >= 2 && *pos == '/' && *(pos + 1) == '/')
    {
        pos += 2;
    }
    else
    {
        Pos scheme_end = data + std::min(size, 16UL);
        for (++pos; pos < scheme_end; ++pos)
        {
            if (!isAlphaNumericASCII(*pos))
            {
                switch (*pos)
                {
                case '.':
                case '-':
                case '+':
                    break;
                case ' ': /// restricted symbols
                case '\t':
                case '<':
                case '>':
                case '%':
                case '{':
                case '}':
                case '|':
                case '\\':
                case '^':
                case '~':
                case '[':
                case ']':
                case ';':
                case '=':
                case '&':
                    return std::string_view{};
                default:
                    goto exloop;
                }
            }
        }
exloop: if ((scheme_end - pos) > 2 && *pos == ':' && *(pos + 1) == '/' && *(pos + 2) == '/')
            pos += 3;
        else
            pos = data;
    }

    Pos dot_pos = nullptr;
    const auto * start_of_host = pos;
    for (; pos < end; ++pos)
    {
        switch (*pos) /// NOLINT(bugprone-switch-missing-default-case)
        {
        case '.':
            dot_pos = pos;
            break;
        case ':': /// end symbols
        case '/':
        case '?':
        case '#':
            return checkAndReturnHost(pos, dot_pos, start_of_host);
        case '@': /// [email protected]
            start_of_host = pos + 1;
            break;

Note the difference in the @ handling: the legacy version takes the last @ (it keeps updating start_of_host), while the RFC version refuses a second @ outright. Every function in the family comes in a legacy and an RFC flavour, and the RFC flavour is a separate registered name:

cpp 
// src/Functions/URL/domain.cpp:11
struct NameDomainRFC { static constexpr auto name = "domainRFC"; };
using FunctionDomainRFC = FunctionStringToString<ExtractSubstringImpl<ExtractDomain<false, true>>, NameDomainRFC>;

So the difference is visible at the call site:

sql 
SELECT domain('http://user@[email protected]/');        -- 'evil.com'   (legacy)
SELECT domainRFC('http://user@[email protected]/');     -- ''           (RFC)

The same pairing exists for domainWithoutWWW / domainWithoutWWWRFC, topLevelDomain / topLevelDomainRFC, firstSignificantSubdomain / firstSignificantSubdomainRFC, cutToFirstSignificantSubdomain / cutToFirstSignificantSubdomainRFC, and firstSignificantSubdomainCustom / firstSignificantSubdomainCustomRFC.

The topLevelDomain pair shows the difference concretely:

cpp 
// src/Functions/URL/topLevelDomain.cpp:56
struct NameTopLevelDomain { static constexpr auto name = "topLevelDomain"; };
using FunctionTopLevelDomain = FunctionStringToString<ExtractSubstringImpl<ExtractTopLevelDomain<false>>, NameTopLevelDomain>;

struct NameTopLevelDomainRFC { static constexpr auto name = "topLevelDomainRFC"; };
using FunctionTopLevelDomainRFC = FunctionStringToString<ExtractSubstringImpl<ExtractTopLevelDomain<true>>, NameTopLevelDomainRFC>;

So topLevelDomain uses the legacy host parser and topLevelDomainRFC uses the RFC one, and the difference is visible in the documented example:

sql 
SELECT topLevelDomain('http://foo:foo%[email protected]'), topLevelDomainRFC('http://foo:foo%[email protected]');
-- ''    |  'com'

The legacy parser bails on %41 (a percent-encoded character in the userinfo), while the RFC parser handles the userinfo properly and reports the host.

What the design buys and what it costs

The hand-written approach buys:

  • Speed. A URL field extraction is a couple of SIMD scans of the input and a memcpy of the result. There is no regexp program, no capture bookkeeping, no per-match allocation.
  • Correctness on the cases that matter. Userinfo confusion, IPv6 literals, IPvFuture, second-@ rejection — these are the cases where “parse like a browser” and “match like a regex” diverge, and where the divergence has security consequences.
  • Zero allocation in the common path. The extractors return pointers into the source buffer; only the final result copy allocates.
  • Composability. The set()/get() generator protocol lets one scanner serve both “give me one field” and “give me a hierarchy of prefixes”, and the same protocol serves the splitBy* family and the regexp-based extractAll.

It costs:

  • Two implementations of the same idea. getURLHost and getURLHostRFC are separate 150-line functions with different behaviour, and the user-visible difference is a documented example. A regex-based implementation would have had one.
  • Manual edge-case handling. Every case in the switch is a decision somebody had to make about an ambiguous input. The comments are full of them: the second-@ rule, the dot-after-colon rule, the bracket-closed-then-@ rule. Each is a bug that was found and fixed.
  • No compositionality with the rest of the SQL. A regex-based implementation would let you write your own pattern against the URL; here you get exactly the twenty-seven functions ClickHouse decided to provide.
  • The goto exloop pattern. It works, but it is a loop-exit mechanism that has to be understood by anyone modifying the scheme detection.

The lesson

The interesting thing about this code is that it is boring in the best sense: it is a hand-written scanner with a small state machine, sitting on top of a SIMD primitive, wired into a columnar execution model through a generic protocol.

The design decision worth copying is the generator protocol. Rather than write twenty-seven near-identical functions, ClickHouse defined a four-method interface (init, set, get, plus checkArguments) and wrote the column-at-a-time driver once. URLHierarchy and URLPathHierarchy differ by three lines; splitByString and extractAll differ by an entire parsing strategy but share the driver.

The second decision worth copying is the willingness to write two implementations when the semantics genuinely differ, and to document the difference with a worked example, rather than pick one and lose users.

ClickhouseInternalsParsingPerformance