You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@sedona.apache.org by "zhangfengcdt (via GitHub)" <gi...@apache.org> on 2025/09/10 22:59:55 UTC
[PR] Troubleshoot performance issue in spatial bench issue in knn join - q9 [sedona-db]
zhangfengcdt opened a new pull request, #53:
URL: https://github.com/apache/sedona-db/pull/53
(no comment)
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "Kontinuation (via GitHub)" <gi...@apache.org>.
Kontinuation commented on code in PR #53:
URL: https://github.com/apache/sedona-db/pull/53#discussion_r2338854370
##########
rust/sedona-spatial-join/src/index.rs:
##########
@@ -235,25 +235,76 @@ impl SpatialIndexBuilder {
geom_idx_vec
}
- /// Build cached geometries and positions for KNN queries to avoid repeated WKB conversions
- fn build_cached_geometries(
- indexed_batches: &[IndexedBatch],
- ) -> (Vec<Geometry<f64>>, Vec<(i32, i32)>) {
+ /// Build cached geometries for KNN queries to avoid repeated WKB conversions
+ fn build_cached_geometries(indexed_batches: &[IndexedBatch]) -> Vec<Geometry<f64>> {
let mut geometries = Vec::new();
- let mut geometry_positions = Vec::new();
- for (batch_idx, indexed_batch) in indexed_batches.iter().enumerate() {
- for (row_idx, wkb_opt) in indexed_batch.geom_array.wkbs().iter().enumerate() {
+ for indexed_batch in indexed_batches.iter() {
+ for wkb_opt in indexed_batch.geom_array.wkbs().iter() {
if let Some(wkb) = wkb_opt.as_ref() {
if let Ok(geom) = item_to_geometry(wkb) {
geometries.push(geom);
- geometry_positions.push((batch_idx as i32, row_idx as i32));
}
}
}
}
- (geometries, geometry_positions)
+ geometries
+ }
+
+ /// Estimate the memory usage of cached geometries for memory reservation
+ /// This provides a rough approximation of the memory used by geo::Geometry objects
+ fn estimate_geometry_memory(geometries: &[Geometry<f64>]) -> usize {
+ // Rough estimation based on geometry types:
+ // - Each Point: ~32 bytes (2 f64s + overhead)
+ // - Each LineString: base size + (num_coords * 16 bytes)
+ // - Each Polygon: base size + exterior ring + interior rings
+ // - Add some overhead for Vec storage and enum variants
+
+ const BASE_GEOMETRY_SIZE: usize = 64; // Base size for geometry enum + overhead
+ const POINT_SIZE: usize = 16; // 2 f64s (x, y)
+ const COORDINATE_SIZE: usize = 16; // 2 f64s per coordinate
+
+ geometries
+ .iter()
+ .map(|geom| {
+ BASE_GEOMETRY_SIZE
+ + match geom {
+ Geometry::Point(_) => POINT_SIZE,
+ Geometry::LineString(ls) => ls.coords().count() * COORDINATE_SIZE,
+ Geometry::Polygon(poly) => {
+ let exterior_coords =
+ poly.exterior().coords().count() * COORDINATE_SIZE;
+ let interior_coords: usize = poly
+ .interiors()
+ .iter()
+ .map(|ring| ring.coords().count() * COORDINATE_SIZE)
+ .sum();
+ exterior_coords + interior_coords
+ }
+ Geometry::MultiPoint(mp) => mp.0.len() * POINT_SIZE,
+ Geometry::MultiLineString(mls) => mls
+ .0
+ .iter()
+ .map(|ls| ls.coords().count() * COORDINATE_SIZE)
+ .sum::<usize>(),
+ Geometry::MultiPolygon(mp) => mp
+ .0
+ .iter()
+ .map(|poly| {
+ let exterior = poly.exterior().coords().count() * COORDINATE_SIZE;
+ let interiors: usize = poly
+ .interiors()
+ .iter()
+ .map(|ring| ring.coords().count() * COORDINATE_SIZE)
+ .sum();
+ exterior + interiors
+ })
+ .sum::<usize>(),
+ _ => 256, // Conservative estimate for other geometry types
+ }
+ })
+ .sum()
}
Review Comment:
This is overly complicated but less accurate than directly using the length of WKB buffer. I'd rather just take the length of WKB buffer plus or multiply some overhead.
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "zhangfengcdt (via GitHub)" <gi...@apache.org>.
zhangfengcdt commented on PR #53:
URL: https://github.com/apache/sedona-db/pull/53#issuecomment-3278014965
> Which side got cached? The trip table will grow linearly together with Scale Factor. If this just caches the buildings table, we should be good.
Yes, this is only cache geometries on the buildings dataset for the Q9.
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "Kontinuation (via GitHub)" <gi...@apache.org>.
Kontinuation commented on code in PR #53:
URL: https://github.com/apache/sedona-db/pull/53#discussion_r2338436235
##########
rust/sedona-spatial-join/src/index.rs:
##########
@@ -331,6 +358,14 @@ pub(crate) struct SpatialIndex {
/// Cleared on `SpatialIndex` drop
#[expect(dead_code)]
reservation: MemoryReservation,
+
+ /// Cached vector of geometries for KNN queries to avoid repeated WKB-to-geometry conversions
+ /// This is computed once during index building for performance optimization
+ cached_geometries: Vec<Geometry<f64>>,
+
+ /// Cached position mapping for geometries to avoid recomputing during KNN queries
+ /// Maps geometry index to (batch_idx, row_idx) pairs
+ cached_geometry_positions: Vec<(i32, i32)>,
Review Comment:
There's no need to add a new field. We can use `data_id_to_batch_pos` for mapping the index retrieved from rtree to (batch_idx, row_idx).
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "Kontinuation (via GitHub)" <gi...@apache.org>.
Kontinuation commented on code in PR #53:
URL: https://github.com/apache/sedona-db/pull/53#discussion_r2338450693
##########
rust/sedona-spatial-join/src/index.rs:
##########
@@ -271,6 +292,10 @@ impl SpatialIndexBuilder {
ConcurrentReservation::try_new(REFINER_RESERVATION_PREALLOC_SIZE, refiner_reservation)
.unwrap();
+ // Pre-compute geometries for KNN queries to avoid repeated WKB-to-geometry conversions
+ let (cached_geometries, cached_geometry_positions) =
+ Self::build_cached_geometries(&self.indexed_batches);
Review Comment:
Additionally memory needs to be reserved for cached geometries. It is hard to know the exact amount of memory taken by `geo::Geometry` objects, but at least we can have a rough estimation.
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "jiayuasu (via GitHub)" <gi...@apache.org>.
jiayuasu merged PR #53:
URL: https://github.com/apache/sedona-db/pull/53
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "jiayuasu (via GitHub)" <gi...@apache.org>.
jiayuasu commented on PR #53:
URL: https://github.com/apache/sedona-db/pull/53#issuecomment-3277271131
Which side got cached? The trip table will grow linearly together with Scale Factor. If this just caches the buildings table, we should be good.
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "zhangfengcdt (via GitHub)" <gi...@apache.org>.
zhangfengcdt commented on PR #53:
URL: https://github.com/apache/sedona-db/pull/53#issuecomment-3278089668
> 1. I regret not spotting this issue when I first reviewed the code.
> 2. [suggestion] The `neighbors_geometry` method defined in geo-index does not have to take an array of `geo::Geometry` as a parameter. We can play all kinds of tricks in the `distance_metric` function to compute a distance value given 2 indices of indexed items. This makes the interface more flexible, and we are free to play all kinds of tricks inside our custom distance metric function. For instance, decoding the WKB on demand and caching decoded geometries for reuse.
It's a great suggestion! And, yes, using a custom distance metric with index-based lookups would be more flexible and could potentially offer even better performance optimizations. However, I'd like to keep this PR focused on the immediate performance fix we're addressing. This keeps the current fix simple and focused while leaving room for future optimization.
The suggested approach would require:
- Changes to the geo-index crate's neighbors_geometry API
- A custom distance metric implementation
- More complex testing across two repositories
- Additional coordination between geo-index and sedona-spatial-join
I think this optimization deserves its own focused PR where we can change both repos and test them accordingly.
What do you think?
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "Kontinuation (via GitHub)" <gi...@apache.org>.
Kontinuation commented on code in PR #53:
URL: https://github.com/apache/sedona-db/pull/53#discussion_r2341031564
##########
benchmarks/test_knn.py:
##########
@@ -0,0 +1,225 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+import json
+import pytest
+from test_bench_base import TestBenchBase
+from sedonadb.testing import SedonaDB
+
+
+class TestBenchKNN(TestBenchBase):
+ def setup_class(self):
+ """Setup test data for KNN benchmarks"""
+ self.sedonadb = SedonaDB.create_or_skip()
+
+ # Create building-like polygons (index side - fewer, larger geometries)
+ # Note: Dataset sizes are limited to avoid DataFusion CoalescePartitionsExec issues
Review Comment:
What is the "DataFusion CoalescePartitionsExec issue"? Subsequent comments also mention "partition issues". Can you explain in the comment what the so-called "partition issue" is?
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "zhangfengcdt (via GitHub)" <gi...@apache.org>.
zhangfengcdt commented on PR #53:
URL: https://github.com/apache/sedona-db/pull/53#issuecomment-3278119405
CC: @prantogg This is a fix we need to fix the performance issues in spatial bench Q9.
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "Kontinuation (via GitHub)" <gi...@apache.org>.
Kontinuation commented on code in PR #53:
URL: https://github.com/apache/sedona-db/pull/53#discussion_r2338854370
##########
rust/sedona-spatial-join/src/index.rs:
##########
@@ -235,25 +235,76 @@ impl SpatialIndexBuilder {
geom_idx_vec
}
- /// Build cached geometries and positions for KNN queries to avoid repeated WKB conversions
- fn build_cached_geometries(
- indexed_batches: &[IndexedBatch],
- ) -> (Vec<Geometry<f64>>, Vec<(i32, i32)>) {
+ /// Build cached geometries for KNN queries to avoid repeated WKB conversions
+ fn build_cached_geometries(indexed_batches: &[IndexedBatch]) -> Vec<Geometry<f64>> {
let mut geometries = Vec::new();
- let mut geometry_positions = Vec::new();
- for (batch_idx, indexed_batch) in indexed_batches.iter().enumerate() {
- for (row_idx, wkb_opt) in indexed_batch.geom_array.wkbs().iter().enumerate() {
+ for indexed_batch in indexed_batches.iter() {
+ for wkb_opt in indexed_batch.geom_array.wkbs().iter() {
if let Some(wkb) = wkb_opt.as_ref() {
if let Ok(geom) = item_to_geometry(wkb) {
geometries.push(geom);
- geometry_positions.push((batch_idx as i32, row_idx as i32));
}
}
}
}
- (geometries, geometry_positions)
+ geometries
+ }
+
+ /// Estimate the memory usage of cached geometries for memory reservation
+ /// This provides a rough approximation of the memory used by geo::Geometry objects
+ fn estimate_geometry_memory(geometries: &[Geometry<f64>]) -> usize {
+ // Rough estimation based on geometry types:
+ // - Each Point: ~32 bytes (2 f64s + overhead)
+ // - Each LineString: base size + (num_coords * 16 bytes)
+ // - Each Polygon: base size + exterior ring + interior rings
+ // - Add some overhead for Vec storage and enum variants
+
+ const BASE_GEOMETRY_SIZE: usize = 64; // Base size for geometry enum + overhead
+ const POINT_SIZE: usize = 16; // 2 f64s (x, y)
+ const COORDINATE_SIZE: usize = 16; // 2 f64s per coordinate
+
+ geometries
+ .iter()
+ .map(|geom| {
+ BASE_GEOMETRY_SIZE
+ + match geom {
+ Geometry::Point(_) => POINT_SIZE,
+ Geometry::LineString(ls) => ls.coords().count() * COORDINATE_SIZE,
+ Geometry::Polygon(poly) => {
+ let exterior_coords =
+ poly.exterior().coords().count() * COORDINATE_SIZE;
+ let interior_coords: usize = poly
+ .interiors()
+ .iter()
+ .map(|ring| ring.coords().count() * COORDINATE_SIZE)
+ .sum();
+ exterior_coords + interior_coords
+ }
+ Geometry::MultiPoint(mp) => mp.0.len() * POINT_SIZE,
+ Geometry::MultiLineString(mls) => mls
+ .0
+ .iter()
+ .map(|ls| ls.coords().count() * COORDINATE_SIZE)
+ .sum::<usize>(),
+ Geometry::MultiPolygon(mp) => mp
+ .0
+ .iter()
+ .map(|poly| {
+ let exterior = poly.exterior().coords().count() * COORDINATE_SIZE;
+ let interiors: usize = poly
+ .interiors()
+ .iter()
+ .map(|ring| ring.coords().count() * COORDINATE_SIZE)
+ .sum();
+ exterior + interiors
+ })
+ .sum::<usize>(),
+ _ => 256, // Conservative estimate for other geometry types
+ }
+ })
+ .sum()
}
Review Comment:
This is overly complicated but even less accurate than directly using the length of WKB buffer. I'd rather just take the length of WKB buffer plus or multiply some overhead.
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf: Cache geometries in KNN queries to eliminate redundant WKB conversions [sedona-db]
Posted by "zhangfengcdt (via GitHub)" <gi...@apache.org>.
zhangfengcdt commented on code in PR #53:
URL: https://github.com/apache/sedona-db/pull/53#discussion_r2341213779
##########
benchmarks/test_knn.py:
##########
@@ -0,0 +1,225 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+import json
+import pytest
+from test_bench_base import TestBenchBase
+from sedonadb.testing import SedonaDB
+
+
+class TestBenchKNN(TestBenchBase):
+ def setup_class(self):
+ """Setup test data for KNN benchmarks"""
+ self.sedonadb = SedonaDB.create_or_skip()
+
+ # Create building-like polygons (index side - fewer, larger geometries)
+ # Note: Dataset sizes are limited to avoid DataFusion CoalescePartitionsExec issues
Review Comment:
This is from issues I see when i was debugging into the Datafusion code and find when calling .collect() from python api, the CoalescePartitionsExec was triggered and caused OOM issues for very large test data sizes. It may not be a real "partition issue", but I assume CoalescePartitionsExec might have issues when combining so many small partitions in preparing the join data. It is an assumption though cause I cannot find real-world data to verify it. But yes, I've rephrased the comments to be more accurate.
--
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: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org