You are viewing a plain text version of this content. The canonical link for it is here.

Posted to reviews@impala.apache.org by "Joe McDonnell (Code Review)" <ge...@cloudera.org> on 2022/08/02 18:21:11 UTC

[Impala-ASF-CR] IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Joe McDonnell has uploaded this change for review. ( http://gerrit.cloudera.org:8080/18807

Change subject: IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu
......................................................................

IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Block Bloom filters have a higher false positive rate than standard
Bloom filter, due to the uneven distribution of keys between
buckets. This patch changes the code to match the theory, using an
approximation from the paper that introduced block Bloom filters,
"Cache-, Hash- and Space-Efficient Bloom Filters" by Putze et al.

In scan_predicate.cc, filters are created with
BlockBloomFilter::MinLogSpace. Prior to this patch, that method will
sometimes return a value that is lower than the true answer, leading
to smaller filters and higher false positive probabilities than
expected. This patch corrects BlockBloomFilter::MinLogSpace, leading
to filters having the expected false positive rate by dint of their
larger size. The performance impact here is dependent on the extent
than a scan is bottlenecked by heap space for the filter vs. compute
time for the scan predicate application to filter false positives.

For a false positive probability of 1%, as is currently set in
scan_predicate.cc, this patch leads to an increase in filter size of
about 10% and a decrease in filter false positive probability by
50%. However, this is obscured by the coarseness of the fact that
filters are constrained to have a size in bytes that is a power of
two. Loosening that restriction is potential future work.

Porting Notes:
- The MaxNdv() function is not present in Impala, so it is omitted.
- This resolves a test failure for ParquetBloomFilter.FindInvalid
when building with GCC 10 and the associated libstdc++.
- This adds a comment noting that the test is also dependent
on the libstdc++ implementation of unordered_set.

Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
---
M be/src/util/parquet-bloom-filter-test.cc
M be/src/util/parquet-bloom-filter.cc
2 files changed, 74 insertions(+), 22 deletions(-)

git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/07/18807/1
--
To view, visit http://gerrit.cloudera.org:8080/18807
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Gerrit-Change-Number: 18807
Gerrit-PatchSet: 1
Gerrit-Owner: Joe McDonnell <jo...@cloudera.com>

[Impala-ASF-CR] IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/18807 )

Change subject: IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu
......................................................................


Patch Set 3:

Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/8439/ DRY_RUN=false


-- 
To view, visit http://gerrit.cloudera.org:8080/18807
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Gerrit-Change-Number: 18807
Gerrit-PatchSet: 3
Gerrit-Owner: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Wenzhe Zhou <wz...@cloudera.com>
Gerrit-Comment-Date: Thu, 11 Aug 2022 16:30:44 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/18807 )

Change subject: IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu
......................................................................


Patch Set 3: Code-Review+2


-- 
To view, visit http://gerrit.cloudera.org:8080/18807
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Gerrit-Change-Number: 18807
Gerrit-PatchSet: 3
Gerrit-Owner: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Wenzhe Zhou <wz...@cloudera.com>
Gerrit-Comment-Date: Thu, 11 Aug 2022 16:30:43 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Posted by "Joe McDonnell (Code Review)" <ge...@cloudera.org>.

Joe McDonnell has posted comments on this change. ( http://gerrit.cloudera.org:8080/18807 )

Change subject: IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu
......................................................................


Patch Set 2: Code-Review+2

Rebased this and decoupled it from the GCC 10 patch, as it isn't dependent on that. This can go in ahead of the GCC 10 patch.

Carrying +2


-- 
To view, visit http://gerrit.cloudera.org:8080/18807
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Gerrit-Change-Number: 18807
Gerrit-PatchSet: 2
Gerrit-Owner: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Wenzhe Zhou <wz...@cloudera.com>
Gerrit-Comment-Date: Thu, 11 Aug 2022 16:30:18 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/18807 )

Change subject: IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu
......................................................................


Patch Set 1:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/18807/1/be/src/util/parquet-bloom-filter.cc
File be/src/util/parquet-bloom-filter.cc:

http://gerrit.cloudera.org:8080/#/c/18807/1/be/src/util/parquet-bloom-filter.cc@152
PS1, Line 152: double ParquetBloomFilter::FalsePositiveProb(const size_t ndv, const int log_space_bytes) {
line too long (91 > 90)



-- 
To view, visit http://gerrit.cloudera.org:8080/18807
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Gerrit-Change-Number: 18807
Gerrit-PatchSet: 1
Gerrit-Owner: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Aug 2022 18:22:47 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Posted by "Joe McDonnell (Code Review)" <ge...@cloudera.org>.

Joe McDonnell has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/18807 )

Change subject: IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu
......................................................................

IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Reviewed-on: http://gerrit.cloudera.org:8080/18807
Reviewed-by: Impala Public Jenkins <im...@cloudera.com>
Tested-by: Joe McDonnell <jo...@cloudera.com>
---
M be/src/util/parquet-bloom-filter-test.cc
M be/src/util/parquet-bloom-filter.cc
2 files changed, 74 insertions(+), 22 deletions(-)

Approvals:
Impala Public Jenkins: Looks good to me, approved
Joe McDonnell: Verified

--
To view, visit http://gerrit.cloudera.org:8080/18807
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Gerrit-Change-Number: 18807
Gerrit-PatchSet: 4
Gerrit-Owner: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Wenzhe Zhou <wz...@cloudera.com>

[Impala-ASF-CR] IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.

Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/18807 )

Change subject: IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu
......................................................................


Patch Set 1:

Build Successful 

https://jenkins.impala.io/job/gerrit-code-review-checks/11075/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/18807
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Gerrit-Change-Number: 18807
Gerrit-PatchSet: 1
Gerrit-Owner: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Aug 2022 18:41:54 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Posted by "Wenzhe Zhou (Code Review)" <ge...@cloudera.org>.

Wenzhe Zhou has posted comments on this change. ( http://gerrit.cloudera.org:8080/18807 )

Change subject: IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu
......................................................................


Patch Set 1: Code-Review+2


-- 
To view, visit http://gerrit.cloudera.org:8080/18807
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Gerrit-Change-Number: 18807
Gerrit-PatchSet: 1
Gerrit-Owner: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Wenzhe Zhou <wz...@cloudera.com>
Gerrit-Comment-Date: Tue, 02 Aug 2022 19:04:34 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu

Posted by "Joe McDonnell (Code Review)" <ge...@cloudera.org>.

Joe McDonnell has posted comments on this change. ( http://gerrit.cloudera.org:8080/18807 )

Change subject: IMPALA-11468: Port "Block Bloom filter false positive correction" from Kudu
......................................................................


Patch Set 3: Verified+1

The gerrit-verify-dryrun succeeded, but did not vote on this change due to gerrit.cloudera.org issues. Going ahead.


-- 
To view, visit http://gerrit.cloudera.org:8080/18807
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ic992e47976274e3ef0db3633d38e5a8e886274b4
Gerrit-Change-Number: 18807
Gerrit-PatchSet: 3
Gerrit-Owner: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <jo...@cloudera.com>
Gerrit-Reviewer: Wenzhe Zhou <wz...@cloudera.com>
Gerrit-Comment-Date: Fri, 12 Aug 2022 03:13:53 +0000
Gerrit-HasComments: No