You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@sedona.apache.org by "dfischercodethoughts (via GitHub)" <gi...@apache.org> on 2023/06/08 18:13:05 UTC
[GitHub] [sedona] dfischercodethoughts opened a new issue, #854: Dynamic Index Build Side is Statically Chosen
dfischercodethoughts opened a new issue, #854:
URL: https://github.com/apache/sedona/issues/854
## Expected behavior
During dynamic join queries on commutative conditions, the local index is built on whichever side is smaller, and the other side is streamed against it. This likely requires some linear scans prior to running
## Actual behavior
We must specify the side on which to build the index for all partitions apriori when using ```JoinQueries.SpatialJoinQueryFlat```.
## Steps to reproduce the problem
N/A
## Settings
N/A
--
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: dev-unsubscribe@sedona.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dynamic Index Build Side is Statically Chosen [sedona]
Posted by "sudhamsh-git (via GitHub)" <gi...@apache.org>.
sudhamsh-git commented on issue #854:
URL: https://github.com/apache/sedona/issues/854#issuecomment-6262439210
Hi, is this still something you'd like done? I'm a student contributing as part of a university software engineering course and I'd like to take Step 2 from your plan (the join-side heuristics in TraitJoinQueryExec.scala). I see dfischercodethoughts offered earlier, so I'm happy to step back if they're still working on it.
Right now TraitJoinQueryExec only calls analyze() on the partitioning dominant side and passes sedonaConf.getJoinBuildSide straight through, so the index is always built on the configured default side (left). My plan: when the user hasn't set sedona.join.indexbuildside or sedona.join.spatitionside, get approximate counts for both sides from analyze() and use the larger side for both, as you suggested, while an explicit setting still wins. Tests would check the chosen side for small and large inputs, and that explicit settings are respected. Does that sound right, and is it OK to analyze both sides even though it adds a pass over the smaller one?
--
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
[GitHub] [sedona] dfischercodethoughts commented on issue #854: Dynamic Index Build Side is Statically Chosen
Posted by "dfischercodethoughts (via GitHub)" <gi...@apache.org>.
dfischercodethoughts commented on issue #854:
URL: https://github.com/apache/sedona/issues/854#issuecomment-1583127264
I can take a stab at fixing this one this weekend if you don't want to get around to it. Probably approach would be just specify an additional option in the query or something like that to do some additional processing to determine the index build side automatically. For the determining, maybe just iterate while the iterator.next is not null to count both sides?
--
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: dev-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [sedona] Kontinuation commented on issue #854: Dynamic Index Build Side is Statically Chosen
Posted by "Kontinuation (via GitHub)" <gi...@apache.org>.
Kontinuation commented on issue #854:
URL: https://github.com/apache/sedona/issues/854#issuecomment-1585667724
I propose a different (more complicated) approach:
1. Make analyze() method of `SpatialRDD` take sample of the RDD. We can integrate the logic of poisson sampler into the `StatCalculator` and calculate the boundary, count, and samples in one pass.
2. When running the spatial join physical plan, we `analyze()` both sides. Now we know the boundary and count of both sides, then we can simply apply some heuristics to determine which is the partitioning side (for example, take the one with more records as the partitioning side).
3. Build a spatial partitioning grid using the samples we collected in `analyze()`. Since we also have samples of the other side, we can estimate how many geometries of both sides will fall into each grid.
4. When running the `DynamicIndexLookupJudgement`, we can determine which side to build and which side to stream on a per-grid basis.
--
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: dev-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [sedona] jiayuasu commented on issue #854: Dynamic Index Build Side is Statically Chosen
Posted by "jiayuasu (via GitHub)" <gi...@apache.org>.
jiayuasu commented on issue #854:
URL: https://github.com/apache/sedona/issues/854#issuecomment-1583448888
There are 3 important params involved in a spatial join:
1. Spatial partitioning dominant side: `sedona.join.spatitionside`. Default: LEFT
2. Spatial index build side: `sedona.join.indexbuildside`. Default: LEFT. See https://github.com/apache/sedona/blob/master/core/src/main/java/org/apache/sedona/core/joinJudgement/DynamicIndexLookupJudgement.java#L91
3. Num of partitions of both RDDs used in a join. Default to use the num partition of `sedona.join.spatitionside` but will be optimized to reasonable partitions if the data is way less than num of partitions.
The best practice is the Spatial partitioning dominant side and Spatial index build side should always be the large dataset (not the smaller dataset). To find out which one is larger, you can use the count of both RDDs. Note that: SpatialRDD.analyze() function already computes the count. You can leverage that to automatically determine the dominant side: https://github.com/apache/sedona/blob/master/sql/common/src/main/scala/org/apache/spark/sql/sedona_sql/strategy/join/TraitJoinQueryExec.scala#L59
You can add the automation and leave `sedona.join.spatitionside` and `sedona.join.indexbuildside` as optional. In other words, our optimizer will automatically determine the two sides unless the user explicitly specifies the parameters.
I will leave the implementation to you. But if you feel this is too hard, please let me know.
--
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: dev-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [sedona] jiayuasu commented on issue #854: Dynamic Index Build Side is Statically Chosen
Posted by "jiayuasu (via GitHub)" <gi...@apache.org>.
jiayuasu commented on issue #854:
URL: https://github.com/apache/sedona/issues/854#issuecomment-1586053598
@Kontinuation I like this idea.
Let's break this proposal to 3 standalone PRs. I believe they can be implemented separately without relying on each other.
Step 1: Move the sampling logic to `analyze()`
1. Update `analyze()` function of `SpatialRDD` to include the poisson sampler
2. Build a spatial partitioning grid using the samples we collected in analyze().
Step 2: Add heuristics to determine the join side in `TraitJoinQueryExec.scala` (https://github.com/apache/sedona/blob/master/sql/common/src/main/scala/org/apache/spark/sql/sedona_sql/strategy/join/TraitJoinQueryExec.scala#L59)
Step 3: `DynamicIndexLookupJudgement` automatically determines the stream side on a per-grid basis.
@dfischercodethoughts What you are proposing is Step 2. You can take a stab if you want. Since the `v1.4.1` will be released soon, I expect this entire proposal will be completed in `v1.5.0`
--
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: dev-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [I] Dynamic Index Build Side is Statically Chosen [sedona]
Posted by "dfischercodethoughts (via GitHub)" <gi...@apache.org>.
dfischercodethoughts commented on issue #854:
URL: https://github.com/apache/sedona/issues/854#issuecomment-6272673540
I haven’t had a chance to build this out. I’ll let @jiayuasu speak for priority / implementation.
--
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