{"action":"created","comment":{"url":"https://api.github.com/repos/apache/incubator-hawq/pulls/comments/181689893","pull_request_review_id":112356778,"id":181689893,"diff_hunk":"@@ -0,0 +1,134 @@\n+/*\n+ * Licensed to the Apache Software Foundation (ASF) under one\n+ * or more contributor license agreements.  See the NOTICE file\n+ * distributed with this work for additional information\n+ * regarding copyright ownership.  The ASF licenses this file\n+ * to you under the Apache License, Version 2.0 (the\n+ * \"License\"); you may not use this file except in compliance\n+ * with the License.  You may obtain a copy of the License at\n+ *\n+ *   http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ * Unless required by applicable law or agreed to in writing,\n+ * software distributed under the License is distributed on an\n+ * \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY\n+ * KIND, either express or implied.  See the License for the\n+ * specific language governing permissions and limitations\n+ * under the License.\n+ */\n+\n+#include \"utils/bloomfilter.h\"\n+#include \"utils/elog.h\"\n+#include \"utils/palloc.h\"\n+#include \"lib/stringinfo.h\"\n+#include <assert.h>\n+#include <math.h>\n+\n+uint32_t HASH_SEEDS[8] __attribute__((aligned(32))) = { 0x14EBCDFFU,\n+        0x2A1C1A99U, 0x85CB78FBU, 0x6E8F82DDU, 0xF8464DFFU, 0x1028FEADU,\n+        0x74F04A4DU, 0x1832DB75U };\n+\n+static uint32_t getBucketIdx(uint32_t hash, uint32_t mask)\n+{\n+    /* use Knuth's multiplicative hash */\n+    return ((uint64_t) (hash) * 2654435769ul >> 32) & mask;\n+}\n+\n+/*\n+ * Returns the smallest power of two that is bigger than v.\n+ */\n+int64_t UpperPowerTwo(int64_t v) {\n+    --v;\n+    v |= v >> 1;\n+    v |= v >> 2;\n+    v |= v >> 4;\n+    v |= v >> 8;\n+    v |= v >> 16;\n+    v |= v >> 32;\n+    ++v;\n+    return v;\n+}\n+\n+/*\n+ * Initialize a Bloom filter structure with the memory size of Bloom filter.\n+ */\n+BloomFilter InitBloomFilter(int memory_size)\n+{\n+    BloomFilter bf;\n+    uint32_t nBuckets = max(1, memory_size/(sizeof(BucketWord)*NUM_BUCKET_WORDS));\n+    size_t size = nBuckets*NUM_BUCKET_WORDS*sizeof(BucketWord);\n+    bf = palloc0(offsetof(BloomFilterData, data)  + size);\n+    bf->nInserted = bf->nTested = bf->nMatched = 0;\n+    bf->nBuckets = nBuckets;\n+    bf->data_mask = bf->nBuckets - 1;\n+    bf->data_size = size;\n+    bf->isCreated = true;\n+    elog(LOG, \"Create a Bloom filter with number of buckets:%d, size:%d\",\n+              bf->nBuckets, size);\n+    return bf;\n+}\n+\n+/*\n+ * Insert a value into Bloom filter.\n+ */\n+void InsertBloomFilter(BloomFilter bf, uint32_t value)\n+{\n+    uint32_t bucket_idx = getBucketIdx(value, bf->data_mask);\n+    uint32_t new_bucket[8];\n+    for (int i = 0; i < NUM_BUCKET_WORDS; ++i) {\n+        /*\n+         * Multiply-shift hashing proposed by Dietzfelbinger et al.\n+         * hash a value universally into 5 bits using the random odd seed.\n+         */\n+        new_bucket[i] = (HASH_SEEDS[i] * value) >> (32 - LOG_BUCKET_WORD_BITS);\n+        new_bucket[i] = 1U << new_bucket[i];\n+        bf->data[bucket_idx][i] |= new_bucket[i];\n+    }\n+}\n+\n+/*\n+ * Check whether a value is in this Bloom filter or not.\n+ */\n+bool FindBloomFilter(BloomFilter bf, uint32_t value)\n+{\n+    uint32_t bucket_idx = getBucketIdx(value, bf->data_mask);\n+    for (int i = 0; i < NUM_BUCKET_WORDS; ++i)\n+    {\n+        BucketWord hval = (HASH_SEEDS[i] * value) >> (32 - LOG_BUCKET_WORD_BITS);\n+        hval = 1U << hval;\n+        if (!(bf->data[bucket_idx][i] & hval))\n+        {\n+            return false;\n+        }\n+    }\n+    return true;\n+}\n+\n+void PrintBloomFilter(BloomFilter bf)\n+{\n+    StringInfo bfinfo = makeStringInfo();\n+    appendStringInfo(bfinfo, \"##### Print Bloom filter #####\\n\");\n+    appendStringInfo(bfinfo, \"data_mask: %x, \", bf->data_mask);\n+    appendStringInfo(bfinfo, \"number of buckets: %d\\n s\", bf->nBuckets);\n+    appendStringInfo(bfinfo, \"number of inserted: %d\\n s\", bf->nInserted);\n+    appendStringInfo(bfinfo, \"number of tested: %d\\n s\", bf->nTested);\n+    appendStringInfo(bfinfo, \"number of matched: %d\\n s\", bf->nMatched);\n+    appendStringInfo(bfinfo, \"size: %d\\n s\", bf->data_size);\n+    appendStringInfo(bfinfo, \"##### END Print Bloom filter #####\\n\");\n+    if(bfinfo->data != NULL)\n+    {\n+        pfree(bfinfo->data);","path":"src/backend/utils/hash/bloomfilter.c","position":120,"original_position":120,"commit_id":"11b20b51026419cf91c71cabb9c17e0e467399f7","original_commit_id":"11b20b51026419cf91c71cabb9c17e0e467399f7","user":{"login":"wengyanqing","id":12286146,"avatar_url":"https://avatars2.githubusercontent.com/u/12286146?v=4","gravatar_id":"","url":"https://api.github.com/users/wengyanqing","html_url":"https://github.com/wengyanqing","followers_url":"https://api.github.com/users/wengyanqing/followers","following_url":"https://api.github.com/users/wengyanqing/following{/other_user}","gists_url":"https://api.github.com/users/wengyanqing/gists{/gist_id}","starred_url":"https://api.github.com/users/wengyanqing/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wengyanqing/subscriptions","organizations_url":"https://api.github.com/users/wengyanqing/orgs","repos_url":"https://api.github.com/users/wengyanqing/repos","events_url":"https://api.github.com/users/wengyanqing/events{/privacy}","received_events_url":"https://api.github.com/users/wengyanqing/received_events","type":"User","site_admin":false},"body":"Print the Bloom filter info before pfree ?","created_at":"2018-04-16T10:33:27Z","updated_at":"2018-04-16T10:44:12Z","html_url":"https://github.com/apache/incubator-hawq/pull/1354#discussion_r181689893","pull_request_url":"https://api.github.com/repos/apache/incubator-hawq/pulls/1354","author_association":"CONTRIBUTOR","_links":{"self":{"href":"https://api.github.com/repos/apache/incubator-hawq/pulls/comments/181689893"},"html":{"href":"https://github.com/apache/incubator-hawq/pull/1354#discussion_r181689893"},"pull_request":{"href":"https://api.github.com/repos/apache/incubator-hawq/pulls/1354"}}},"pull_request":{"url":"https://api.github.com/repos/apache/incubator-hawq/pulls/1354","id":181694261,"html_url":"https://github.com/apache/incubator-hawq/pull/1354","diff_url":"https://github.com/apache/incubator-hawq/pull/1354.diff","patch_url":"https://github.com/apache/incubator-hawq/pull/1354.patch","issue_url":"https://api.github.com/repos/apache/incubator-hawq/issues/1354","number":1354,"state":"open","locked":false,"title":"HAWQ-1606. Implement Deciding to Create Bloom Filter During Query Plan And Create Bloom filter For Inner Table","user":{"login":"linwen","id":985318,"avatar_url":"https://avatars0.githubusercontent.com/u/985318?v=4","gravatar_id":"","url":"https://api.github.com/users/linwen","html_url":"https://github.com/linwen","followers_url":"https://api.github.com/users/linwen/followers","following_url":"https://api.github.com/users/linwen/following{/other_user}","gists_url":"https://api.github.com/users/linwen/gists{/gist_id}","starred_url":"https://api.github.com/users/linwen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/linwen/subscriptions","organizations_url":"https://api.github.com/users/linwen/orgs","repos_url":"https://api.github.com/users/linwen/repos","events_url":"https://api.github.com/users/linwen/events{/privacy}","received_events_url":"https://api.github.com/users/linwen/received_events","type":"User","site_admin":false},"body":"This commit implements deciding to create Bloom Filter during query plan and create Bloom filter for inner table, including:\r\n\r\n1. Introduce a GUC, hawq_hashjoin_bloomfilter_max_memory_size, controls the maximum memory size for one bloom filter in hash join.\r\n2. Introduce a GUC, hawq_hashjoin_bloomfilter_ratio, when the ratio of (the estimated number of hash join tuples)/(number of tuples of outer table) is lower than the GUC, then Bloom filter can be used in hash join.\r\n3. Decide whether to create Bloom filter during query plan phase.\r\n4. During query execution phase, create Bloom filter structure and poputlate it for tuples from inner table.\r\n\r\nPlease review it, thanks!","created_at":"2018-04-15T11:36:50Z","updated_at":"2018-04-16T10:44:12Z","closed_at":null,"merged_at":null,"merge_commit_sha":"358340f73f607bff8b76448a87d99f0a107fd5e0","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/apache/incubator-hawq/pulls/1354/commits","review_comments_url":"https://api.github.com/repos/apache/incubator-hawq/pulls/1354/comments","review_comment_url":"https://api.github.com/repos/apache/incubator-hawq/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/incubator-hawq/issues/1354/comments","statuses_url":"https://api.github.com/repos/apache/incubator-hawq/statuses/11b20b51026419cf91c71cabb9c17e0e467399f7","head":{"label":"linwen:hawq-1606","ref":"hawq-1606","sha":"11b20b51026419cf91c71cabb9c17e0e467399f7","user":{"login":"linwen","id":985318,"avatar_url":"https://avatars0.githubusercontent.com/u/985318?v=4","gravatar_id":"","url":"https://api.github.com/users/linwen","html_url":"https://github.com/linwen","followers_url":"https://api.github.com/users/linwen/followers","following_url":"https://api.github.com/users/linwen/following{/other_user}","gists_url":"https://api.github.com/users/linwen/gists{/gist_id}","starred_url":"https://api.github.com/users/linwen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/linwen/subscriptions","organizations_url":"https://api.github.com/users/linwen/orgs","repos_url":"https://api.github.com/users/linwen/repos","events_url":"https://api.github.com/users/linwen/events{/privacy}","received_events_url":"https://api.github.com/users/linwen/received_events","type":"User","site_admin":false},"repo":{"id":44303111,"name":"incubator-hawq","full_name":"linwen/incubator-hawq","owner":{"login":"linwen","id":985318,"avatar_url":"https://avatars0.githubusercontent.com/u/985318?v=4","gravatar_id":"","url":"https://api.github.com/users/linwen","html_url":"https://github.com/linwen","followers_url":"https://api.github.com/users/linwen/followers","following_url":"https://api.github.com/users/linwen/following{/other_user}","gists_url":"https://api.github.com/users/linwen/gists{/gist_id}","starred_url":"https://api.github.com/users/linwen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/linwen/subscriptions","organizations_url":"https://api.github.com/users/linwen/orgs","repos_url":"https://api.github.com/users/linwen/repos","events_url":"https://api.github.com/users/linwen/events{/privacy}","received_events_url":"https://api.github.com/users/linwen/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/linwen/incubator-hawq","description":"Mirror of Apache HAWQ (Incubating)","fork":true,"url":"https://api.github.com/repos/linwen/incubator-hawq","forks_url":"https://api.github.com/repos/linwen/incubator-hawq/forks","keys_url":"https://api.github.com/repos/linwen/incubator-hawq/keys{/key_id}","collaborators_url":"https://api.github.com/repos/linwen/incubator-hawq/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/linwen/incubator-hawq/teams","hooks_url":"https://api.github.com/repos/linwen/incubator-hawq/hooks","issue_events_url":"https://api.github.com/repos/linwen/incubator-hawq/issues/events{/number}","events_url":"https://api.github.com/repos/linwen/incubator-hawq/events","assignees_url":"https://api.github.com/repos/linwen/incubator-hawq/assignees{/user}","branches_url":"https://api.github.com/repos/linwen/incubator-hawq/branches{/branch}","tags_url":"https://api.github.com/repos/linwen/incubator-hawq/tags","blobs_url":"https://api.github.com/repos/linwen/incubator-hawq/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/linwen/incubator-hawq/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/linwen/incubator-hawq/git/refs{/sha}","trees_url":"https://api.github.com/repos/linwen/incubator-hawq/git/trees{/sha}","statuses_url":"https://api.github.com/repos/linwen/incubator-hawq/statuses/{sha}","languages_url":"https://api.github.com/repos/linwen/incubator-hawq/languages","stargazers_url":"https://api.github.com/repos/linwen/incubator-hawq/stargazers","contributors_url":"https://api.github.com/repos/linwen/incubator-hawq/contributors","subscribers_url":"https://api.github.com/repos/linwen/incubator-hawq/subscribers","subscription_url":"https://api.github.com/repos/linwen/incubator-hawq/subscription","commits_url":"https://api.github.com/repos/linwen/incubator-hawq/commits{/sha}","git_commits_url":"https://api.github.com/repos/linwen/incubator-hawq/git/commits{/sha}","comments_url":"https://api.github.com/repos/linwen/incubator-hawq/comments{/number}","issue_comment_url":"https://api.github.com/repos/linwen/incubator-hawq/issues/comments{/number}","contents_url":"https://api.github.com/repos/linwen/incubator-hawq/contents/{+path}","compare_url":"https://api.github.com/repos/linwen/incubator-hawq/compare/{base}...{head}","merges_url":"https://api.github.com/repos/linwen/incubator-hawq/merges","archive_url":"https://api.github.com/repos/linwen/incubator-hawq/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/linwen/incubator-hawq/downloads","issues_url":"https://api.github.com/repos/linwen/incubator-hawq/issues{/number}","pulls_url":"https://api.github.com/repos/linwen/incubator-hawq/pulls{/number}","milestones_url":"https://api.github.com/repos/linwen/incubator-hawq/milestones{/number}","notifications_url":"https://api.github.com/repos/linwen/incubator-hawq/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/linwen/incubator-hawq/labels{/name}","releases_url":"https://api.github.com/repos/linwen/incubator-hawq/releases{/id}","deployments_url":"https://api.github.com/repos/linwen/incubator-hawq/deployments","created_at":"2015-10-15T08:14:07Z","updated_at":"2015-10-15T08:14:37Z","pushed_at":"2018-04-15T11:31:20Z","git_url":"git://github.com/linwen/incubator-hawq.git","ssh_url":"git@github.com:linwen/incubator-hawq.git","clone_url":"https://github.com/linwen/incubator-hawq.git","svn_url":"https://github.com/linwen/incubator-hawq","homepage":null,"size":71070,"stargazers_count":0,"watchers_count":0,"language":"C","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"other","name":"Other","spdx_id":null,"url":null},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"b6391f19163e5e332a870c652c2f4327ed861b68","user":{"login":"apache","id":47359,"avatar_url":"https://avatars0.githubusercontent.com/u/47359?v=4","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":41952293,"name":"incubator-hawq","full_name":"apache/incubator-hawq","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars0.githubusercontent.com/u/47359?v=4","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/incubator-hawq","description":"Mirror of Apache HAWQ (Incubating)","fork":false,"url":"https://api.github.com/repos/apache/incubator-hawq","forks_url":"https://api.github.com/repos/apache/incubator-hawq/forks","keys_url":"https://api.github.com/repos/apache/incubator-hawq/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/incubator-hawq/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/incubator-hawq/teams","hooks_url":"https://api.github.com/repos/apache/incubator-hawq/hooks","issue_events_url":"https://api.github.com/repos/apache/incubator-hawq/issues/events{/number}","events_url":"https://api.github.com/repos/apache/incubator-hawq/events","assignees_url":"https://api.github.com/repos/apache/incubator-hawq/assignees{/user}","branches_url":"https://api.github.com/repos/apache/incubator-hawq/branches{/branch}","tags_url":"https://api.github.com/repos/apache/incubator-hawq/tags","blobs_url":"https://api.github.com/repos/apache/incubator-hawq/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/incubator-hawq/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/incubator-hawq/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/incubator-hawq/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/incubator-hawq/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/incubator-hawq/languages","stargazers_url":"https://api.github.com/repos/apache/incubator-hawq/stargazers","contributors_url":"https://api.github.com/repos/apache/incubator-hawq/contributors","subscribers_url":"https://api.github.com/repos/apache/incubator-hawq/subscribers","subscription_url":"https://api.github.com/repos/apache/incubator-hawq/subscription","commits_url":"https://api.github.com/repos/apache/incubator-hawq/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/incubator-hawq/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/incubator-hawq/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/incubator-hawq/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/incubator-hawq/contents/{+path}","compare_url":"https://api.github.com/repos/apache/incubator-hawq/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/incubator-hawq/merges","archive_url":"https://api.github.com/repos/apache/incubator-hawq/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/incubator-hawq/downloads","issues_url":"https://api.github.com/repos/apache/incubator-hawq/issues{/number}","pulls_url":"https://api.github.com/repos/apache/incubator-hawq/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/incubator-hawq/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/incubator-hawq/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/incubator-hawq/labels{/name}","releases_url":"https://api.github.com/repos/apache/incubator-hawq/releases{/id}","deployments_url":"https://api.github.com/repos/apache/incubator-hawq/deployments","created_at":"2015-09-05T07:00:05Z","updated_at":"2018-04-12T18:21:45Z","pushed_at":"2018-04-16T09:18:08Z","git_url":"git://github.com/apache/incubator-hawq.git","ssh_url":"git@github.com:apache/incubator-hawq.git","clone_url":"https://github.com/apache/incubator-hawq.git","svn_url":"https://github.com/apache/incubator-hawq","homepage":null,"size":177159,"stargazers_count":350,"watchers_count":350,"language":"C","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":199,"mirror_url":null,"archived":false,"open_issues_count":11,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0"},"forks":199,"open_issues":11,"watchers":350,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/incubator-hawq/pulls/1354"},"html":{"href":"https://github.com/apache/incubator-hawq/pull/1354"},"issue":{"href":"https://api.github.com/repos/apache/incubator-hawq/issues/1354"},"comments":{"href":"https://api.github.com/repos/apache/incubator-hawq/issues/1354/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/incubator-hawq/pulls/1354/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/incubator-hawq/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/incubator-hawq/pulls/1354/commits"},"statuses":{"href":"https://api.github.com/repos/apache/incubator-hawq/statuses/11b20b51026419cf91c71cabb9c17e0e467399f7"}},"author_association":"CONTRIBUTOR"}}
{"actor":{"display_login":"wengyanqing"}}