WHERE condtions optimization leveraging projection feature by suzyw-w · Pull Request #57216 · ClickHouse/ClickHouse

suzyw-w · 2023-11-24T20:43:32Z

This is a proposal to optimize select query by leveraging projection feature.
Since PROJECTION can effectively create a new primary key for the table, it can increase the searching speed if using properly.
This implementation inserts a new subquery to the original where condition, in order to use the projection feature in more general cases.
For example,
select * from table where secondary_key='-42';
will now become
select * from table where primary_key in (select primary_key from test_a where secondary_key='-42') and secondary_key='-42';
This implementation is tested and proved increasing query execution speed vastly.

Thanks to @UnamedRus 's suggestion, indexHint() is also added to further optimize the query. Now the query is going to be re-write to select * from table where indexHint(primary_key in (select primary_key from test_a where secondary_key='-42')) and secondary_key='-42';
It is proved that this will also optimize query execution speed. Tests results are attached below.

Pseudo Code

for each query (including subqueries):
   for each predicate in WHERE clause in the query:
	 1. check if it's a simple condition <column>=<value>;
	 2. check if <column> is NOT the primary key of the table;
	 3. check if <column> is the primary key of a projection that contains table primary keys;
	 4. if all condition met, rewrite the query as mentioned above and break

Restrictions

Currently the re-write only works for WHERE condition with no subquery. (e.x Select * Where src in () will not be optimized).
The re-write only support WHERE condition that is using = function.
The re-write can work with Alias but not function wrapping around columns.
For example,

SELECT
      user_account AS my_user,
      user_id
FROM events
WHERE my_user = 'admin'

can be re-written to

SELECT                                                     
     user_account AS my_user,                    
     user_id
 FROM events                                                                          
 WHERE (my_user = 'admin') AND indexHint( primary_key IN (
     SELECT primary_key 
     FROM events                                           
     WHERE (user_account AS my_user) = 'admin'
 ))

However, query like the following will not be recognized, and will not be re-written.

SELECT
      If(user_id = 0, NULL, user_account) AS user_id AS my_user,
      user_id
FROM events
WHERE my_user = 'admin'

Aggregation Function projection is not supported.
This re-written is implemented on top of projection feature, hence anything that Projection feature currently does not support will not be supported with this optimization.

Test result

CREATE TABLE test_a
(
    `src` String,
    `dst` String,
    `other_cols` String,
    PROJECTION p1
    (
        SELECT
            src,
            dst
        ORDER BY dst
    )
)
ENGINE = MergeTree
ORDER BY src

/* Query using primary key (fastest) */

palmtops1.fyre.ibm.com :) select * from test_a where src='42';

SELECT *
FROM test_a
WHERE src = '42'

Query id: 9220dadb-bdbc-4fe5-bf70-b4c04b3e7ddd

┌─src─┬─dst─┬─other_cols───┐
│ 42  │ -42 │ other_col 42 │
└─────┴─────┴──────────────┘

1 row in set. Elapsed: 0.042 sec. Processed 16.38 thousand rows, 619.85 KB (388.58 thousand rows/s., 14.70 MB/s.)
Peak memory usage: 44.66 KiB.

/* Query does not using projection */

palmtops1.fyre.ibm.com :) select * from test_a where dst='-42';

SELECT *
FROM test_a
WHERE dst = '-42'

Query id: 7835b759-e894-4e34-b51b-f54fe3d1645c

┌─src─┬─dst─┬─other_cols───┐
│ 42  │ -42 │ other_col 42 │
└─────┴─────┴──────────────┘

1 row in set. Elapsed: 2.177 sec. Processed 100.00 million rows, 1.79 GB (45.94 million rows/s., 821.86 MB/s.)
Peak memory usage: 1021.77 KiB.

/* Optimized non-projection query now can leveraging projection feature */

palmtops1.fyre.ibm.com :) select * from test_a where src in (select src from test_a where dst='-42') and dst='-42';

SELECT *
FROM test_a
WHERE (src IN (
    SELECT src
    FROM test_a
    WHERE dst = '-42'
)) AND (dst = '-42')

Query id: 68ca1b70-940f-41d2-983b-4df7c06df5ae

┌─src─┬─dst─┬─other_cols───┐
│ 42  │ -42 │ other_col 42 │
└─────┴─────┴──────────────┘

1 row in set. Elapsed: 0.101 sec. Processed 32.77 thousand rows, 1.18 MB (325.38 thousand rows/s., 11.75 MB/s.)
Peak memory usage: 275.28 KiB

/* Optimized query with indexHint */

palmtops1.fyre.ibm.com :) select * from test_a where indexHint(src in (select src from test_a where dst='-42')) and dst='-42';

SELECT *
FROM test_a
WHERE indexHint(src IN (
    SELECT src
    FROM test_a
    WHERE dst = '-42'
)) AND (dst = '-42')

Query id: 365d4fae-93dc-48e5-b0c0-42dc2ba9904e

┌─src─┬─dst─┬─other_cols───┐
│ 42  │ -42 │ other_col 42 │
└─────┴─────┴──────────────┘

1 row in set. Elapsed: 0.094 sec. Processed 32.77 thousand rows, 1.18 MB (350.31 thousand rows/s., 12.65 MB/s.)
Peak memory usage: 223.92 KiB.

Query using primary key (fastest) : 0.042 sec, Peak memory usage: 44.66 KiB
Query does not using projection : 2.177 sec, Peak memory usage: 1021.77 KiB.
Optimized non-projection query : 0.101 sec, Peak memory usage: 275.28 KiB
Optimized query with indexHint : 0.094 sec, Peak memory usage: 223.92 KiB.

Changelog category (leave one):

Improvement

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

Documentation entry for user-facing changes

Documentation is written (mandatory for new features)

Information about CI checks: https://clickhouse.com/docs/en/development/continuous-integration/

…ature

UnamedRus · 2023-11-24T21:55:10Z

Should be slightly better

select * from table where indexHint(primary_key in (select primary_key from test_a where secondary_key='-42')) and secondary_key='-42';

But there is also potential problem, with case when subquery return big set of keys, index analysis in that case can be slower than reading whole table and filtering.

robot-ch-test-poll3 · 2023-11-24T22:14:19Z

This is an automated comment for commit 020fb95 with description of existing statuses. It's updated for the latest CI running

❌ Click here to open a full report in a separate page

Check name	Description	Status
CI running	A meta-check that indicates the running CI. Normally, it's in success or pending state. The failed status indicates some problems with the PR	⏳ pending
ClickHouse build check	Builds ClickHouse in various configurations for use in further steps. You have to fix the builds that fail. Build logs often has enough information to fix the error, but you might have to reproduce the failure locally. The cmake options can be found in the build log, grepping for cmake. Use these options and follow the general build process	❌ failure
Mergeable Check	Checks if all other necessary checks are successful	❌ failure
Stateless tests	Runs stateless functional tests for ClickHouse binaries built in various configurations -- release, debug, with sanitizers, etc	❌ failure
Stress test	Runs stateless functional tests concurrently from several clients to detect concurrency-related errors	❌ failure
Upgrade check	Runs stress tests on server version from last release and then tries to upgrade it to the version from the PR. It checks if the new server can successfully startup without any errors, crashes or sanitizer asserts	❌ failure

Successful checks

Check name	Description	Status
A Sync	There's no description for the check yet, please add it to tests/ci/ci_config.py:CHECK_DESCRIPTIONS	✅ success
AST fuzzer	Runs randomly generated queries to catch program errors. The build type is optionally given in parenthesis. If it fails, ask a maintainer for help	✅ success
ClickBench	Runs [ClickBench](https://github.com/ClickHouse/ClickBench/) with instant-attach table	✅ success
Compatibility check	Checks that clickhouse binary runs on distributions with old libc versions. If it fails, ask a maintainer for help	✅ success
Docker keeper image	The check to build and optionally push the mentioned image to docker hub	✅ success
Docker server image	The check to build and optionally push the mentioned image to docker hub	✅ success
Docs check	Builds and tests the documentation	✅ success
Fast test	Normally this is the first check that is ran for a PR. It builds ClickHouse and runs most of stateless functional tests, omitting some. If it fails, further checks are not started until it is fixed. Look at the report to see which tests fail, then reproduce the failure locally as described here	✅ success
Flaky tests	Checks if new added or modified tests are flaky by running them repeatedly, in parallel, with more randomization. Functional tests are run 100 times with address sanitizer, and additional randomization of thread scheduling. Integrational tests are run up to 10 times. If at least once a new test has failed, or was too long, this check will be red. We don't allow flaky tests, read the doc	✅ success
Install packages	Checks that the built packages are installable in a clear environment	✅ success
Integration tests	The integration tests report. In parenthesis the package type is given, and in square brackets are the optional part/total tests	✅ success
PR Check	There's no description for the check yet, please add it to tests/ci/ci_config.py:CHECK_DESCRIPTIONS	✅ success
Performance Comparison	Measure changes in query performance. The performance test report is described in detail here. In square brackets are the optional part/total tests	✅ success
Stateful tests	Runs stateful functional tests for ClickHouse binaries built in various configurations -- release, debug, with sanitizers, etc	✅ success
Style check	Runs a set of checks to keep the code style clean. If some of tests failed, see the related log from the report	✅ success
Unit tests	Runs the unit tests for different release types	✅ success

amosbird · 2023-11-25T00:34:07Z

I also have some plan to implement secondary indices on top of normal projections. It might rely on ColumnLazy.

suzyw-w · 2023-12-04T14:45:29Z

TODO list:

Recognition of a select query already using projection feature, no rewrite of such query
With some error and trial test, rewrite the query using one projection table is enough to speed up query execution, leveraging multiple projection table increases the execution time. Hence going to update the code to use single projection table.

…proj_optimize

UnamedRus · 2023-12-16T01:25:15Z

Ideally, this "rewrite" should happen on level of part.

So each part, will be filtered by list of PK from it's own projection.

suzyw-w · 2023-12-19T14:44:16Z

Ideally, this "rewrite" should happen on level of part.

So each part, will be filtered by list of PK from it's own projection.

This is in our consideration for the next stage.

suzyw-w · 2024-01-05T15:15:58Z

Would this actually slow down the process?

It could slowdown merge, but we still need to do it in that way (for some engines) because of Replacing/... table engines #24778

So far we have been limited our usecase of MergeTree Enginee while using projection. Is this a known issue for CollapsingMergeTree and ReplacingMergeTree only? Meaning does MergeTree enginee has the same problem?

UnamedRus · 2024-01-05T15:28:45Z

Is this a known issue for CollapsingMergeTree and ReplacingMergeTree only?

It's known issue that currently projections are not working correctly (but, it's mostly harm aggregation projections) for ReplacingMergeTree and CollapsingMergeTree.

Fix is to recalculate projections from result of merge, instead of source projections.

For your case, if we want to use _part_offset column instead of PK in projection for filtering. we also need to recalculate projection in order to obtain new _part_offset in merged part.

suzyw-w · 2024-01-05T16:12:18Z

Is this a known issue for CollapsingMergeTree and ReplacingMergeTree only?

It's known issue that currently projections are not working correctly (but, it's mostly harm aggregation projections) for ReplacingMergeTree and CollapsingMergeTree.

Fix is to recalculate projections from result of merge, instead of source projections.

For your case, if we want to use _part_offset column instead of PK in projection for filtering. we also need to recalculate projection in order to obtain new _part_offset in merged part.

It sounds like there's still some uncertainty about _part_offset, I think it is the best that we open a separate pr and keep this pr simple.

suzyw-w · 2024-01-17T15:18:17Z

@alexey-milovidov Hi, can someone please take a look at this pr?

suzyw-w · 2024-02-01T21:03:33Z

@UnamedRus @amosbird Hi, as you guys are the expert on this, do we have any more concerns of this change?

suzyw-w · 2024-02-01T21:03:40Z

@alexey-milovidov @KochetovNicolai @davenger Hi, Can we please have someone review the pr?

suzyw-w · 2024-02-12T16:12:10Z

@UnamedRus @amosbird @alexey-milovidov @KochetovNicolai @davenger Hi, as this pr has been sitting around for a while, can we please have someone start reviewing this?

UnamedRus · 2024-02-13T23:04:42Z

I'm not a part of ClickHouse Inc team. (so I can only speak for myself)

Overall Idea is good and needs to be implemented.

But, i see few concern points:

What if projection is not materialized for some parts.
If this subquery will be added explicitly as normal part of query, it would force "materialization" of projection for those parts on fly, basically read main table instead of "lightweight" projection. (but, it's back to a question of making such optimization on part level)
New ast based optimizations for old parser is debatable topic because of it's fragile nature and ongoing movement to new analyzer-based infrastructure.
https://github.com/ClickHouse/ClickHouse/tree/b9d3ae3b0a1c62fd6d0bfa413ac2ad7a78e18849/src/Analyzer/Passes

suzyw-w · 2024-02-20T16:11:51Z

I'm not a part of ClickHouse Inc team. (so I can only speak for myself)

Overall Idea is good and needs to be implemented.

But, i see few concern points:

What if projection is not materialized for some parts.
If this subquery will be added explicitly as normal part of query, it would force "materialization" of projection for those parts on fly, basically read main table instead of "lightweight" projection. (but, it's back to a question of making such optimization on part level)

New ast based optimizations for old parser is debatable topic because of it's fragile nature and ongoing movement to new analyzer-based infrastructure.
https://github.com/ClickHouse/ClickHouse/tree/b9d3ae3b0a1c62fd6d0bfa413ac2ad7a78e18849/src/Analyzer/Passes

Thank you for your response. I do need some backup here to let clickhouse team start looking at this pr.

suzyw-w · 2024-02-22T18:57:35Z

@alexey-milovidov @KochetovNicolai @davenger Can we please have someone start review this pr?

alexey-milovidov · 2024-03-22T03:07:24Z

@SuzyWangIBMer This pull request didn't pass tests.

suzyw-w · 2024-03-26T17:40:11Z

@alexey-milovidov Conflicts are resolved now. Current failures seems non-relevant to my change.

suzyw-w · 2024-04-30T19:42:48Z

Closes as new implementation moving to Analyzer/Passes is done. New PR opened #63207

suzyw-w added 4 commits November 12, 2023 20:09

projection feature leveraging query optimization

eb2cdcc

More change to support complicated cases for leveraging projection fe…

0c5df54

…ature

Organize

66f6971

Clean and organize

f93ef84

suzyw-w marked this pull request as ready for review November 24, 2023 20:43

alexey-milovidov added the can be tested Allows running workflows for external contributors label Nov 24, 2023

robot-ch-test-poll3 added the pr-improvement Pull request with some product improvements label Nov 24, 2023

suzyw-w added 2 commits November 27, 2023 21:32

format fix

dd7d5a1

remove trailing whitespace

cef3fb0

suzyw-w marked this pull request as draft December 4, 2023 14:44

suzyw-w added 8 commits December 7, 2023 04:30

Fix nestes subquery reading; fix minor issues

95ffe77

Fix nestes subquery reading; fix minor issues

b83aba5

Merge branch 'proj_optimize' of github.com:ClibMouse/ClickHouse into …

733a1ff

…proj_optimize

remove accidently added line

bb22cd8

style fixes

cd007b8

insert pk into select query if optimize projection

ee9e60f

update testcase reference

7e0a56b

Fix recursion for indexhint

65b703e

suzyw-w marked this pull request as ready for review December 8, 2023 16:03

suzyw-w added 5 commits December 11, 2023 19:19

some more comments

7d101f8

some more flags

1d91ec9

Fix primary key insertion conditions

95fc187

Fuzzer fix

6139ed8

some extra case handling

a6393a8

suzyw-w added 5 commits January 16, 2024 11:29

Merge branch 'master' into proj_optimize

69d8682

include multiple primary keys in the optimized query

ffb85b5

style fix

de4b6f1

style update

5fcb498

clang tidy fix

d8d37fc

Merge branch 'master' into proj_optimize

af10658

Added more test cases, added flag preventing endless optimization

b2dd002

suzyw-w added 7 commits March 22, 2024 08:36

testcase update according to latest rebase

c131524

end of line fix

b4520ba

add optimize_project_query to settings

ed0d9f1

Merge branch 'master' into proj_optimize

420c29e

remove trailing whitespace

bb46d7f

Merge branch 'master' into proj_optimize

c62ede0

Merge branch 'master' into proj_optimize

69f3d9e

remove database from func test

020fb95

suzyw-w mentioned this pull request Apr 30, 2024

WHERE clauses optimization leveraging Projection feature #63207

Closed

30 tasks

suzyw-w closed this Apr 30, 2024

Conversation

suzyw-w commented Nov 24, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pseudo Code

Restrictions

Test result

Changelog category (leave one):

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

Documentation entry for user-facing changes

Uh oh!

UnamedRus commented Nov 24, 2023

Uh oh!

robot-ch-test-poll3 commented Nov 24, 2023 • edited by robot-ch-test-poll Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

amosbird commented Nov 25, 2023

Uh oh!

suzyw-w commented Dec 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

UnamedRus commented Dec 16, 2023

Uh oh!

suzyw-w commented Dec 19, 2023

Uh oh!

suzyw-w commented Jan 5, 2024

Uh oh!

UnamedRus commented Jan 5, 2024

Uh oh!

suzyw-w commented Jan 5, 2024

Uh oh!

suzyw-w commented Jan 17, 2024

Uh oh!

suzyw-w commented Feb 1, 2024

Uh oh!

suzyw-w commented Feb 1, 2024

Uh oh!

suzyw-w commented Feb 12, 2024

Uh oh!

UnamedRus commented Feb 13, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

suzyw-w commented Feb 20, 2024

Uh oh!

suzyw-w commented Feb 22, 2024

Uh oh!

alexey-milovidov commented Mar 22, 2024

Uh oh!

suzyw-w commented Mar 26, 2024

Uh oh!

suzyw-w commented Apr 30, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

suzyw-w commented Nov 24, 2023 •

edited

Loading

robot-ch-test-poll3 commented Nov 24, 2023 •

edited by robot-ch-test-poll

Loading

suzyw-w commented Dec 4, 2023 •

edited

Loading

UnamedRus commented Feb 13, 2024 •

edited

Loading