You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by ChengXiangLi <gi...@git.apache.org> on 2015/07/06 10:51:14 UTC
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
GitHub user ChengXiangLi opened a pull request:
https://github.com/apache/flink/pull/888
[FLINK-2240] Use BloomFilter to filter probe records in Hybrid-Hash-Join
In Hybrid-Hash-Join, while small table does not fit into memory, part of the small table data would be spilled to disk, and the counterpart partition of big table data would be spilled to disk in probe phase as well. If we build a BloomFilter while spill small table to disk during build phase, and use it to filter the big table records which tend to be spilled to disk, this may greatly reduce the spilled big table file size, and saved the disk IO cost for writing and further reading.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/ChengXiangLi/flink hj-bloomfilter
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/flink/pull/888.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #888
----
commit 78c59d6ee52a00fd4964001cbce81437c38d86cb
Author: chengxiang li <ch...@intel.com>
Date: 2015-07-03T15:53:47Z
add bloom filter for spilled partitions in hashtable.
commit cacaa9a15a5330c6130306841ef73958490cf69d
Author: chengxiang li <ch...@intel.com>
Date: 2015-07-06T07:15:39Z
fix previous get buckets method
commit 6bbbb27d4935da72ae44ec404f884a74de7bbc4c
Author: chengxiang li <ch...@intel.com>
Date: 2015-07-06T08:07:30Z
fix some format issues.
commit b7fee8d26445db4bba7928bfff8a9dd5ada8cd03
Author: chengxiang li <ch...@intel.com>
Date: 2015-07-06T08:08:52Z
Merge remote-tracking branch 'upstream/master' into hj-bloomfilter
commit d352c090b9c06baf701235809f7dfd0b4e9b87af
Author: Li <ch...@intel.com>
Date: 2015-07-06T08:44:13Z
add tab as indent of blank line.
commit edacfb3ae17beeb84630d73f8452629d3e19b66b
Author: Li <ch...@intel.com>
Date: 2015-07-06T08:48:56Z
fix tab indent for blank lines.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by StephanEwen <gi...@git.apache.org>.
Github user StephanEwen commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-125903682
Okay, it took me a while, but I actually walked through this and would like to merge it soon.
To make this functionality configurable, I opened an issue to give runtime operators access to the TaskManager config, so that we can define a switch to turn this on and off.
I would actually turn it on by default, it seems to work well as far as I have tried it.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by ChengXiangLi <gi...@git.apache.org>.
Github user ChengXiangLi commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-128563750
Thanks for the review, @StephanEwen , i'm very interesting in this project, and i would like to contribute more. @vasia , I think stephan has helped to answer the question yet, the most important reason is that i want to reuse the memory occupied by hash table buckets. Besides, since this is a performance sense issue, i try to make this bloom filter as much simple and efficient as i can, for example, the hashcode of join key is already generated and stored in hybrid hash join, i just reuse the hashcode instead of generate it by join key value inside bloom filter again.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by vasia <gi...@git.apache.org>.
Github user vasia commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-128620294
Makes sense. Thank you both!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by StephanEwen <gi...@git.apache.org>.
Github user StephanEwen commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-128446267
The bloom filters are stored in subregions of Flink's memory segments, not in any additional memory.
That is very nice (occupies no extra memory), but requires to go against Flink's memory segments, rather than longs or byte arrays. Hence, the custom implementation.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by ChengXiangLi <gi...@git.apache.org>.
Github user ChengXiangLi commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-119778981
Fixed the unit test failure and merge it into the latest patch, it passed all the checks now.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by ChengXiangLi <gi...@git.apache.org>.
Github user ChengXiangLi commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-118786914
I did a simple test on single node, here is the related information:
1 task manager, 1 slot, 1G RAM assigned, probe table 5G, build table 1G, half of build table partitions get spilled to disk.
FOF: how many percent records been filtered out during probe phase?
FOF | without bloom filter(s) | with bloom filter(s)
------------- | ------------- | -------------------
90% | 210 | 147
50% | 214 | 187
0 | 236 | 252
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by StephanEwen <gi...@git.apache.org>.
Github user StephanEwen commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-119873635
Nice, thank you.
I will try to take a look soon...
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by ChengXiangLi <gi...@git.apache.org>.
Github user ChengXiangLi commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-119530383
Thanks Stephan for comments, i've added the configuration switch and performance benchmark in the latest commit, and research on the unit test failure now.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by StephanEwen <gi...@git.apache.org>.
Github user StephanEwen commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-128440090
Manually merged in 61dcae391cb3b45ba3aff47d4d9163889d2958a4
I added a commit on top to pass the flag to enable/disable bloom filters through the runtime configuration. That is the basis for later allowing it to enable it on a per-job basis. Also, we want to get rid of the `GlobalConfiguration` singleton pattern.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by StephanEwen <gi...@git.apache.org>.
Github user StephanEwen commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-128442757
Oh, I forgot to add the closing message to the commit, so the ASF bot did not close the pull request. Can you close the pull request manually (only you as the owner can do that).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by ChengXiangLi <gi...@git.apache.org>.
Github user ChengXiangLi closed the pull request at:
https://github.com/apache/flink/pull/888
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by StephanEwen <gi...@git.apache.org>.
Github user StephanEwen commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-128441993
This was a super cool contribution. A pretty sophisticated addition, super testing, high code quality.
I am very impressed!
I hope you will contribute more to Flink. Already saw that you opened another pull request, for a sampling operator. Happy that this is happening :-)
In the future, I can hopefully review and merge the pull requests faster. The past weeks, I did not get to code work as much as I wanted, and the list of critical issues was long, so this pull request got delayed a bit.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by ChengXiangLi <gi...@git.apache.org>.
Github user ChengXiangLi commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-125914138
Thanks to point that out, Stephan, i didn't notice the configuration issue before.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by StephanEwen <gi...@git.apache.org>.
Github user StephanEwen commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-119136367
This is a very nice idea, thank you for the contribution! The numbers look quite encouraging.
I need to look into this carefully, as it touches a very sensitive part of the system. It will probably take me a bit of time.
Here are some initial comments:
- The integration tests seem to be failing, this change apparently triggers a stack-overflow at some point. Have a look at the logs of the Travis CI build.
- Can we add a flag to the hash-table, to enable/disable the bloom-filters? That would make it easier for future comparisons.
- Could you include a standalone mini benchmark similar to the one you did where you posted the numbers here? A simple standalone Java executable that creates the hash table and feeds some generated records through it (with bloom filters activated and deactivated)? It would not start a full Flink cluster, but only test the HashJoin in isolation.
We like to include some of those mini bechmarks for performance critical parts, and re-run them once in a while to determine how the performance behaves at that point.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] flink pull request: [FLINK-2240] Use BloomFilter to filter probe r...
Posted by vasia <gi...@git.apache.org>.
Github user vasia commented on the pull request:
https://github.com/apache/flink/pull/888#issuecomment-128445757
Hi,
this looks great indeed!
Just out of curiosity, why did you write your own bloom filter implementation and not use a ready one, e.g. from guava? I'm wondering because in #923 we also want to use a bloom filter for an approximate algorithm implementation.
Thanks!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---