guptashivam04 opened a new pull request, #70302:
URL: https://github.com/apache/doris/pull/70302
### Background
`st_contains`, `st_within`, `st_intersects`, `st_touches` and `st_disjoint`
share one BE implementation, `StRelationFunction`. Shapes travel between
functions in their encoded form, so the relation function decodes both
arguments before comparing them. Decoding a polygon also validates it
(`S2Polygon::IsValid()`).
### What problem does this PR solve?
Issue Number: None
Related PR: None
PR Type: Performance
Problem Summary:
A filter like `ST_Contains(ST_Polygon('POLYGON ((...))'), ST_Point(lng,
lat)) = 1` decodes and validates the constant polygon again for every row.
Validation builds an S2 index over all edges, so the cost per row grows with
the vertex count. With a 12,864-vertex polygon that is about 1 ms per row: 20k
candidate rows take about 17 s, while the scan itself takes about 20 ms. This
PR decodes a constant argument once per scan thread and makes the point-on-edge
check in `GeoPolygon::contains` cheaper. Query results do not change.
### Details
- **Why it was slow:**
- In a flame graph of the query above, 85% of the time is in
`GeoPolygon::decode` → `S2Polygon::IsValid` → `MutableS2ShapeIndex` building,
once per row.
- Another 13% is the point-on-edge loop in `GeoPolygon::contains`. For
every edge it converts both end vertices and the point to `S2LatLng`, which
means trig calls, so 3 × vertices conversions per row.
- **Optimization:**
- `StRelationFunction` decodes a `ColumnConst` argument once. It keeps the
decoded shape in a thread-local `FunctionContext` state, keyed by the encoded
bytes, so later blocks reuse it, and a different constant is decoded again.
- Non-constant arguments are decoded per row as before.
- `GeoPolygon` caches the lat/lng of its vertices on first use by
`contains(point)`.
- The edge loop first skips edges whose bounding box, grown by 2× the
tolerance, does not contain the point. It then runs the same
`project_distance(...) < TOLERANCE` check on the same values as before, so the
result is the same.
- The unused `StContainsState` is replaced by the new state struct.
- **Results:**
- 3 BEs, 3M-row table, Release build on macOS arm64.
- The baseline is the same tree without this patch.
- Each figure is the median of 3 runs, in ms.
| Rows reaching st_contains | Polygon vertices | Before | After |
|---:|---:|---:|---:|
| 2,041 | 1,000 | 112 | 21 |
| 2,041 | 12,864 | 1,716 | 42 |
| 20,662 | 100 | 117 | 14 |
| 20,662 | 1,000 | 1,048 | 18 |
| 20,662 | 10,000 | 13,686 | 63 |
| 20,662 | 12,864 | 17,383 | 83 |
| 245,382 | 100 | 1,273 | 39 |
| 245,382 | 1,000 | 13,255 | 83 |
| 245,382 | 12,864 | not run (~4 min) | 523 |
Small polygons (10 vertices) are unchanged, within noise.
- **Applicability and cost:**
- This helps any spatial relation function with a constant shape argument;
polygons gain the most.
- Each scan thread keeps one copy of the encoded constant and its decoded
shape: about 0.3 MB plus the S2 index for a 12,864-vertex polygon.
- `st_intersects`, `st_touches` and `st_disjoint` against points get the
decode saving but still loop over edges in `polygon_touch_point`. That can be a
follow-up.
### Testing
- **New BE unit tests:**
- `function_geo_st_contains_const_polygon`: a constant polygon over many
rows, as the first argument of `st_contains` and the second of `st_within`,
plus an invalid constant.
- `function_geo_st_contains_const_polygon_across_blocks`: one
`FunctionContext` across blocks whose constant changes.
- `GeoTypesTest.polygon_contains_point_near_edge`: points just inside and
outside the 1e-6 edge tolerance, on outer and hole edges, with repeated calls
on the same polygon.
- **Result equivalence on a local 3-BE cluster:**
- Compared old vs new binaries on about 97k points placed on, 3e-7 / 9e-7
/ 1.1e-6 / 3e-6 off, and between the edges and vertices of three polygons
(12,864, 1,000 and 100 vertices).
- Covered `st_contains`, `st_within`, `st_intersects`, `st_touches` and
`st_disjoint`, a constant multipolygon, a per-row (non-constant) polygon, and
polygon-in-polygon.
- Count, sum(id) and sum(id²) for TRUE, FALSE and NULL are identical
across all 18 checks.
- Match counts in the timing table are identical before and after.
### Release note
Spatial relation functions (`ST_Contains`, `ST_Within`, `ST_Intersects`,
`ST_Touches`, `ST_Disjoint`) with a constant polygon argument are much faster
when the polygon has many vertices.
### Check List (For Author)
- Behavior changed: No
- Does this need documentation: No
- Pre-submission status: Partially verified: the new unit tests compile
against master but were not run locally (no BE UT build here). The same cases
were checked through SQL on a local cluster, and CI will run them.
--
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]
