Xuanwo opened a new pull request, #23738: URL: https://github.com/apache/datafusion/pull/23738
## Which issue does this PR close? - Closes #318. ## Rationale for this change Time-series and ordered-event workloads often need to match each left row with the nearest eligible right row, optionally within equality-key groups. Expressing this through correlated subqueries is awkward and does not give the physical planner a dedicated ordered streaming execution contract. This PR adds a first-class, left-preserving ASOF join for bounded inputs. ## What changes are included in this PR? - Add `ASOF JOIN ... MATCH_CONDITION (...)` SQL planning and unparsing, plus logical-plan, `LogicalPlanBuilder`, and `DataFrame` APIs. - Add `AsOfJoinExec`, which consumes inputs ordered by equality keys and the match expression, preserves state across input/output batches, and supports `<`, `<=`, `>`, and `>=` nearest-match directions. - Integrate type coercion, projection/filter optimization, physical distribution and ordering requirements, statistics, and metrics. - Add logical and physical protobuf round trips. Substrait serialization fails closed until an ASOF extension is defined. - Add end-to-end and physical-plan benchmarks covering ordered input reuse, optimizer-inserted sort/repartition, wide payloads, dictionary payloads, and descending successor matching. ## Are these changes tested? Yes. The following passed on commit `13ef0651144fda009e5bf5e4e268c753381949e5`: - `./dev/rust_lint.sh` - `cargo clippy --all-targets --all-features -- -D warnings` - `cargo check --all --tests --benches` - `RUST_MIN_STACK=33554432 RUST_BACKTRACE=1 cargo test --profile ci --exclude datafusion-examples --exclude datafusion-benchmarks --exclude datafusion-cli --workspace --lib --tests --bins --features avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption` - `cargo bench -p datafusion-physical-plan --bench asof_join --features test_utils -- --quick` - `cargo run --release -p datafusion-benchmarks --bin dfbench -- asof --iterations 3 --partitions 4` ### Benchmark Measured on an Apple M4 Max (Darwin arm64), using four DataFusion partitions. These are absolute results: `main` cannot parse or plan the ASOF workload, so there is no equivalent main-branch baseline. | Workload | Output rows | Median elapsed | | --- | ---: | ---: | | Ordered predecessor, no equality keys | 1,000,000 | 249.8 ms | | Grouped predecessor with optimizer sort/repartition | 1,000,000 | 101.4 ms | | Grouped predecessor with 256-byte payload | 250,000 | 30.6 ms | | Ordered successor with descending inputs | 500,000 | 132.3 ms | The physical-plan benchmark completed at approximately 33 ms for 100,000-row Int64, wide UTF-8, and dictionary payload cases. ## Are there any user-facing changes? Yes. Users can construct ASOF joins through SQL, `LogicalPlanBuilder`, and `DataFrame`. The initial contract is left-preserving, supports optional equality keys plus one ordered match condition, and rejects unbounded inputs. Existing join behavior is unchanged. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
