You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by "bziobrowski (via GitHub)" <gi...@apache.org> on 2024/12/10 15:07:33 UTC
[PR] Fix H3 index boundary calculations. [pinot]
bziobrowski opened a new pull request, #14628:
URL: https://github.com/apache/pinot/pull/14628
PR fixes H3IndexFilterOperator's accuracy when used with ST_Distance function.
Calculations in master branch are inaccurate because:
- hexagon size in is not constant per level, so using average value could lead to including too many points without verifying actual distances
- distance between given point (e.g.hexagon center) and center's of n-th ring or hexagons is not uniform and varies greatly for large values of N
Example:
```sql
SELECT COUNT(*)
FROM testTable
WHERE ST_Distance(indexed_point, ST_Point(-122, 37.5, 1)) < 10000
```
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Fix H3 index boundary calculations. [pinot]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #14628:
URL: https://github.com/apache/pinot/pull/14628#issuecomment-2532111553
## [Codecov](https://app.codecov.io/gh/apache/pinot/pull/14628?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 0.00%. Comparing base [(`59551e4`)](https://app.codecov.io/gh/apache/pinot/commit/59551e45224f1535c4863fd577622b37366ccc97?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) to head [(`443d7e9`)](https://app.codecov.io/gh/apache/pinot/commit/443d7e9b7c8dbaf56ec4fc9ffbf3b391c57cecc3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
> Report is 1448 commits behind head on master.
> :exclamation: There is a different number of reports uploaded between BASE (59551e4) and HEAD (443d7e9). Click for more details.
>
> <details><summary>HEAD has 53 uploads less than BASE</summary>
>
>| Flag | BASE (59551e4) | HEAD (443d7e9) |
>|------|------|------|
>|integration|7|1|
>|integration2|3|1|
>|temurin|12|1|
>|java-21|7|1|
>|skip-bytebuffers-true|3|0|
>|skip-bytebuffers-false|7|1|
>|unittests|5|0|
>|unittests1|2|0|
>|java-11|5|0|
>|unittests2|3|0|
>|integration1|2|0|
>|custom-integration1|2|0|
></details>
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## master #14628 +/- ##
=============================================
- Coverage 61.75% 0.00% -61.76%
=============================================
Files 2436 3 -2433
Lines 133233 6 -133227
Branches 20636 0 -20636
=============================================
- Hits 82274 0 -82274
+ Misses 44911 6 -44905
+ Partials 6048 0 -6048
```
| [Flag](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [custom-integration1](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `0.00% <ø> (-0.01%)` | :arrow_down: |
| [integration1](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [integration2](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `0.00% <ø> (ø)` | |
| [java-11](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [java-21](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `0.00% <ø> (-61.63%)` | :arrow_down: |
| [skip-bytebuffers-false](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `0.00% <ø> (-61.75%)` | :arrow_down: |
| [skip-bytebuffers-true](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [temurin](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `0.00% <ø> (-61.76%)` | :arrow_down: |
| [unittests](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [unittests1](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [unittests2](https://app.codecov.io/gh/apache/pinot/pull/14628/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
</details>
[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/apache/pinot/pull/14628?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Fix H3 index boundary calculations. [pinot]
Posted by "bziobrowski (via GitHub)" <gi...@apache.org>.
bziobrowski commented on code in PR #14628:
URL: https://github.com/apache/pinot/pull/14628#discussion_r1879603841
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/H3IndexFilterOperator.java:
##########
@@ -78,7 +78,15 @@ public H3IndexFilterOperator(IndexSegment segment, QueryContext queryContext, Pr
assert _h3IndexReader != null;
int resolution = _h3IndexReader.getH3IndexResolution().getLowestResolution();
_h3Id = H3Utils.H3_CORE.geoToH3(coordinate.y, coordinate.x, resolution);
- _edgeLength = H3Utils.H3_CORE.edgeLength(resolution, LengthUnit.m);
+
+ // choose current hexagon's longest edge instead of average for the resolution;
Review Comment:
Calculating precise edge length for each ring would most likely defeat any potential performance gains coming from using H3. That's because we could end up calculating distances for up to 30k hexagons even if we don't have any points belonging to them. For finger-grained precisions (7+) using current edge length should be fine because edge length shouldn't change much within the boundary of 100 rings (or 30k closest hexagons). For coarse-grained precisions, if center is placed near icosahedron edge and distance is large it could end up producing more results because hexagons far from it would be visibly bigger (and we claim them even though we shouldn't ).
In general - I don't think this application of H3 makes too much sense.
It'd be better to expose library functions such as geoToH3, h3Distance, ... and let users express geo queries in terms of hexagon distances, e.g.
```sql
SELECT COUNT(*)
FROM testTable
WHERE geoToH3(indexed_point) = geoToH3(ST_Point(-122, 37.5, 1))
```
or
```sql
SELECT COUNT(*)
FROM testTable
WHERE h3Distance( geoToH3(indexed_point),geoToH3(ST_Point(-122, 37.5, 1)) ) < 10
```
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Fix H3 index boundary calculations. [pinot]
Posted by "bziobrowski (via GitHub)" <gi...@apache.org>.
bziobrowski commented on code in PR #14628:
URL: https://github.com/apache/pinot/pull/14628#discussion_r1879603841
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/H3IndexFilterOperator.java:
##########
@@ -78,7 +78,15 @@ public H3IndexFilterOperator(IndexSegment segment, QueryContext queryContext, Pr
assert _h3IndexReader != null;
int resolution = _h3IndexReader.getH3IndexResolution().getLowestResolution();
_h3Id = H3Utils.H3_CORE.geoToH3(coordinate.y, coordinate.x, resolution);
- _edgeLength = H3Utils.H3_CORE.edgeLength(resolution, LengthUnit.m);
+
+ // choose current hexagon's longest edge instead of average for the resolution;
Review Comment:
Calculating precise edge length for each ring would most likely defeat any potential performance gains coming from using H3. That's because we could end up calculating distances for up to 30k hexagons even if we don't have any points belonging to them. For finger-grained precisions (7+) using current edge length should be fine because edge length shouldn't change much within the boundary of 100 rings (or 30k closest hexagons). For coarse-grained precisions, if center is placed near icosahedron edge and distance is large it could end up producing more results because hexagons far from it would be visibly bigger (and we claim them even though we shouldn't ).
In general - I don't think this application of H3 makes too much sense.
It'd be better to expose library functions such as geoToH3, h3Distance, etc. and let users express geo queries in terms of hexagon distances, e.g.
```sql
SELECT COUNT(*)
FROM testTable
WHERE geoToH3(indexed_point) = geoToH3(ST_Point(-122, 37.5, 1))
```
or
```sql
SELECT COUNT(*)
FROM testTable
WHERE h3Distance( geoToH3(indexed_point),geoToH3(ST_Point(-122, 37.5, 1)) ) < 10
```
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Fix H3 index boundary calculations. [pinot]
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on code in PR #14628:
URL: https://github.com/apache/pinot/pull/14628#discussion_r1880731417
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/H3IndexFilterOperator.java:
##########
@@ -78,7 +78,15 @@ public H3IndexFilterOperator(IndexSegment segment, QueryContext queryContext, Pr
assert _h3IndexReader != null;
int resolution = _h3IndexReader.getH3IndexResolution().getLowestResolution();
_h3Id = H3Utils.H3_CORE.geoToH3(coordinate.y, coordinate.x, resolution);
- _edgeLength = H3Utils.H3_CORE.edgeLength(resolution, LengthUnit.m);
+
+ // choose current hexagon's longest edge instead of average for the resolution;
Review Comment:
@yupeng9 Can you please help comment on this? We'll need some guidance on how to use H3 index
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Fix H3 index boundary calculations. [pinot]
Posted by "bziobrowski (via GitHub)" <gi...@apache.org>.
bziobrowski commented on code in PR #14628:
URL: https://github.com/apache/pinot/pull/14628#discussion_r1879603841
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/H3IndexFilterOperator.java:
##########
@@ -78,7 +78,15 @@ public H3IndexFilterOperator(IndexSegment segment, QueryContext queryContext, Pr
assert _h3IndexReader != null;
int resolution = _h3IndexReader.getH3IndexResolution().getLowestResolution();
_h3Id = H3Utils.H3_CORE.geoToH3(coordinate.y, coordinate.x, resolution);
- _edgeLength = H3Utils.H3_CORE.edgeLength(resolution, LengthUnit.m);
+
+ // choose current hexagon's longest edge instead of average for the resolution;
Review Comment:
Calculating precise edge length for each ring would most likely defeat any potential performance gains coming from using H3. That's because, considering that operator doesn't apply when number of rings exceeds 100, we could end up calculating distances for up to ~30k hexagons even if we don't have any points belonging to them.
For finger-grained precisions (7+) using current edge length should be fine because edge length shouldn't change much within the boundary of 100 rings.
For coarse-grained precisions, if center is placed near icosahedron edge and distance is large it could end up producing more results because hexagons far from it would be visibly bigger (max ratio is about 1.4) (and we claim them even though we shouldn't ).
In general - I don't think this application of H3 makes too much sense.
It'd be better to expose library functions such as geoToH3, h3Distance, etc. and let users express geo queries in terms of hexagon distances, without having to calculate spherical distances, e.g.
```sql
SELECT COUNT(*)
FROM testTable
WHERE geoToH3(indexed_point) = geoToH3(ST_Point(-122, 37.5, 1))
```
or
```sql
SELECT COUNT(*)
FROM testTable
WHERE h3Distance( geoToH3(indexed_point),geoToH3(ST_Point(-122, 37.5, 1)) ) < 10
```
Note: H3 would also need better documentation to let user easily choose proper resolution that would speed up query (given some range of values for distance) and not revert to regular distance check due to hitting ring limit.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Fix H3 index boundary calculations. [pinot]
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on code in PR #14628:
URL: https://github.com/apache/pinot/pull/14628#discussion_r1878763687
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/H3IndexFilterOperator.java:
##########
@@ -78,7 +78,15 @@ public H3IndexFilterOperator(IndexSegment segment, QueryContext queryContext, Pr
assert _h3IndexReader != null;
int resolution = _h3IndexReader.getH3IndexResolution().getLowestResolution();
_h3Id = H3Utils.H3_CORE.geoToH3(coordinate.y, coordinate.x, resolution);
- _edgeLength = H3Utils.H3_CORE.edgeLength(resolution, LengthUnit.m);
+
+ // choose current hexagon's longest edge instead of average for the resolution;
Review Comment:
Is this correct? This is just the max edge length for the center id, but not other hexagons. If the edge length is not all the same, the fundamental assumption doesn't hold, and we need to think for a new algorithm
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Fix H3 index boundary calculations. [pinot]
Posted by "npawar (via GitHub)" <gi...@apache.org>.
npawar commented on code in PR #14628:
URL: https://github.com/apache/pinot/pull/14628#discussion_r1894295830
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/H3IndexFilterOperator.java:
##########
@@ -78,7 +78,15 @@ public H3IndexFilterOperator(IndexSegment segment, QueryContext queryContext, Pr
assert _h3IndexReader != null;
int resolution = _h3IndexReader.getH3IndexResolution().getLowestResolution();
_h3Id = H3Utils.H3_CORE.geoToH3(coordinate.y, coordinate.x, resolution);
- _edgeLength = H3Utils.H3_CORE.edgeLength(resolution, LengthUnit.m);
+
+ // choose current hexagon's longest edge instead of average for the resolution;
Review Comment:
bumping this @yupeng9 ^
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org