{"action":"created","comment":{"url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments/62291452","id":62291452,"diff_hunk":"@@ -101,5 +104,23 @@ void ExecutionHeuristics::optimizeExecutionPlan(QueryPlan *query_plan,\n   }\n }\n \n+void ExecutionHeuristics::setBloomFilterProperties(serialization::BloomFilter *bloom_filter_proto,\n+                                                   const CatalogRelation *relation) {\n+  const std::size_t cardinality = relation->estimateTupleCardinality();\n+  if (cardinality < kOneThousand) {\n+    bloom_filter_proto->set_bloom_filter_size(kOneThousand / kCompressionFactor);\n+    bloom_filter_proto->set_number_of_hashes(kVeryLowSparsityHash);\n+  } else if (cardinality >= kOneThousand && cardinality < kTenThousand) {\n+    bloom_filter_proto->set_bloom_filter_size(kTenThousand / kCompressionFactor);\n+    bloom_filter_proto->set_number_of_hashes(kLowSparsityHash);\n+  } else if (cardinality >= kTenThousand && cardinality < kHundredThousand) {","path":"query_optimizer/ExecutionHeuristics.cpp","position":null,"original_position":36,"commit_id":"42a645ae183825d614dc2703c2baa3b05edce12b","original_commit_id":"c6f11d860cbeb8c4ab39bccc3db3ebde5053833f","user":{"login":"saketj","id":3624476,"avatar_url":"https://avatars.githubusercontent.com/u/3624476?v=3","gravatar_id":"","url":"https://api.github.com/users/saketj","html_url":"https://github.com/saketj","followers_url":"https://api.github.com/users/saketj/followers","following_url":"https://api.github.com/users/saketj/following{/other_user}","gists_url":"https://api.github.com/users/saketj/gists{/gist_id}","starred_url":"https://api.github.com/users/saketj/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/saketj/subscriptions","organizations_url":"https://api.github.com/users/saketj/orgs","repos_url":"https://api.github.com/users/saketj/repos","events_url":"https://api.github.com/users/saketj/events{/privacy}","received_events_url":"https://api.github.com/users/saketj/received_events","type":"User","site_admin":false},"body":"Done.","created_at":"2016-05-06T06:01:07Z","updated_at":"2016-05-06T06:01:07Z","html_url":"https://github.com/pivotalsoftware/quickstep/pull/195#discussion_r62291452","pull_request_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/195","_links":{"self":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments/62291452"},"html":{"href":"https://github.com/pivotalsoftware/quickstep/pull/195#discussion_r62291452"},"pull_request":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/195"}}},"pull_request":{"url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/195","id":68078363,"html_url":"https://github.com/pivotalsoftware/quickstep/pull/195","diff_url":"https://github.com/pivotalsoftware/quickstep/pull/195.diff","patch_url":"https://github.com/pivotalsoftware/quickstep/pull/195.patch","issue_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/195","number":195,"state":"open","locked":false,"title":"Enable semi-join optimization for left-deep trees through bloom filters","user":{"login":"saketj","id":3624476,"avatar_url":"https://avatars.githubusercontent.com/u/3624476?v=3","gravatar_id":"","url":"https://api.github.com/users/saketj","html_url":"https://github.com/saketj","followers_url":"https://api.github.com/users/saketj/followers","following_url":"https://api.github.com/users/saketj/following{/other_user}","gists_url":"https://api.github.com/users/saketj/gists{/gist_id}","starred_url":"https://api.github.com/users/saketj/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/saketj/subscriptions","organizations_url":"https://api.github.com/users/saketj/orgs","repos_url":"https://api.github.com/users/saketj/repos","events_url":"https://api.github.com/users/saketj/events{/privacy}","received_events_url":"https://api.github.com/users/saketj/received_events","type":"User","site_admin":false},"body":"This PR adds support for semi-join optimization for left-deep trees through the use of bloom filters. The motivation behind this PR is that often the bottom-most join in a left-deep tree returns maximum number of tuples from the fact table, a majority of which are then discarded by joins up the tree. If somehow, the selectivity information from up the tree could be passed down to the bottom-most operators, we could avoid the cost of potentially passing and storing huge number of unnecessary tuples during query execution. \r\n\r\nBloom filters are lightweight data structures that can help us push down this selectivity information down the operator tree. Therefore, the key idea is to delay the processing of the bottom-most probe operator on the fact table, until bloom filters on all the build operators on all the dimension tables are built. Then pass the bloom filters sideways to this probe operator, which can use these bloom filters to weed out the unnecessary tuples.\r\n\r\nThis feature is controlled by GFLAGs and is turned off by default. Pass the `--optimize_joins` flag from the command-line to explicitly enable this optimization.\r\n\r\nOn a typical left-deep join query like SSB Query 4, this optimization reduces the query execution time by almost 40%.","created_at":"2016-04-27T15:54:55Z","updated_at":"2016-05-06T06:01:07Z","closed_at":null,"merged_at":null,"merge_commit_sha":"9b1ac1f30f52ec9fa92f5154c119d792acf8ff9d","assignee":{"login":"hbdeshmukh","id":3750801,"avatar_url":"https://avatars.githubusercontent.com/u/3750801?v=3","gravatar_id":"","url":"https://api.github.com/users/hbdeshmukh","html_url":"https://github.com/hbdeshmukh","followers_url":"https://api.github.com/users/hbdeshmukh/followers","following_url":"https://api.github.com/users/hbdeshmukh/following{/other_user}","gists_url":"https://api.github.com/users/hbdeshmukh/gists{/gist_id}","starred_url":"https://api.github.com/users/hbdeshmukh/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hbdeshmukh/subscriptions","organizations_url":"https://api.github.com/users/hbdeshmukh/orgs","repos_url":"https://api.github.com/users/hbdeshmukh/repos","events_url":"https://api.github.com/users/hbdeshmukh/events{/privacy}","received_events_url":"https://api.github.com/users/hbdeshmukh/received_events","type":"User","site_admin":false},"milestone":null,"commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/195/commits","review_comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/195/comments","review_comment_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments{/number}","comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/195/comments","statuses_url":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/42a645ae183825d614dc2703c2baa3b05edce12b","head":{"label":"pivotalsoftware:bloom-optimized-joins","ref":"bloom-optimized-joins","sha":"42a645ae183825d614dc2703c2baa3b05edce12b","user":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"repo":{"id":45578105,"name":"quickstep","full_name":"pivotalsoftware/quickstep","owner":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pivotalsoftware/quickstep","description":"Quickstep Project","fork":false,"url":"https://api.github.com/repos/pivotalsoftware/quickstep","forks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/forks","keys_url":"https://api.github.com/repos/pivotalsoftware/quickstep/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pivotalsoftware/quickstep/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pivotalsoftware/quickstep/teams","hooks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/hooks","issue_events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/events{/number}","events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/events","assignees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/assignees{/user}","branches_url":"https://api.github.com/repos/pivotalsoftware/quickstep/branches{/branch}","tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/tags","blobs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/refs{/sha}","trees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/{sha}","languages_url":"https://api.github.com/repos/pivotalsoftware/quickstep/languages","stargazers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/stargazers","contributors_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contributors","subscribers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscribers","subscription_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscription","commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/commits{/sha}","git_commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/commits{/sha}","comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/comments{/number}","issue_comment_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/comments{/number}","contents_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contents/{+path}","compare_url":"https://api.github.com/repos/pivotalsoftware/quickstep/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pivotalsoftware/quickstep/merges","archive_url":"https://api.github.com/repos/pivotalsoftware/quickstep/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pivotalsoftware/quickstep/downloads","issues_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues{/number}","pulls_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls{/number}","milestones_url":"https://api.github.com/repos/pivotalsoftware/quickstep/milestones{/number}","notifications_url":"https://api.github.com/repos/pivotalsoftware/quickstep/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pivotalsoftware/quickstep/labels{/name}","releases_url":"https://api.github.com/repos/pivotalsoftware/quickstep/releases{/id}","deployments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/deployments","created_at":"2015-11-05T01:06:50Z","updated_at":"2016-05-03T17:41:32Z","pushed_at":"2016-05-06T05:33:41Z","git_url":"git://github.com/pivotalsoftware/quickstep.git","ssh_url":"git@github.com:pivotalsoftware/quickstep.git","clone_url":"https://github.com/pivotalsoftware/quickstep.git","svn_url":"https://github.com/pivotalsoftware/quickstep","homepage":null,"size":9152,"stargazers_count":17,"watchers_count":17,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":10,"mirror_url":null,"open_issues_count":18,"forks":10,"open_issues":18,"watchers":17,"default_branch":"master"}},"base":{"label":"pivotalsoftware:master","ref":"master","sha":"c7a58f972e96868c5317e8c94fc0f1e423f64899","user":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"repo":{"id":45578105,"name":"quickstep","full_name":"pivotalsoftware/quickstep","owner":{"login":"pivotalsoftware","id":4247270,"avatar_url":"https://avatars.githubusercontent.com/u/4247270?v=3","gravatar_id":"","url":"https://api.github.com/users/pivotalsoftware","html_url":"https://github.com/pivotalsoftware","followers_url":"https://api.github.com/users/pivotalsoftware/followers","following_url":"https://api.github.com/users/pivotalsoftware/following{/other_user}","gists_url":"https://api.github.com/users/pivotalsoftware/gists{/gist_id}","starred_url":"https://api.github.com/users/pivotalsoftware/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pivotalsoftware/subscriptions","organizations_url":"https://api.github.com/users/pivotalsoftware/orgs","repos_url":"https://api.github.com/users/pivotalsoftware/repos","events_url":"https://api.github.com/users/pivotalsoftware/events{/privacy}","received_events_url":"https://api.github.com/users/pivotalsoftware/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pivotalsoftware/quickstep","description":"Quickstep Project","fork":false,"url":"https://api.github.com/repos/pivotalsoftware/quickstep","forks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/forks","keys_url":"https://api.github.com/repos/pivotalsoftware/quickstep/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pivotalsoftware/quickstep/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pivotalsoftware/quickstep/teams","hooks_url":"https://api.github.com/repos/pivotalsoftware/quickstep/hooks","issue_events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/events{/number}","events_url":"https://api.github.com/repos/pivotalsoftware/quickstep/events","assignees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/assignees{/user}","branches_url":"https://api.github.com/repos/pivotalsoftware/quickstep/branches{/branch}","tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/tags","blobs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/refs{/sha}","trees_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/{sha}","languages_url":"https://api.github.com/repos/pivotalsoftware/quickstep/languages","stargazers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/stargazers","contributors_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contributors","subscribers_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscribers","subscription_url":"https://api.github.com/repos/pivotalsoftware/quickstep/subscription","commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/commits{/sha}","git_commits_url":"https://api.github.com/repos/pivotalsoftware/quickstep/git/commits{/sha}","comments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/comments{/number}","issue_comment_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/comments{/number}","contents_url":"https://api.github.com/repos/pivotalsoftware/quickstep/contents/{+path}","compare_url":"https://api.github.com/repos/pivotalsoftware/quickstep/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pivotalsoftware/quickstep/merges","archive_url":"https://api.github.com/repos/pivotalsoftware/quickstep/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pivotalsoftware/quickstep/downloads","issues_url":"https://api.github.com/repos/pivotalsoftware/quickstep/issues{/number}","pulls_url":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls{/number}","milestones_url":"https://api.github.com/repos/pivotalsoftware/quickstep/milestones{/number}","notifications_url":"https://api.github.com/repos/pivotalsoftware/quickstep/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pivotalsoftware/quickstep/labels{/name}","releases_url":"https://api.github.com/repos/pivotalsoftware/quickstep/releases{/id}","deployments_url":"https://api.github.com/repos/pivotalsoftware/quickstep/deployments","created_at":"2015-11-05T01:06:50Z","updated_at":"2016-05-03T17:41:32Z","pushed_at":"2016-05-06T05:33:41Z","git_url":"git://github.com/pivotalsoftware/quickstep.git","ssh_url":"git@github.com:pivotalsoftware/quickstep.git","clone_url":"https://github.com/pivotalsoftware/quickstep.git","svn_url":"https://github.com/pivotalsoftware/quickstep","homepage":null,"size":9152,"stargazers_count":17,"watchers_count":17,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":10,"mirror_url":null,"open_issues_count":18,"forks":10,"open_issues":18,"watchers":17,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/195"},"html":{"href":"https://github.com/pivotalsoftware/quickstep/pull/195"},"issue":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/195"},"comments":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/issues/195/comments"},"review_comments":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/195/comments"},"review_comment":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/pulls/195/commits"},"statuses":{"href":"https://api.github.com/repos/pivotalsoftware/quickstep/statuses/42a645ae183825d614dc2703c2baa3b05edce12b"}}}}