Opensource internals

ClickHouse Compiles a Date Format String into a Program

18 min read Jay Hubbert

formatDateTime parses its format string once into a vector of machine-code instructions and a pre-filled byte template, then runs that program over every row.

TL;DR: formatDateTime does not call strftime per row. It parses the format string once into a vector of Instruction objects (each holding a member-function pointer) plus a pre-rendered byte “template” of the literal text, memcpies that template into the result buffer, and then walks the instruction vector once per row, each instruction stamping its field over the pre-placed literal.

Every columnar database eventually needs to turn a timestamp into text. The naive implementation is the obvious one: call strftime in a loop.

sql 
SELECT formatDateTime(toDateTime('2018-01-01 00:00:00') + number, '%F %T')
FROM numbers(100000000);

strftime is a general-purpose formatter. It re-parses its format string on every call, walks a locale-aware table of conversion specifiers, calls localtime_r/gmtime_r to decompose the timestamp (which involves a division and a table lookup per field), and copies the result out byte by byte. It also has to be thread-safe, so it uses a locked or thread-local buffer.

ClickHouse’s formatDateTime takes the opposite approach: it treats the format string as a program to be compiled once and then interpreted (or rather, executed) many times. The interesting part is not that it caches the parse — plenty of libraries do that — but how it structures the compiled form so that the per-row work is as close to memcpy as it can get.

The file is src/Functions/formatDateTime.cpp, and it is 2342 lines mostly because the MySQL and Joda syntaxes each need a formatter for every field.

The two-step shape of the whole thing

The author of the file states the design up front, and it is worth reading because every subsequent line follows from it:

cpp 
// src/Functions/formatDateTime.cpp:113
  *
  * It is implemented in two steps.
  * At first step, it creates a template of zeros, literal characters, whitespaces, etc.
  *  and quickly fills resulting character array (string column) with this format.
  * At second step, it walks across the resulting character array and modifies/replaces specific characters,
  *  by calling some functions by pointers and shifting cursor by specified amount.
  *
  * Advantages:
  * - memcpy is mostly unrolled;
  * - low number of arithmetic ops due to pre-filled template;
  * - for somewhat reason, function by pointer call is faster than switch/case.
  *
  * Possible further optimization options:
  * - slightly interleave first and second step for better cache locality
  *   (but it has no sense when character array fits in L1d cache);
  * - avoid indirect function calls and inline functions with JIT compilation.
  *
  * Performance on Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz:
  *
  * WITH formatDateTime(now() + number, '%H:%i:%S') AS x SELECT count() FROM system.numbers WHERE NOT ignore(x);
  * - 97 million rows per second per core;
  *
  * WITH formatDateTime(toDateTime('2018-01-01 00:00:00') + number, '%F %T') AS x SELECT count() FROM system.numbers WHERE NOT ignore(x)
  * - 71 million rows per second per core;
  *
  * select count() from (select formatDateTime(t, '%m/%d/%Y %H:%i:%S') from (select toDateTime('2018-01-01 00:00:00')+number as t from numbers(100000000)));
  * - 53 million rows per second per core;
  *
  * select count() from (select formatDateTime(t, 'Hello %Y World') from (select toDateTime('2018-01-01 00:00:00')+number as t from numbers(100000000)));
  * - 138 million rows per second per core;
  *
  * PS. We can make this function to return FixedString. Currently it returns String.
  */

Note the last benchmark: 'Hello %Y World' runs at 138 M rows/s, more than twice the rate of '%m/%d/%Y %H:%i:%S'. The only difference is the number of formatter invocations per row. That ratio is the cost model of the whole design: the fixed cost of “one instruction per format field” dominates.

Note also the last line: “avoid indirect function calls and inline functions with JIT compilation”. The author identifies the indirect call as the remaining overhead — and ClickHouse later built a general expression JIT (see the companion piece on the LLVM expression compiler). formatDateTime itself was not ported to it; the instruction-pointer design is what remains.

Step one: the template

The trick that makes the whole thing fast is that the literal parts of the format string — everything that is not a % conversion — do not need to be copied per row at all. They can be baked into a single byte blob once, and that blob can be memcpy’d across the entire result buffer in one go.

Consider formatDateTime(t, '%Y-%m-%d %H:%M:%S'). The literal text is -, -, , :, :. The output for every row has the same shape:

text 
2024-03-17 11:22:33
^^^^ ^ ^^ ^^ ^^ ^^ ^^

If the only formatters are fixed-width, every row’s output is the same number of bytes with the same bytes in the same places. So ClickHouse builds a template in which the literal characters are already in place, and the formatter positions are filled with placeholder bytes:

text 
template:  "2024-03-17 11:22:33"
           ^ template is built by the parser; the digits are placeholders
             that the instructions will overwrite

The parser builds this template and the instruction vector at the same time. Here is the MySQL parse loop, which is the heart of the compilation:

cpp 
// src/Functions/formatDateTime.cpp:1295
        Pos pos = format.data();
        const Pos end = format.data() + format.size();

        while (true)
        {
            const Pos percent_pos = find_first_symbols<'%'>(pos, end);

            if (percent_pos < end)
            {
                if (pos < percent_pos)
                {
                    /// Handle characters before next %
                    add_extra_shift_or_literal_instruction(std::string_view(pos, percent_pos - pos));
                    out_template += String(pos, percent_pos - pos);
                }

                pos = percent_pos + 1;
                if (pos >= end)
                    throwLastCharacterIsPercentException();

                switch (*pos)
                {
                    // Abbreviated weekday [Mon-Sun]
                    case 'a':
                    {
                        Instruction<T> instruction;
                        instruction.setMysqlFunc(&Instruction<T>::mysqlDayOfWeekTextShort);
                        instructions.push_back(std::move(instruction));
                        out_template += "Mon";
                        break;
                    }

                    // Abbreviated month [Jan-Dec]
                    case 'b':
                    {
                        Instruction<T> instruction;
                        instruction.setMysqlFunc(&Instruction<T>::mysqlMonthOfYearTextShort);
                        instructions.push_back(std::move(instruction));
                        out_template += "Jan";
                        break;
                    }

Read the two halves of each case carefully:

  • instructions.push_back(...) — a program instruction: a pointer to the formatter that will compute this field.
  • out_template += "Mon" — the placeholder bytes for this field. For a weekday it is three bytes, "Mon", because the longest possible weekday abbreviation is three characters. For a month, "Jan". The parser is choosing the worst-case width of each field so that the template has a fixed size.

So the template for '%a %b %d' is "Mon Jan 00" — 10 bytes, with the separators already correct and the field positions padded to their maximum width. Every row’s output is exactly 10 bytes and the separators never move.

Step two: the instructions

The instruction is a small object holding a member function pointer. Note the comment explaining why it is a member pointer and not a static one:

cpp 
// src/Functions/formatDateTime.cpp:165
    template <typename Time>
    class Instruction
    {
    public:
        /// Joda format generally requires capturing extra variables (i.e. holding state) which is more convenient with
        /// std::function and std::bind. Unfortunately, std::function causes a performance degradation by 0.45x compared to raw function
        /// pointers. For MySQL format, we generally prefer raw function pointers. Because of the special case that not all formatters are
        /// fixed-width formatters (see mysqlLiteral instruction), we still need to be able to store state. For that reason, we use member
        /// function pointers instead of static function pointers.
        using FuncMysql = size_t (Instruction<Time>::*)(char *, Time, UInt64, UInt32, const DateLUTImpl &);
        FuncMysql func_mysql = nullptr;

        using FuncJoda = std::function<size_t(char *, Time, UInt64, UInt32, const DateLUTImpl &)>;
        FuncJoda func_joda = nullptr;

        /// extra_shift is only used in MySQL format syntax. It is always 0 in Joda format syntax.
        size_t extra_shift = 0;

        // Holds literal characters that will be copied into the output. Used by the mysqlLiteral instruction.
        String literal;

        Instruction() = default;

        void setMysqlFunc(FuncMysql && func) { func_mysql = std::move(func); }
        void setJodaFunc(FuncJoda && func) { func_joda = std::move(func); }
        void setLiteral(std::string_view literal_) { literal = literal_; }

        void perform(char *& dest, Time source, UInt64 fractional_second, UInt32 scale, const DateLUTImpl & timezone)
        {
            size_t shift = func_mysql
                           ? std::invoke(func_mysql, this, dest, source, fractional_second, scale, timezone)
                           : std::invoke(func_joda, dest, source, fractional_second, scale, timezone);
            dest += shift + extra_shift;
        }

Several things worth unpacking:

Member function pointer, not static. A member function pointer carries the this of the Instruction itself. Why would the instruction need state? Because of the mysqlLiteral instruction — the one case where the output is variable width. If the format string contains something like %W (the full weekday name, “Wednesday” or “Monday”) whose width depends on the value, then the literal text between two formatters cannot be pre-placed at a fixed offset: the position of everything after it depends on the width of the first. In that mode the parser emits a mysqlLiteral instruction that carries the literal text in the instruction and copies it at run time:

cpp 
// src/Functions/formatDateTime.cpp:286
    public:
        size_t mysqlNoop(char *, Time, UInt64, UInt32, const DateLUTImpl &)
        {
            return 0;
        }

        size_t mysqlLiteral(char * dest, Time, UInt64, UInt32, const DateLUTImpl &)
        {
            memcpy(dest, literal.data(), literal.size());
            return literal.size();
        }

That is exactly why the pointer must be a member pointer: mysqlLiteral reads this->literal. A static function pointer cannot carry that state, and std::function (which could) costs 0.45x — nearly half the throughput — in the type erasure. The comment quantifies the tradeoff precisely, and the design resolves it by splitting into two paths: MySQL uses raw member pointers (with state only where it needs it), Joda uses std::function because Joda’s formatters genuinely need to capture.

extra_shift. The instruction returns the number of bytes it wrote. perform then advances dest by shift + extra_shift. The extra_shift is the number of bytes of literal text that the template already placed and that the instruction must therefore skip over. In fixed-width mode the parser adds the literal length to the preceding instruction’s extra_shift:

cpp 
// src/Functions/formatDateTime.cpp:1254
        auto add_extra_shift = [&](size_t amount)
        {
            if (instructions.empty())
            {
                Instruction<T> instruction;
                instruction.setMysqlFunc(&Instruction<T>::mysqlNoop);
                instructions.push_back(std::move(instruction));
            }
            instructions.back().extra_shift += amount;
        };

        auto add_literal_instruction = [&](std::string_view literal)
        {
            Instruction<T> instruction;
            instruction.setMysqlFunc(&Instruction<T>::mysqlLiteral);
            instruction.setLiteral(literal);
            instructions.push_back(std::move(instruction));
        };

        auto add_extra_shift_or_literal_instruction = [&](std::string_view literal)
        {
            if (mysql_with_only_fixed_length_formatters)
                add_extra_shift(literal.size());
            else
                add_literal_instruction(literal);
        };

add_extra_shift_or_literal_instruction is the fork in the road: in fixed-width mode the literal goes into the template (and the cursor is skipped via extra_shift); in variable-width mode the literal becomes a copy-at-runtime instruction. Note the mysqlNoop guard: if the format string starts with a literal, there is no preceding instruction to hang the shift on, so a no-op instruction is inserted to carry it.

Deciding which mode

The mode is decided by a scan of the format string, before any of the real work happens:

cpp 
// src/Functions/formatDateTime.cpp:871
    static bool containsOnlyFixedWidthMySQLFormatters(std::string_view format, bool mysql_M_is_month_name, bool mysql_format_ckl_without_leading_zeros, bool mysql_e_with_space_padding)
    {
        static constexpr std::array variable_width_formatter = {'W'};
        static constexpr std::array variable_width_formatter_M_is_month_name = {'M'};
        static constexpr std::array variable_width_formatter_leading_zeros = {'c', 'l', 'k'};
        static constexpr std::array variable_width_formatter_e_with_space_padding = {'e'};

%W (the full weekday name) is unconditionally variable width: “Wednesday” is nine bytes and “Monday” is six. %M is variable width only if formatdatetime_parsedatetime_m_is_month_name is set — because “September” is nine characters but “00” is two. %c, %l, %k are variable width only if the “no leading zeros” setting is on, since “1” is shorter than “01”. %e is variable width only if space padding is off, since " 1" is two bytes and “1” is one.

Each of those conditions is a setting. That is why the check takes four boolean parameters rather than reading the settings itself: the settings are read once in the constructor and baked into the decision.

Here is the whole decision, and the two execution modes it selects:

cpp 
// src/Functions/formatDateTime.cpp:1140
        bool mysql_with_only_fixed_length_formatters = (format_syntax == FormatSyntax::MySQL)
            ? containsOnlyFixedWidthMySQLFormatters(format, mysql_M_is_month_name, mysql_format_ckl_without_leading_zeros, mysql_e_with_space_padding)
            : false;

        using T = typename InstructionValueTypeMap<DataType>::InstructionValueType;
        VectorWithMemoryTracking<Instruction<T>> instructions;
        String out_template;
        size_t out_template_size = parseFormat(format, instructions, scale, mysql_with_only_fixed_length_formatters, out_template);

and the two modes, described in the source’s own words:

cpp 
// src/Functions/formatDateTime.cpp:1125
        /// For MySQL, we support two modes of execution:
        ///
        /// - All formatters in the format string are fixed-width. As a result, all output rows will have the same width and structure. We
        ///   take advantage of this and
        ///     1. create a "template" with placeholders from the format string,
        ///     2. allocate a result column large enough to store the template on each row,
        ///     3. copy the template into each result row,
        ///     4. run instructions which replace the formatter placeholders. All other parts of the template (e.g. whitespaces) are already
        ///        as desired and instructions skip over them (see 'extra_shift' in the formatters).
        ///
        /// - The format string contains at least one variable-width formatter. Output rows will potentially be of different size.
        ///   Steps 1. and 2. are performed as above (the result column is allocated based on a worst-case size estimation). The result
        ///   column rows are NOT populated with the template and left uninitialized. We run the normal instructions for formatters AND
        ///   instructions that copy literal characters before/between/after formatters. As a result, each byte of each result row is
        ///   written which is obviously slow.

“Each byte of each result row is written which is obviously slow” — the author is not happy about the variable-width path, but it exists because some formats genuinely need it.

Filling the buffer: the exponential memcpy

The template fill is a neat piece of code. The result buffer is input_rows_count * out_template_size bytes. You want to fill it with out_template_size copies of the template. Doing that with a loop of memcpy(template) calls would be input_rows_count memcpys of a short string. Instead the code copies the template once and then keeps doubling the amount copied:

cpp 
// src/Functions/formatDateTime.cpp:1162
        auto col_res = ColumnString::create();
        auto & res_data = col_res->getChars();
        auto & res_offsets = col_res->getOffsets();
        res_data.resize(input_rows_count * out_template_size);
        res_offsets.resize(input_rows_count);

        if constexpr (format_syntax == FormatSyntax::MySQL)
        {
            if (mysql_with_only_fixed_length_formatters)
            {
                /// Fill result with template.
                {
                    const UInt8 * const begin = res_data.data();
                    const UInt8 * const end = res_data.data() + res_data.size();
                    UInt8 * pos = res_data.data();

                    if (pos < end)
                    {
                        memcpy(pos, out_template.data(), out_template_size);
                        pos += out_template_size;
                    }

                    /// Copy exponentially growing ranges.
                    while (pos < end)
                    {
                        size_t bytes_to_copy = std::min(pos - begin, end - pos);
                        memcpy(pos, begin, bytes_to_copy);
                        pos += bytes_to_copy;
                    }
                }
            }
        }

The first memcpy puts the template at offset 0. Then the loop copies everything written so far (pos - begin bytes) onto the end, doubling the filled region each time: 1 copy, then 2, then 4, then 8. After log2(input_rows_count) iterations the whole buffer is full. For a million rows that is 20 memcpys of ever-increasing size instead of a million memcpys of 10 bytes. Total bytes moved is 2 * N instead of N (each byte is written about twice on average), but the number of calls is log N, and memcpy of a large block is much more efficient per byte than memcpy of a 10-byte block.

This is a standard trick — it is essentially how you fill a buffer with a repeated pattern in logarithmic time — but the placement of it here, as a “fill with the template” step, is what makes the whole formatDateTime design coherent: the buffer is a giant memset-alike, and the instructions are merely patching it.

The per-row loop

Once the buffer is full of templates, the actual work is short. Each row runs the instruction vector:

cpp 
// src/Functions/formatDateTime.cpp:1204
        for (size_t i = 0; i < input_rows_count; ++i)
        {
            if (!const_time_zone_column && arguments.size() > 2)
            {
                std::string_view time_zone_name = arguments[2].column->getDataAt(i);
                if (time_zone_name.empty())
                    throw Exception(ErrorCodes::ILLEGAL_TYPE_OF_ARGUMENT, "Provided time zone must be non-empty");
                time_zone = &time_zone_cache.getOrSet(time_zone_name);
            }
            if constexpr (std::is_same_v<DataType, DataTypeDateTime64>)
            {
                auto c = DecimalUtils::split(vec[i], scale);

                // -1.123 splits to -1 /  0.123
                if (vec[i].value < 0 && c.fractional)
                {
                    using F = typename DataType::FieldType;
                    c.fractional = DecimalUtils::scaleMultiplier<F>(scale) + (c.whole ? F(-1) : F(1)) * c.fractional;
                    --c.whole;
                }

                for (auto & instruction : instructions)
                    instruction.perform(pos, static_cast<Int64>(c.whole), c.fractional, scale, *time_zone);
            }
            else
            {
                for (auto & instruction : instructions)
                    instruction.perform(pos, static_cast<T>(vec[i]), 0, 0, *time_zone);
            }
            res_offsets[i] = pos - begin;
        }

The inner loop is the whole cost of the function: one indirect call per instruction, each stamping a few bytes. pos is a raw char * into the result buffer that marches forward across the whole result, and res_offsets[i] = pos - begin records the end of row i — the ColumnString offsets are produced as a side effect of the formatting, not computed afterwards.

Note the negative-DateTime64 fixup: DecimalUtils::split divides the decimal into whole and fractional parts by truncation toward zero, so -1.123 splits into whole -1 and fractional +0.123. The formatting wants the floor convention (-1 and -0.123), so the code detects the negative case and adjusts: the fractional part gets 10^scale - 0.123 and the whole part is decremented.

The formatters themselves

Each formatter is a member function of Instruction that writes into the destination buffer and returns the number of bytes written. The simplest ones are two-digit writes, and they use a lookup table rather than division:

cpp 
// src/Functions/formatDateTime.cpp:200
    private:
        template <typename T>
        static size_t writeNumber2(char * p, T v)
        {
            static_assert(std::is_integral_v<T>);
            chassert(v >= 0 && v <= 99);

            memcpy(p, &digits100[v * 2], 2);  /// NOLINT(clang-analyzer-security.ArrayBound)
            return 2;
        }

digits100 is a 201-byte table of all two-digit decimal numbers concatenated:

cpp 
// src/IO/WriteHelpers.h:966
static const char digits100[201] =
    "00010203040506070809"
    "10111213141516171819"
    "20212223242526272829"
    "30313233343536373839"
    "40414243444546474849"

so writeNumber2(p, 42) is a two-byte memcpy from &digits100[84]. No division, no branching, no digit extraction. writeNumber3 and writeNumber4 compose it:

cpp 
// src/Functions/formatDateTime.cpp:211
        template <typename T>
        static size_t writeNumber3(char * p, T v)
        {
            writeNumber2(p, v / 10);
            p[2] = '0' + v % 10;
            return 3;
        }

        template <typename T>
        static size_t writeNumber4(char * p, T v)
        {
            writeNumber2(p, v / 100);
            writeNumber2(p + 2, v % 100);
            return 4;
        }

The date-decomposing formatters are thin wrappers over the shared ToYearImpl / ToMonthImpl / ToDayOfMonthImpl helpers, which take the timestamp and the DateLUTImpl for the time zone and return the field:

cpp 
// src/Functions/formatDateTime.cpp:298
        size_t mysqlCentury(char * dest, Time source, UInt64, UInt32, const DateLUTImpl & timezone)
        {
            auto year = ToYearImpl::execute(source, timezone);
            auto century = year / 100;
            return writeNumber2(dest, century);
        }

        size_t mysqlDayOfMonth(char * dest, Time source, UInt64, UInt32, const DateLUTImpl & timezone)
        {
            return writeNumber2(dest, ToDayOfMonthImpl::execute(source, timezone));
        }

Note that ToYearImpl::execute and friends are not strftime’s decomposition. They are ClickHouse’s own, and they work off the DateLUTImpl — the time-zone table — which caches the civil-date decomposition for a whole range of days. This is where the second big win comes from: the expensive part of strftime (decomposing a timestamp into year/month/day in the right zone) is done once per day boundary, not once per row, by the LUT, and the formatter only does an array lookup.

Time zones

One more piece of machinery is worth mentioning, because it is a straightforward example of a cache that exists purely because the underlying operation is expensive and mutex-protected:

cpp 
// src/Functions/formatDateTime.cpp:923
    class TimeZoneCache
    {
    public:
        const DateLUTImpl & getOrSet(std::string_view time_zone_name)
        {
            for (const Entry & cached_time_zone : cached_time_zones)
            {
                if (cached_time_zone.time_zone == nullptr)
                    break;
                if (cached_time_zone.name == time_zone_name)
                    return *cached_time_zone.time_zone;
            }

            /// insert new entry or replace existing entry
            const DateLUTImpl & time_zone = DateLUT::instance(time_zone_name);
            cached_time_zones[next] = {String(time_zone_name), &time_zone};
            next = (next + 1) % CACHE_SIZE;
            return time_zone;
        }

    private:
        constexpr static size_t CACHE_SIZE = 4;

        struct Entry
        {
            String name;
            const DateLUTImpl * time_zone = nullptr;
        };
        using CacheTable = std::array<Entry, CACHE_SIZE>;
        CacheTable cached_time_zones;
        size_t next = 0; /// position to insert the next entry at
    };

Four entries, round-robin, linear scan. The comment above the call site explains why it exists at all: “Non-const time zone arguments are resolved per row. This is done under an expensive mutex in DateLUT. Lots of queries use only a handful of different time zones. As an optimization, cache the resolved time zones.” A 4-entry cache is deliberately tiny — it lives on the stack, it is scanned linearly, and it costs nothing to miss.

What the design costs

The design is not free, and the trade-offs are worth stating plainly.

The template is only valid if every formatter is fixed-width. One %W and the entire fast path is gone; every byte of every output row gets written individually. This is why containsOnlyFixedWidthMySQLFormatters exists and why the settings that change a formatter’s width are consulted at compile time rather than at run time.

The buffer is allocated at worst-case size. `res_data.resize(input_rows_count

  • out_template_size)— in variable-width mode the rows are shorter thanout_template_size and the buffer is trimmed at the end (res_data.resize(pos
  • begin)`), but the peak allocation is the worst case. For a format with a 9-byte month name and 65 409 rows, that is fine; for a pathological format it is a real allocation.

The compile step allocates a vector of instructions per call. The instructions are built inside executeImpl, not cached across calls. The format string is required to be a constant (getArgumentsThatAreAlwaysConstant returns {1}, the format argument), so the parse could be cached across blocks, but it is not: each block re-parses the format string and rebuilds the instruction vector. For a 65 409-row block that is negligible; for a query over a million tiny blocks it would not be. This is a real remaining optimization.

Indirect calls are still indirect. The author names this explicitly as the next thing to fix (“avoid indirect function calls and inline functions with JIT compilation”). One indirect call per format field per row is the floor of this design. The 'Hello %Y World' benchmark at 138 M rows/s illustrates the payoff of fewer instructions, not of faster ones.

The lesson

The interesting idea here is not “cache the format string”. Lots of code does that. It is the observation that a format string describes a fixed byte layout when all its fields are fixed-width, and that this layout can be materialized once into a template and copied across the output buffer in logarithmic time — leaving the per-row work as nothing but a few dozen bytes of patching.

That converts a text-formatting problem (which is inherently a string-building problem, with all the allocation and copying that implies) into a fixed-size-output problem, which is what a columnar engine wants: the result is a ColumnString whose rows are all the same width, produced by a bulk memcpy plus a handful of in-place edits.

The cost is a fork in the design (fixed-width vs variable-width), a worst-case allocation, and a per-block re-parse. The benefit is a 20x difference between “a format string with three fields” and one with nine.

ClickhouseInternalsPerformanceDates