Read-in-order over query plan by KochetovNicolai · Pull Request #42829 · ClickHouse/ClickHouse

KochetovNicolai · 2022-10-31T13:57:39Z

Changelog category (leave one):

Improvement

Changelog entry (a user-readable short description of the changes that goes to CHANGELOG.md):

Implement read-in-order optimization on top of query plan. It is enabled by default. Set query_plan_read_in_order = 0 to use previous AST-based version.

KochetovNicolai · 2022-11-02T17:12:57Z

tests/queries/0_stateless/01952_optimize_distributed_group_by_sharding_key.reference

  LimitBy
-    Expression (Before LIMIT BY)
-      Union
+    Union


Changed after liftUpUnion

KochetovNicolai · 2022-11-02T17:13:55Z

tests/queries/0_stateless/02155_read_in_order_max_rows_to_read.sql

+SELECT a FROM t_max_rows_to_read WHERE a > 10 ORDER BY a LIMIT 5 SETTINGS max_rows_to_read = 12;
+SELECT a FROM t_max_rows_to_read WHERE a = 10 OR a = 20 SETTINGS max_rows_to_read = 12;


Now, both of this queries works.

KochetovNicolai · 2022-11-02T17:16:28Z

tests/queries/0_stateless/02317_distinct_in_order_optimization_explain.reference

-Sorting (Stream): a ASC
-Sorting (Stream): a ASC


Now, read-in-order optimization happens after plan is built.
Current implementation does not propagate sorting property upwards, so it was changed only for reading step.

KochetovNicolai · 2022-11-02T17:18:13Z

tests/queries/0_stateless/02377_optimize_sorting_by_input_stream_properties_explain.reference

 -- enable optimization -> sorting order is propagated from subquery -> merge sort
 -- QUERY: set optimize_sorting_by_input_stream_properties=1;set max_threads=1;EXPLAIN PIPELINE SELECT a FROM (SELECT a FROM optimize_sorting) ORDER BY a
-MergeSortingTransform
+MergingSortedTransform 3 → 1


From the comment, there should have been MergingSortedTransform initially. MergeSortingTransform is a full sort.
It was magically fixed.

KochetovNicolai · 2022-11-02T17:21:11Z

tests/queries/0_stateless/02377_optimize_sorting_by_input_stream_properties_explain.reference

+Sorting (Sorting for ORDER BY)
 Sorting (Global): a ASC
-Sorting (Stream): a ASC
+Sorting (Chunk): a ASC, b ASC


This is an incorrect property, but it won't be used cause plan is already built.
We should probably fix it later.

KochetovNicolai · 2022-11-02T17:21:41Z

tests/queries/0_stateless/02381_join_dup_columns_in_plan.reference

      ReadFromStorage
      Header: dummy UInt8
-    Expression
+    Union


Changed after liftUpUnion

…lan is enabled.

KochetovNicolai · 2022-11-08T14:20:38Z

Tsan should be fixed in #43009

kitaisreal · 2022-11-08T14:59:21Z

Something is wrong with performance tests, probably it does not work for such queries https://s3.amazonaws.com/clickhouse-test-reports/42829/7ac258c2a77fa813052ac67cc67977b05368fa1d/performance_comparison_[4/4]/report.html.
We need to add a lot of additional performance tests to cover all scenarious.

CurtizJ

In general ok, but let's wait for review from someone who is more familiar with code near plan optimizations.

CurtizJ · 2022-11-07T18:04:06Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+        return reading;
+    }
+
+    if (auto * merge = typeid_cast<ReadFromMerge *>(step))


Will it be supported for other storages like Buffer and MaterializedView, because they have a ReadFromMergeTree inside plan, which is built to read from those storages, right?

Yes. For MV it is naturally supported. For Buffer I had to support a simple optimization with union.
Anyway, we had a test for such engines.

CurtizJ · 2022-11-07T18:46:46Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+using FixedColumns = std::unordered_set<const ActionsDAG::Node *>;
+
+/// Right now we find only simple cases like 'and(..., and(..., and(column = value, ...), ...'
+void appendFixedColumnsFromFilterExpression(const ActionsDAG::Node & filter_expression, FixedColumns & fiexd_columns)


A typo fiexd_columns

CurtizJ · 2022-11-07T18:47:02Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+            else if (name == "equals")
+            {
+                const ActionsDAG::Node * maybe_fixed_column = nullptr;
+                bool is_singe = true;


A typo is_singe

CurtizJ · 2022-11-08T15:04:46Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+        if (!sort_column_node)
+            break;
+
+        if (!dag)


Is it possible? Shouldn't we build dag just for input columns even without any functions?

It is possible. This DAG is from SELECT. For example, SELECT * FROM tab ORDER BY a, b will not have any expression steps, and DAG will be empty.

CurtizJ · 2022-11-08T15:20:02Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+                auto it = matches.find(child);
+                if (it == matches.end())
+                {
+                    stack.push(Frame{child, {}});
+                    break;
+                }


Need a comment why do we do this if node is not in matches.

CurtizJ · 2022-11-08T15:23:27Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+
+                bool found_all_children = true;
+                for (const auto * child : frame.mapped_children)
+                    if (!child)


How is it possible to get nullptr in mapped_children?

Yes. Will write a comment.

CurtizJ · 2022-11-08T15:32:36Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+/// This structure stores a node mapping from one DAG to another.
+/// The rule is following:
+/// * Input nodes are mapped by name.
+/// * Function is mapped to function if all children are mapped and function names are same.


Does it mean that function is mapped to itself?

Yes, but from different DAGs.
I mean, this is the idea - to find equal calculations if DAGs

KochetovNicolai · 2022-11-08T19:16:06Z

Lol, one query from order_by_read_in_order perftest became slower cause read-in-order actually did not work for it

EXPLAIN PIPELINE
SELECT *
FROM datasets.hits_100m_obfuscated
WHERE UserID = 1988954671305023629
ORDER BY
    CounterID ASC,
    EventDate ASC
LIMIT 100
SETTINGS query_plan_read_in_order = 1

Query id: 7a3efb48-35f5-428d-a1f6-51668b44a779

┌─explain────────────────────────┐
│ (Expression)                   │
│ ExpressionTransform            │
│   (Limit)                      │
│   Limit                        │
│     (Sorting)                  │
│       (Expression)             │
│       ExpressionTransform      │
│         (ReadFromMergeTree)    │
│         MergeTreeInOrder 0 → 1 │
└────────────────────────────────┘


EXPLAIN PIPELINE
SELECT *
FROM datasets.hits_100m_obfuscated
WHERE UserID = 1988954671305023629
ORDER BY
    CounterID ASC,
    EventDate ASC
LIMIT 100
SETTINGS query_plan_read_in_order = 0

Query id: 73f61e3e-89ac-488c-97b7-2522428895b7

┌─explain─────────────────────────────┐
│ (Expression)                        │
│ ExpressionTransform                 │
│   (Limit)                           │
│   Limit                             │
│     (Sorting)                       │
│     MergingSortedTransform 16 → 1   │
│       (Expression)                  │
│       ExpressionTransform × 16      │
│         (ReadFromMergeTree)         │
│         MergeTreeInOrder × 16 0 → 1 │
└─────────────────────────────────────┘

Looks like ordinary read worked faster cause condition on pk is good and we full sort not so many data. parallel execution wins in this case.

KochetovNicolai · 2022-11-08T19:19:57Z

And the same for a query from monotonous_order_by

EXPLAIN PIPELINE
SELECT *
FROM
(
    SELECT
        CounterID,
        EventDate
    FROM datasets.hits_100m_obfuscated
)
ORDER BY
    toFloat32(toFloat64(toFloat32(toFloat64(CounterID)))) DESC,
    toFloat32(toFloat64(toFloat32(toFloat64(EventDate)))) ASC
SETTINGS max_threads = 3, query_plan_read_in_order = 1

Query id: 0d9bbfc9-2e36-4a91-910e-9602d736542f

┌─explain────────────────────────────────────┐
│ (Expression)                               │
│ ExpressionTransform                        │
│   (Sorting)                                │
│   FinishSortingTransform                   │
│     PartialSortingTransform                │
│       MergingSortedTransform 3 → 1         │
│         (Expression)                       │
│         ExpressionTransform × 3            │
│           (ReadFromMergeTree)              │
│           ReverseTransform                 │
│             MergeTreeReverse 0 → 1         │
│               ReverseTransform             │
│                 MergeTreeReverse 0 → 1     │
│                   ReverseTransform         │
│                     MergeTreeReverse 0 → 1 │
└────────────────────────────────────────────┘

15 rows in set. Elapsed: 0.003 sec. 

EXPLAIN PIPELINE
SELECT *
FROM
(
    SELECT
        CounterID,
        EventDate
    FROM datasets.hits_100m_obfuscated
)
ORDER BY
    toFloat32(toFloat64(toFloat32(toFloat64(CounterID)))) DESC,
    toFloat32(toFloat64(toFloat32(toFloat64(EventDate)))) ASC
SETTINGS max_threads = 3, query_plan_read_in_order = 0

Query id: de260a83-1190-4f6f-9f4f-2ae530aaa21a

┌─explain───────────────────────────────┐
│ (Expression)                          │
│ ExpressionTransform                   │
│   (Sorting)                           │
│   MergingSortedTransform 3 → 1        │
│     MergeSortingTransform × 3         │
│       LimitsCheckingTransform × 3     │
│         PartialSortingTransform × 3   │
│           (Expression)                │
│           ExpressionTransform × 3     │
│             (ReadFromMergeTree)       │
│             MergeTreeThread × 3 0 → 1 │
└───────────────────────────────────────┘

But in this case it's harder to explain why. Probably, computation of toFloat32(toFloat64(toFloat32(toFloat64( is slow, and parallel execution wins again. Also, optimized query need to add FinishSorting to sort by EventDate.

CurtizJ · 2022-11-08T22:22:45Z

Lol, one query from order_by_read_in_order perftest became slower cause read-in-order actually did not work for it

@KochetovNicolai

But in the second case:

EXPLAIN PIPELINE
SELECT *
FROM datasets.hits_100m_obfuscated
WHERE UserID = 1988954671305023629
ORDER BY
    CounterID ASC,
    EventDate ASC
LIMIT 100
SETTINGS query_plan_read_in_order = 0

Query id: 73f61e3e-89ac-488c-97b7-2522428895b7

┌─explain─────────────────────────────┐
│ (Expression)                        │
│ ExpressionTransform                 │
│   (Limit)                           │
│   Limit                             │
│     (Sorting)                       │
│     MergingSortedTransform 16 → 1   │
│       (Expression)                  │
│       ExpressionTransform × 16      │
│         (ReadFromMergeTree)         │
│         MergeTreeInOrder × 16 0 → 1 │
└─────────────────────────────────────┘

reading in order also worked, because we have MergeTreeInOrder and MergingSortedTransform instead of MergeTreeThread, MergeSorting and PartialSorting. The difference is in number of threads.

CurtizJ · 2022-11-08T22:27:50Z

The case with monotonous_order_by is reasonable. I think the cause is that sorting with FinishSorting without or with high limit is never faster than regular sorting, because it has the same algorithmic complexity, but slower reading method.

In that case reading in order was not enable previously, because the chain of monotonic function was not supported.

kitaisreal

Everything is good. Just added small comments for clarification.

kitaisreal · 2022-11-09T09:53:12Z

src/Interpreters/ExpressionAnalyzer.cpp

            && !query.final()
            && join_allow_read_in_order;

-        if (storage && optimize_read_in_order)


Why this is removed ?

This was a fix of a bug from #39157
I was reproduced again with a new implementation, and I had to fix it in a different way.

kitaisreal · 2022-11-09T09:53:51Z

src/Interpreters/InterpreterExplainQuery.cpp

            if (getContext()->getSettingsRef().allow_experimental_analyzer)
            {
                InterpreterSelectQueryAnalyzer interpreter(ast.getExplainedQuery(), options, getContext());
+                context = interpreter.getContext();


Why we use context from interpreter, not context from EXPLAIN QUERY ?

There was a stupid bug that some settings were not applied for EXPLAIN.
InterpreterSelectQuery copied context and changed settings only for it, and the following plan.optimize did not see this settings change.
I don't know if this is applied to InterpreterSelectQueryAnalyzer as well, but I think it's better to copy context anyway.

kitaisreal · 2022-11-09T09:55:09Z

src/Interpreters/InterpreterSelectQuery.cpp

                        for (const auto & key_name : key_names)
                            order_descr.emplace_back(key_name);

+                        SortingStep::Settings sort_settings;


Consider to add constructor in SortingStep::Settings from Settings. Currently such construction is worse then was before, because you can easy do not initialize some setting, and there will be no error.

kitaisreal · 2022-11-09T09:55:44Z

src/Planner/Planner.cpp


        const Settings & settings = query_context->getSettingsRef();

+        SortingStep::Settings sort_settings;


This is copy pases several times in Interpreter and Planner, need to be extracted in separate method, or added constructor.

kitaisreal · 2022-11-09T09:57:56Z

src/Processors/QueryPlan/Optimizations/Optimizations.h

-size_t tryDistinctReadInOrder(QueryPlan::Node * node, QueryPlan::Nodes & nodes);
+size_t tryDistinctReadInOrder(QueryPlan::Node * node);
+
+/// Put some steps under union, so that plan optimisation could be applied to union parts separately.


Need example in comment. It is impossible to understand what some steps are and what we can expect from this function to do with query plan, without reading its internals.

kitaisreal · 2022-11-09T10:31:27Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+    using Matches = std::unordered_map<const ActionsDAG::Node *, Match>;
+};
+
+MatchedTrees::Matches matchTrees(const ActionsDAG & inner_dag, const ActionsDAG & outer_dag)


This function is generally well written, we need to just add some internal comments, for each step that follows documentation above.

I consider moving it somewhere to common interface, but likely will do it later (after aggregation-in-order)

kitaisreal · 2022-11-09T10:32:11Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+    ///
+    /// So far, 0 means any direction is possible. It is ok for constant prefix.
+    int read_direction = 0;
+    size_t next_descr_column = 0;


Consider to rename next_descr_column into next_description_column.

kitaisreal · 2022-11-09T10:32:40Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+    while (next_descr_column < description.size() && next_sort_key < sorting_key_columns.size())
+    {
+        const auto & sorting_key_column = sorting_key_columns[next_sort_key];
+        const auto & descr = description[next_descr_column];


Consider to rename descr into sort_column_description.

kitaisreal · 2022-11-09T10:33:48Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+    const auto & sorting_key = reading->getStorageMetadata()->getSortingKey();
+    const auto & sorting_key_columns = sorting_key.column_names;
+
+    return buildInputOrderInfo(


Probably if we decide to split this function call in multiple lines, better to have each function argument on the same line.

Or on the different lines.

kitaisreal · 2022-11-09T10:34:56Z

src/Processors/QueryPlan/Optimizations/optimizeReadInOrder.cpp

+
+/// This optimisation is obsolete and will be removed.
+/// optimizeReadInOrder covers it.
+size_t tryReuseStorageOrderingForWindowFunctions(QueryPlan::Node * parent_node, QueryPlan::Nodes & /*nodes*/)


Need to remove this. It should be supported by default from code above, and even better.

I like to have it till next stable release just in case.

KochetovNicolai added 7 commits August 15, 2022 19:33

Reimplement read-in-order optimisation on top of query plan.

e286902

Reimplement read-in-order optimisation on top of query plan.

dc03a83

Reimplement read-in-order optimisation on top of query plan.

f0fd85a

Merge branch 'master' into read-in-order-from-query-plan

5106c24

Merge branch 'master' into read-in-order-from-query-plan

79b30fe

Read-in-order over query plan (continuation)

5d41e7a

Use read-in-order from query plan by default.

375db5b

robot-ch-test-poll2 added the pr-improvement Pull request with some product improvements label Oct 31, 2022

KochetovNicolai added 2 commits October 31, 2022 14:01

Comment debug code.

068ae90

Add test

e99fd4e

nickitat self-assigned this Oct 31, 2022

kitaisreal self-assigned this Nov 1, 2022

KochetovNicolai and others added 6 commits November 1, 2022 15:11

Fix some more tests.

5220423

Fixing read-in-order for special storages.

9ffebf4

Remove some debug output.

30f7c04

Merge branch 'master' into read-in-order-from-query-plan

478d307

Fix typos.

2766c55

Another one try.

d551161

KochetovNicolai commented Nov 2, 2022

View reviewed changes

KochetovNicolai and others added 6 commits November 2, 2022 17:54

Another try.

fc38ddd

Another try.

4641f12

Another try.

1f11c73

More fixes.

280e609

Fixing test again.

8bd6607

Merge branch 'master' into read-in-order-from-query-plan

d01ef8c

KochetovNicolai added 5 commits November 3, 2022 20:33

Try to fix #39157 in a different way.

51ec95e

Fixnig test.

4db8389

Make query plan optimisation respect query settings in EXPLAIN

79facdb

Disable optimize_in_window_order in case if read-in-order for query p…

2db1638

…lan is enabled.

Add comments, fix tests.

9043df5

KochetovNicolai marked this pull request as ready for review November 4, 2022 17:40

Improve test.

7ac258c

CurtizJ reviewed Nov 8, 2022

View reviewed changes

Fix typos. Add comments.

5a3d4cd

kitaisreal approved these changes Nov 9, 2022

View reviewed changes

KochetovNicolai and others added 7 commits November 9, 2022 16:07

Review fixes.

997881c

Fix typo.

3c3771a

Fix limit.

ff65ca4

Fix test.

c6f0701

Fix test.

0261ff5

Merge branch 'master' into read-in-order-from-query-plan

f2f5c17

Fix aarch build.

77c0728

KochetovNicolai merged commit 63d06c8 into master Nov 11, 2022

KochetovNicolai deleted the read-in-order-from-query-plan branch November 11, 2022 11:15

devcrafter mentioned this pull request Feb 3, 2023

Update sorting properties after reading in order applied #46014

Merged

novikd mentioned this pull request Apr 6, 2023

[Umbrella] Analyzer, Planner migration #42648

Closed

tavplubix mentioned this pull request Apr 12, 2023

Cannot find column less(id, 100) in ActionsDAG result. (UNKNOWN_IDENTIFIER) #48682

Closed

UnamedRus mentioned this pull request May 24, 2023

read_in_order not used for SELECT key FROM test_read JOIN tbl as n ON value = n.number ORDER BY key #50168

Open

		SELECT a FROM t_max_rows_to_read WHERE a > 10 ORDER BY a LIMIT 5 SETTINGS max_rows_to_read = 12;
		SELECT a FROM t_max_rows_to_read WHERE a = 10 OR a = 20 SETTINGS max_rows_to_read = 12;


		const Settings & settings = query_context->getSettingsRef();

		SortingStep::Settings sort_settings;

Conversation

KochetovNicolai commented Oct 31, 2022

Changelog category (leave one):

Changelog entry (a user-readable short description of the changes that goes to CHANGELOG.md):

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

KochetovNicolai commented Nov 8, 2022

Uh oh!

kitaisreal commented Nov 8, 2022

Uh oh!

CurtizJ left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

KochetovNicolai commented Nov 8, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

KochetovNicolai commented Nov 8, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

CurtizJ commented Nov 8, 2022

Uh oh!

CurtizJ commented Nov 8, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kitaisreal left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

KochetovNicolai commented Nov 8, 2022 •

edited

Loading

KochetovNicolai commented Nov 8, 2022 •

edited

Loading

CurtizJ commented Nov 8, 2022 •

edited

Loading