Support st_contains using H3 index #8498

WangCHX · 2022-04-09T09:12:30Z

This is a follow up PR for : #7252 since that one seems doesn't get update for long time.

The idea is to convert input geometry into a list of h3 cells by using polyfill. But h3 polyfill only fills with the hexagons whose centers are contained by the geometry.
so creating a method coverGeometryInH3 to return the set of H3 cells at the specified resolution which completely cover the input shape.
Instructions:

The PR has to be tagged with at least one of the following labels (*):
1. feature

(**) Use release-notes label for scenarios like:

New configuration options
Deprecation of configurations
Signature changes to public methods/interfaces
New plugins added or old plugins removed

codecov-commenter · 2022-04-09T09:53:52Z

Codecov Report

Merging #8498 (094d2f1) into master (fc12dce) will increase coverage by 5.18%.
The diff coverage is 63.77%.

@@             Coverage Diff              @@
##             master    #8498      +/-   ##
============================================
+ Coverage     63.60%   68.79%   +5.18%     
- Complexity     4322     4326       +4     
============================================
  Files          1648     1694      +46     
  Lines         86917    88960    +2043     
  Branches      13265    13497     +232     
============================================
+ Hits          55281    61197    +5916     
+ Misses        27595    23431    -4164     
- Partials       4041     4332     +291

Flag	Coverage Δ
integration2	`25.61% <3.93%> (?)`
unittests1	`66.51% <63.77%> (+<0.01%)`	⬆️
unittests2	`14.15% <0.00%> (-0.03%)`	⬇️

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
.../org/apache/pinot/segment/local/utils/H3Utils.java	`40.38% <38.29%> (-19.62%)`	⬇️
...ava/org/apache/pinot/core/plan/FilterPlanNode.java	`82.53% <66.66%> (-4.13%)`	⬇️
...perator/filter/H3InclusionIndexFilterOperator.java	`83.92% <83.92%> (ø)`
...he/pinot/segment/local/segment/store/IndexKey.java	`75.00% <0.00%> (-5.00%)`	⬇️
.../impl/dictionary/BaseOffHeapMutableDictionary.java	`81.33% <0.00%> (-3.34%)`	⬇️
.../java/org/apache/pinot/spi/data/TimeFieldSpec.java	`88.63% <0.00%> (-2.28%)`	⬇️
...e/pinot/segment/local/io/util/PinotDataBitSet.java	`95.62% <0.00%> (-1.46%)`	⬇️
...server/starter/helix/HelixInstanceDataManager.java	`78.64% <0.00%> (ø)`
.../pinot/plugin/metrics/yammer/YammerMetricName.java	`33.33% <0.00%> (ø)`
.../pinot/server/api/resources/MmapDebugResource.java	`0.00% <0.00%> (ø)`
... and 338 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update fc12dce...094d2f1. Read the comment docs.

pinot-segment-local/src/main/java/org/apache/pinot/segment/local/utils/H3Utils.java

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java

richardstartin

👍🏻

pinot-core/src/main/java/org/apache/pinot/core/plan/FilterPlanNode.java

yupeng9 · 2022-04-13T03:21:02Z

pinot-core/src/test/java/org/apache/pinot/queries/H3IndexQueriesTest.java

shall we add some tests of the corner cases, such as on the line/vertex of the polygon?

The ST_Contains seems doesn't include the point or line lying in polygon boundary. https://postgis.net/docs/ST_Contains.html
but let me try create a test with points very close to the boundary.

yupeng9 · 2022-04-13T03:22:18Z

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java

I think this is just approximation, but it doesn't return same result of ST_Contains, right?

i think

expressionFilterOperator.getNextBlock().getBlockDocIdSet().iterator(); MutableRoaringBitmap result = docIdIterator.applyAnd(partialMatchDocIds);

will do the final check on the potential match set.

okay, it could be further optimized to skip the cells fully contained in the polygon. But we can leave it for futture (add a TODO) if you find it too difficult.

sure. will create a TODO.

Created an issue to track here: #8547

actually I did the optimization. but still will use the issue to track if H3 support different polyfill natively.

yupeng9 · 2022-04-13T03:26:21Z

High-level comment is that using H3 index can speed up query evaluation, but we need to ensure it does not change query results. H3's Polyfill returns a set of H3 for approximation, but we need one more round of evaluation to check the borderlines.

yupeng9

LGTM. Thanks for adding the tests and glad to see the improved index handling

yupeng9 · 2022-04-20T19:46:35Z

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java

throw some meaningful error message for better debugging?

sure. add error message for the assert.

pinot-core/src/main/java/org/apache/pinot/core/plan/FilterPlanNode.java

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java

pinot-core/src/main/java/org/apache/pinot/core/plan/FilterPlanNode.java

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java

Jackie-Jiang

LGTM with minor comments

Jackie-Jiang · 2022-04-26T20:00:29Z

pinot-core/src/main/java/org/apache/pinot/core/plan/FilterPlanNode.java

(minor) No need to check st_within and st_contains because the function name is already canonicalized (we keep 2 function names for st_distance for backward compatibility). We may directly use the value equals check into the canApplyH3IndexForInclusionCheck() instead of using a set for 2 values.

Jackie-Jiang · 2022-04-26T20:02:19Z

pinot-core/src/main/java/org/apache/pinot/core/plan/FilterPlanNode.java

(minor) columnName will never be null

Suggested change

return columnName != null && _indexSegment.getDataSource(columnName).getH3Index() != null;

return _indexSegment.getDataSource(columnName).getH3Index() != null;

update on line 183 as well.

Jackie-Jiang · 2022-04-26T20:03:22Z

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java

(minor) We don't usually put final for local variables

Jackie-Jiang · 2022-04-26T20:04:58Z

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java

Use iterator (LongIterator.nextLong()) instead to avoid the unnecessary boxing/unboxing, same for other places when iterating over LongSet

sure. updated.

Jackie-Jiang · 2022-04-26T20:11:11Z

pinot-segment-local/src/main/java/org/apache/pinot/segment/local/utils/H3Utils.java

(minor)

Suggested change

.collect(Collectors.toList()), ImmutableList.of(), resolution));

.collect(Collectors.toList()), Collections.emptyList(), resolution));

KKcorps requested review from Jackie-Jiang and yupeng9 April 9, 2022 11:07

richardstartin reviewed Apr 9, 2022

View reviewed changes

pinot-segment-local/src/main/java/org/apache/pinot/segment/local/utils/H3Utils.java Outdated Show resolved Hide resolved

richardstartin reviewed Apr 9, 2022

View reviewed changes

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java Outdated Show resolved Hide resolved

richardstartin reviewed Apr 11, 2022

View reviewed changes

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java Outdated Show resolved Hide resolved

richardstartin reviewed Apr 11, 2022

View reviewed changes

...core/src/main/java/org/apache/pinot/core/operator/filter/H3InclusionIndexFilterOperator.java Outdated Show resolved Hide resolved

richardstartin approved these changes Apr 12, 2022

View reviewed changes

yupeng9 requested changes Apr 13, 2022

View reviewed changes

WangCHX force-pushed the cwang/stcontiansindex branch 4 times, most recently from 2717ee1 to d8f86c4 Compare April 16, 2022 10:07

Jackie-Jiang added feature enhancement labels Apr 18, 2022

yupeng9 approved these changes Apr 20, 2022

View reviewed changes

Jackie-Jiang reviewed Apr 21, 2022

View reviewed changes

WangCHX force-pushed the cwang/stcontiansindex branch 2 times, most recently from dc7b903 to 15e03bb Compare April 23, 2022 11:16

Jackie-Jiang approved these changes Apr 26, 2022

View reviewed changes

WangCHX force-pushed the cwang/stcontiansindex branch from f9bba02 to 3dcf59b Compare April 29, 2022 07:43

chengxuan.wang added 8 commits April 29, 2022 23:22

Support st_contains using H3 index

14046bf

Fix comments

d446006

fix comment

a03dff7

fix comment

66c06c6

update

8525b8a

add todo

21e9264

add positive and negative check

67e50d4

update

de5570d

chengxuan.wang added 7 commits April 29, 2022 23:22

rebase master

92e7200

Fix Jackie's comment

873802e

update

049275d

fix Jackie's commnet again

54c644f

update

b802716

a little optimization for cover polygon

66bcaa2

rebase master

094d2f1

WangCHX force-pushed the cwang/stcontiansindex branch from 3dcf59b to 094d2f1 Compare April 29, 2022 15:24

Jackie-Jiang merged commit 498387a into apache:master Apr 30, 2022

WangCHX deleted the cwang/stcontiansindex branch May 10, 2022 12:36

	return columnName != null && _indexSegment.getDataSource(columnName).getH3Index() != null;
	return _indexSegment.getDataSource(columnName).getH3Index() != null;

	.collect(Collectors.toList()), ImmutableList.of(), resolution));
	.collect(Collectors.toList()), Collections.emptyList(), resolution));

Support st_contains using H3 index #8498

Support st_contains using H3 index #8498

Uh oh!

Conversation

WangCHX commented Apr 9, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov-commenter commented Apr 9, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

richardstartin left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

WangCHX Apr 15, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

yupeng9 commented Apr 13, 2022

Uh oh!

yupeng9 left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Jackie-Jiang left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

WangCHX commented Apr 9, 2022 •

edited

Loading

codecov-commenter commented Apr 9, 2022 •

edited

Loading

WangCHX Apr 15, 2022 •

edited

Loading