perf(sql): improve performance of linear as-of join algo#6338
perf(sql): improve performance of linear as-of join algo#6338bluestreak01 merged 22 commits intomasterfrom
Conversation
|
Important Review skippedAuto reviews are disabled on this repository. Please check the settings in the CodeRabbit UI or the You can disable this status message by setting the WalkthroughAdds a single-symbol ASOF join cursor and integrates it into SQL code generation, refactors switch blocks to switch expressions, adds column-access helper overloads for RecordCursor, updates pattern matching and exception flow in AsyncFilteredRecordCursor, and adds tests for the single-symbol ASOF path. Changes
Sequence Diagram(s)sequenceDiagram
%%{init: {"themeVariables":{"sequenceActorBackground":"#f6f8fa","actorBorder":"#cbd5e1"}}}%%
actor Client
participant SqlCodeGenerator
participant MasterFactory
participant SlaveFactory
participant AsOfSingleFactory
participant AsOfLightFactory
participant AsOfCursor as "AsOfSingleSymbolJoinCursor"
Client->>SqlCodeGenerator: compile SELECT ... ASOF ... WITH HINT ASOF_LINEAR_SEARCH
SqlCodeGenerator->>MasterFactory: build master factory
SqlCodeGenerator->>SlaveFactory: analyze slave, detect single-symbol?
alt single-symbol and linear hint
SqlCodeGenerator->>AsOfSingleFactory: instantiate AsOfJoinSingleSymbolRecordCursorFactory
AsOfSingleFactory->>AsOfCursor: create inner cursor, build joinKeyMap from slave
AsOfCursor-->>MasterFactory: drive master rows, probe joinKeyMap for symbol key
else fallback
SqlCodeGenerator->>AsOfLightFactory: instantiate AsOfJoinLightRecordCursorFactory
AsOfLightFactory->>SlaveFactory: build slave time frame structure
end
SqlCodeGenerator->>Client: return compiled plan using chosen factory
Estimated code review effort🎯 4 (Complex) | ⏱️ ~45 minutes
Possibly related PRs
Suggested labels
Suggested reviewers
Pre-merge checks and finishing touches❌ Failed checks (1 warning)
✅ Passed checks (2 passed)
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. Comment |
|
@CodeRabbit review |
✅ Actions performedReview triggered.
|
There was a problem hiding this comment.
Actionable comments posted: 2
🧹 Nitpick comments (5)
core/src/main/java/io/questdb/griffin/SqlCodeGenerator.java (2)
314-316: Remove redundant static import
import static io.questdb.griffin.model.QueryModel.*;already bringsQUERY; the extra explicit static import is unnecessary.- import static io.questdb.griffin.model.QueryModel.QUERY; + // QUERY already available via wildcard static import above
5298-5302: Pattern-matchinginstanceofintroduces unusedaf
afisn’t referenced; either use the bound var or keep classicinstanceof.- if (!(f instanceof WindowFunction af)) { + if (!(f instanceof WindowFunction)) {core/src/main/java/io/questdb/griffin/engine/join/AsOfJoinSingleSymbolRecordCursorFactory.java (3)
230-243: Consider adding circuit breaker check for long-running queries.The while loop could iterate through many slave records without checking for query cancellation. For large slave cursors, this might delay cancellation.
Consider adding a circuit breaker check:
final Record rec = slaveCursor.getRecord(); while (slaveCursor.hasNext()) { + circuitBreaker.statefulThrowExceptionIfTripped(); slaveTimestamp = scaleTimestamp(rec.getTimestamp(slaveTimestampIndex), slaveTimestampScale);Note: You'll need to pass the circuit breaker to the hasNext method or store it as a field if this approach is adopted.
215-218: Consider extracting map update logic to reduce duplication.The map update logic appears twice (lines 215-218 and 235-238) with identical structure.
Consider extracting to a helper method:
private void updateJoinKeyMap(Record rec, int symbolColumnIndex) { MapKey key = joinKeyMap.withKey(); key.putInt(rec.getInt(symbolColumnIndex)); MapValue value = key.createValue(); value.putLong(0, rec.getRowId()); }Then call it from both locations.
Also applies to: 235-238
249-258: Tolerance recheck is correct but subtle.The tolerance check on line 255 is necessary because map entries may have been added during previous master record iterations with different tolerance windows. A brief comment would help future maintainers understand why this recheck is required.
Consider adding a clarifying comment:
key = joinKeyMap.withKey(); key.putInt(slaveSymbolKey); value = key.findValue(); if (value != null) { + // Recheck tolerance: map entry may have been added for a previous master record slaveCursor.recordAt(slaveRecord, value.getLong(0)); slaveTimestamp = scaleTimestamp(slaveRecord.getTimestamp(slaveTimestampIndex), slaveTimestampScale); record.hasSlave(toleranceInterval == Numbers.LONG_NULL || slaveTimestamp >= masterTimestamp - toleranceInterval);
📜 Review details
Configuration used: Path: .coderabbit.yaml
Review profile: CHILL
Plan: Pro
📒 Files selected for processing (8)
core/src/main/java/io/questdb/griffin/SqlCodeGenerator.java(9 hunks)core/src/main/java/io/questdb/griffin/engine/functions/date/GenerateSeriesTimestampStringRecordCursorFactory.java(3 hunks)core/src/main/java/io/questdb/griffin/engine/join/AsOfJoinSingleSymbolRecordCursorFactory.java(1 hunks)core/src/main/java/io/questdb/griffin/engine/join/AsofJoinColumnAccessHelper.java(2 hunks)core/src/main/java/io/questdb/griffin/engine/join/SingleSymbolColumnAccessHelper.java(2 hunks)core/src/main/java/io/questdb/griffin/engine/table/AsyncFilteredRecordCursor.java(1 hunks)core/src/main/java/io/questdb/std/Hash.java(1 hunks)core/src/test/java/io/questdb/test/griffin/AsOfJoinTest.java(1 hunks)
⏰ Context from checks skipped due to timeout of 90000ms. You can increase the timeout in your CodeRabbit configuration to a maximum of 15 minutes (900000ms). (3)
- GitHub Check: New pull request (Check Changes Check changes)
- GitHub Check: build
- GitHub Check: build
🔇 Additional comments (13)
core/src/main/java/io/questdb/griffin/engine/functions/date/GenerateSeriesTimestampStringRecordCursorFactory.java (4)
83-87: LGTM! Clean switch expression refactor.The switch expression correctly maps timestamp types to their corresponding metadata. The refactor improves readability while maintaining the same behavior.
205-209: LGTM! Switch expression correctly identifies fixed-length time units.The logic appropriately returns
falsefor variable-length units ('M', 'y') that don't support random access, andtruefor all fixed-length units. The refactor is clean and maintains existing semantics.
217-228: LGTM! Switch expression correctly maps time units to timestamp conversions.The refactor cleanly converts each unit to its corresponding timestamp value. The method is only invoked when
supportsRandomAccess()returns true (excluding 'M' and 'y'), and upstream validation at line 148-151 ensures only valid units reach this point.
235-249: LGTM! Switch expression provides clear validation for time unit characters.The refactor correctly identifies all valid time units and returns the appropriate boolean. The inclusion of both 'h' and 'H' for hours, and 'u' and 'U' for micros provides good compatibility coverage.
core/src/main/java/io/questdb/griffin/SqlCodeGenerator.java (3)
196-196: Import for single‑symbol ASOF pathImporting AsOfJoinSingleSymbolRecordCursorFactory looks correct and scoped.
2672-2700: Switch expression simplification for CROSS OUTER joins LGTMCleaner and equivalent control flow; null‑row factories preserved per side.
4388-4402: Switch expression for select model LGTMBranching is clearer; fall‑through to joins/no‑select is preserved.
core/src/main/java/io/questdb/griffin/engine/join/AsOfJoinSingleSymbolRecordCursorFactory.java (6)
55-89: LGTM! Excellent resource management.The constructor properly handles resource cleanup in the exception path, ensuring the joinKeyMap is freed before calling close() and rethrowing.
96-109: LGTM! Proper cursor lifecycle management.The getCursor method correctly handles cleanup of both master and slave cursors in the exception path.
129-135: LGTM! Complete resource cleanup.All resources are properly freed.
152-173: LGTM! Efficient timestamp scaling logic.The optimization to avoid timestamp scaling when types match is good for performance.
175-194: LGTM! Standard cursor lifecycle methods.The close() method properly guards against double-close and resets state.
266-301: LGTM! Complete state management.The toTop() method correctly resets all state, and the of() method properly handles map reopening for cursor reuse.
|
@CodeRabbit review |
✅ Actions performedReview triggered.
|
|
@CodeRabbit review. Make sure NoOpAccessor cannot be passed to asof join implementations that expect a functioning accessor |
🧩 Analysis chain🏁 Script executed: Length of output: 0 🏁 Script executed: Length of output: 17413 🏁 Script executed: Length of output: 3577 🏁 Script executed: Length of output: 3094 🏁 Script executed: Length of output: 6299 🏁 Script executed: Length of output: 7285 🏁 Script executed: Length of output: 5828 🏁 Script executed: Length of output: 2119 🏁 Script executed: Length of output: 10966 🏁 Script executed: Length of output: 4065 🏁 Script executed: Length of output: 2641 🏁 Script executed: Length of output: 138 🏁 Script executed: Length of output: 170 🏁 Script executed: Length of output: 0 🏁 Script executed: Length of output: 0 🏁 Script executed: Length of output: 3420 @bluestreak01, I've analyzed the code paths and found that while there is protection in place, it could be strengthened with explicit assertions. Here's what I found: Current ProtectionThe code already prevents // Line 2882-2884
AsofJoinColumnAccessHelper columnAccessHelper = createAsofColumnAccessHelper(masterMetadata, slaveMetadata, selfJoin);
boolean isOptimizable = columnAccessHelper != NoopColumnAccessHelper.INSTANCE;
if (isOptimizable) {
// Only creates AsOfJoinSingleSymbolRecordCursorFactory when not NoopColumnAccessHelper
master = new AsOfJoinSingleSymbolRecordCursorFactory(..., columnAccessHelper, ...);
}If not optimizable, it falls back to Recommended ImprovementHowever, to fail fast and prevent future bugs, I recommend adding defensive assertions in the constructors: AsOfJoinSingleSymbolRecordCursorFactory.java: public AsOfJoinSingleSymbolRecordCursorFactory(
CairoConfiguration configuration,
RecordMetadata metadata,
RecordCursorFactory masterFactory,
RecordCursorFactory slaveFactory,
@Transient ColumnTypes joinColumnTypes,
@Transient ColumnTypes valueTypes,
int columnSplit,
int slaveSymbolColumnIndex,
AsofJoinColumnAccessHelper columnAccessHelper,
JoinContext joinContext,
long toleranceInterval
) {
super(metadata, joinContext, masterFactory, slaveFactory);
assert columnAccessHelper != NoopColumnAccessHelper.INSTANCE : "NoopColumnAccessHelper cannot be used with AsOfJoinSingleSymbolRecordCursorFactory";
this.slaveSymbolColumnIndex = slaveSymbolColumnIndex;
this.columnAccessHelper = columnAccessHelper;
// ... rest of constructorThe same assertion should be added to:
These factories all use Why This MattersWithout the assertion, if a bug were introduced or the code were refactored, Would you like me to proceed with adding these assertions? ✅ Actions performedReview triggered.
|
…sof-linear-symbol
[PR Coverage check]😍 pass : 179 / 200 (89.50%) file detail
|
optimisation for as-of joins on single symbol, such as:
It is activated with "ASOF_LINEAR_SEARCH" hint and is non-default, as it is a variant of linear as-of algo.
The performance improvement comes from re-indexing symbols and joining on "int" rather than symbol "text"