Speed up DISTINCT in order, sort-merge joins, LIMIT BY and negative LIMIT BY#106502
Conversation
clickhouse-gh
Bot
added
the
pr-performance
|
📊 Cloud Performance Report ✅ AI verdict: This PR adds a galloping plus binary-search fast path for finding equal-value runs in sorted columns (getEqualRangeEndAssumeSorted), wired only into sort-merge join equal-length detection and the LIMIT BY / negative-LIMIT-BY sorted-stream transforms. ClickBench queries use neither merge joins nor LIMIT BY, so the flagged improvements on Q4, Q28, and Q32 cannot be attributed to this change and read as run-to-run variance across the two builds; they have been downgraded. Notably the tpch_adapted_1_official suite, which is where join and ordering changes would actually surface, showed no per-query shifts, reinforcing that the ClickBench deltas are noise rather than a real effect of this PR. clickbenchFlagged queries (3 of 43)
q-value = BH-FDR adjusted p; smaller is stronger evidence. MIRAI flags a query when q < fdr_q (default 0.10) — the value the verdict is based on. tpch_adapted_1_official🟢 No significant changes Debug info
|
nihalzp
changed the title
DISTINCT in order, sort-merge joins, ORDER BY ... WITH FILL and LIMIT BYDISTINCT in order, sort-merge joins, ORDER BY ... WITH FILL, LIMIT BY and negative LIMIT BY
![clickhouse-gh[bot]](https://avatars.githubusercontent.com/in/928874?s=60&v=4){kind=small}
Algunenano
left a comment
Algunenano
left a comment
There was a problem hiding this comment.
@nihalzp It seems #106502 (comment) and #106502 (comment) are still unaddressed.
You mentioned Okay, I will keep it safe and not apply it for Float LC. but didn't change it AFAICT.
ColumnLowCardinality::getEqualRangeEndAssumeSorted would need to deal with floats, and nullable(float). And after that uniqueInsertCanonicalFloat is unused and should be removed
I requested review before I made that comment and have not gotten chance to work on it yet :'. I will work on it soon. |
LLVM Coverage ReportChanged lines: Changed C/C++ lines covered by tests: 482/490 (98.37%) | Lost baseline coverage (was covered on master, now uncovered in this PR): 5 line(s) · Uncovered code |
9f7b790
robot-ch-test-poll2
added
the
pr-synced-to-cloud
4 participants
The PR tries to optimize the scenario when we have a sorted
IColumnand we want to find the end row number of equal key in the column. In many places, we do normal linear scan and in some places, we do binary search but have duplicate implementation. This PR unifies this utility it as aIColumnmethod and allows a single optimized binary search implementation for all use cases.Changelog category (leave one):
Changelog entry (a user-readable short description of the changes that goes into CHANGELOG.md):
Speed up operators that scan a sorted stream for runs of equal key values —
DISTINCTin order,LIMIT BYin order, negativeLIMIT BYin order,full_sorting_mergeandpartial_mergejoins.