ClickHouse Pushes ORDER BY into the Storage Read

TL;DR: A MergeTree table’s ORDER BY defines its sorting key, and the rows inside every part are physically stored in that order. So SELECT ... ORDER BY k LIMIT 10 does not need to sort the table: it needs the first 10 rows in key order. ClickHouse matches the query’s ORDER BY expression against the sorting key — using the monotonicity of the functions in between — and hands the storage an InputOrderInfo saying “read the first N key columns in this direction, stop after this many rows”. The sort step then becomes a partial sort of an already-sorted stream.

Consider the archetypal analytical query:

sql
SELECT * FROM events ORDER BY event_time LIMIT 10;

The obvious plan reads every row of events, sorts them all by event_time, and takes the first ten. On a table with a billion rows that is a billion rows of I/O to produce ten.

But events is a MergeTree table, and MergeTree tables have a sorting key — the table’s own ORDER BY clause. The rows inside each part are physically stored in that order. If the sorting key is (event_time), then:

reading part 1 from its beginning gives you the earliest rows of part 1;
reading part 2 from its beginning gives you the earliest rows of part 2;
a k-way merge of those gives you the global earliest rows;
and if you only need 10 rows, you can stop as soon as you have 10.

That is the optimisation ClickHouse calls read in order, and it is on by default:

cpp
// src/Core/Settings.cpp:5119
    DECLARE(Bool, optimize_read_in_order, true, R"(
Enables [ORDER BY](/reference/statements/select/order-by#optimization-of-data-reading) optimization in [SELECT](/reference/statements/select/index) queries for reading data from [MergeTree](/reference/engines/table-engines/mergetree-family/mergetree) tables.

Possible values:

- 0 — `ORDER BY` optimization is disabled.
- 1 — `ORDER BY` optimization is enabled.

**See Also**

- [ORDER BY Clause](/reference/statements/select/order-by#optimization-of-data-reading)
)", 0) \

The hard part is not the reading. It is deciding whether the query’s ORDER BY can be served by the sorting key, which is a question about expressions, not about columns.

The contract: `InputOrderInfo`

The agreement between the plan optimiser and the storage is a small struct:

cpp
// src/Storages/SelectQueryInfo.h:84
struct InputOrderInfo
{
    /// Sort description for merging of already sorted streams.
    /// Always a prefix of ORDER BY or GROUP BY description specified in query.
    SortDescription sort_description_for_merging;

    /** Size of prefix of sorting key that is already
     * sorted before execution of sorting or aggreagation.
     *
     * Contains both columns that scpecified in
     * ORDER BY or GROUP BY clause of query
     * and columns that turned out to be already sorted.
     *
     * E.g. if we have sorting key ORDER BY (a, b, c, d)
     * and query with `WHERE a = 'x' AND b = 'y' ORDER BY c, d` clauses.
     * sort_description_for_merging will be equal to (c, d) and
     * used_prefix_of_sorting_key_size will be equal to 4.
     */
    const size_t used_prefix_of_sorting_key_size;

    const int direction;
    const UInt64 limit;

    InputOrderInfo(
        const SortDescription & sort_description_for_merging_,
        size_t used_prefix_of_sorting_key_size_,
        int direction_, UInt64 limit_)
        : sort_description_for_merging(sort_description_for_merging_)
        , used_prefix_of_sorting_key_size(used_prefix_of_sorting_key_size_)
        , direction(direction_), limit(limit_)
    {
    }

    bool operator==(const InputOrderInfo &) const = default;
};

Four things:

sort_description_for_merging — the sort columns the consumer of the stream needs.
used_prefix_of_sorting_key_size — how many columns of the table’s sorting key are physically ordered in the stream.
direction — 1 for ascending, -1 for descending, 0 for “either”.
limit — how many rows the consumer will take, so the read can stop early.

The used_prefix_of_sorting_key_size is the crucial one, and the doc comment gives the example that makes it click: with sorting key (a, b, c, d) and a query WHERE a = 'x' AND b = 'y' ORDER BY c, d, the merging description is (c, d) — because a and b are constant — but the prefix size is 4, because the stream is physically ordered by all four columns.

Matching the ORDER BY against the sorting key

The matching lives in optimizeReadInOrder.cpp, in the function buildInputOrderFromSortDescription. It walks the query’s sort description and the table’s sorting key in parallel, and for each pair decides whether the sort expression is equivalent to the key expression, possibly up to a monotonic transformation.

The first thing it does is build a tree match between the sorting key’s expression DAG and the DAG of the expressions that produced the sort columns:

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:599
    if (dag)
    {
        matches = matchTrees(sorting_key_dag.getOutputs(), *dag);

        for (const auto & [node, match] : matches)
        {
            //std::cerr << "------- matching " << static_cast<const void *>(node) << " " << node->result_name
            //    << " to " << static_cast<const void *>(match.node) << " " << (match.node ? match.node->result_name : "") << std::endl;
            if (!match.monotonicity || match.monotonicity->strict)
            {
                if (match.node && fixed_columns.contains(node))
                    fixed_key_columns.insert(match.node);
            }
        }

        enrichFixedColumns(sorting_key_dag, fixed_key_columns);
    }

matchTrees is a structural matcher between two ActionsDAGs: it walks the outer DAG and, for each node, looks for a node in the inner DAG that computes the same thing. The interesting part is the monotonicity field of a match — it records how the outer expression relates to the inner one:

cpp
// src/Functions/IFunction.h:410
    struct Monotonicity
    {
        bool is_monotonic = false;   /// Is the function monotonous (non-decreasing or non-increasing).
        bool is_positive = true;     /// true if the function is non-decreasing, false if non-increasing. If is_monotonic = false, then it does not matter.
        bool is_always_monotonic = false; /// Is true if function is monotonic on the whole input range I
        bool is_strict = false;      /// true if the function is strictly decreasing or increasing.
        /// Is true if the function is monotonic over the whole subset of the input range on which it
        /// is defined, while the rest of the range either throws an exception or wraps around (so it
        /// is weaker than is_always_monotonic, which requires the whole range to be mapped).
        /// It is enough to push a comparison constant through a sorting or partition key expression:
        /// a constant outside of that subset is rejected by the guards in `applyFunctionChainToColumn`.
        /// It is not enough to map a key range through the function, which needs `is_monotonic`.
        bool is_always_monotonic_where_defined = false;
    };

This is what makes ORDER BY negate(x) work on an ascending key: negate is monotonically decreasing, so the ascending key can be read backwards to produce a descending stream. The matching loop applies the monotonicity’s direction to the read direction:

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:739
                current_direction = sort_column_description.direction * reverse_indicator;
                if (match.monotonicity)
                {
                    current_direction *= match.monotonicity->direction;
                    strict_monotonic = match.monotonicity->strict;
                    match_infos.push_back({.source = sort_node, .monotonic = &match});
                }
                else
                    match_infos.push_back({.source = sort_node});

current_direction is the direction the key column is physically read in, after applying both the requested sort direction and the monotonicity of the matching expression. reverse_indicator accounts for a key column declared DESC in the table’s ORDER BY.

Once the directions disagree, the match stops:

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:810
        /// read_direction == 0 means we can choose any global direction.
        /// current_direction == 0 means current key if fixed and any direction is possible for it.
        if (current_direction && read_direction && current_direction != read_direction)
            break;

        if (read_direction == 0)
            read_direction = current_direction;

        if (current_direction)
            order_key_prefix_descr.push_back(sort_column_description);

        if (current_direction && !strict_monotonic)
            break;

The last line is the reason the loop stops at the first non-strictly monotonic match: if the function is monotonic but not strictly so (e.g. it maps several input values to the same output), then the stream is sorted by the output, but the output is not a bijection of the input, so the physical order of the next key column is not preserved. The stream is still sorted by the prefix, but not by anything beyond it.

Fixed columns: `WHERE x = 42`

A column that the WHERE clause has pinned to a constant is a special case: it is in the sorting key but carries no information. The matcher skips it without giving up the direction:

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:716
                /// If the ORDER BY column is fixed (constant due to WHERE clause),
                /// don't let it determine read direction - skip to next columns.
                /// Example: ORDER BY tenant, event_time DESC with WHERE tenant='42'
                /// tenant is constant, so read direction should come from event_time DESC.
                if (fixed_columns.contains(sort_node))
                {
                    /// Virtual row for fixed column from order by is not supported now.
                    can_optimize_virtual_row = false;

                    /// Still add the fixed column to the sort description (required for sort matching)
                    /// but don't set current_direction so it won't influence read_direction.
                    match_infos.push_back({.source = sort_node, .fixed_column = sort_node});
                    order_key_prefix_descr.push_back(sort_column_description);
                    ++next_description_column;
                    ++next_sort_key;
                    continue;
                }

NULLs and NaNs: the physical end

The subtlest constraint is where NULLs and NaNs end up. A MergeTree part stores the NULLs of a Nullable key column and the NaNs of a Float key column at one physical end of the part — the forward end for an ordinary key column, the other end for one declared DESC. Reading the part cannot move them. So whether the requested order is satisfiable depends on the direction the key is read in:

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:787
        /** The NULLs and NaNs of this key column come out at the end of the stream when the part is read
          * in the direction that has them last, and at its beginning otherwise; `nulls_direction` asks for
          * them last exactly when it agrees with `direction` (`ASC NULLS LAST`, `DESC NULLS FIRST`). A
          * mismatch cannot be repaired downstream - the sort is elided, which is the point of this
          * optimization - so the match ends here.
          *
          * `current_direction` is the direction the key is read in, with the monotonicity of the match
          * already applied, and `reverse_indicator` says which physical end holds the NULLs and NaNs.
          */
        if (column_is_nullable && current_direction != 0)
        {
            const bool produces_nulls_last = current_direction * reverse_indicator == 1;
            const bool requests_nulls_last = sort_column_description.direction == sort_column_description.nulls_direction;
            if (produces_nulls_last != requests_nulls_last)
            {
                /// `next_description_column` is not read after the loop, so it is left alone.
                next_sort_key = prev_sort_key;
                match_infos.resize(prev_match_infos_size);
                order_key_prefix_descr.resize(prev_order_key_prefix_size);
                break;
            }
        }

ORDER BY negate(x) NULLS FIRST over an ascending x is the case the comment describes: the backward read surfaces the NaNs first, but NULLS FIRST wants them first — that one matches. The opposite combination does not, and the match is rolled back to the previous key.

Note the rollback: the code explicitly restores next_sort_key, match_infos and order_key_prefix_descr to their previous values, because next_sort_key becomes used_prefix_of_sorting_key_size — the width the storage reads with and applies a hard LIMIT to:

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:645
        /// The NULL/NaN placement check below can only run after this iteration consumed the key, so
        /// remember how much was consumed and undo it when the check rejects the key. Otherwise the
        /// rejected key would still widen `next_sort_key`, which becomes
        /// `InputOrderInfo::used_prefix_of_sorting_key_size` - the width the storage actually reads with
        /// and applies a hard `LIMIT` to - and the read would stop on a row the advertised prefix does
        /// not order.
        const size_t prev_sort_key = next_sort_key;
        const size_t prev_match_infos_size = match_infos.size();
        const size_t prev_order_key_prefix_size = order_key_prefix_descr.size();

That is a bug class that the comment is guarding against, written down in the code that could cause it.

The result

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:844
    auto order_info = std::make_shared<InputOrderInfo>(order_key_prefix_descr, next_sort_key, read_direction, limit);

and the plan asks the storage whether it can honour it:

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:1408
            bool can_read = reading->requestReadingInOrder(
                order_info.input_order->used_prefix_of_sorting_key_size,
                order_info.input_order->direction,
                order_info.input_order->limit,
                query_limit);

            if (!can_read)
                return nullptr;

The storage has the last word:

cpp
// src/Processors/QueryPlan/ReadFromMergeTree.cpp:4116
bool ReadFromMergeTree::requestReadingInOrder(size_t prefix_size, int direction, size_t read_limit, size_t query_limit)
{
    /// if direction is not set, use current one
    if (!direction)
        direction = getSortDirection();

    if (direction != 1 && !canReadInReverseOrder())
        return false;

    /// The prefix indexes this snapshot's sorting key, and a clone of its expression list is resized
    /// to `prefix_size`, which appends null `ASTPtr` children when the prefix is longer than the key.
    if (prefix_size > storage_snapshot->metadata->getSortingKey().column_names.size())
        return false;

The read

Once the storage agrees, the read itself changes shape. The parts are read in sorting-key order, and inside each part the rows are read in key order too — ReadType::InOrder or ReadType::InReverseOrder:

cpp
// src/Processors/QueryPlan/ReadFromMergeTree.cpp:1356
        sort_description.reserve(input_order_info->used_prefix_of_sorting_key_size);
        for (size_t i = 0; i < input_order_info->used_prefix_of_sorting_key_size; ++i)
        {
            if (!reverse_flags.empty() && reverse_flags[i])
                sort_description.emplace_back(sorting_columns[i], input_order_info->direction * -1);
            else
                sort_description.emplace_back(sorting_columns[i], input_order_info->direction);
        }

        ReadType in_order_read_type = input_order_info->direction > 0 ? ReadType::InOrder : ReadType::InReverseOrder;

The sorting key’s expression is applied to the read stream, because the sorting key may be an expression (ORDER BY (a + b)), not a plain column:

cpp
// src/Processors/QueryPlan/ReadFromMergeTree.cpp:1388
            pipe.addSimpleTransform([sorting_expr](const SharedHeader & header)
            {
                return std::make_shared<ExpressionTransform>(header, sorting_expr);
            });

and if there is more than one stream, the streams are merged with a MergingSortedTransform — a k-way merge of already-sorted streams, not a sort:

cpp
// src/Processors/QueryPlan/ReadFromMergeTree.cpp:1393
            if (pipe.numOutputPorts() != 1)
            {
                auto transform = std::make_shared<MergingSortedTransform>(
                    pipe.getSharedHeader(),
                    pipe.numOutputPorts(),
                    sort_description,
                    block_size.max_block_size_rows,
                    /*max_block_size_bytes=*/ 0,

The sort step becomes a partial sort

The other half of the optimisation is on the consumer side. The SortingStep in the plan was a full sort; now that the input is sorted by a prefix, it becomes a FinishSorting:

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:1975
    else if (auto order_info = buildInputOrderInfo(*sorting, apply_virtual_row, virtual_row_reader, *node.children.front(), optimization_settings))
    {
        /// Use buffering only if have filter or don't have limit.
        bool use_buffering = order_info->limit == 0;
        sorting->convertToFinishSorting(order_info->sort_description_for_merging, use_buffering, apply_virtual_row);
    }

and convertToFinishSorting just changes the step’s type:

cpp
// src/Processors/QueryPlan/SortingStep.cpp:320
void SortingStep::convertToFinishSorting(SortDescription prefix_description_, bool use_buffering_, bool apply_virtual_row_conversions_)
{
    type = Type::FinishSorting;
    prefix_description = std::move(prefix_description_);
    use_buffering = use_buffering_;
    apply_virtual_row_conversions = apply_virtual_row_conversions_;
}

The pipeline first merges the already-sorted streams by the prefix description, and then, only if the prefix is shorter than the full sort description, installs a partial sort plus a finish sort:

cpp
// src/Processors/QueryPlan/SortingStep.cpp:381
void SortingStep::finishSorting(
    QueryPipelineBuilder & pipeline, const SortDescription & input_sort_desc, const SortDescription & result_sort_desc, const UInt64 limit_)
{
    pipeline.addSimpleTransform(
        [&](const SharedHeader & header, QueryPipelineBuilder::StreamType stream_type) -> ProcessorPtr
        {
            if (stream_type != QueryPipelineBuilder::StreamType::Main)
                return nullptr;

            return std::make_shared<PartialSortingTransform>(header, result_sort_desc, limit_, threshold_tracker);
        });

PartialSortingTransform sorts each block but only keeps the rows that could still be in the top-limit (using a threshold tracker), and FinishSortingTransform then completes the ordering of the remaining sort columns within the already-sorted prefix:

cpp
// src/Processors/Transforms/FinishSortingTransform.cpp:32
    /// Check for sanity non-modified descriptions
    if (!isPrefix(description_sorted_, description_to_sort_))
        throw Exception(ErrorCodes::LOGICAL_ERROR,
                        "Can't finish sorting. SortDescription "
                        "of already sorted stream is not prefix of SortDescription needed to sort");

The isPrefix check is the safety net: the finish-sort transform requires that the input is already sorted by a prefix of the requested description, and throws if it is not. This is the last line of defence for the whole optimisation.

The limit is pushed into the read

The limit field of InputOrderInfo is what turns “read in order” into “read only what you need”. The read knows how many rows the consumer wants:

cpp
// src/Processors/QueryPlan/ReadFromMergeTree.cpp:1039
    const UInt64 in_order_limit = query_info.input_order_info ? query_info.input_order_info->limit : 0;

and when distributing the marks of the parts among the reading streams, a part that is smaller than the limit is taken whole, while the read stops as soon as the limit is reached:

cpp
// src/Processors/QueryPlan/ReadFromMergeTree.cpp:2156
                /// We take full part if it contains enough marks or
                /// if we know limit and part contains less than 'limit' rows.
                bool take_full_part = marks_in_part <= need_marks || (input_order_info->limit && input_order_info->limit < part.getRowsCount());

This is where the 100× difference between “sort a billion rows” and “read ten rows” actually comes from: not fewer bytes sorted, but not reading the parts that cannot contain the answer.

The picture

text
   plan before                      plan after
   ----------                       -----------
   ReadFromMergeTree                 ReadFromMergeTree
     (parts in arbitrary order,       (parts in sorting-key order,
      rows in arbitrary order)         rows in key order, stops at LIMIT)
        |                                  |
   SortingStep (FULL)                   SortingStep (FINISH)
     (sorts everything)                  (partial sort + finish sort)
        |                                  |
   Limit                                 Limit

   cost: O(N log N), reads N rows     cost: O(K log P), reads ~K rows
                                         where K = LIMIT, P = parts

The same machinery, four ways

optimizeReadInOrder is not the only user of this machinery. The same buildInputOrderInfo is reused for four different consumers, each of which has a different idea of what “in order” means:

SortingStep — the ORDER BY case above.
AggregatingStep — optimizeAggregationInOrder: if the data is already sorted by the grouping key, the aggregation can be done in a single pass over the stream instead of a hash table.
DistinctStep — optimizeDistinctInOrder: DISTINCT on sorted data is a “compare with the previous row” operation, not a hash set.
LimitByStep — optimizeLimitByInOrder: LIMIT n BY k on sorted data is a “take the first n rows of each k group” operation.

The aggregation one has an extra requirement — the sort description must cover the grouping keys:

cpp
// src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp:2050
    /// The sorted-stream transform needs every key in the sort prefix (and in that order); otherwise a
    /// key not covered by the prefix would be dropped from grouping.
    auto sort_prefix
        = getCollationAwareSortPrefixInColumns(order_info.sort_description, limit_by->getColumns(), *limit_by->getInputHeaders().front());
    if (sort_prefix.size() != limit_by->getColumns().size())
        return;

Trade-offs

What the optimisation buys:

ORDER BY ... LIMIT n becomes O(K log P) instead of O(N log N) where K is the limit and P the number of parts. The parts that cannot contain the answer are never opened.
The sort step becomes a partial sort. The consumer no longer sorts the whole table; it sorts the top-K of each block and merges.
It is not a special case for MergeTree. The same machinery drives aggregation-in-order, distinct-in-order and limit-by-in-order, and works for Merge, ObjectStorage and distributed plans.

What it costs:

The matching logic is genuinely hard. optimizeReadInOrder.cpp is 2060 lines, and the direction/NULL/NaN/monotonicity interactions are the reason. Every one of them is a potential wrong answer if it is got wrong, because the sort is elided — there is no downstream check.
The safety net is a throw. FinishSortingTransform throws a LOGICAL_ERROR if the prefix assumption is violated. That is the right failure mode (loud, not silent) but it means a bug in the matcher is a server error, not a wrong answer.
The read has to be ordered, which constrains the read strategy. Parts must be read in key order, which interacts with parallel replicas, with FINAL (which may need a reverse read), and with the decision of how to spread the marks of the parts among the reading threads.
Not every ORDER BY qualifies. ORDER BY on a non-key column, on a collation, on a non-monotonic expression, or with a conflicting direction simply does not match, and the query falls back to a full sort. The matching is precise, not heuristic — which is why it is worth the complexity, and also why it does not fire as often as you might hope.

The one thing to remember: the sorting key is a physical property of the data, and the optimisation is about discovering that the query’s sort order is already implied by it. The InputOrderInfo is the handshake: “I promise the stream is ordered by these N key columns in this direction, and I will take at most L rows”.

The part people get wrong: the LIMIT is what makes this optimisation worthwhile, and it is easy to lose. SELECT * FROM events ORDER BY event_time (without a limit) still has to read every row, and the benefit is only that the rows arrive already sorted — which saves the sort, but not the read. The dramatic case is ORDER BY ... LIMIT, where the read itself is truncated.

What to go do about it: compare EXPLAIN PIPELINE for the same query with optimize_read_in_order = 1 and = 0. If the plans differ in the ReadFromMergeTree step’s description or in the sort step’s type, the optimisation fired. And check that your table’s sorting key starts with the column you are ordering by — a sorting key of (tenant_id, event_time) will not help ORDER BY event_time, but a sorting key of (event_time, tenant_id) will.

The contract: InputOrderInfo