Google Git
Sign in
apache / impala / 8e33b84b049e9d31188792ae18ad43c0e887966b / . / be / src / exec / hash-table.cc
blob: 6ea5fdfffbf8ef785f6f2ffe5f19482a3c4dbfc7 [file] [log] [blame]
// 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.
#include "exec/hash-table.inline.h"
#include <functional>
#include <numeric>
#include <gutil/strings/substitute.h>
#include "codegen/codegen-anyval.h"
#include "codegen/llvm-codegen.h"
#include "exprs/slot-ref.h"
#include "exprs/scalar-expr.h"
#include "exprs/scalar-expr-evaluator.h"
#include "runtime/bufferpool/reservation-tracker.h"
#include "runtime/mem-tracker.h"
#include "runtime/raw-value.inline.h"
#include "runtime/runtime-state.h"
#include "runtime/string-value.inline.h"
#include "util/debug-util.h"
#include "util/impalad-metrics.h"
#include "common/names.h"
using namespace impala;
using strings::Substitute;
DEFINE_bool(enable_quadratic_probing, true, "Enable quadratic probing hash table");
const char* HashTableCtx::LLVM_CLASS_NAME = "class.impala::HashTableCtx";
// Random primes to multiply the seed with.
static uint32_t SEED_PRIMES[] = {
1, // First seed must be 1, level 0 is used by other operators in the fragment.
1431655781,
1183186591,
622729787,
472882027,
338294347,
275604541,
41161739,
29999999,
27475109,
611603,
16313357,
11380003,
21261403,
33393119,
101,
71043403
};
// Put a non-zero constant in the result location for NULL.
// We don't want(NULL, 1) to hash to the same as (0, 1).
// This needs to be as big as the biggest primitive type since the bytes
// get copied directly.
// TODO find a better approach, since primitives like CHAR(N) can be up
// to 255 bytes
static int64_t NULL_VALUE[] = {
HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED,
HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED,
HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED,
HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED,
HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED,
HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED,
HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED,
HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED, HashUtil::FNV_SEED
};
static_assert(sizeof(NULL_VALUE) >= ColumnType::MAX_CHAR_LENGTH,
"NULL_VALUE must be at least as large as the largest possible slot");
HashTableCtx::HashTableCtx(const std::vector<ScalarExpr*>& build_exprs,
const std::vector<ScalarExpr*>& probe_exprs, bool stores_nulls,
const std::vector<bool>& finds_nulls, int32_t initial_seed,
int max_levels, MemPool* expr_perm_pool, MemPool* build_expr_results_pool,
MemPool* probe_expr_results_pool)
: build_exprs_(build_exprs),
probe_exprs_(probe_exprs),
stores_nulls_(stores_nulls),
finds_nulls_(finds_nulls),
finds_some_nulls_(std::accumulate(
finds_nulls_.begin(), finds_nulls_.end(), false, std::logical_or<bool>())),
level_(0),
scratch_row_(NULL),
expr_perm_pool_(expr_perm_pool),
build_expr_results_pool_(build_expr_results_pool),
probe_expr_results_pool_(probe_expr_results_pool) {
DCHECK(!finds_some_nulls_ || stores_nulls_);
// Compute the layout and buffer size to store the evaluated expr results
DCHECK_EQ(build_exprs_.size(), probe_exprs_.size());
DCHECK_EQ(build_exprs_.size(), finds_nulls_.size());
DCHECK(!build_exprs_.empty());
// Populate the seeds to use for all the levels. TODO: revisit how we generate these.
DCHECK_GE(max_levels, 0);
DCHECK_LT(max_levels, sizeof(SEED_PRIMES) / sizeof(SEED_PRIMES[0]));
DCHECK_NE(initial_seed, 0);
seeds_.resize(max_levels + 1);
seeds_[0] = initial_seed;
for (int i = 1; i <= max_levels; ++i) {
seeds_[i] = seeds_[i - 1] * SEED_PRIMES[i];
}
}
Status HashTableCtx::Init(ObjectPool* pool, RuntimeState* state, int num_build_tuples) {
int scratch_row_size = sizeof(Tuple*) * num_build_tuples;
scratch_row_ = reinterpret_cast<TupleRow*>(malloc(scratch_row_size));
if (UNLIKELY(scratch_row_ == NULL)) {
return Status(Substitute("Failed to allocate $0 bytes for scratch row of "
"HashTableCtx.", scratch_row_size));
}
RETURN_IF_ERROR(ScalarExprEvaluator::Create(build_exprs_, state, pool, expr_perm_pool_,
build_expr_results_pool_, &build_expr_evals_));
DCHECK_EQ(build_exprs_.size(), build_expr_evals_.size());
RETURN_IF_ERROR(ScalarExprEvaluator::Create(probe_exprs_, state, pool, expr_perm_pool_,
probe_expr_results_pool_, &probe_expr_evals_));
DCHECK_EQ(probe_exprs_.size(), probe_expr_evals_.size());
return expr_values_cache_.Init(state, expr_perm_pool_->mem_tracker(), build_exprs_);
}
Status HashTableCtx::Create(ObjectPool* pool, RuntimeState* state,
const std::vector<ScalarExpr*>& build_exprs,
const std::vector<ScalarExpr*>& probe_exprs, bool stores_nulls,
const std::vector<bool>& finds_nulls, int32_t initial_seed, int max_levels,
int num_build_tuples, MemPool* expr_perm_pool, MemPool* build_expr_results_pool,
MemPool* probe_expr_results_pool, scoped_ptr<HashTableCtx>* ht_ctx) {
ht_ctx->reset(new HashTableCtx(build_exprs, probe_exprs, stores_nulls,
finds_nulls, initial_seed, max_levels, expr_perm_pool,
build_expr_results_pool, probe_expr_results_pool));
return (*ht_ctx)->Init(pool, state, num_build_tuples);
}
Status HashTableCtx::Open(RuntimeState* state) {
RETURN_IF_ERROR(ScalarExprEvaluator::Open(build_expr_evals_, state));
RETURN_IF_ERROR(ScalarExprEvaluator::Open(probe_expr_evals_, state));
return Status::OK();
}
void HashTableCtx::Close(RuntimeState* state) {
free(scratch_row_);
scratch_row_ = NULL;
expr_values_cache_.Close(expr_perm_pool_->mem_tracker());
ScalarExprEvaluator::Close(build_expr_evals_, state);
ScalarExprEvaluator::Close(probe_expr_evals_, state);
}
uint32_t HashTableCtx::Hash(const void* input, int len, uint32_t hash) const {
/// Use CRC hash at first level for better performance. Switch to murmur hash at
/// subsequent levels since CRC doesn't randomize well with different seed inputs.
if (level_ == 0) return HashUtil::Hash(input, len, hash);
return HashUtil::MurmurHash2_64(input, len, hash);
}
uint32_t HashTableCtx::HashRow(
const uint8_t* expr_values, const uint8_t* expr_values_null) const noexcept {
DCHECK_LT(level_, seeds_.size());
if (expr_values_cache_.var_result_offset() == -1) {
/// This handles NULLs implicitly since a constant seed value was put
/// into results buffer for nulls.
return Hash(
expr_values, expr_values_cache_.expr_values_bytes_per_row(), seeds_[level_]);
} else {
return HashTableCtx::HashVariableLenRow(expr_values, expr_values_null);
}
}
bool HashTableCtx::EvalRow(const TupleRow* row,
const vector<ScalarExprEvaluator*>& evals,
uint8_t* expr_values, uint8_t* expr_values_null) noexcept {
bool has_null = false;
for (int i = 0; i < evals.size(); ++i) {
void* loc = expr_values_cache_.ExprValuePtr(expr_values, i);
const void* val = evals[i]->GetValue(row);
if (val == NULL) {
// If the table doesn't store nulls, no reason to keep evaluating
if (!stores_nulls_) return true;
expr_values_null[i] = true;
val = reinterpret_cast<void*>(&NULL_VALUE);
has_null = true;
} else {
expr_values_null[i] = false;
}
const ColumnType& expr_type = build_exprs_[i]->type();
DCHECK_LE(expr_type.GetSlotSize(), sizeof(NULL_VALUE));
if (RawValue::IsNaN(val, expr_type)) {
val = RawValue::CanonicalNaNValue(expr_type);
}
RawValue::Write(val, loc, expr_type, NULL);
}
return has_null;
}
uint32_t HashTableCtx::HashVariableLenRow(const uint8_t* expr_values,
const uint8_t* expr_values_null) const {
uint32_t hash = seeds_[level_];
int var_result_offset = expr_values_cache_.var_result_offset();
// Hash the non-var length portions (if there are any)
if (var_result_offset != 0) {
hash = Hash(expr_values, var_result_offset, hash);
}
for (int i = 0; i < build_exprs_.size(); ++i) {
// non-string and null slots are already part of 'expr_values'.
if (build_exprs_[i]->type().type != TYPE_STRING &&
build_exprs_[i]->type().type != TYPE_VARCHAR) {
continue;
}
const void* loc = expr_values_cache_.ExprValuePtr(expr_values, i);
if (expr_values_null[i]) {
// Hash the null random seed values at 'loc'
hash = Hash(loc, sizeof(StringValue), hash);
} else {
// Hash the string
// TODO: when using CRC hash on empty string, this only swaps bytes.
const StringValue* str = reinterpret_cast<const StringValue*>(loc);
hash = Hash(str->ptr, str->len, hash);
}
}
return hash;
}
template <bool INCLUSIVE_EQUALITY>
bool HashTableCtx::Equals(const TupleRow* build_row, const uint8_t* expr_values,
const uint8_t* expr_values_null) const noexcept {
for (int i = 0; i < build_expr_evals_.size(); ++i) {
void* val = build_expr_evals_[i]->GetValue(build_row);
if (val == NULL) {
if (!(INCLUSIVE_EQUALITY || finds_nulls_[i])) return false;
if (!expr_values_null[i]) return false;
continue;
} else {
if (expr_values_null[i]) return false;
}
const void* loc = expr_values_cache_.ExprValuePtr(expr_values, i);
DCHECK(build_exprs_[i] == &build_expr_evals_[i]->root());
const ColumnType& expr_type = build_exprs_[i]->type();
if (!RawValue::Eq(loc, val, expr_type)) {
if (INCLUSIVE_EQUALITY) {
bool val_is_nan = RawValue::IsNaN(val, expr_type);
bool local_is_nan = RawValue::IsNaN(loc, expr_type);
if (val_is_nan && local_is_nan) continue;
}
return false;
}
}
return true;
}
template bool HashTableCtx::Equals<true>(const TupleRow* build_row,
const uint8_t* expr_values, const uint8_t* expr_values_null) const;
template bool HashTableCtx::Equals<false>(const TupleRow* build_row,
const uint8_t* expr_values, const uint8_t* expr_values_null) const;
HashTableCtx::ExprValuesCache::ExprValuesCache()
: capacity_(0),
cur_expr_values_(NULL),
cur_expr_values_null_(NULL),
cur_expr_values_hash_(NULL),
cur_expr_values_hash_end_(NULL),
expr_values_array_(NULL),
expr_values_null_array_(NULL),
expr_values_hash_array_(NULL),
null_bitmap_(0) {}
Status HashTableCtx::ExprValuesCache::Init(RuntimeState* state,
MemTracker* tracker, const std::vector<ScalarExpr*>& build_exprs) {
// Initialize the number of expressions.
num_exprs_ = build_exprs.size();
// Compute the layout of evaluated values of a row.
expr_values_bytes_per_row_ = ScalarExpr::ComputeResultsLayout(build_exprs,
&expr_values_offsets_, &var_result_offset_);
if (expr_values_bytes_per_row_ == 0) {
DCHECK_EQ(num_exprs_, 0);
return Status::OK();
}
DCHECK_GT(expr_values_bytes_per_row_, 0);
// Compute the maximum number of cached rows which can fit in the memory budget.
// TODO: Find the optimal prefetch batch size. This may be something
// processor dependent so we may need calibration at Impala startup time.
capacity_ = std::max(1, std::min(state->batch_size(),
MAX_EXPR_VALUES_ARRAY_SIZE / expr_values_bytes_per_row_));
int mem_usage = MemUsage(capacity_, expr_values_bytes_per_row_, num_exprs_);
if (UNLIKELY(!tracker->TryConsume(mem_usage))) {
capacity_ = 0;
string details = Substitute("HashTableCtx::ExprValuesCache failed to allocate $0 bytes.",
mem_usage);
return tracker->MemLimitExceeded(state, details, mem_usage);
}
int expr_values_size = expr_values_bytes_per_row_ * capacity_;
expr_values_array_.reset(new uint8_t[expr_values_size]);
cur_expr_values_ = expr_values_array_.get();
memset(cur_expr_values_, 0, expr_values_size);
int expr_values_null_size = num_exprs_ * capacity_;
expr_values_null_array_.reset(new uint8_t[expr_values_null_size]);
cur_expr_values_null_ = expr_values_null_array_.get();
memset(cur_expr_values_null_, 0, expr_values_null_size);
expr_values_hash_array_.reset(new uint32_t[capacity_]);
cur_expr_values_hash_ = expr_values_hash_array_.get();
cur_expr_values_hash_end_ = cur_expr_values_hash_;
memset(cur_expr_values_hash_, 0, sizeof(uint32) * capacity_);
null_bitmap_.Reset(capacity_);
return Status::OK();
}
void HashTableCtx::ExprValuesCache::Close(MemTracker* tracker) {
if (capacity_ == 0) return;
cur_expr_values_ = NULL;
cur_expr_values_null_ = NULL;
cur_expr_values_hash_ = NULL;
cur_expr_values_hash_end_ = NULL;
expr_values_array_.reset();
expr_values_null_array_.reset();
expr_values_hash_array_.reset();
null_bitmap_.Reset(0);
int mem_usage = MemUsage(capacity_, expr_values_bytes_per_row_, num_exprs_);
tracker->Release(mem_usage);
}
int HashTableCtx::ExprValuesCache::MemUsage(int capacity,
int expr_values_bytes_per_row, int num_exprs) {
return expr_values_bytes_per_row * capacity + // expr_values_array_
num_exprs * capacity + // expr_values_null_array_
sizeof(uint32) * capacity + // expr_values_hash_array_
Bitmap::MemUsage(capacity); // null_bitmap_
}
uint8_t* HashTableCtx::ExprValuesCache::ExprValuePtr(
uint8_t* expr_values, int expr_idx) const {
return expr_values + expr_values_offsets_[expr_idx];
}
const uint8_t* HashTableCtx::ExprValuesCache::ExprValuePtr(
const uint8_t* expr_values, int expr_idx) const {
return expr_values + expr_values_offsets_[expr_idx];
}
void HashTableCtx::ExprValuesCache::ResetIterators() {
cur_expr_values_ = expr_values_array_.get();
cur_expr_values_null_ = expr_values_null_array_.get();
cur_expr_values_hash_ = expr_values_hash_array_.get();
}
void HashTableCtx::ExprValuesCache::Reset() noexcept {
ResetIterators();
// Set the end pointer after resetting the other pointers so they point to
// the same location.
cur_expr_values_hash_end_ = cur_expr_values_hash_;
null_bitmap_.SetAllBits(false);
}
void HashTableCtx::ExprValuesCache::ResetForRead() {
// Record the end of hash values iterator to be used in AtEnd().
// Do it before resetting the pointers.
cur_expr_values_hash_end_ = cur_expr_values_hash_;
ResetIterators();
}
constexpr double HashTable::MAX_FILL_FACTOR;
constexpr int64_t HashTable::DATA_PAGE_SIZE;
HashTable* HashTable::Create(Suballocator* allocator, bool stores_duplicates,
int num_build_tuples, BufferedTupleStream* tuple_stream, int64_t max_num_buckets,
int64_t initial_num_buckets) {
return new HashTable(FLAGS_enable_quadratic_probing, allocator, stores_duplicates,
num_build_tuples, tuple_stream, max_num_buckets, initial_num_buckets);
}
HashTable::HashTable(bool quadratic_probing, Suballocator* allocator,
bool stores_duplicates, int num_build_tuples, BufferedTupleStream* stream,
int64_t max_num_buckets, int64_t num_buckets)
: allocator_(allocator),
tuple_stream_(stream),
stores_tuples_(num_build_tuples == 1),
stores_duplicates_(stores_duplicates),
quadratic_probing_(quadratic_probing),
max_num_buckets_(max_num_buckets),
num_buckets_(num_buckets),
num_build_tuples_(num_build_tuples) {
DCHECK_EQ((num_buckets & (num_buckets - 1)), 0) << "num_buckets must be a power of 2";
DCHECK_GT(num_buckets, 0) << "num_buckets must be larger than 0";
DCHECK(stores_tuples_ || stream != NULL);
}
Status HashTable::Init(bool* got_memory) {
int64_t buckets_byte_size = num_buckets_ * sizeof(Bucket);
RETURN_IF_ERROR(allocator_->Allocate(buckets_byte_size, &bucket_allocation_));
if (bucket_allocation_ == nullptr) {
num_buckets_ = 0;
*got_memory = false;
return Status::OK();
}
buckets_ = reinterpret_cast<Bucket*>(bucket_allocation_->data());
memset(buckets_, 0, buckets_byte_size);
*got_memory = true;
return Status::OK();
}
unique_ptr<HashTableStatsProfile> HashTable::AddHashTableCounters(
RuntimeProfile* parent_profile) {
unique_ptr<HashTableStatsProfile> stats_profile(new HashTableStatsProfile());
RuntimeProfile *hashtable_profile = stats_profile->hashtable_profile =
parent_profile->CreateChild("Hash Table", true, true);
stats_profile->num_hash_probes_ =
ADD_COUNTER(hashtable_profile, "Probes", TUnit::UNIT);
stats_profile->num_hash_travels_ =
ADD_COUNTER(hashtable_profile, "Travel", TUnit::UNIT);
stats_profile->num_hash_collisions_ =
ADD_COUNTER(hashtable_profile, "HashCollisions", TUnit::UNIT);
stats_profile->num_hash_buckets_ =
ADD_COUNTER(hashtable_profile, "HashBuckets", TUnit::UNIT);
stats_profile->num_hash_resizes_ =
ADD_COUNTER(hashtable_profile, "Resizes", TUnit::UNIT);
return stats_profile;
}
void HashTable::Close() {
// Print statistics only for the large or heavily used hash tables.
// TODO: Tweak these numbers/conditions, or print them always?
const int64_t LARGE_HT = 128 * 1024;
const int64_t HEAVILY_USED = 1024 * 1024;
// TODO: These statistics should go to the runtime profile as well.
if ((num_buckets_ > LARGE_HT) || (num_probes_ > HEAVILY_USED)) VLOG(2) << PrintStats();
for (auto& data_page : data_pages_) allocator_->Free(move(data_page));
data_pages_.clear();
if (bucket_allocation_ != nullptr) allocator_->Free(move(bucket_allocation_));
}
void HashTable::StatsCountersAdd(HashTableStatsProfile* profile) {
COUNTER_ADD(profile->num_hash_collisions_, num_hash_collisions_);
COUNTER_ADD(profile->num_hash_probes_, num_probes_);
COUNTER_ADD(profile->num_hash_travels_, travel_length_);
COUNTER_ADD(profile->num_hash_resizes_, this->num_resizes_);
}
Status HashTable::CheckAndResize(
uint64_t buckets_to_fill, const HashTableCtx* ht_ctx, bool* got_memory) {
uint64_t shift = 0;
while (num_filled_buckets_ + buckets_to_fill >
(num_buckets_ << shift) * MAX_FILL_FACTOR) {
++shift;
}
if (shift > 0) return ResizeBuckets(num_buckets_ << shift, ht_ctx, got_memory);
*got_memory = true;
return Status::OK();
}
Status HashTable::ResizeBuckets(
int64_t num_buckets, const HashTableCtx* ht_ctx, bool* got_memory) {
DCHECK_EQ((num_buckets & (num_buckets - 1)), 0)
<< "num_buckets=" << num_buckets << " must be a power of 2";
DCHECK_GT(num_buckets, num_filled_buckets_)
<< "Cannot shrink the hash table to smaller number of buckets than the number of "
<< "filled buckets.";
VLOG(2) << "Resizing hash table from " << num_buckets_ << " to " << num_buckets
<< " buckets.";
if (max_num_buckets_ != -1 && num_buckets > max_num_buckets_) {
*got_memory = false;
return Status::OK();
}
++num_resizes_;
// All memory that can grow proportional to the input should come from the block mgrs
// mem tracker.
// Note that while we copying over the contents of the old hash table, we need to have
// allocated both the old and the new hash table. Once we finish, we return the memory
// of the old hash table.
// int64_t old_size = num_buckets_ * sizeof(Bucket);
int64_t new_size = num_buckets * sizeof(Bucket);
unique_ptr<Suballocation> new_allocation;
RETURN_IF_ERROR(allocator_->Allocate(new_size, &new_allocation));
if (new_allocation == NULL) {
*got_memory = false;
return Status::OK();
}
Bucket* new_buckets = reinterpret_cast<Bucket*>(new_allocation->data());
memset(new_buckets, 0, new_size);
// Walk the old table and copy all the filled buckets to the new (resized) table.
// We do not have to do anything with the duplicate nodes. This operation is expected
// to succeed.
for (HashTable::Iterator iter = Begin(ht_ctx); !iter.AtEnd();
NextFilledBucket(&iter.bucket_idx_, &iter.node_)) {
Bucket* bucket_to_copy = &buckets_[iter.bucket_idx_];
bool found = false;
int64_t bucket_idx =
Probe<true>(new_buckets, num_buckets, NULL, bucket_to_copy->hash, &found);
DCHECK(!found);
DCHECK_NE(bucket_idx, Iterator::BUCKET_NOT_FOUND) << " Probe failed even though "
" there are free buckets. " << num_buckets << " " << num_filled_buckets_;
Bucket* dst_bucket = &new_buckets[bucket_idx];
*dst_bucket = *bucket_to_copy;
}
num_buckets_ = num_buckets;
allocator_->Free(move(bucket_allocation_));
bucket_allocation_ = move(new_allocation);
buckets_ = reinterpret_cast<Bucket*>(bucket_allocation_->data());
*got_memory = true;
return Status::OK();
}
bool HashTable::GrowNodeArray(Status* status) {
unique_ptr<Suballocation> allocation;
*status = allocator_->Allocate(DATA_PAGE_SIZE, &allocation);
if (!status->ok() || allocation == nullptr) return false;
next_node_ = reinterpret_cast<DuplicateNode*>(allocation->data());
data_pages_.push_back(move(allocation));
node_remaining_current_page_ = DATA_PAGE_SIZE / sizeof(DuplicateNode);
total_data_page_size_ += DATA_PAGE_SIZE;
return true;
}
void HashTable::DebugStringTuple(stringstream& ss, HtData& htdata,
const RowDescriptor* desc) {
if (stores_tuples_) {
ss << "(" << htdata.tuple << ")";
} else {
ss << "(" << htdata.flat_row << ")";
}
if (desc != NULL) {
Tuple* row[num_build_tuples_];
ss << " " << PrintRow(GetRow(htdata, reinterpret_cast<TupleRow*>(row)), *desc);
}
}
string HashTable::DebugString(bool skip_empty, bool show_match,
const RowDescriptor* desc) {
stringstream ss;
ss << endl;
for (int i = 0; i < num_buckets_; ++i) {
if (skip_empty && !buckets_[i].filled) continue;
ss << i << ": ";
if (show_match) {
if (buckets_[i].matched) {
ss << " [M]";
} else {
ss << " [U]";
}
}
if (buckets_[i].hasDuplicates) {
DuplicateNode* node = buckets_[i].bucketData.duplicates;
bool first = true;
ss << " [D] ";
while (node != NULL) {
if (!first) ss << ",";
DebugStringTuple(ss, node->htdata, desc);
node = node->next;
first = false;
}
} else {
ss << " [B] ";
if (buckets_[i].filled) {
DebugStringTuple(ss, buckets_[i].bucketData.htdata, desc);
} else {
ss << " - ";
}
}
ss << endl;
}
return ss.str();
}
string HashTable::PrintStats() const {
double curr_fill_factor = (double)num_filled_buckets_/(double)num_buckets_;
double avg_travel = (double)travel_length_/(double)num_probes_;
double avg_collisions = (double)num_hash_collisions_/(double)num_filled_buckets_;
stringstream ss;
ss << "Buckets: " << num_buckets_ << " " << num_filled_buckets_ << " "
<< curr_fill_factor << endl;
ss << "Duplicates: " << num_buckets_with_duplicates_ << " buckets "
<< num_duplicate_nodes_ << " nodes" << endl;
ss << "Probes: " << num_probes_ << endl;
ss << "Travel: " << travel_length_ << " " << avg_travel << endl;
ss << "HashCollisions: " << num_hash_collisions_ << " " << avg_collisions << endl;
ss << "Resizes: " << num_resizes_ << endl;
return ss.str();
}
// Helper function to store a value into the results buffer if the expr
// evaluated to NULL. We don't want (NULL, 1) to hash to the same as (0,1) so
// we'll pick a more random value.
static void CodegenAssignNullValue(LlvmCodeGen* codegen, LlvmBuilder* builder,
llvm::Value* dst, const ColumnType& type) {
uint64_t fnv_seed = HashUtil::FNV_SEED;
if (type.type == TYPE_STRING || type.type == TYPE_VARCHAR) {
llvm::Value* dst_ptr = builder->CreateStructGEP(NULL, dst, 0, "string_ptr");
llvm::Value* dst_len = builder->CreateStructGEP(NULL, dst, 1, "string_len");
llvm::Value* null_len = codegen->GetI32Constant(fnv_seed);
llvm::Value* null_ptr = builder->CreateIntToPtr(null_len, codegen->ptr_type());
builder->CreateStore(null_ptr, dst_ptr);
builder->CreateStore(null_len, dst_len);
} else {
llvm::Value* null_value = NULL;
int byte_size = type.GetByteSize();
// Get a type specific representation of fnv_seed
switch (type.type) {
case TYPE_BOOLEAN:
// In results, booleans are stored as 1 byte
dst = builder->CreateBitCast(dst, codegen->ptr_type());
null_value = codegen->GetI8Constant(fnv_seed);
break;
case TYPE_TIMESTAMP: {
// Cast 'dst' to 'i128*'
DCHECK_EQ(byte_size, 16);
llvm::PointerType* fnv_seed_ptr_type =
codegen->GetPtrType(llvm::Type::getIntNTy(codegen->context(), byte_size * 8));
dst = builder->CreateBitCast(dst, fnv_seed_ptr_type);
null_value = codegen->GetIntConstant(byte_size, fnv_seed, fnv_seed);
break;
}
case TYPE_TINYINT:
case TYPE_SMALLINT:
case TYPE_INT:
case TYPE_BIGINT:
case TYPE_DECIMAL:
case TYPE_DATE:
null_value = codegen->GetIntConstant(byte_size, fnv_seed, fnv_seed);
break;
case TYPE_FLOAT: {
// Don't care about the value, just the bit pattern
float fnv_seed_float = *reinterpret_cast<float*>(&fnv_seed);
null_value =
llvm::ConstantFP::get(codegen->context(), llvm::APFloat(fnv_seed_float));
break;
}
case TYPE_DOUBLE: {
// Don't care about the value, just the bit pattern
double fnv_seed_double = *reinterpret_cast<double*>(&fnv_seed);
null_value =
llvm::ConstantFP::get(codegen->context(), llvm::APFloat(fnv_seed_double));
break;
}
default:
DCHECK(false);
}
builder->CreateStore(null_value, dst);
}
}
// Codegen for evaluating a tuple row over either build_expr_evals_ or
// probe_expr_evals_. For a group by with (big int, string) the IR looks like:
//
// define i1 @EvalProbeRow(%"class.impala::HashTableCtx"* %this_ptr,
// %"class.impala::TupleRow"* %row, i8* %expr_values, i8* %expr_values_null) #34 {
// entry:
// %loc_addr = getelementptr i8, i8* %expr_values, i32 0
// %loc = bitcast i8* %loc_addr to i64*
// %result = call { i8, i64 } @GetSlotRef.2(%"class.impala::ExprContext"*
// inttoptr (i64 197737664 to %"class.impala::ExprContext"*),
// %"class.impala::TupleRow"* %row)
// %0 = extractvalue { i8, i64 } %result, 0
// %is_null = trunc i8 %0 to i1
// %1 = zext i1 %is_null to i8
// %null_byte_loc = getelementptr i8, i8* %expr_values_null, i32 0
// store i8 %1, i8* %null_byte_loc
// br i1 %is_null, label %null, label %not_null
//
// null: ; preds = %entry
// store i64 2166136261, i64* %loc
// br label %continue
//
// not_null: ; preds = %entry
// %val = extractvalue { i8, i64 } %result, 1
// store i64 %val, i64* %loc
// br label %continue
//
// continue: ; preds = %not_null, %null
// %is_null_phi = phi i1 [ true, %null ], [ false, %not_null ]
// %has_null = or i1 false, %is_null_phi
// %loc_addr1 = getelementptr i8, i8* %expr_values, i32 8
// %loc2 = bitcast i8* %loc_addr1 to %"struct.impala::StringValue"*
// %result6 = call { i64, i8* } @GetSlotRef.3(%"class.impala::ExprContext"*
// inttoptr (i64 197738048 to %"class.impala::ExprContext"*),
// %"class.impala::TupleRow"* %row)
// %2 = extractvalue { i64, i8* } %result6, 0
// %is_null7 = trunc i64 %2 to i1
// %3 = zext i1 %is_null7 to i8
// %null_byte_loc8 = getelementptr i8, i8* %expr_values_null, i32 1
// store i8 %3, i8* %null_byte_loc8
// br i1 %is_null7, label %null3, label %not_null4
//
// null3: ; preds = %continue
// %string_ptr = getelementptr inbounds %"struct.impala::StringValue",
// %"struct.impala::StringValue"* %loc2, i32 0, i32 0
// %string_len = getelementptr inbounds %"struct.impala::StringValue",
// %"struct.impala::StringValue"* %loc2, i32 0, i32 1
// store i8* inttoptr (i32 -2128831035 to i8*), i8** %string_ptr
// store i32 -2128831035, i32* %string_len
// br label %continue5
//
// not_null4: ; preds = %continue
// %4 = extractvalue { i64, i8* } %result6, 0
// %5 = ashr i64 %4, 32
// %6 = trunc i64 %5 to i32
// %7 = insertvalue %"struct.impala::StringValue" zeroinitializer, i32 %6, 1
// %result9 = extractvalue { i64, i8* } %result6, 1
// %8 = insertvalue %"struct.impala::StringValue" %7, i8* %result9, 0
// store %"struct.impala::StringValue" %8, %"struct.impala::StringValue"* %loc2
// br label %continue5
//
// continue5: ; preds = %not_null4, %null3
// %is_null_phi10 = phi i1 [ true, %null3 ], [ false, %not_null4 ]
// %has_null11 = or i1 %has_null, %is_null_phi10
// ret i1 %has_null11
// }
//
// For each expr, we create 3 code blocks. The null, not null and continue blocks.
// Both the null and not null branch into the continue block. The continue block
// becomes the start of the next block for codegen (either the next expr or just the
// end of the function).
Status HashTableCtx::CodegenEvalRow(
LlvmCodeGen* codegen, bool build, llvm::Function** fn) {
const vector<ScalarExpr*>& exprs = build ? build_exprs_ : probe_exprs_;
for (int i = 0; i < exprs.size(); ++i) {
// Disable codegen for CHAR
if (exprs[i]->type().type == TYPE_CHAR) {
return Status("HashTableCtx::CodegenEvalRow(): CHAR NYI");
}
}
// Get types to generate function prototype
llvm::PointerType* this_ptr_type = codegen->GetStructPtrType<HashTableCtx>();
llvm::PointerType* tuple_row_ptr_type = codegen->GetStructPtrType<TupleRow>();
LlvmCodeGen::FnPrototype prototype(codegen, build ? "EvalBuildRow" : "EvalProbeRow",
codegen->bool_type());
prototype.AddArgument(LlvmCodeGen::NamedVariable("this_ptr", this_ptr_type));
prototype.AddArgument(LlvmCodeGen::NamedVariable("row", tuple_row_ptr_type));
prototype.AddArgument(LlvmCodeGen::NamedVariable("expr_values", codegen->ptr_type()));
prototype.AddArgument(
LlvmCodeGen::NamedVariable("expr_values_null", codegen->ptr_type()));
llvm::LLVMContext& context = codegen->context();
LlvmBuilder builder(context);
llvm::Value* args[4];
*fn = prototype.GeneratePrototype(&builder, args);
llvm::Value* this_ptr = args[0];
llvm::Value* row = args[1];
llvm::Value* expr_values = args[2];
llvm::Value* expr_values_null = args[3];
llvm::Value* has_null = codegen->false_value();
// evaluator_vector = build_expr_evals_.data() / probe_expr_evals_.data()
llvm::Value* eval_vector = codegen->CodegenCallFunction(&builder,
build ? IRFunction::HASH_TABLE_GET_BUILD_EXPR_EVALUATORS :
IRFunction::HASH_TABLE_GET_PROBE_EXPR_EVALUATORS,
this_ptr, "eval_vector");
for (int i = 0; i < exprs.size(); ++i) {
// TODO: refactor this to somewhere else? This is not hash table specific except for
// the null handling bit and would be used for anyone that needs to materialize a
// vector of exprs
// Convert result buffer to llvm ptr type
int offset = expr_values_cache_.expr_values_offsets(i);
llvm::Value* loc = builder.CreateInBoundsGEP(
NULL, expr_values, codegen->GetI32Constant(offset), "loc_addr");
llvm::Value* llvm_loc = builder.CreatePointerCast(loc,
codegen->GetSlotPtrType(exprs[i]->type()), "loc");
llvm::BasicBlock* null_block = llvm::BasicBlock::Create(context, "null", *fn);
llvm::BasicBlock* not_null_block = llvm::BasicBlock::Create(context, "not_null", *fn);
llvm::BasicBlock* continue_block = llvm::BasicBlock::Create(context, "continue", *fn);
// Call expr
llvm::Function* expr_fn;
Status status = exprs[i]->GetCodegendComputeFn(codegen, false, &expr_fn);
if (!status.ok()) {
*fn = NULL;
return Status(Substitute(
"Problem with HashTableCtx::CodegenEvalRow(): $0", status.GetDetail()));
}
// Avoid bloating function by inlining too many exprs into it.
if (i >= LlvmCodeGen::CODEGEN_INLINE_EXPRS_THRESHOLD) {
codegen->SetNoInline(expr_fn);
}
llvm::Value* eval_arg = codegen->CodegenArrayAt(&builder, eval_vector, i, "eval");
CodegenAnyVal result = CodegenAnyVal::CreateCallWrapped(
codegen, &builder, exprs[i]->type(), expr_fn, {eval_arg, row}, "result");
llvm::Value* is_null = result.GetIsNull();
// Set null-byte result
llvm::Value* null_byte = builder.CreateZExt(is_null, codegen->i8_type());
llvm::Value* llvm_null_byte_loc = builder.CreateInBoundsGEP(
NULL, expr_values_null, codegen->GetI32Constant(i), "null_byte_loc");
builder.CreateStore(null_byte, llvm_null_byte_loc);
builder.CreateCondBr(is_null, null_block, not_null_block);
// Null block
builder.SetInsertPoint(null_block);
if (!stores_nulls_) {
// hash table doesn't store nulls, no reason to keep evaluating exprs
builder.CreateRet(codegen->true_value());
} else {
CodegenAssignNullValue(codegen, &builder, llvm_loc, exprs[i]->type());
builder.CreateBr(continue_block);
}
// Not null block
builder.SetInsertPoint(not_null_block);
result.ConvertToCanonicalForm();
result.StoreToNativePtr(llvm_loc);
builder.CreateBr(continue_block);
// Continue block
builder.SetInsertPoint(continue_block);
if (stores_nulls_) {
// Update has_null
llvm::PHINode* is_null_phi =
builder.CreatePHI(codegen->bool_type(), 2, "is_null_phi");
is_null_phi->addIncoming(codegen->true_value(), null_block);
is_null_phi->addIncoming(codegen->false_value(), not_null_block);
has_null = builder.CreateOr(has_null, is_null_phi, "has_null");
}
}
builder.CreateRet(has_null);
// Avoid inlining a large EvalRow() function into caller.
if (exprs.size() > LlvmCodeGen::CODEGEN_INLINE_EXPR_BATCH_THRESHOLD) {
codegen->SetNoInline(*fn);
}
*fn = codegen->FinalizeFunction(*fn);
if (*fn == NULL) {
return Status("Codegen'd HashTableCtx::EvalRow() function failed verification, "
"see log");
}
return Status::OK();
}
// Codegen for hashing the current row. In the case with both string and non-string data
// (group by int_col, string_col), the IR looks like:
//
// define i32 @HashRow(%"class.impala::HashTableCtx"* %this_ptr, i8* %expr_values,
// i8* %expr_values_null) #34 {
// entry:
// %seed = call i32 @_ZNK6impala12HashTableCtx11GetHashSeedEv(
// %"class.impala::HashTableCtx"* %this_ptr)
// %hash = call i32 @CrcHash8(i8* %expr_values, i32 8, i32 %seed)
// %loc_addr = getelementptr i8, i8* %expr_values, i32 8
// %null_byte_loc = getelementptr i8, i8* %expr_values_null, i32 1
// %null_byte = load i8, i8* %null_byte_loc
// %is_null = icmp ne i8 %null_byte, 0
// br i1 %is_null, label %null, label %not_null
//
// null: ; preds = %entry
// %str_null = call i32 @CrcHash16(i8* %loc_addr, i32 16, i32 %hash)
// br label %continue
//
// not_null: ; preds = %entry
// %str_val = bitcast i8* %loc_addr to %"struct.impala::StringValue"*
// %0 = getelementptr inbounds %"struct.impala::StringValue",
// %"struct.impala::StringValue"* %str_val, i32 0, i32 0
// %1 = getelementptr inbounds %"struct.impala::StringValue",
// %"struct.impala::StringValue"* %str_val, i32 0, i32 1
// %ptr = load i8*, i8** %0
// %len = load i32, i32* %1
// %string_hash = call i32 @IrCrcHash(i8* %ptr, i32 %len, i32 %hash)
// br label %continue
//
// continue: ; preds = %not_null, %null
// %hash_phi = phi i32 [ %string_hash, %not_null ], [ %str_null, %null ]
// ret i32 %hash_phi
// }
Status HashTableCtx::CodegenHashRow(
LlvmCodeGen* codegen, bool use_murmur, llvm::Function** fn) {
for (int i = 0; i < build_exprs_.size(); ++i) {
// Disable codegen for CHAR
if (build_exprs_[i]->type().type == TYPE_CHAR) {
return Status("HashTableCtx::CodegenHashRow(): CHAR NYI");
}
}
// Get types to generate function prototype
llvm::PointerType* this_ptr_type = codegen->GetStructPtrType<HashTableCtx>();
LlvmCodeGen::FnPrototype prototype(
codegen, (use_murmur ? "MurmurHashRow" : "HashRow"), codegen->i32_type());
prototype.AddArgument(LlvmCodeGen::NamedVariable("this_ptr", this_ptr_type));
prototype.AddArgument(LlvmCodeGen::NamedVariable("expr_values", codegen->ptr_type()));
prototype.AddArgument(
LlvmCodeGen::NamedVariable("expr_values_null", codegen->ptr_type()));
llvm::LLVMContext& context = codegen->context();
LlvmBuilder builder(context);
llvm::Value* args[3];
*fn = prototype.GeneratePrototype(&builder, args);
llvm::Value* this_arg = args[0];
llvm::Value* expr_values = args[1];
llvm::Value* expr_values_null = args[2];
// Call GetHashSeed() to get seeds_[level_]
llvm::Value* seed = codegen->CodegenCallFunction(
&builder, IRFunction::HASH_TABLE_GET_HASH_SEED, this_arg, "seed");
llvm::Value* hash_result = seed;
const int var_result_offset = expr_values_cache_.var_result_offset();
const int expr_values_bytes_per_row = expr_values_cache_.expr_values_bytes_per_row();
if (var_result_offset == -1) {
// No variable length slots, just hash what is in 'expr_expr_values_cache_'
if (expr_values_bytes_per_row > 0) {
llvm::Function* hash_fn = use_murmur ?
codegen->GetMurmurHashFunction(expr_values_bytes_per_row) :
codegen->GetHashFunction(expr_values_bytes_per_row);
llvm::Value* len = codegen->GetI32Constant(expr_values_bytes_per_row);
hash_result = builder.CreateCall(
hash_fn, llvm::ArrayRef<llvm::Value*>({expr_values, len, hash_result}), "hash");
}
} else {
if (var_result_offset > 0) {
llvm::Function* hash_fn = use_murmur ?
codegen->GetMurmurHashFunction(var_result_offset) :
codegen->GetHashFunction(var_result_offset);
llvm::Value* len = codegen->GetI32Constant(var_result_offset);
hash_result = builder.CreateCall(
hash_fn, llvm::ArrayRef<llvm::Value*>({expr_values, len, hash_result}), "hash");
}
// Hash string slots
for (int i = 0; i < build_exprs_.size(); ++i) {
if (build_exprs_[i]->type().type != TYPE_STRING &&
build_exprs_[i]->type().type != TYPE_VARCHAR) {
continue;
}
llvm::BasicBlock* null_block = NULL;
llvm::BasicBlock* not_null_block = NULL;
llvm::BasicBlock* continue_block = NULL;
llvm::Value* str_null_result = NULL;
int offset = expr_values_cache_.expr_values_offsets(i);
llvm::Value* llvm_loc = builder.CreateInBoundsGEP(
NULL, expr_values, codegen->GetI32Constant(offset), "loc_addr");
// If the hash table stores nulls, we need to check if the stringval
// evaluated to NULL
if (stores_nulls_) {
null_block = llvm::BasicBlock::Create(context, "null", *fn);
not_null_block = llvm::BasicBlock::Create(context, "not_null", *fn);
continue_block = llvm::BasicBlock::Create(context, "continue", *fn);
llvm::Value* llvm_null_byte_loc = builder.CreateInBoundsGEP(NULL,
expr_values_null, codegen->GetI32Constant(i), "null_byte_loc");
llvm::Value* null_byte = builder.CreateLoad(llvm_null_byte_loc, "null_byte");
llvm::Value* is_null = builder.CreateICmpNE(
null_byte, codegen->GetI8Constant(0), "is_null");
builder.CreateCondBr(is_null, null_block, not_null_block);
// For null, we just want to call the hash function on the portion of
// the data
builder.SetInsertPoint(null_block);
llvm::Function* null_hash_fn = use_murmur ?
codegen->GetMurmurHashFunction(sizeof(StringValue)) :
codegen->GetHashFunction(sizeof(StringValue));
llvm::Value* len = codegen->GetI32Constant(sizeof(StringValue));
str_null_result = builder.CreateCall(null_hash_fn,
llvm::ArrayRef<llvm::Value*>({llvm_loc, len, hash_result}), "str_null");
builder.CreateBr(continue_block);
builder.SetInsertPoint(not_null_block);
}
// Convert expr_values_buffer_ loc to llvm value
llvm::Value* str_val = builder.CreatePointerCast(
llvm_loc, codegen->GetSlotPtrType(TYPE_STRING), "str_val");
llvm::Value* ptr = builder.CreateStructGEP(NULL, str_val, 0);
llvm::Value* len = builder.CreateStructGEP(NULL, str_val, 1);
ptr = builder.CreateLoad(ptr, "ptr");
len = builder.CreateLoad(len, "len");
// Call hash(ptr, len, hash_result);
llvm::Function* general_hash_fn =
use_murmur ? codegen->GetMurmurHashFunction() : codegen->GetHashFunction();
llvm::Value* string_hash_result = builder.CreateCall(general_hash_fn,
llvm::ArrayRef<llvm::Value*>({ptr, len, hash_result}), "string_hash");
if (stores_nulls_) {
builder.CreateBr(continue_block);
builder.SetInsertPoint(continue_block);
// Use phi node to reconcile that we could have come from the string-null
// path and string not null paths.
llvm::PHINode* phi_node =
builder.CreatePHI(codegen->i32_type(), 2, "hash_phi");
phi_node->addIncoming(string_hash_result, not_null_block);
phi_node->addIncoming(str_null_result, null_block);
hash_result = phi_node;
} else {
hash_result = string_hash_result;
}
}
}
builder.CreateRet(hash_result);
// Avoid inlining into caller if there are many exprs.
if (build_exprs_.size() > LlvmCodeGen::CODEGEN_INLINE_EXPR_BATCH_THRESHOLD) {
codegen->SetNoInline(*fn);
}
*fn = codegen->FinalizeFunction(*fn);
if (*fn == NULL) {
return Status(
"Codegen'd HashTableCtx::HashRow() function failed verification, see log");
}
return Status::OK();
}
// Codegen for HashTableCtx::Equals. For a group by with (bigint, string),
// the IR looks like:
//
// define i1 @Equals(%"class.impala::HashTableCtx"* %this_ptr, %"class.impala::TupleRow"*
// %row,
// i8* %expr_values, i8* %expr_values_null) #34 {
// entry:
// %0 = alloca { i64, i8* }
// %result = call { i8, i64 } @GetSlotRef.2(%"class.impala::ExprContext"*
// inttoptr (i64 139107136 to %"class.impala::ExprContext"*),
// %"class.impala::TupleRow"* %row)
// %1 = extractvalue { i8, i64 } %result, 0
// %is_null = trunc i8 %1 to i1
// %null_byte_loc = getelementptr i8, i8* %expr_values_null, i32 0
// %2 = load i8, i8* %null_byte_loc
// %3 = icmp ne i8 %2, 0
// %loc = getelementptr i8, i8* %expr_values, i32 0
// %row_val = bitcast i8* %loc to i64*
// br i1 %is_null, label %null, label %not_null
//
// false_block: ; preds = %cmp9, %not_null2, %null1,
// %cmp, %not_null, %null
// ret i1 false
//
// null: ; preds = %entry
// br i1 %3, label %continue, label %false_block
//
// not_null: ; preds = %entry
// br i1 %3, label %false_block, label %cmp
//
// continue: ; preds = %cmp, %null
// %result4 = call { i64, i8* } @GetSlotRef.3(%"class.impala::ExprContext"*
// inttoptr (i64 139107328 to %"class.impala::ExprContext"*),
// %"class.impala::TupleRow"* %row)
// %4 = extractvalue { i64, i8* } %result4, 0
// %is_null5 = trunc i64 %4 to i1
// %null_byte_loc6 = getelementptr i8, i8* %expr_values_null, i32 1
// %5 = load i8, i8* %null_byte_loc6
// %6 = icmp ne i8 %5, 0
// %loc7 = getelementptr i8, i8* %expr_values, i32 8
// %row_val8 = bitcast i8* %loc7 to %"struct.impala::StringValue"*
// br i1 %is_null5, label %null1, label %not_null2
//
// cmp: ; preds = %not_null
// %7 = load i64, i64* %row_val
// %val = extractvalue { i8, i64 } %result, 1
// %cmp_raw = icmp eq i64 %val, %7
// br i1 %cmp_raw, label %continue, label %false_block
//
// null1: ; preds = %continue
// br i1 %6, label %continue3, label %false_block
//
// not_null2: ; preds = %continue
// br i1 %6, label %false_block, label %cmp9
//
// continue3: ; preds = %cmp9, %null1
// ret i1 true
//
// cmp9: ; preds = %not_null2
// store { i64, i8* } %result4, { i64, i8* }* %0
// %8 = bitcast { i64, i8* }* %0 to %"struct.impala_udf::StringVal"*
// %cmp_raw10 = call i1
// @_Z13StringValueEqRKN10impala_udf9StringValERKN6impala11StringValueE(
// %"struct.impala_udf::StringVal"* %8, %"struct.impala::StringValue"* %row_val8)
// br i1 %cmp_raw10, label %continue3, label %false_block
// }
Status HashTableCtx::CodegenEquals(
LlvmCodeGen* codegen, bool inclusive_equality, llvm::Function** fn) {
for (int i = 0; i < build_exprs_.size(); ++i) {
// Disable codegen for CHAR
if (build_exprs_[i]->type().type == TYPE_CHAR) {
return Status("HashTableCtx::CodegenEquals(): CHAR NYI");
}
}
// Get types to generate function prototype
llvm::PointerType* this_ptr_type = codegen->GetStructPtrType<HashTableCtx>();
llvm::PointerType* tuple_row_ptr_type = codegen->GetStructPtrType<TupleRow>();
LlvmCodeGen::FnPrototype prototype(codegen, "Equals", codegen->bool_type());
prototype.AddArgument(LlvmCodeGen::NamedVariable("this_ptr", this_ptr_type));
prototype.AddArgument(LlvmCodeGen::NamedVariable("row", tuple_row_ptr_type));
prototype.AddArgument(LlvmCodeGen::NamedVariable("expr_values", codegen->ptr_type()));
prototype.AddArgument(
LlvmCodeGen::NamedVariable("expr_values_null", codegen->ptr_type()));
llvm::LLVMContext& context = codegen->context();
LlvmBuilder builder(context);
llvm::Value* args[4];
*fn = prototype.GeneratePrototype(&builder, args);
llvm::Value* this_ptr = args[0];
llvm::Value* row = args[1];
llvm::Value* expr_values = args[2];
llvm::Value* expr_values_null = args[3];
// eval_vector = build_expr_evals_.data()
llvm::Value* eval_vector = codegen->CodegenCallFunction(&builder,
IRFunction::HASH_TABLE_GET_BUILD_EXPR_EVALUATORS, this_ptr, "eval_vector");
llvm::BasicBlock* false_block = llvm::BasicBlock::Create(context, "false_block", *fn);
for (int i = 0; i < build_exprs_.size(); ++i) {
llvm::BasicBlock* null_block = llvm::BasicBlock::Create(context, "null", *fn);
llvm::BasicBlock* not_null_block = llvm::BasicBlock::Create(context, "not_null", *fn);
llvm::BasicBlock* continue_block = llvm::BasicBlock::Create(context, "continue", *fn);
// call GetValue on build_exprs[i]
llvm::Function* expr_fn;
Status status = build_exprs_[i]->GetCodegendComputeFn(codegen, false, &expr_fn);
if (!status.ok()) {
*fn = NULL;
return Status(
Substitute("Problem with HashTableCtx::CodegenEquals: $0", status.GetDetail()));
}
if (build_exprs_.size() > LlvmCodeGen::CODEGEN_INLINE_EXPRS_THRESHOLD) {
// Avoid bloating function by inlining too many exprs into it.
codegen->SetNoInline(expr_fn);
}
// Load ScalarExprEvaluator*: eval = eval_vector[i];
llvm::Value* eval_arg = codegen->CodegenArrayAt(&builder, eval_vector, i, "eval");
// Evaluate the expression.
CodegenAnyVal result = CodegenAnyVal::CreateCallWrapped(codegen, &builder,
build_exprs_[i]->type(), expr_fn, {eval_arg, row}, "result");
llvm::Value* is_null = result.GetIsNull();
// Determine if row is null (i.e. expr_values_null[i] == true). In
// the case where the hash table does not store nulls, this is always false.
llvm::Value* row_is_null = codegen->false_value();
// We consider null values equal if we are comparing build rows or if the join
// predicate is <=>
if (inclusive_equality || finds_nulls_[i]) {
llvm::Value* llvm_null_byte_loc = builder.CreateInBoundsGEP(
NULL, expr_values_null, codegen->GetI32Constant(i), "null_byte_loc");
llvm::Value* null_byte = builder.CreateLoad(llvm_null_byte_loc);
row_is_null =
builder.CreateICmpNE(null_byte, codegen->GetI8Constant(0));
}
if (inclusive_equality) result.ConvertToCanonicalForm();
// Get llvm value for row_val from 'expr_values'
int offset = expr_values_cache_.expr_values_offsets(i);
llvm::Value* loc = builder.CreateInBoundsGEP(
NULL, expr_values, codegen->GetI32Constant(offset), "loc");
llvm::Value* row_val = builder.CreatePointerCast(
loc, codegen->GetSlotPtrType(build_exprs_[i]->type()), "row_val");
// Branch for GetValue() returning NULL
builder.CreateCondBr(is_null, null_block, not_null_block);
// Null block
builder.SetInsertPoint(null_block);
builder.CreateCondBr(row_is_null, continue_block, false_block);
// Not-null block
builder.SetInsertPoint(not_null_block);
if (stores_nulls_) {
llvm::BasicBlock* cmp_block = llvm::BasicBlock::Create(context, "cmp", *fn);
// First need to compare that row expr[i] is not null
builder.CreateCondBr(row_is_null, false_block, cmp_block);
builder.SetInsertPoint(cmp_block);
}
// Check result == row_val
llvm::Value* is_equal = result.EqToNativePtr(row_val, inclusive_equality);
builder.CreateCondBr(is_equal, continue_block, false_block);
builder.SetInsertPoint(continue_block);
}
builder.CreateRet(codegen->true_value());
builder.SetInsertPoint(false_block);
builder.CreateRet(codegen->false_value());
// Avoid inlining into caller if it is large.
if (build_exprs_.size() > LlvmCodeGen::CODEGEN_INLINE_EXPR_BATCH_THRESHOLD) {
codegen->SetNoInline(*fn);
}
*fn = codegen->FinalizeFunction(*fn);
if (*fn == NULL) {
return Status("Codegen'd HashTableCtx::Equals() function failed verification, "
"see log");
}
return Status::OK();
}
Status HashTableCtx::ReplaceHashTableConstants(LlvmCodeGen* codegen,
bool stores_duplicates, int num_build_tuples, llvm::Function* fn,
HashTableReplacedConstants* replacement_counts) {
replacement_counts->stores_nulls = codegen->ReplaceCallSitesWithBoolConst(
fn, stores_nulls(), "stores_nulls");
replacement_counts->finds_some_nulls = codegen->ReplaceCallSitesWithBoolConst(
fn, finds_some_nulls(), "finds_some_nulls");
replacement_counts->stores_tuples = codegen->ReplaceCallSitesWithBoolConst(
fn, num_build_tuples == 1, "stores_tuples");
replacement_counts->stores_duplicates = codegen->ReplaceCallSitesWithBoolConst(
fn, stores_duplicates, "stores_duplicates");
replacement_counts->quadratic_probing = codegen->ReplaceCallSitesWithBoolConst(
fn, FLAGS_enable_quadratic_probing, "quadratic_probing");
return Status::OK();
}