Skip to content

perf(sql): speed up ORDER BY on SYMBOL columns#6870

Merged
bluestreak01 merged 47 commits intomasterfrom
sort_symbol_opt
Mar 13, 2026
Merged

perf(sql): speed up ORDER BY on SYMBOL columns#6870
bluestreak01 merged 47 commits intomasterfrom
sort_symbol_opt

Conversation

@kafka1991
Copy link
Copy Markdown
Collaborator

@kafka1991 kafka1991 commented Mar 12, 2026

Depends on #6862

Summary

  • Eliminates the temporary DirectIntList used when building symbol rank maps. Replaces it with in-place permutation inversion after quicksort, reducing extra space from O(N) to O(1) (N = symbol count). Mainly benefits high-cardinality symbol columns.
  • Replaces string comparison (getSym() + Chars.compare) with rank-based comparison (getInt() + rank map lookup) when sorting SYMBOL columns that have static symbol tables. At cursor open, a rank map maps each symbol key to its alphabetical rank; the comparator then compares ranks instead of strings.
  • Applies the optimization to all comparator-based sort paths: tree-based sort cursors, top-K cursors, window function tree comparators (CachedWindowRecordCursorFactory), and window function internal comparators (rank(), percent_rank()).
  • Non-static symbol columns (e.g. CAST(str AS SYMBOL)) fall back to the original getSym() + Chars.compare path.

Benchmark

R-B tree sort path (ORDER BY includes a STRING column, so encoded sort is not used):

SELECT *, 'ab' FROM fx_trades t
WHERE t.timestamp IN '$now-130h..$now'
ORDER BY t.symbol, t.ecn, t.counterparty, t.passive, 'ab';

7,235,498 rows:

Branch Execute time
master 6.25s
branch 5.70s

@coderabbitai
Copy link
Copy Markdown

coderabbitai bot commented Mar 12, 2026

Important

Review skipped

Auto reviews are disabled on this repository. Please check the settings in the CodeRabbit UI or the .coderabbit.yaml file in this repository. To trigger a single review, invoke the @coderabbitai review command.

⚙️ Run configuration

Configuration used: Path: .coderabbit.yaml

Review profile: CHILL

Plan: Pro

Run ID: 3da25f64-4db1-410c-9cf4-09c5daa15192

You can disable this status message by setting the reviews.review_status to false in the CodeRabbit configuration file.

Use the checkbox below for a quick retry:

  • 🔍 Trigger review
✨ Finishing Touches
🧪 Generate unit tests (beta)
  • Create PR with unit tests
  • Post copyable unit tests in a comment
  • Commit unit tests in branch sort_symbol_opt
📝 Coding Plan
  • Generate coding plan for human review comments

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

Comment @coderabbitai help to get the list of available commands and usage tips.

@kafka1991 kafka1991 changed the title perf(sql): speed up symbol sort perf(sql): speed up ORDER BY on SYMBOL columns using pre-built rank maps Mar 12, 2026
@kafka1991 kafka1991 changed the title perf(sql): speed up ORDER BY on SYMBOL columns using pre-built rank maps perf(sql): speed up ORDER BY on SYMBOL columns Mar 12, 2026
kafka1991 and others added 4 commits March 12, 2026 15:51
# Conflicts:
#	core/src/main/resources/io/questdb/bin/linux-aarch64/libquestdb.so
#	core/src/main/resources/io/questdb/bin/windows-x86-64/libquestdb.dll
@kafka1991 kafka1991 added Performance Performance improvements SQL Issues or changes relating to SQL execution labels Mar 12, 2026
bluestreak01
bluestreak01 previously approved these changes Mar 13, 2026
@glasstiger
Copy link
Copy Markdown
Contributor

[PR Coverage check]

😍 pass : 300 / 316 (94.94%)

file detail

path covered line new line coverage
🔵 io/questdb/griffin/engine/RecordComparator.java 0 1 00.00%
🔵 io/questdb/griffin/engine/window/CachedWindowRecordCursorFactory.java 11 19 57.89%
🔵 io/questdb/griffin/engine/orderby/LimitedSizeSortedLightRecordCursorFactory.java 3 4 75.00%
🔵 io/questdb/griffin/engine/orderby/SortKeyEncoder.java 60 64 93.75%
🔵 io/questdb/griffin/engine/orderby/EncodedSortRecordCursor.java 30 31 96.77%
🔵 io/questdb/griffin/engine/functions/window/PercentRankFunctionFactory.java 42 43 97.67%
🔵 io/questdb/griffin/engine/orderby/EncodedSortLightRecordCursor.java 28 28 100.00%
🔵 io/questdb/griffin/engine/orderby/SortedRecordCursor.java 6 6 100.00%
🔵 io/questdb/griffin/engine/orderby/SortedLightRecordCursorFactory.java 1 1 100.00%
🔵 io/questdb/griffin/engine/orderby/LimitedSizeSortedLightRecordCursor.java 3 3 100.00%
🔵 io/questdb/cairo/DefaultCairoConfiguration.java 1 1 100.00%
🔵 io/questdb/griffin/engine/orderby/LimitedSizePartiallySortedLightRecordCursor.java 3 3 100.00%
🔵 io/questdb/PropertyKey.java 1 1 100.00%
🔵 io/questdb/griffin/engine/table/AsyncTopKAtom.java 8 8 100.00%
🔵 io/questdb/griffin/engine/orderby/RecordComparatorCompiler.java 79 79 100.00%
🔵 io/questdb/griffin/SqlCodeGenerator.java 1 1 100.00%
🔵 io/questdb/cairo/CairoConfigurationWrapper.java 1 1 100.00%
🔵 io/questdb/PropServerConfiguration.java 2 2 100.00%
🔵 io/questdb/griffin/engine/functions/window/RankFunctionFactory.java 15 15 100.00%
🔵 io/questdb/griffin/engine/orderby/SortedLightRecordCursor.java 4 4 100.00%
🔵 io/questdb/griffin/engine/orderby/SortedRecordCursorFactory.java 1 1 100.00%

@bluestreak01 bluestreak01 merged commit 9ebbf17 into master Mar 13, 2026
53 checks passed
@bluestreak01 bluestreak01 deleted the sort_symbol_opt branch March 13, 2026 13:26
maciulis pushed a commit to maciulis/questdb that referenced this pull request Mar 16, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

Performance Performance improvements SQL Issues or changes relating to SQL execution

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants