You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@quickstep.apache.org by na...@apache.org on 2016/07/11 23:34:31 UTC
[1/3] incubator-quickstep git commit: Use estimated selectivity for
setting BF size
Repository: incubator-quickstep
Updated Branches:
refs/heads/expt_bloom_filter_hash_fn [created] 30824632d
Use estimated selectivity for setting BF size
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/3e52dbd7
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/3e52dbd7
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/3e52dbd7
Branch: refs/heads/expt_bloom_filter_hash_fn
Commit: 3e52dbd7211628236c24a81661190ad5cf1a735e
Parents: f6eeb35
Author: Navneet Potti <na...@gmail.com>
Authored: Mon Jul 11 12:44:22 2016 -0500
Committer: Navneet Potti <na...@gmail.com>
Committed: Mon Jul 11 12:44:22 2016 -0500
----------------------------------------------------------------------
query_optimizer/ExecutionHeuristics.cpp | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/3e52dbd7/query_optimizer/ExecutionHeuristics.cpp
----------------------------------------------------------------------
diff --git a/query_optimizer/ExecutionHeuristics.cpp b/query_optimizer/ExecutionHeuristics.cpp
index 1d35e22..2d82d39 100644
--- a/query_optimizer/ExecutionHeuristics.cpp
+++ b/query_optimizer/ExecutionHeuristics.cpp
@@ -114,9 +114,10 @@ void ExecutionHeuristics::optimizeExecutionPlan(QueryPlan *query_plan,
void ExecutionHeuristics::setBloomFilterProperties(serialization::BloomFilter *bloom_filter_proto,
const CatalogRelation *relation) {
- const std::size_t cardinality = relation->getStatistics().getNumTuples();
bloom_filter_proto->set_bloom_filter_size(
- (FLAGS_bloom_num_bits_per_tuple * cardinality)/kNumBitsPerByte);
+ (FLAGS_bloom_num_bits_per_tuple * estimated_build_relation_cardinality_)/kNumBitsPerByte);
+ // std::cerr << "Est cardinality for " << relation->getID() << " is "
+ // << estimated_build_relation_cardinality_ << "\n";
bloom_filter_proto->set_number_of_hashes(FLAGS_bloom_num_hash_fns);
}
[3/3] incubator-quickstep git commit: Get rid of Bloom filter random
seed
Posted by na...@apache.org.
Get rid of Bloom filter random seed
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/30824632
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/30824632
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/30824632
Branch: refs/heads/expt_bloom_filter_hash_fn
Commit: 30824632df92feb8c4355d2599d152530f391ff2
Parents: 499b661
Author: Navneet Potti <na...@gmail.com>
Authored: Mon Jul 11 12:56:31 2016 -0500
Committer: Navneet Potti <na...@gmail.com>
Committed: Mon Jul 11 12:56:31 2016 -0500
----------------------------------------------------------------------
storage/BloomFilterIndexSubBlock.cpp | 4 +---
storage/BloomFilterIndexSubBlock.hpp | 6 ------
storage/HashTable.hpp | 3 +--
utility/BloomFilter.hpp | 27 +++++----------------------
utility/BloomFilter.proto | 6 ++----
utility/tests/BloomFilter_unittest.cpp | 9 +++------
6 files changed, 12 insertions(+), 43 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/30824632/storage/BloomFilterIndexSubBlock.cpp
----------------------------------------------------------------------
diff --git a/storage/BloomFilterIndexSubBlock.cpp b/storage/BloomFilterIndexSubBlock.cpp
index e806217..a40f69f 100644
--- a/storage/BloomFilterIndexSubBlock.cpp
+++ b/storage/BloomFilterIndexSubBlock.cpp
@@ -55,7 +55,6 @@ BloomFilterIndexSubBlock::BloomFilterIndexSubBlock(const TupleStorageSubBlock &t
sub_block_memory_size),
is_initialized_(false),
is_consistent_(false),
- random_seed_(kBloomFilterSeed),
bit_array_size_in_bytes_(description.GetExtension(
BloomFilterIndexSubBlockDescription::bloom_filter_size)) {
CHECK(DescriptionIsValid(relation_, description_))
@@ -74,8 +73,7 @@ BloomFilterIndexSubBlock::BloomFilterIndexSubBlock(const TupleStorageSubBlock &t
const std::uint32_t salt_count = description.GetExtension(BloomFilterIndexSubBlockDescription::number_of_hashes);
// Initialize the bloom_filter_ data structure to operate on bit_array.
- bloom_filter_.reset(new BloomFilter(random_seed_,
- salt_count,
+ bloom_filter_.reset(new BloomFilter(salt_count,
bit_array_size_in_bytes_,
bit_array_.get(),
is_bloom_filter_initialized));
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/30824632/storage/BloomFilterIndexSubBlock.hpp
----------------------------------------------------------------------
diff --git a/storage/BloomFilterIndexSubBlock.hpp b/storage/BloomFilterIndexSubBlock.hpp
index 4925673..8c81156 100644
--- a/storage/BloomFilterIndexSubBlock.hpp
+++ b/storage/BloomFilterIndexSubBlock.hpp
@@ -65,11 +65,6 @@ class BloomFilterIndexSubBlock : public IndexSubBlock {
kSelectivityNone
};
- /**
- * @brief A random seed to initialize the bloom filter hash functions.
- **/
- static const std::uint64_t kBloomFilterSeed = 0xA5A5A5A55A5A5A5AULL;
-
BloomFilterIndexSubBlock(const TupleStorageSubBlock &tuple_store,
const IndexSubBlockDescription &description,
const bool new_block,
@@ -179,7 +174,6 @@ class BloomFilterIndexSubBlock : public IndexSubBlock {
private:
bool is_initialized_;
bool is_consistent_;
- const std::uint64_t random_seed_;
const std::uint64_t bit_array_size_in_bytes_;
std::vector<attribute_id> indexed_attribute_ids_;
std::unique_ptr<unsigned char> bit_array_;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/30824632/storage/HashTable.hpp
----------------------------------------------------------------------
diff --git a/storage/HashTable.hpp b/storage/HashTable.hpp
index 2100430..1e153f2 100644
--- a/storage/HashTable.hpp
+++ b/storage/HashTable.hpp
@@ -1481,8 +1481,7 @@ HashTablePutResult HashTable<ValueT, resizable, serializable, force_key_copy, al
}
std::unique_ptr<BloomFilter> thread_local_bloom_filter;
if (has_build_side_bloom_filter_) {
- thread_local_bloom_filter.reset(new BloomFilter(build_bloom_filter_->getRandomSeed(),
- build_bloom_filter_->getNumberOfHashes(),
+ thread_local_bloom_filter.reset(new BloomFilter(build_bloom_filter_->getNumberOfHashes(),
build_bloom_filter_->getBitArraySize()));
}
if (resizable) {
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/30824632/utility/BloomFilter.hpp
----------------------------------------------------------------------
diff --git a/utility/BloomFilter.hpp b/utility/BloomFilter.hpp
index 4125292..332cb0f 100644
--- a/utility/BloomFilter.hpp
+++ b/utility/BloomFilter.hpp
@@ -57,15 +57,12 @@ class BloomFilter {
* @note When no bit_array is being passed to the constructor,
* then the bit_array is owned and managed by this class.
*
- * @param random_seed A random_seed that generates unique hash functions.
* @param hash_fn_count The number of hash functions used by this bloom filter.
* @param bit_array_size_in_bytes Size of the bit array.
**/
- BloomFilter(const std::uint64_t random_seed,
- const std::size_t hash_fn_count,
+ BloomFilter(const std::size_t hash_fn_count,
const std::uint64_t bit_array_size_in_bytes)
- : random_seed_(random_seed),
- hash_fn_count_(hash_fn_count),
+ : hash_fn_count_(hash_fn_count),
array_size_in_bytes_(bit_array_size_in_bytes),
array_size_(array_size_in_bytes_ * kNumBitsPerByte),
bit_array_(new std::uint8_t[array_size_in_bytes_]),
@@ -78,20 +75,17 @@ class BloomFilter {
* @note When a bit_array is passed as an argument to the constructor,
* then the ownership of the bit array lies with the caller.
*
- * @param random_seed A random_seed that generates unique hash functions.
* @param hash_fn_count The number of hash functions used by this bloom filter.
* @param bit_array_size_in_bytes Size of the bit array.
* @param bit_array A pointer to the memory region that is used to store bit array.
* @param is_initialized A boolean that indicates whether to zero-out the region
* before use or not.
**/
- BloomFilter(const std::uint64_t random_seed,
- const std::size_t hash_fn_count,
+ BloomFilter(const std::size_t hash_fn_count,
const std::uint64_t bit_array_size_in_bytes,
std::uint8_t *bit_array,
const bool is_initialized)
- : random_seed_(random_seed),
- hash_fn_count_(hash_fn_count),
+ : hash_fn_count_(hash_fn_count),
array_size_in_bytes_(bit_array_size_in_bytes),
array_size_(bit_array_size_in_bytes * kNumBitsPerByte),
bit_array_(bit_array), // Owned by the calling method.
@@ -110,8 +104,7 @@ class BloomFilter {
* bloom filter configuration.
**/
explicit BloomFilter(const serialization::BloomFilter &bloom_filter_proto)
- : random_seed_(bloom_filter_proto.bloom_filter_seed()),
- hash_fn_count_(bloom_filter_proto.number_of_hashes()),
+ : hash_fn_count_(bloom_filter_proto.number_of_hashes()),
array_size_in_bytes_(bloom_filter_proto.bloom_filter_size()),
array_size_(array_size_in_bytes_ * kNumBitsPerByte),
bit_array_(new std::uint8_t[array_size_in_bytes_]),
@@ -144,15 +137,6 @@ class BloomFilter {
}
/**
- * @brief Get the random seed that was used to initialize this bloom filter.
- *
- * @return Returns the random seed.
- **/
- inline std::uint64_t getRandomSeed() const {
- return random_seed_;
- }
-
- /**
* @brief Get the number of hash functions used in this bloom filter.
*
* @return Returns the number of hash functions.
@@ -320,7 +304,6 @@ class BloomFilter {
}
private:
- const std::uint64_t random_seed_;
std::vector<std::uint32_t> hash_fn_;
const std::uint32_t hash_fn_count_;
std::uint64_t array_size_in_bytes_;
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/30824632/utility/BloomFilter.proto
----------------------------------------------------------------------
diff --git a/utility/BloomFilter.proto b/utility/BloomFilter.proto
index 8dd9163..b5d14a9 100644
--- a/utility/BloomFilter.proto
+++ b/utility/BloomFilter.proto
@@ -21,10 +21,8 @@ message BloomFilter {
// The default values were determined from empirical experiments.
// These values control the amount of false positivity that
// is expected from Bloom Filter.
- // - Default seed for initializing family of hashes = 0xA5A5A5A55A5A5A5A.
// - Default bloom filter size = 10 KB.
// - Default number of hash functions used in bloom filter = 5.
- optional fixed64 bloom_filter_seed = 1 [default = 0xA5A5A5A55A5A5A5A];
- optional uint32 bloom_filter_size = 2 [default = 10000];
- optional uint32 number_of_hashes = 3 [default = 5];
+ optional uint32 bloom_filter_size = 1 [default = 10000];
+ optional uint32 number_of_hashes = 2 [default = 5];
}
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/30824632/utility/tests/BloomFilter_unittest.cpp
----------------------------------------------------------------------
diff --git a/utility/tests/BloomFilter_unittest.cpp b/utility/tests/BloomFilter_unittest.cpp
index 4d8beae..03ac9f1 100644
--- a/utility/tests/BloomFilter_unittest.cpp
+++ b/utility/tests/BloomFilter_unittest.cpp
@@ -28,14 +28,13 @@ namespace quickstep {
class BloomFilterTest : public ::testing::Test {
public:
- static const std::uint64_t kBloomFilterSeed = 0xA5A5A5A55A5A5A5AULL;
static const std::uint32_t kNumberOfHashFunctions = 20;
static const std::uint32_t kBloomFilterSize = 100000; // in bytes.
};
TEST_F(BloomFilterTest, BloomFilterInsertTest) {
// This test inserts an element into a known bloom filter size
- // with given number of hash functions and initial seed,
+ // with given number of hash functions,
// and tests whether the expected bits are set or not.
std::unique_ptr<std::uint8_t> bit_array;
std::unique_ptr<BloomFilter> bloom_filter;
@@ -44,8 +43,7 @@ TEST_F(BloomFilterTest, BloomFilterInsertTest) {
const std::uint32_t bloom_filter_size = 1;
bit_array.reset(new std::uint8_t[bloom_filter_size]);
- bloom_filter.reset(new BloomFilter(kBloomFilterSeed,
- num_hashes,
+ bloom_filter.reset(new BloomFilter(num_hashes,
bloom_filter_size,
bit_array.get(),
false));
@@ -61,8 +59,7 @@ TEST_F(BloomFilterTest, BloomFilterContainsTest) {
std::unique_ptr<BloomFilter> bloom_filter;
bit_array.reset(new std::uint8_t[kBloomFilterSize]);
- bloom_filter.reset(new BloomFilter(kBloomFilterSeed,
- kNumberOfHashFunctions,
+ bloom_filter.reset(new BloomFilter(kNumberOfHashFunctions,
kBloomFilterSize,
bit_array.get(),
false));
[2/3] incubator-quickstep git commit: Use multiplicative hash instead
of hash_ap
Posted by na...@apache.org.
Use multiplicative hash instead of hash_ap
Project: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/commit/499b6613
Tree: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/tree/499b6613
Diff: http://git-wip-us.apache.org/repos/asf/incubator-quickstep/diff/499b6613
Branch: refs/heads/expt_bloom_filter_hash_fn
Commit: 499b6613db75fdac1e96a622bc365549722eee47
Parents: 3e52dbd
Author: Navneet Potti <na...@gmail.com>
Authored: Mon Jul 11 12:45:26 2016 -0500
Committer: Navneet Potti <na...@gmail.com>
Committed: Mon Jul 11 12:45:26 2016 -0500
----------------------------------------------------------------------
utility/BloomFilter.hpp | 104 ++++++++-----------------------------------
1 file changed, 18 insertions(+), 86 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-quickstep/blob/499b6613/utility/BloomFilter.hpp
----------------------------------------------------------------------
diff --git a/utility/BloomFilter.hpp b/utility/BloomFilter.hpp
index b93df84..4125292 100644
--- a/utility/BloomFilter.hpp
+++ b/utility/BloomFilter.hpp
@@ -71,7 +71,6 @@ class BloomFilter {
bit_array_(new std::uint8_t[array_size_in_bytes_]),
is_bit_array_owner_(true) {
reset();
- generate_unique_hash_fn();
}
/**
@@ -100,7 +99,6 @@ class BloomFilter {
if (!is_initialized) {
reset();
}
- generate_unique_hash_fn();
}
/**
@@ -119,7 +117,6 @@ class BloomFilter {
bit_array_(new std::uint8_t[array_size_in_bytes_]),
is_bit_array_owner_(true) {
reset();
- generate_unique_hash_fn();
}
/**
@@ -198,7 +195,7 @@ class BloomFilter {
// Determine all the bit positions that are required to be set.
for (std::size_t i = 0; i < hash_fn_count_; ++i) {
- compute_indices(hash_ap(key_begin, length, hash_fn_[i]), &bit_index, &bit);
+ compute_indices(hash_multiplicative(key_begin, length, hash_fn_[i]), &bit_index, &bit);
modified_bit_positions.push_back(std::make_pair(bit_index, bit));
}
@@ -243,7 +240,7 @@ class BloomFilter {
std::size_t bit = 0;
for (std::size_t i = 0; i < hash_fn_count_; ++i) {
- compute_indices(hash_ap(key_begin, length, hash_fn_[i]), &bit_index, &bit);
+ compute_indices(hash_multiplicative(key_begin, length, hash_fn_[i]), &bit_index, &bit);
(bit_array_.get())[bit_index / kNumBitsPerByte] |= (1 << bit);
}
@@ -265,7 +262,7 @@ class BloomFilter {
std::size_t bit_index = 0;
std::size_t bit = 0;
for (std::size_t i = 0; i < hash_fn_count_; ++i) {
- compute_indices(hash_ap(key_begin, length, hash_fn_[i]), &bit_index, &bit);
+ compute_indices(hash_multiplicative(key_begin, length, hash_fn_[i]), &bit_index, &bit);
if (((bit_array_.get())[bit_index / kNumBitsPerByte] & (1 << bit)) != (1 << bit)) {
return false;
}
@@ -301,88 +298,23 @@ class BloomFilter {
*bit = *bit_index % kNumBitsPerByte;
}
- void generate_unique_hash_fn() {
- hash_fn_.reserve(hash_fn_count_);
- const std::uint32_t predef_hash_fn_count = 128;
- static const std::uint32_t predef_hash_fn[predef_hash_fn_count] = {
- 0xAAAAAAAA, 0x55555555, 0x33333333, 0xCCCCCCCC,
- 0x66666666, 0x99999999, 0xB5B5B5B5, 0x4B4B4B4B,
- 0xAA55AA55, 0x55335533, 0x33CC33CC, 0xCC66CC66,
- 0x66996699, 0x99B599B5, 0xB54BB54B, 0x4BAA4BAA,
- 0xAA33AA33, 0x55CC55CC, 0x33663366, 0xCC99CC99,
- 0x66B566B5, 0x994B994B, 0xB5AAB5AA, 0xAAAAAA33,
- 0x555555CC, 0x33333366, 0xCCCCCC99, 0x666666B5,
- 0x9999994B, 0xB5B5B5AA, 0xFFFFFFFF, 0xFFFF0000,
- 0xB823D5EB, 0xC1191CDF, 0xF623AEB3, 0xDB58499F,
- 0xC8D42E70, 0xB173F616, 0xA91A5967, 0xDA427D63,
- 0xB1E8A2EA, 0xF6C0D155, 0x4909FEA3, 0xA68CC6A7,
- 0xC395E782, 0xA26057EB, 0x0CD5DA28, 0x467C5492,
- 0xF15E6982, 0x61C6FAD3, 0x9615E352, 0x6E9E355A,
- 0x689B563E, 0x0C9831A8, 0x6753C18B, 0xA622689B,
- 0x8CA63C47, 0x42CC2884, 0x8E89919B, 0x6EDBD7D3,
- 0x15B6796C, 0x1D6FDFE4, 0x63FF9092, 0xE7401432,
- 0xEFFE9412, 0xAEAEDF79, 0x9F245A31, 0x83C136FC,
- 0xC3DA4A8C, 0xA5112C8C, 0x5271F491, 0x9A948DAB,
- 0xCEE59A8D, 0xB5F525AB, 0x59D13217, 0x24E7C331,
- 0x697C2103, 0x84B0A460, 0x86156DA9, 0xAEF2AC68,
- 0x23243DA5, 0x3F649643, 0x5FA495A8, 0x67710DF8,
- 0x9A6C499E, 0xDCFB0227, 0x46A43433, 0x1832B07A,
- 0xC46AFF3C, 0xB9C8FFF0, 0xC9500467, 0x34431BDF,
- 0xB652432B, 0xE367F12B, 0x427F4C1B, 0x224C006E,
- 0x2E7E5A89, 0x96F99AA5, 0x0BEB452A, 0x2FD87C39,
- 0x74B2E1FB, 0x222EFD24, 0xF357F60C, 0x440FCB1E,
- 0x8BBE030F, 0x6704DC29, 0x1144D12F, 0x948B1355,
- 0x6D8FD7E9, 0x1C11A014, 0xADD1592F, 0xFB3C712E,
- 0xFC77642F, 0xF9C4CE8C, 0x31312FB9, 0x08B0DD79,
- 0x318FA6E7, 0xC040D23D, 0xC0589AA7, 0x0CA5C075,
- 0xF874B172, 0x0CF914D5, 0x784D3280, 0x4E8CFEBC,
- 0xC569F575, 0xCDB2A091, 0x2CC016B4, 0x5C5F4421
- };
- if (hash_fn_count_ <= predef_hash_fn_count) {
- std::copy(predef_hash_fn, predef_hash_fn + hash_fn_count_, hash_fn_.begin());
- for (std::uint32_t i = 0; i < hash_fn_.size(); ++i) {
- hash_fn_[i] = hash_fn_[i] * hash_fn_[(i + 3) % hash_fn_count_] + static_cast<std::uint32_t>(random_seed_);
+ inline std::uint32_t hash_multiplicative(
+ const std::uint8_t *begin,
+ std::size_t remaining_length,
+ const std::size_t multiplier) const {
+ std::uint32_t hash = 0;
+ std::size_t bytes_hashed = 0;
+ if (remaining_length >= 4) {
+ while (bytes_hashed < remaining_length) {
+ auto val = *reinterpret_cast<const std::uint32_t *>(begin + bytes_hashed);
+ hash = multiplier * hash + val;
+ bytes_hashed += 4;
}
- } else {
- LOG(FATAL) << "Requested number of hash functions is too large.";
- }
- }
-
- inline std::uint32_t hash_ap(const std::uint8_t *begin, std::size_t remaining_length, std::uint32_t hash) const {
- const std::uint8_t *itr = begin;
- std::uint32_t loop = 0;
- while (remaining_length >= 8) {
- const std::uint32_t &i1 = *(reinterpret_cast<const std::uint32_t*>(itr)); itr += sizeof(std::uint32_t);
- const std::uint32_t &i2 = *(reinterpret_cast<const std::uint32_t*>(itr)); itr += sizeof(std::uint32_t);
- hash ^= (hash << 7) ^ i1 * (hash >> 3) ^ (~((hash << 11) + (i2 ^ (hash >> 5))));
- remaining_length -= 8;
}
- if (remaining_length) {
- if (remaining_length >= 4) {
- const std::uint32_t &i = *(reinterpret_cast<const std::uint32_t*>(itr));
- if (loop & 0x01) {
- hash ^= (hash << 7) ^ i * (hash >> 3);
- } else {
- hash ^= (~((hash << 11) + (i ^ (hash >> 5))));
- }
- ++loop;
- remaining_length -= 4;
- itr += sizeof(std::uint32_t);
- }
- if (remaining_length >= 2) {
- const std::uint16_t &i = *(reinterpret_cast<const std::uint16_t*>(itr));
- if (loop & 0x01) {
- hash ^= (hash << 7) ^ i * (hash >> 3);
- } else {
- hash ^= (~((hash << 11) + (i ^ (hash >> 5))));
- }
- ++loop;
- remaining_length -= 2;
- itr += sizeof(std::uint16_t);
- }
- if (remaining_length) {
- hash += ((*itr) ^ (hash * 0xA5A5A5A5)) + loop;
- }
+ while (bytes_hashed < remaining_length) {
+ std::uint8_t val = *(begin + bytes_hashed);
+ hash = multiplier * hash + val;
+ bytes_hashed++;
}
return hash;
}