Improve all join performance by append `RowRefList` or `RowRef` to AddedColumns for lazy output by KevinyhZou · Pull Request #63677 · ClickHouse/ClickHouse

KevinyhZou · 2024-05-13T01:51:14Z

Changelog category (leave one):

Performance Improvement

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

Improve all join perfromance by append RowRefList or RowRef to AddedColumns for lazy output, while buildOutput, we use RowRefList/RowRef for output, and remove is_join_get condition from buildOutput for loop.

And we test as below, the left table test1((a Int64, b String, c LowCardinality(String), has 10000000 rows, the right table test2(a Int64, b String, c LowCardinality(String)) has 100000 rows, the test sql SELECT MAX(test1.a) FROM test1 INNER JOIN test2 on test1.b = test2.b SETTINGS max_threads=1

before this pr:

1 row in set. Elapsed: 2.024 sec. Processed 10.10 million rows, 130.88 MB (4.99 million rows/s., 64.66 MB/s.)
1 row in set. Elapsed: 2.146 sec. Processed 10.10 million rows, 130.88 MB (4.71 million rows/s., 60.98 MB/s.)
1 row in set. Elapsed: 2.091 sec. Processed 10.10 million rows, 130.88 MB (4.83 million rows/s., 62.60 MB/s.)

after this pr:

1 row in set. Elapsed: 1.347 sec. Processed 10.10 million rows, 130.88 MB (7.50 million rows/s., 97.14 MB/s.)
1 row in set. Elapsed: 1.356 sec. Processed 10.10 million rows, 130.88 MB (7.45 million rows/s., 96.50 MB/s.)
1 row in set. Elapsed: 1.451 sec. Processed 10.10 million rows, 130.88 MB (6.96 million rows/s., 90.22 MB/s.)

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/

Modify your CI run

NOTE: If your merge the PR with modified CI you MUST KNOW what you are doing
NOTE: Checked options will be applied if set before CI RunConfig/PrepareRunConfig step

Include tests (required builds will be added automatically):

Exclude tests:

Extra options:

do not test (only style check)
disable merge-commit (no merge from master before tests)
disable CI cache (job reuse)

Only specified batches in multi-batch jobs:

1
2
3
4

Details

robot-ch-test-poll2 · 2024-05-13T10:15:01Z

This is an automated comment for commit 95e07ce 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
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	❌ failure

Successful checks

Check name	Description	Status
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
Builds	There's no description for the check yet, please add it to tests/ci/ci_config.py:CHECK_DESCRIPTIONS	✅ 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
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. Integration 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
Stateful tests	Runs stateful functional tests for ClickHouse binaries built in various configurations -- release, debug, with sanitizers, etc	✅ success
Stateless tests	Runs stateless functional tests for ClickHouse binaries built in various configurations -- release, debug, with sanitizers, etc	✅ success
Stress test	Runs stateless functional tests concurrently from several clients to detect concurrency-related errors	✅ 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
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	✅ success

KevinyhZou · 2024-05-17T01:41:26Z

the performance improves in join_in_memory

nickitat · 2024-05-27T19:51:55Z

src/Interpreters/RowRefs.h

it is not a good idea to increase RowRefList size. do we really need this field?

yes, this is needed. it will be used to compute the current_offset in addFoundRowAll

nickitat · 2024-05-28T10:29:53Z

src/Interpreters/HashJoin.cpp

imo it would be better to avoid using func pointers (i.e. replace with template parameters) to avoid indirect call here

nickitat · 2024-05-28T10:31:06Z

tests/performance/all_join_opt.xml

why do we test only with max_threads=1?

nickitat · 2024-06-13T23:03:37Z

pls check reported slowdowns in storage_join_direct_join

KevinyhZou · 2024-06-14T04:21:37Z

yes, I see. Maybe it it same problem as join_append_block, has the cache miss problems in the buildOutput for loop.

KevinyhZou · 2024-06-17T01:49:12Z

It seems the reference in the for loop of buildOutputFromRowRefList cause storage_join_direct_join slowdown, and it is fixed now. But still has 9.7% performance slowdown in jon_append_block. @nickitat

nickitat · 2024-06-17T21:35:57Z

src/Interpreters/HashJoin.cpp

and why it is beneficial in the end? just because we filling in one array instead of two?

I think it is because the fill array operation of addFoundRowAll is inside the joinRightColumns for loop, which will scan all the left table rows, and if the right table rows has a lots of matched rows per key, then the time complexity is very high. so I move the for loop of addFoundRowAll to the buildOutput to reduce the time complexity of joinRightColumns. and on another hand, the old code will fill 2 array, and now it fill one, and it can also improve the performance.

But like the case in join_append_block, every row in right table matched is single one, which will not reduce the time complexity, and it slowdown as the buildOutput's for loop cache miss of block. @nickitat

indeed, it could be almost fixed by the following patch: https://pastila.nl/?0169ab09/eb769dfb95b000c681651866b8c89d86#VYcmBdzNznC3fy/9hHzw3Q==
afaiu the similar problem should exist for buildOutputFromRowRef as well, so it makes sense to unify their implementation and use this patch in both cases

indeed, it could be almost fixed by the following patch: https://pastila.nl/?0169ab09/eb769dfb95b000c681651866b8c89d86#VYcmBdzNznC3fy/9hHzw3Q== afaiu the similar problem should exist for buildOutputFromRowRef as well, so it makes sense to unify their implementation and use this patch in both cases

This patch make test case hashjoin_with_large_output 10% slowdown. @nickitat , should we add a setting like a threshold, when the matched rows number exceed this threshold, then we use buildOutFromRowRefList, otherwise, output by a vector of blocks like in this patch?

nickitat · 2024-06-18T22:32:22Z

overall looks ok for me, I'll check perf myself

KevinyhZou · 2024-07-16T09:09:34Z

@nickitat I had add a settings join_output_by_rowlist_perkey_rows_threshold to control not to use output by rowref list if the average rows perkey in right table is below this threshold, and now it has no performance slowdown. could you help to review this?

nickitat

otherwise lgtm

nickitat · 2024-07-23T16:47:11Z

src/Interpreters/HashJoin/AddedColumns.h

pls leave a comment explaining why do we do this. it is really tricky place

KevinyhZou · 2024-08-14T01:49:19Z

could this pr be merged ? @nickitat

nickitat · 2024-08-15T12:05:25Z

thanks for the contribution and your patience )

Algunenano · 2024-09-23T17:40:37Z

src/Core/Settings.h

    \
    M(Bool, join_use_nulls, false, "Use NULLs for non-joined rows of outer JOINs for types that can be inside Nullable. If false, use default value of corresponding columns data type.", IMPORTANT) \
    \
+    M(Int32, join_output_by_rowlist_perkey_rows_threshold, 5, "The lower limit of per-key average rows in the right table to determine whether to output by row list in hash join.", 0) \


The setting is used as unsigned int (size_t) but declared as Int32 here. It makes sense to make it unsigned (before 24.9)

KevinyhZou changed the title ~~Improve all join performance by append RowRefList to LazyOutput directly~~ Improve all join performance by append RowRefList / RowRef to LazyOutput directly May 13, 2024

KevinyhZou changed the title ~~Improve all join performance by append RowRefList / RowRef to LazyOutput directly~~ Improve all join performance by append RowRefList or RowRef to LazyOutput directly May 13, 2024

KevinyhZou changed the title ~~Improve all join performance by append RowRefList or RowRef to LazyOutput directly~~ Improve all join performance by append RowRefList or RowRef to AddedColumns for lazy output May 13, 2024

Algunenano added the can be tested Allows running workflows for external contributors label May 13, 2024

robot-ch-test-poll2 added the pr-performance Pull request with some performance improvements label May 13, 2024

KevinyhZou marked this pull request as draft May 14, 2024 04:14

KevinyhZou force-pushed the improve_hash_join_by_reduce_vector_emplace branch from 9dbaac4 to ec1886b Compare May 14, 2024 10:11

KevinyhZou marked this pull request as ready for review May 17, 2024 01:40

nickitat self-assigned this May 17, 2024

nickitat reviewed May 28, 2024

View reviewed changes

tests/performance/all_join_opt.xml Outdated

Copy link
Copy Markdown

Member

nickitat May 28, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

why do we test only with max_threads=1?

KevinyhZou force-pushed the improve_hash_join_by_reduce_vector_emplace branch from 669f417 to b44ea2f Compare June 12, 2024 11:18

nickitat reviewed Jun 17, 2024

View reviewed changes

nickitat closed this Jun 18, 2024

nickitat reopened this Jun 18, 2024

pamarcos mentioned this pull request Jun 21, 2024

Add system.error_log #65381

Merged

1 task

nickitat approved these changes Jun 25, 2024

View reviewed changes

KevinyhZou force-pushed the improve_hash_join_by_reduce_vector_emplace branch from e1992fc to 397deee Compare July 5, 2024 07:11

nikitamikhaylov mentioned this pull request Jul 23, 2024

min_bytes_to_use_direct_io > 0 can lead to "Cannot read all array values" or even segfault #65690

Closed

nickitat approved these changes Jul 23, 2024

View reviewed changes

KevinyhZou mentioned this pull request Jul 31, 2024

Improve left/inner join performance by rerange right table by keys #60341

Merged

1 task

nickitat approved these changes Aug 8, 2024

View reviewed changes

rebase and resolve conflict

85bd63a

KevinyhZou force-pushed the improve_hash_join_by_reduce_vector_emplace branch from 5f874cc to 85bd63a Compare August 13, 2024 11:20

Merge branch 'master' into improve_hash_join_by_reduce_vector_emplace

95e07ce

nickitat added this pull request to the merge queue Aug 15, 2024

Merged via the queue into ClickHouse:master with commit 418c3fa Aug 15, 2024

robot-clickhouse-ci-1 added the pr-synced-to-cloud The PR is synced to the cloud repo label Aug 15, 2024

baibaichen mentioned this pull request Aug 15, 2024

[CH]Improve all join performance apache/gluten#6870

Open

ycli12 mentioned this pull request Aug 20, 2024

Is there any better way to do join bitmap？ #68598

Closed

Algunenano reviewed Sep 23, 2024

View reviewed changes

Conversation

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

Uh oh!

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

Include tests (required builds will be added automatically):

Exclude tests:

Extra options:

Only specified batches in multi-batch jobs:

Uh oh!

robot-ch-test-poll2 commented May 13, 2024 • edited by robot-ch-test-poll Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

KevinyhZou commented May 17, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

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!

nickitat commented Jun 13, 2024

Uh oh!

KevinyhZou commented Jun 14, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

KevinyhZou commented Jun 17, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

KevinyhZou Jun 18, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

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!

KevinyhZou Jul 8, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

nickitat commented Jun 18, 2024

Uh oh!

KevinyhZou commented Jul 16, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

nickitat 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!

KevinyhZou commented Aug 14, 2024

Uh oh!

nickitat commented Aug 15, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

KevinyhZou commented May 13, 2024 •

edited

Loading

robot-ch-test-poll2 commented May 13, 2024 •

edited by robot-ch-test-poll

Loading

KevinyhZou commented May 17, 2024 •

edited

Loading

KevinyhZou commented Jun 14, 2024 •

edited

Loading

KevinyhZou commented Jun 17, 2024 •

edited

Loading

KevinyhZou Jun 18, 2024 •

edited

Loading

KevinyhZou Jul 8, 2024 •

edited

Loading

KevinyhZou commented Jul 16, 2024 •

edited

Loading