You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@kudu.apache.org by "Jim Apple (Code Review)" <ge...@cloudera.org> on 2020/07/28 22:59:15 UTC

[kudu-CR] Block Bloom filter false positive rate correction 

Jim Apple has uploaded this change for review. ( http://gerrit.cloudera.org:8080/16248


Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 85 insertions(+), 28 deletions(-)



  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/1
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 1
Gerrit-Owner: Jim Apple <jb...@apache.org>

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Jim Apple has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 8:

(3 comments)

http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc@222
PS8, Line 222: ldexp(1.0, log_space_bytes)
> As against simply (1 << log_space_bytes), this is to account the case if lo
I don't think log_space_bytes will show up like that, but 1 << k is an int, so log_space_bytes can't be even 32, and 1L << k sets off the tidy detector, so now it's static_cast(1L << k).


http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc@236
PS8, Line 236: static constexpr uint64_t kBloomFppIters = 750;
> Original equation suggests up to infinity which is obviously not practical.
Done


http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc@288
PS8, Line 288: this method could use binary search
> Agreed this method which is typically used in the creation of the BlockBloo
Benchmarking was more effort than just moving to binary search, so I just moved to binary search.



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 8
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Sun, 16 Aug 2020 00:13:31 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins, Bankim Bhavsar, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16248

to look at the new patch set (#6).

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 99 insertions(+), 32 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/6
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 6
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 10:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/16248/10/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/10/src/kudu/util/block_bloom_filter.cc@296
PS10, Line 296: (candidate <= fpp)
Isn't it a typo?

I guess it should have been 'if (candidate > fpp)'.



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 10
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 09 Sep 2020 19:34:22 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Alexey Serbin, Attila Bukor, Kudu Jenkins, Bankim Bhavsar, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16248

to look at the new patch set (#9).

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 105 insertions(+), 32 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/9
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 9
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Attila Bukor, Kudu Jenkins, Bankim Bhavsar, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16248

to look at the new patch set (#8).

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 99 insertions(+), 32 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/8
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 8
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Attila Bukor (Code Review)" <ge...@cloudera.org>.
Attila Bukor has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 7:

> Patch Set 7:
> 
> > Thanks for fixing this, Jim.
>  > 
>  > Some high level questions:
>  > - Would it be possible to quantify the error in false positive rate
>  > seen earlier without this change?
>  > - Were Block Bloom filters created prior to this change smaller in
>  > size and yield higher false positive rate?
> 
> Good questions!
> 
> 1. It's possible to quantify, but there is no closed-form solution. Look for Table 1 in the referenced paper by Putze et al. The error in fpp depends on the density of the filter, but it's around 2x fpp error (aka 1 bit of space, aka 10% of space) when using an fpp of 1%.
> 
> 2. Yes.

Can you add the latter to the commit message? Also, you mentioned that this doesn't change the perf of the BF, but doesn't a higher than expected FPP effectively reduce the scan throughput? Sorry if this doesn't make sense, I haven't yet read the paper.


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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 7
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Tue, 04 Aug 2020 07:39:45 +0000
Gerrit-HasComments: No

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Attila Bukor (Code Review)" <ge...@cloudera.org>.
Attila Bukor has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 6:

(2 comments)

http://gerrit.cloudera.org:8080/#/c/16248/6//COMMIT_MSG
Commit Message:

PS6: 
can you add some benchmarks/measurements before and after this patch in the commit message?


http://gerrit.cloudera.org:8080/#/c/16248/6//COMMIT_MSG@12
PS6, Line 12: paper that introduced block Bloom filters
can you add a link or a citation to the paper?



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 6
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Mon, 03 Aug 2020 14:21:42 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Jim Apple has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 7:

> Can you add the latter to the commit message?

Done

 > Also, you mentioned
 > that this doesn't change the perf of the BF, but doesn't a higher
 > than expected FPP effectively reduce the scan throughput? Sorry if
 > this doesn't make sense, I haven't yet read the paper.

The tradeoff goes the other way, but performance depends on the space/time tradeoff in a particular query on that particular hardware, as well as cache pressure and other factors specific to a setting.


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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 7
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 05 Aug 2020 15:01:23 +0000
Gerrit-HasComments: No

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins, Bankim Bhavsar, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16248

to look at the new patch set (#5).

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 100 insertions(+), 30 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/5
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 5
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Reviewed-on: http://gerrit.cloudera.org:8080/16248
Tested-by: Kudu Jenkins
Reviewed-by: Bankim Bhavsar <ba...@cloudera.com>
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 106 insertions(+), 32 deletions(-)

Approvals:
  Kudu Jenkins: Verified
  Bankim Bhavsar: Looks good to me, approved

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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 11
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 10:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/16248/10/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/10/src/kudu/util/block_bloom_filter.cc@296
PS10, Line 296: (candidate <= fpp)
> I tried this:
Ah, please disregard my two comments above.  I guess FalsePositiveProb() has all the necessary properties to be searched as implemented.

Just for clarification: I was looking at the micro-benchmark results, trying to explain the recent change.  It seems that should be something else.

Sorry for the noise.



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 10
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 09 Sep 2020 19:57:58 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins, Bankim Bhavsar, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16248

to look at the new patch set (#4).

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 86 insertions(+), 28 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/4
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 4
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 8:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc@288
PS8, Line 288: this method could use binary search
Why not to implement that, especially if in average it would be faster?



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 8
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 05 Aug 2020 16:30:58 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Jim Apple has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 7:

(2 comments)

http://gerrit.cloudera.org:8080/#/c/16248/6//COMMIT_MSG
Commit Message:

PS6: 
> can you add some benchmarks/measurements before and after this patch in the
This patch doesn't change the performance of the Bloom filter itself, only the estimation of false positive rates, which I doubt is on any hot paths.


http://gerrit.cloudera.org:8080/#/c/16248/6//COMMIT_MSG@12
PS6, Line 12: paper that introduced block Bloom filters
> can you add a link or a citation to the paper?
Done



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 7
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Mon, 03 Aug 2020 14:47:46 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 10:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/16248/10/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/10/src/kudu/util/block_bloom_filter.cc@296
PS10, Line 296: (candidate <= fpp)
> Isn't it a typo?
I tried this:


#include <iostream>                                                             
                                                                                
using namespace std;                                                            
                                                                                
double FalsePositiveProb(int mid) {                                             
  return mid;                                                                   
}                                                                               
                                                                                
int search(double fpp) {                                                        
  int low = 0;                                                                  
  int high = 64;                                                                
  while (high > low + 1) {                                                      
    int mid = (high + low) / 2;                                                 
    const double candidate = FalsePositiveProb(mid);                            
    if (candidate <= fpp) {                                                     
    //if (candidate > fpp) {                                                    
      high = mid;                                                               
    } else {                                                                    
      low = mid;                                                                
    }                                                                           
  }                                                                             
  return high;                                                                  
}                                                                               
                                                                                
int main() {                                                                    
  cout << search(2) << endl;                                                    
  return 0;                                                                     
}

It seems search() returns 64 here for 2, but it should return 2 or 3 instead, it seems.  If uncommenting the alternative 'if()' line, it starts working as expected.



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 10
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 09 Sep 2020 19:37:14 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 7:

Thanks for fixing this, Jim.

Some high level questions:
- Would it be possible to quantify the error in false positive rate seen earlier without this change?
- Were Block Bloom filters created prior to this change smaller in size and yield higher false positive rate?


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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 7
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Mon, 03 Aug 2020 22:02:22 +0000
Gerrit-HasComments: No

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 10: Code-Review+2


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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 10
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Mon, 24 Aug 2020 16:49:14 +0000
Gerrit-HasComments: No

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16248

to look at the new patch set (#3).

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 86 insertions(+), 28 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/3
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 3
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Jim Apple has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 2:

> Build Failed
 > 
 > http://jenkins.kudu.apache.org/job/kudu-gerrit/22128/ : FAILURE

Some of these appear to be compilation failures in src/kudu/experiments/rwlock-perf.cc. Not sure what's going on there.


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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 2
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Tue, 28 Jul 2020 23:32:30 +0000
Gerrit-HasComments: No

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16248

to look at the new patch set (#2).

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 85 insertions(+), 28 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/2
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 2
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Attila Bukor, Kudu Jenkins, Bankim Bhavsar, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16248

to look at the new patch set (#7).

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 99 insertions(+), 32 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/7
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 7
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Jim Apple has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 7:

> Thanks for fixing this, Jim.
 > 
 > Some high level questions:
 > - Would it be possible to quantify the error in false positive rate
 > seen earlier without this change?
 > - Were Block Bloom filters created prior to this change smaller in
 > size and yield higher false positive rate?

Good questions!

1. It's possible to quantify, but there is no closed-form solution. Look for Table 1 in the referenced paper by Putze et al. The error in fpp depends on the density of the filter, but it's around 2x fpp error (aka 1 bit of space, aka 10% of space) when using an fpp of 1%.

2. Yes.


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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 7
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Mon, 03 Aug 2020 23:40:46 +0000
Gerrit-HasComments: No

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Alexey Serbin, Attila Bukor, Kudu Jenkins, Bankim Bhavsar, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/16248

to look at the new patch set (#10).

Change subject: Block Bloom filter false positive rate correction
......................................................................

Block Bloom filter false positive rate correction

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.

Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
---
M src/kudu/util/block_bloom_filter-test.cc
M src/kudu/util/block_bloom_filter.cc
2 files changed, 106 insertions(+), 32 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/48/16248/10
-- 
To view, visit http://gerrit.cloudera.org:8080/16248
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 10
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Jim Apple has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 5:

(3 comments)

http://gerrit.cloudera.org:8080/#/c/16248/4/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/4/src/kudu/util/block_bloom_filter.cc@221
PS4, Line 221: double
> Does this variable need to be a double?
Generally the arithmetic in this method is in doubles; I found this easier to reason about when using doubles for everything bug the loop counter.


http://gerrit.cloudera.org:8080/#/c/16248/4/src/kudu/util/block_bloom_filter.cc@236
PS4, Line 236: kBloo
> constants start with k and use camelCase.
Done


http://gerrit.cloudera.org:8080/#/c/16248/4/src/kudu/util/block_bloom_filter.cc@262
PS4, Line 262: while (FalsePositiveProb(too_many, log_space_bytes) <= fpp) {
> Can you add braces and move the loop block to new line?
Done



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 5
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 29 Jul 2020 22:24:50 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 3:

> Patch Set 2:
> 
> > Build Failed
>  > 
>  > http://jenkins.kudu.apache.org/job/kudu-gerrit/22128/ : FAILURE
> 
> Some of these appear to be compilation failures in src/kudu/experiments/rwlock-perf.cc. Not sure what's going on there.

Following boost upgrade looks suspiciously related but it hasn't been submitted yet as per gerrit.
https://gerrit.cloudera.org/c/16247/


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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 3
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 29 Jul 2020 00:14:06 +0000
Gerrit-HasComments: No

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Jim Apple has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 10:

(1 comment)

Thank you for the comments! Did you see a bug in testing that inspired you to take another look?

http://gerrit.cloudera.org:8080/#/c/16248/10/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/10/src/kudu/util/block_bloom_filter.cc@296
PS10, Line 296: (candidate <= fpp)
> I tried this:
If candidate logSpaceSize is less than fpp, then the filter is bigger than it needs to be. That means mid was too large. By setting high to mid, the new range is the lower half of the old range.

I'm not sure about the test: in your FalsePositiveProb function, as the parameter increases, so does the return value, whereas the opposite is true here.



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 10
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 09 Sep 2020 19:50:38 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 8:

(3 comments)

Thanks for the detailed commit message, Jim.

http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc@222
PS8, Line 222: ldexp(1.0, log_space_bytes)
As against simply (1 << log_space_bytes), this is to account the case if log_space_bytes is greater than 63?


http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc@236
PS8, Line 236: static constexpr uint64_t kBloomFppIters = 750;
Original equation suggests up to infinity which is obviously not practical.
Could you add justification why 750 iterations is enough for the computation?


http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc@288
PS8, Line 288: this method could use binary search
> Because this adds code size and complexity and I think this is not on any h
Agreed this method which is typically used in the creation of the BlockBloomFilter is not in the hot path for predicate evaluation. Though it's possible the same BBF is used for other purposes in future.

FalsePositiveProb() function involves bunch of floating point calculations with high number of iterations.
It'd be good to quantify the change in BBF creation time perhaps using BlockBloomFilterTest/Constructor test case.

If the difference is non-trivial adding binary search like above will be worthwhile.



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 8
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Tue, 11 Aug 2020 22:49:44 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Jim Apple (Code Review)" <ge...@cloudera.org>.
Jim Apple has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 8:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/8/src/kudu/util/block_bloom_filter.cc@288
PS8, Line 288: this method could use binary search
> Why not to implement that, especially if in average it would be faster?
Because this adds code size and complexity and I think this is not on any hot path and is unlikely to be on any hot paths in the future.



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 8
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Attila Bukor <ab...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 05 Aug 2020 17:05:30 +0000
Gerrit-HasComments: Yes

[kudu-CR] Block Bloom filter false positive rate correction

Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/16248 )

Change subject: Block Bloom filter false positive rate correction
......................................................................


Patch Set 4:

(3 comments)

http://gerrit.cloudera.org:8080/#/c/16248/4/src/kudu/util/block_bloom_filter.cc
File src/kudu/util/block_bloom_filter.cc:

http://gerrit.cloudera.org:8080/#/c/16248/4/src/kudu/util/block_bloom_filter.cc@221
PS4, Line 221: double
Does this variable need to be a double?


http://gerrit.cloudera.org:8080/#/c/16248/4/src/kudu/util/block_bloom_filter.cc@236
PS4, Line 236: MAX_J
constants start with k and use camelCase.


http://gerrit.cloudera.org:8080/#/c/16248/4/src/kudu/util/block_bloom_filter.cc@262
PS4, Line 262: while (FalsePositiveProb(too_many, log_space_bytes) <= fpp) too_many *= 2;
Can you add braces and move the loop block to new line?



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

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I58a5191ee86edfa6e4f415829a6a647f586e9af6
Gerrit-Change-Number: 16248
Gerrit-PatchSet: 4
Gerrit-Owner: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jb...@apache.org>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Wed, 29 Jul 2020 20:42:28 +0000
Gerrit-HasComments: Yes