jiayuasu opened a new issue, #3034: URL: https://github.com/apache/sedona/issues/3034
Follow-up to the Box3D EPIC ([#2973](https://github.com/apache/sedona/issues/2973)) and PR [#3032](https://github.com/apache/sedona/pull/3032). PR #3032 wired Box3D-on-Box3D `ST_Intersects` / `ST_Contains` into the planner; `ST_3DDWithin` is still unplanned, so distance joins on the 3D predicate run as O(n × m) row-by-row. This issue gives `ST_3DDWithin` the same indexed treatment. ## Approach Same XY-projection trick used in #3032, applied to the existing distance-join path (`toExpandedEnvelopeRDD` + `DistanceJoinExec` / broadcast-index distance join). Correctness rests on a one-sided inequality: if `||A − B||_3D ≤ d`, then the XY distance between A's and B's XY footprints is also `≤ d`. So expanding each XY rectangle by `d` and probing the 2D R-tree gives a valid superset filter; the actual 3D refine runs at the per-pair condition step using `Predicates.dWithin3D`. Wires both inferrable branches of `ST_3DDWithin`: - `ST_3DDWithin(Geometry, Geometry, d)` — the R-tree key is the Geometry's existing 2D envelope, expanded by `d`. Refine uses JTS `Distance3DOp` on the original geometries. - `ST_3DDWithin(Box3D, Box3D, d)` — the R-tree key is the XY footprint rectangle (already materialised in `TraitJoinQueryBase.shapeToGeometry` by #3032), expanded by `d`. Refine uses `Predicates.dWithin3D(Box3D, Box3D, d)`. ## Implementation - `JoinQueryDetector`: add a `case ST_3DDWithin(Seq(leftShape, rightShape, distance))` arm that produces a `JoinQueryDetection` with `SpatialPredicate.INTERSECTS` for the R-tree pass, `distance = Some(distance)` so the executor builds an expanded envelope, and `extraCondition = Some(condition)` (the full original predicate) so the per-pair filter enforces the 3D distance. Same shape as the existing `ST_DWithin` 3-arg arm but no Geography branching. - No changes to `TraitJoinQueryBase` required — Box3D's XY-footprint materialisation already lands there from #3032, and `toExpandedEnvelopeRDD` already calls into it. - `OptimizableJoinCondition`: add `_: ST_3DDWithin` to the whitelist of distance-join predicates so `isDistanceJoinOptimizable` will accept it. ## Tests Add to `Box3DJoinSuite` (or a new `Box3DDWithinJoinSuite`): - `ST_3DDWithin(Box3D, Box3D, d)` broadcast distance join with mixed-axis fixture, including discriminating rows that overlap in XY-expanded-by-d but exceed `d` in 3D — must be rejected by the refine. - `ST_3DDWithin(Geometry, Geometry, d)` broadcast distance join verifying the Geometry-input path also routes through `DistanceJoinExec` / `BroadcastIndexJoinExec`. - Non-broadcast partition path. - Inverted-bound Box3D throw at the join boundary (already covered for `ST_Intersects` / `ST_Contains` in #3032; `ST_3DDWithin` shares the same `shapeToGeometry` path, so this should just work). ## Out of scope - No new index type — reuses the existing 2D R-tree and `toExpandedEnvelopeRDD` plumbing. - Filter pushdown for `ST_3DDWithin` (would need Parquet inequalities on the six double leaves; tracked separately). -- 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]
