You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@paimon.apache.org by "Aitozi (via GitHub)" <gi...@apache.org> on 2024/01/15 03:31:42 UTC
[PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Aitozi opened a new pull request, #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696
<!-- Please specify the module before the PR name: [core] ... or [flink] ... -->
### Purpose
Introduce bloom filter for local lookup cache file to speed up the local file lookup
<!-- What is the purpose of the change -->
### Tests
<!-- List UT and IT cases to verify this change -->
### API and Format
<!-- Does this change affect API or storage format -->
### Documentation
<!-- Does this change introduce a new feature -->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on code in PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#discussion_r1456838698
##########
paimon-common/src/main/java/org/apache/paimon/lookup/bloom/BloomFilter.java:
##########
@@ -0,0 +1,148 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+
+package org.apache.paimon.lookup.bloom;
+
+import org.apache.paimon.memory.MemorySegment;
+
+import static org.apache.paimon.utils.Preconditions.checkArgument;
+
+/**
+ * BloomFilter is a probabilistic data structure for set membership check. BloomFilters are highly
+ * space efficient when compared to using a HashSet. Because of the probabilistic nature of bloom
+ * filter false positive (element not present in bloom filter but test() says true) are possible but
+ * false negatives are not possible (if element is present then test() will never say false). The
+ * false positive probability is configurable depending on which storage requirement may increase or
+ * decrease. Lower the false positive probability greater is the space requirement. Bloom filters
+ * are sensitive to number of elements that will be inserted in the bloom filter. During the
+ * creation of bloom filter expected number of entries must be specified. If the number of
+ * insertions exceed the specified initial number of entries then false positive probability will
+ * increase accordingly.
+ *
+ * <p>Internally, this implementation of bloom filter uses MemorySegment to store BitSet,
+ * BloomFilter and BitSet are designed to be able to switch between different MemorySegments, so
+ * that Flink can share the same BloomFilter/BitSet object instance for different bloom filters.
+ *
+ * <p>Part of this class refers to the implementation from Apache Hive project
+ * https://github.com/apache/hive/blob/master/common/src/java/org/apache/hive/common/util/BloomFilter.java
+ */
+public class BloomFilter {
Review Comment:
Can you add some ut for these classes?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "Aitozi (via GitHub)" <gi...@apache.org>.
Aitozi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1892954338
> > Thanks @Aitozi for your contribution.
> > Can you provide some benchmarks? For example, for high update rates, low update rates, and first-row.
>
> Yes, I'm still doing some tests, I will share some data here later.
Some tests data for low updates of first-row. The input throughput can be doubled compared to the non-bloomfilter version. One of the bottlenecks in the non-bloomfilter is key lookup.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "Aitozi (via GitHub)" <gi...@apache.org>.
Aitozi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1901778847
Results of highMatch
```
Apple M1 Pro
lookup: Best/Avg Time(ms) Row Rate(M/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_lookup_bf-disabled-0B-value 16 / 19 6.2 160.8 1.0X
OPERATORTEST_lookup_bf-enabled-0B-value 20 / 20 5.1 196.7 0.8X
OPERATORTEST_lookup_bf-disabled-500B-value 27 / 36 3.7 272.4 0.6X
OPERATORTEST_lookup_bf-enabled-500B-value 22 / 35 4.6 215.6 0.7X
OPERATORTEST_lookup_bf-disabled-1000B-value 45 / 53 2.2 453.7 0.4X
OPERATORTEST_lookup_bf-enabled-1000B-value 46 / 53 2.2 464.5 0.3X
OPERATORTEST_lookup_bf-disabled-2000B-value 68 / 76 1.5 677.6 0.2X
OPERATORTEST_lookup_bf-enabled-2000B-value 62 / 74 1.6 624.0 0.3X
```
Results of low match
```
OpenJDK 64-Bit Server VM 1.8.0_292-b10 on Mac OS X 10.16
Apple M1 Pro
lookup: Best/Avg Time(ms) Row Rate(M/s) Per Row(ns) Relative
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
OPERATORTEST_lookup_bf-disabled-0B-value 41 / 44 2.4 409.6 1.0X
OPERATORTEST_lookup_bf-enabled-0B-value 6 / 8 16.0 62.7 6.5X
OPERATORTEST_lookup_bf-disabled-500B-value 37 / 38 2.7 367.5 1.1X
OPERATORTEST_lookup_bf-enabled-500B-value 5 / 6 18.2 54.9 7.5X
OPERATORTEST_lookup_bf-disabled-1000B-value 37 / 38 2.7 366.0 1.1X
OPERATORTEST_lookup_bf-enabled-1000B-value 5 / 5 19.2 52.1 7.9X
OPERATORTEST_lookup_bf-disabled-2000B-value 37 / 40 2.7 368.7 1.1X
OPERATORTEST_lookup_bf-enabled-2000B-value 5 / 5 19.0 52.6 7.8X
```
The benefit is clearly seen in the low match result, and for the high match, the result is almost identical in two versions. Do you think it's alright to have this feature enabled by default? @JingsongLi
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "Aitozi (via GitHub)" <gi...@apache.org>.
Aitozi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1903072811
> @Aitozi Can you explain what is 0B 500B 1000B?
It's the size of the value. 0B represents the first_row case. The size of the value will affect the cache usage.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "Aitozi (via GitHub)" <gi...@apache.org>.
Aitozi commented on code in PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#discussion_r1456845540
##########
paimon-common/src/main/java/org/apache/paimon/lookup/bloom/BloomFilter.java:
##########
@@ -0,0 +1,148 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ */
+
+package org.apache.paimon.lookup.bloom;
+
+import org.apache.paimon.memory.MemorySegment;
+
+import static org.apache.paimon.utils.Preconditions.checkArgument;
+
+/**
+ * BloomFilter is a probabilistic data structure for set membership check. BloomFilters are highly
+ * space efficient when compared to using a HashSet. Because of the probabilistic nature of bloom
+ * filter false positive (element not present in bloom filter but test() says true) are possible but
+ * false negatives are not possible (if element is present then test() will never say false). The
+ * false positive probability is configurable depending on which storage requirement may increase or
+ * decrease. Lower the false positive probability greater is the space requirement. Bloom filters
+ * are sensitive to number of elements that will be inserted in the bloom filter. During the
+ * creation of bloom filter expected number of entries must be specified. If the number of
+ * insertions exceed the specified initial number of entries then false positive probability will
+ * increase accordingly.
+ *
+ * <p>Internally, this implementation of bloom filter uses MemorySegment to store BitSet,
+ * BloomFilter and BitSet are designed to be able to switch between different MemorySegments, so
+ * that Flink can share the same BloomFilter/BitSet object instance for different bloom filters.
+ *
+ * <p>Part of this class refers to the implementation from Apache Hive project
+ * https://github.com/apache/hive/blob/master/common/src/java/org/apache/hive/common/util/BloomFilter.java
+ */
+public class BloomFilter {
Review Comment:
OK
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1905852130
See https://github.com/apache/incubator-paimon/pull/2773
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "Aitozi (via GitHub)" <gi...@apache.org>.
Aitozi commented on code in PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#discussion_r1452848141
##########
paimon-common/src/main/java/org/apache/paimon/lookup/hash/HashLookupStoreReader.java:
##########
@@ -87,6 +94,15 @@ public class HashLookupStoreReader
int keyLengthCount = dataInputStream.readInt();
// Max key length
int maxKeyLength = dataInputStream.readInt();
+ // BloomFilter
+ bloomFilterEnabled = dataInputStream.readBoolean();
+ if (bloomFilterEnabled) {
+ this.bloomFilter =
Review Comment:
I'll take a look
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1903054035
@Aitozi Can you explain what is 0B 500B 1000B?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi merged PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1891256261
Thanks @Aitozi for your contribution.
Can you provide some benchmarks? For example, for high update rates, low update rates, and first-row.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "Aitozi (via GitHub)" <gi...@apache.org>.
Aitozi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1891267793
> Thanks @Aitozi for your contribution.
>
> Can you provide some benchmarks? For example, for high update rates, low update rates, and first-row.
Yes, I'm still doing some tests, I will share some data here later.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1905254383
Hi @Aitozi Thanks for your update!
Left two comments:
1. There is no need to use segments when writing BloomFilter, just use byte[] instead
2. It is best to use standard Segments (default 64KB) when reading BloomFilter to avoid modifying the Cache management system
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on code in PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#discussion_r1452845747
##########
paimon-common/src/main/java/org/apache/paimon/lookup/hash/HashLookupStoreReader.java:
##########
@@ -87,6 +94,15 @@ public class HashLookupStoreReader
int keyLengthCount = dataInputStream.readInt();
// Max key length
int maxKeyLength = dataInputStream.readInt();
+ // BloomFilter
+ bloomFilterEnabled = dataInputStream.readBoolean();
+ if (bloomFilterEnabled) {
+ this.bloomFilter =
Review Comment:
Can this BF into cache?
We have an implementation in Flink: `HashTableBloomFilter`.
BF can base on memory segment too.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "JingsongLi (via GitHub)" <gi...@apache.org>.
JingsongLi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1907703111
Hi @Aitozi , I append this commit https://github.com/apache/incubator-paimon/pull/2696/commits/443a30584b209181653d7e33f21984bb21a60e32 to refactor
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [core] Introduce bloom filter for local lookup cache file [incubator-paimon]
Posted by "Aitozi (via GitHub)" <gi...@apache.org>.
Aitozi commented on PR #2696:
URL: https://github.com/apache/incubator-paimon/pull/2696#issuecomment-1907756595
> Hi @Aitozi , I append this commit [443a305](https://github.com/apache/incubator-paimon/commit/443a30584b209181653d7e33f21984bb21a60e32) to refactor
+1, It looks much natural, thanks for your update
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@paimon.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org