#include <OverlapsJoinHashTable.h>

Inheritance diagram for OverlapsJoinHashTable:

Collaboration diagram for OverlapsJoinHashTable:

Classes
struct	AlternativeCacheKeyForOverlapsHashJoin

Public Member Functions
	OverlapsJoinHashTable (const std::shared_ptr< Analyzer::BinOper > condition, const JoinType join_type, const std::vector< InputTableInfo > &query_infos, const Data_Namespace::MemoryLevel memory_level, ColumnCacheMap &column_cache, Executor *executor, const std::vector< InnerOuter > &inner_outer_pairs, const int device_count, const RegisteredQueryHint &query_hints, const HashTableBuildDagMap &hashtable_build_dag_map, const TableIdToNodeMap &table_id_to_node_map)

virtual	~OverlapsJoinHashTable ()

Public Member Functions inherited from HashJoin
virtual std::string	toStringFlat64 (const ExecutorDeviceType device_type, const int device_id) const

virtual std::string	toStringFlat32 (const ExecutorDeviceType device_type, const int device_id) const

JoinColumn	fetchJoinColumn (const Analyzer::ColumnVar hash_col, const std::vector< Fragmenter_Namespace::FragmentInfo > &fragment_info, const Data_Namespace::MemoryLevel effective_memory_level, const int device_id, std::vector< std::shared_ptr< Chunk_NS::Chunk >> &chunks_owner, DeviceAllocator dev_buff_owner, std::vector< std::shared_ptr< void >> &malloc_owner, Executor executor, ColumnCacheMap column_cache)

HashTable *	getHashTableForDevice (const size_t device_id) const

size_t	getJoinHashBufferSize (const ExecutorDeviceType device_type)

size_t	getJoinHashBufferSize (const ExecutorDeviceType device_type, const int device_id) const

int8_t *	getJoinHashBuffer (const ExecutorDeviceType device_type, const int device_id) const

void	freeHashBufferMemory ()

Static Public Member Functions
static std::shared_ptr < OverlapsJoinHashTable >	getInstance (const std::shared_ptr< Analyzer::BinOper > condition, const std::vector< InputTableInfo > &query_infos, const Data_Namespace::MemoryLevel memory_level, const JoinType join_type, const int device_count, ColumnCacheMap &column_cache, Executor *executor, const HashTableBuildDagMap &hashtable_build_dag_map, const RegisteredQueryHint &query_hint, const TableIdToNodeMap &table_id_to_node_map)
	Make hash table from an in-flight SQL query's parse tree etc. More...

static void	invalidateCache ()

static void	markCachedItemAsDirty (size_t table_key)

static HashtableRecycler *	getHashTableCache ()

static OverlapsTuningParamRecycler *	getOverlapsTuningParamCache ()

Static Public Member Functions inherited from HashJoin
static bool	layoutRequiresAdditionalBuffers (HashType layout) noexcept

static std::string	getHashTypeString (HashType ht) noexcept

static HashJoinMatchingSet	codegenMatchingSet (const std::vector< llvm::Value * > &hash_join_idx_args_in, const bool is_sharded, const bool col_is_nullable, const bool is_bw_eq, const int64_t sub_buff_size, Executor *executor, const bool is_bucketized=false)

static llvm::Value *	codegenHashTableLoad (const size_t table_idx, Executor *executor)

static std::shared_ptr< HashJoin >	getInstance (const std::shared_ptr< Analyzer::BinOper > qual_bin_oper, const std::vector< InputTableInfo > &query_infos, const Data_Namespace::MemoryLevel memory_level, const JoinType join_type, const HashType preferred_hash_type, const int device_count, ColumnCacheMap &column_cache, Executor *executor, const HashTableBuildDagMap &hashtable_build_dag_map, const RegisteredQueryHint &query_hint, const TableIdToNodeMap &table_id_to_node_map)
	Make hash table from an in-flight SQL query's parse tree etc. More...

static std::shared_ptr< HashJoin >	getSyntheticInstance (std::string_view table1, std::string_view column1, const Catalog_Namespace::Catalog &catalog1, std::string_view table2, std::string_view column2, const Catalog_Namespace::Catalog &catalog2, const Data_Namespace::MemoryLevel memory_level, const HashType preferred_hash_type, const int device_count, ColumnCacheMap &column_cache, Executor *executor)
	Make hash table from named tables and columns (such as for testing). More...

static std::shared_ptr< HashJoin >	getSyntheticInstance (const std::shared_ptr< Analyzer::BinOper > qual_bin_oper, const Data_Namespace::MemoryLevel memory_level, const HashType preferred_hash_type, const int device_count, ColumnCacheMap &column_cache, Executor *executor)
	Make hash table from named tables and columns (such as for testing). More...

static std::pair< std::string, std::shared_ptr< HashJoin > >	getSyntheticInstance (std::vector< std::shared_ptr< Analyzer::BinOper >>, const Data_Namespace::MemoryLevel memory_level, const HashType preferred_hash_type, const int device_count, ColumnCacheMap &column_cache, Executor *executor)

static shared::TableKey	getInnerTableId (const std::vector< InnerOuter > &inner_outer_pairs)

static bool	canAccessHashTable (bool allow_hash_table_recycling, bool invalid_cache_key, JoinType join_type)

static void	checkHashJoinReplicationConstraint (const shared::TableKey &table_key, const size_t shard_count, const Executor *executor)

static std::pair< InnerOuter, InnerOuterStringOpInfos >	normalizeColumnPair (const Analyzer::Expr lhs, const Analyzer::Expr rhs, const TemporaryTables *temporary_tables, const bool is_overlaps_join=false)

template<typename T >
static const T *	getHashJoinColumn (const Analyzer::Expr *expr)

static std::pair< std::vector < InnerOuter >, std::vector < InnerOuterStringOpInfos > >	normalizeColumnPairs (const Analyzer::BinOper condition, const TemporaryTables temporary_tables)

static std::vector< int >	collectFragmentIds (const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments)

static CompositeKeyInfo	getCompositeKeyInfo (const std::vector< InnerOuter > &inner_outer_pairs, const Executor *executor, const std::vector< InnerOuterStringOpInfos > &inner_outer_string_op_infos_pairs={})

static std::vector< const StringDictionaryProxy::IdMap * >	translateCompositeStrDictProxies (const CompositeKeyInfo &composite_key_info, const std::vector< InnerOuterStringOpInfos > &string_op_infos_for_keys, const Executor *executor)

static std::pair< const StringDictionaryProxy , StringDictionaryProxy >	getStrDictProxies (const InnerOuter &cols, const Executor *executor, const bool has_string_ops)

static const StringDictionaryProxy::IdMap *	translateInnerToOuterStrDictProxies (const InnerOuter &cols, const InnerOuterStringOpInfos &inner_outer_string_op_infos, ExpressionRange &old_col_range, const Executor *executor)

Protected Member Functions
void	reify (const HashType preferred_layout)

virtual void	reifyWithLayout (const HashType layout)

virtual void	reifyImpl (std::vector< ColumnsForDevice > &columns_per_device, const Fragmenter_Namespace::TableInfo &query_info, const HashType layout, const size_t shard_count, const size_t entry_count, const size_t emitted_keys_count, const bool skip_hashtable_caching, const size_t chosen_max_hashtable_size, const double chosen_bucket_threshold)

void	reifyForDevice (const ColumnsForDevice &columns_for_device, const HashType layout, const size_t entry_count, const size_t emitted_keys_count, const bool skip_hashtable_caching, const int device_id, const logger::ThreadLocalIds parent_thread_local_ids)

size_t	calculateHashTableSize (size_t number_of_dimensions, size_t emitted_keys_count, size_t entry_count) const

ColumnsForDevice	fetchColumnsForDevice (const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments, const int device_id, DeviceAllocator *dev_buff_owner)

virtual std::pair< size_t, size_t >	approximateTupleCount (const std::vector< double > &inverse_bucket_sizes_for_dimension, std::vector< ColumnsForDevice > &, const size_t chosen_max_hashtable_size, const double chosen_bucket_threshold)

virtual std::pair< size_t, size_t >	computeHashTableCounts (const size_t shard_count, const std::vector< double > &inverse_bucket_sizes_for_dimension, std::vector< ColumnsForDevice > &columns_per_device, const size_t chosen_max_hashtable_size, const double chosen_bucket_threshold)

void	setInverseBucketSizeInfo (const std::vector< double > &inverse_bucket_sizes, std::vector< ColumnsForDevice > &columns_per_device, const size_t device_count)

size_t	getKeyComponentWidth () const

size_t	getKeyComponentCount () const

HashType	getHashType () const noexceptoverride

Data_Namespace::MemoryLevel	getMemoryLevel () const noexceptoverride

int	getDeviceCount () const noexceptoverride

std::shared_ptr < BaselineHashTable >	initHashTableOnCpu (const std::vector< JoinColumn > &join_columns, const std::vector< JoinColumnTypeInfo > &join_column_types, const std::vector< JoinBucketInfo > &join_bucket_info, const HashType layout, const size_t entry_count, const size_t emitted_keys_count, const bool skip_hashtable_caching)

HashJoinMatchingSet	codegenMatchingSet (const CompilationOptions &, const size_t) override

std::string	toString (const ExecutorDeviceType device_type, const int device_id=0, bool raw=false) const override

DecodedJoinHashBufferSet	toSet (const ExecutorDeviceType device_type, const int device_id) const override

llvm::Value *	codegenSlot (const CompilationOptions &, const size_t) override

const RegisteredQueryHint &	getRegisteredQueryHint ()

size_t	getEntryCount () const

size_t	getEmittedKeysCount () const

size_t	getComponentBufferSize () const noexceptoverride

size_t	shardCount () const

Data_Namespace::MemoryLevel	getEffectiveMemoryLevel (const std::vector< InnerOuter > &inner_outer_pairs) const

shared::TableKey	getInnerTableId () const noexceptoverride

int	getInnerTableRteIdx () const noexceptoverride

size_t	getKeyBufferSize () const noexcept

size_t	offsetBufferOff () const noexceptoverride

size_t	countBufferOff () const noexceptoverride

size_t	payloadBufferOff () const noexceptoverride

std::string	getHashJoinType () const final

bool	isBitwiseEq () const override

std::shared_ptr< HashTable >	initHashTableOnCpuFromCache (QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier)

std::optional< std::pair < size_t, size_t > >	getApproximateTupleCountFromCache (QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier)

void	putHashTableOnCpuToCache (QueryPlanHash key, CacheItemType item_type, std::shared_ptr< HashTable > hashtable_ptr, DeviceIdentifier device_identifier, size_t hashtable_building_time)

llvm::Value *	codegenKey (const CompilationOptions &)

std::vector< llvm::Value * >	codegenManyKey (const CompilationOptions &)

std::optional < OverlapsHashTableMetaInfo >	getOverlapsHashTableMetaInfo ()

QueryPlanHash	getAlternativeCacheKey (AlternativeCacheKeyForOverlapsHashJoin &info)

void	generateCacheKey (const size_t max_hashtable_size, const double bucket_threshold, const std::vector< double > &bucket_sizes, std::vector< std::vector< Fragmenter_Namespace::FragmentInfo >> &fragments_per_device, int device_count)

QueryPlanHash	getCacheKey (int device_id) const

const std::vector< InnerOuter > &	getInnerOuterPairs () const

void	setOverlapsHashtableMetaInfo (size_t max_table_size_bytes, double bucket_threshold, std::vector< double > &bucket_sizes)

Protected Attributes
const std::shared_ptr < Analyzer::BinOper >	condition_

const JoinType	join_type_

const std::vector < InputTableInfo > &	query_infos_

const Data_Namespace::MemoryLevel	memory_level_

Executor *	executor_

ColumnCacheMap &	column_cache_

std::vector< InnerOuter >	inner_outer_pairs_

const int	device_count_

RegisteredQueryHint	query_hints_

std::vector< double >	inverse_bucket_sizes_for_dimension_

double	chosen_overlaps_bucket_threshold_

size_t	chosen_overlaps_max_table_size_bytes_

CompositeKeyInfo	composite_key_info_

std::optional< HashType >	layout_override_

std::mutex	cpu_hash_table_buff_mutex_

HashTableBuildDagMap	hashtable_build_dag_map_

QueryPlanDAG	query_plan_dag_

std::vector< QueryPlanHash >	hashtable_cache_key_

HashtableCacheMetaInfo	hashtable_cache_meta_info_

std::unordered_set< size_t >	table_keys_

const TableIdToNodeMap	table_id_to_node_map_

Protected Attributes inherited from HashJoin
std::vector< std::shared_ptr < HashTable > >	hash_tables_for_device_

Static Protected Attributes
static std::unique_ptr < HashtableRecycler >	hash_table_cache_

static std::unique_ptr < OverlapsTuningParamRecycler >	auto_tuner_cache_

Additional Inherited Members
Static Protected Member Functions inherited from HashJoin
static llvm::Value *	codegenColOrStringOper (const Analyzer::Expr *col_or_string_oper, const std::vector< StringOps_Namespace::StringOpInfo > &string_op_infos, CodeGenerator &code_generator, const CompilationOptions &co)

Detailed Description

Definition at line 24 of file OverlapsJoinHashTable.h.

Constructor & Destructor Documentation

OverlapsJoinHashTable::OverlapsJoinHashTable	(	const std::shared_ptr< Analyzer::BinOper >	condition,
		const JoinType	join_type,
		const std::vector< InputTableInfo > &	query_infos,
		const Data_Namespace::MemoryLevel	memory_level,
		ColumnCacheMap &	column_cache,
		Executor *	executor,
		const std::vector< InnerOuter > &	inner_outer_pairs,
		const int	device_count,
		const RegisteredQueryHint &	query_hints,
		const HashTableBuildDagMap &	hashtable_build_dag_map,
		const TableIdToNodeMap &	table_id_to_node_map
	)

inline

Definition at line 26 of file OverlapsJoinHashTable.h.

References CHECK_GT, device_count_, and HashJoin::hash_tables_for_device_.

       : condition_(condition)
       , join_type_(join_type)
       , query_infos_(query_infos)
       , memory_level_(memory_level)
       , executor_(executor)
       , column_cache_(column_cache)
       , inner_outer_pairs_(inner_outer_pairs)
       , device_count_(device_count)
       , query_hints_(query_hints)
       , hashtable_build_dag_map_(hashtable_build_dag_map)
       , table_id_to_node_map_(table_id_to_node_map) {
     CHECK_GT(device_count_, 0);
     hash_tables_for_device_.resize(std::max(device_count_, 1));
   }

virtual OverlapsJoinHashTable::~OverlapsJoinHashTable ( )

inlinevirtual

Definition at line 52 of file OverlapsJoinHashTable.h.

52 {}

Member Function Documentation

std::pair< size_t, size_t > OverlapsJoinHashTable::approximateTupleCount	(	const std::vector< double > &	inverse_bucket_sizes_for_dimension,
		std::vector< ColumnsForDevice > &	columns_per_device,
		const size_t	chosen_max_hashtable_size,
		const double	chosen_bucket_threshold
	)

protectedvirtual

Reimplemented in RangeJoinHashTable.

Definition at line 979 of file OverlapsJoinHashTable.cpp.

References gpu_enabled::accumulate(), approximate_distinct_tuples_on_device_overlaps(), approximate_distinct_tuples_overlaps(), threading_serial::async(), Bitmap, CHECK, CHECK_EQ, CHECK_GT, CPU, DataRecyclerUtil::CPU_DEVICE_IDENTIFIER, Data_Namespace::CPU_LEVEL, cpu_threads(), device_count_, executor_, getApproximateTupleCountFromCache(), getEffectiveMemoryLevel(), getQueryEngineCudaStreamForDevice(), GPU, Data_Namespace::GPU_LEVEL, hashtable_cache_key_, hll_size(), hll_unify(), inner_outer_pairs_, OVERLAPS_HT, transfer_flat_object_to_gpu(), transfer_vector_of_flat_objects_to_gpu(), UNREACHABLE, and VLOG.

Referenced by computeHashTableCounts().

                                           {
   const auto effective_memory_level = getEffectiveMemoryLevel(inner_outer_pairs_);
   CountDistinctDescriptor count_distinct_desc{
       CountDistinctImplType::Bitmap,
       0,
       11,
       true,
       effective_memory_level == Data_Namespace::MemoryLevel::GPU_LEVEL
           ? ExecutorDeviceType::GPU
           : ExecutorDeviceType::CPU,
       1};
   const auto padded_size_bytes = count_distinct_desc.bitmapPaddedSizeBytes();
 
   CHECK(!columns_per_device.empty() && !columns_per_device.front().join_columns.empty());
   if (columns_per_device.front().join_columns.front().num_elems == 0) {
     return std::make_pair(0, 0);
   }
 
   // TODO: state management in here should be revisited, but this should be safe enough
   // for now
   // re-compute bucket counts per device based on global bucket size
   for (size_t device_id = 0; device_id < columns_per_device.size(); ++device_id) {
     auto& columns_for_device = columns_per_device[device_id];
     columns_for_device.setBucketInfo(inverse_bucket_sizes_for_dimension,
                                      inner_outer_pairs_);
   }
 
   // Number of keys must match dimension of buckets
   CHECK_EQ(columns_per_device.front().join_columns.size(),
            columns_per_device.front().join_buckets.size());
   if (effective_memory_level == Data_Namespace::MemoryLevel::CPU_LEVEL) {
     // Note that this path assumes each device has the same hash table (for GPU hash
     // join w/ hash table built on CPU)
     const auto cached_count_info =
         getApproximateTupleCountFromCache(hashtable_cache_key_.front(),
                                           CacheItemType::OVERLAPS_HT,
                                           DataRecyclerUtil::CPU_DEVICE_IDENTIFIER);
     if (cached_count_info) {
       VLOG(1) << "Using a cached tuple count: " << cached_count_info->first
               << ", emitted keys count: " << cached_count_info->second;
       return *cached_count_info;
     }
     int thread_count = cpu_threads();
     std::vector<uint8_t> hll_buffer_all_cpus(thread_count * padded_size_bytes);
     auto hll_result = &hll_buffer_all_cpus[0];
 
     std::vector<int32_t> num_keys_for_row;
     // TODO(adb): support multi-column overlaps join
     num_keys_for_row.resize(columns_per_device.front().join_columns[0].num_elems);
 
     approximate_distinct_tuples_overlaps(hll_result,
                                          num_keys_for_row,
                                          count_distinct_desc.bitmap_sz_bits,
                                          padded_size_bytes,
                                          columns_per_device.front().join_columns,
                                          columns_per_device.front().join_column_types,
                                          columns_per_device.front().join_buckets,
                                          thread_count);
     for (int i = 1; i < thread_count; ++i) {
       hll_unify(hll_result,
                 hll_result + i * padded_size_bytes,
                 1 << count_distinct_desc.bitmap_sz_bits);
     }
     return std::make_pair(
         hll_size(hll_result, count_distinct_desc.bitmap_sz_bits),
         static_cast<size_t>(num_keys_for_row.size() > 0 ? num_keys_for_row.back() : 0));
   }
 #ifdef HAVE_CUDA
   auto data_mgr = executor_->getDataMgr();
   std::vector<std::vector<uint8_t>> host_hll_buffers(device_count_);
   for (auto& host_hll_buffer : host_hll_buffers) {
     host_hll_buffer.resize(count_distinct_desc.bitmapPaddedSizeBytes());
   }
   std::vector<size_t> emitted_keys_count_device_threads(device_count_, 0);
   std::vector<std::future<void>> approximate_distinct_device_threads;
   for (int device_id = 0; device_id < device_count_; ++device_id) {
     approximate_distinct_device_threads.emplace_back(std::async(
         std::launch::async,
         [device_id,
          &columns_per_device,
          &count_distinct_desc,
          data_mgr,
          &host_hll_buffers,
          &emitted_keys_count_device_threads] {
           auto allocator = std::make_unique<CudaAllocator>(
               data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id));
           auto device_hll_buffer =
               allocator->alloc(count_distinct_desc.bitmapPaddedSizeBytes());
           data_mgr->getCudaMgr()->zeroDeviceMem(
               device_hll_buffer,
               count_distinct_desc.bitmapPaddedSizeBytes(),
               device_id,
               getQueryEngineCudaStreamForDevice(device_id));
           const auto& columns_for_device = columns_per_device[device_id];
           auto join_columns_gpu = transfer_vector_of_flat_objects_to_gpu(
               columns_for_device.join_columns, *allocator);
 
           CHECK_GT(columns_for_device.join_buckets.size(), 0u);
           const auto& inverse_bucket_sizes_for_dimension =
               columns_for_device.join_buckets[0].inverse_bucket_sizes_for_dimension;
           auto inverse_bucket_sizes_gpu = allocator->alloc(
               inverse_bucket_sizes_for_dimension.size() * sizeof(double));
           allocator->copyToDevice(
               inverse_bucket_sizes_gpu,
               inverse_bucket_sizes_for_dimension.data(),
               inverse_bucket_sizes_for_dimension.size() * sizeof(double));
           const size_t row_counts_buffer_sz =
               columns_per_device.front().join_columns[0].num_elems * sizeof(int32_t);
           auto row_counts_buffer = allocator->alloc(row_counts_buffer_sz);
           data_mgr->getCudaMgr()->zeroDeviceMem(
               row_counts_buffer,
               row_counts_buffer_sz,
               device_id,
               getQueryEngineCudaStreamForDevice(device_id));
           const auto key_handler =
               OverlapsKeyHandler(inverse_bucket_sizes_for_dimension.size(),
                                  join_columns_gpu,
                                  reinterpret_cast<double*>(inverse_bucket_sizes_gpu));
           const auto key_handler_gpu =
               transfer_flat_object_to_gpu(key_handler, *allocator);
           approximate_distinct_tuples_on_device_overlaps(
               reinterpret_cast<uint8_t*>(device_hll_buffer),
               count_distinct_desc.bitmap_sz_bits,
               reinterpret_cast<int32_t*>(row_counts_buffer),
               key_handler_gpu,
               columns_for_device.join_columns[0].num_elems);
 
           auto& host_emitted_keys_count = emitted_keys_count_device_threads[device_id];
           allocator->copyFromDevice(
               &host_emitted_keys_count,
               row_counts_buffer +
                   (columns_per_device.front().join_columns[0].num_elems - 1) *
                       sizeof(int32_t),
               sizeof(int32_t));
 
           auto& host_hll_buffer = host_hll_buffers[device_id];
           allocator->copyFromDevice(&host_hll_buffer[0],
                                     device_hll_buffer,
                                     count_distinct_desc.bitmapPaddedSizeBytes());
         }));
   }
   for (auto& child : approximate_distinct_device_threads) {
     child.get();
   }
   CHECK_EQ(Data_Namespace::MemoryLevel::GPU_LEVEL, effective_memory_level);
   auto& result_hll_buffer = host_hll_buffers.front();
   auto hll_result = reinterpret_cast<int32_t*>(&result_hll_buffer[0]);
   for (int device_id = 1; device_id < device_count_; ++device_id) {
     auto& host_hll_buffer = host_hll_buffers[device_id];
     hll_unify(hll_result,
               reinterpret_cast<int32_t*>(&host_hll_buffer[0]),
               1 << count_distinct_desc.bitmap_sz_bits);
   }
   const size_t emitted_keys_count =
       std::accumulate(emitted_keys_count_device_threads.begin(),
                       emitted_keys_count_device_threads.end(),
                       0);
   return std::make_pair(hll_size(hll_result, count_distinct_desc.bitmap_sz_bits),
                         emitted_keys_count);
 #else
   UNREACHABLE();
   return {0, 0};
 #endif  // HAVE_CUDA
 }

Here is the call graph for this function:

Here is the caller graph for this function:

size_t OverlapsJoinHashTable::calculateHashTableSize	(	size_t	number_of_dimensions,
		size_t	emitted_keys_count,
		size_t	entry_count
	)		const

protected

Definition at line 909 of file OverlapsJoinHashTable.cpp.

References getKeyComponentWidth().

Referenced by RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

                                                                                {
   const auto key_component_width = getKeyComponentWidth();
   const auto key_component_count = number_of_dimensions;
   const auto entry_size = key_component_count * key_component_width;
   const auto keys_for_all_rows = emitted_keys_count;
   const size_t one_to_many_hash_entries = 2 * entry_count + keys_for_all_rows;
   const size_t hash_table_size =
       entry_size * entry_count + one_to_many_hash_entries * sizeof(int32_t);
   return hash_table_size;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

llvm::Value * OverlapsJoinHashTable::codegenKey ( const CompilationOptions & co )

protected

Definition at line 1469 of file OverlapsJoinHashTable.cpp.

References AUTOMATIC_IR_METADATA, CodeGenerator::castArrayPointer(), CHECK, CHECK_EQ, CodeGenerator::codegen(), executor_, Catalog_Namespace::get_metadata_for_column(), getKeyComponentCount(), getKeyComponentWidth(), inner_outer_pairs_, inverse_bucket_sizes_for_dimension_, kPOINT, kTINYINT, LL_BUILDER, LL_CONTEXT, LL_INT, CodeGenerator::posArg(), and UNREACHABLE.

Referenced by codegenMatchingSet().

                                                                          {
   AUTOMATIC_IR_METADATA(executor_->cgen_state_.get());
   const auto key_component_width = getKeyComponentWidth();
   CHECK(key_component_width == 4 || key_component_width == 8);
   const auto key_size_lv = LL_INT(getKeyComponentCount() * key_component_width);
   llvm::Value* key_buff_lv{nullptr};
   switch (key_component_width) {
     case 4:
       key_buff_lv =
           LL_BUILDER.CreateAlloca(llvm::Type::getInt32Ty(LL_CONTEXT), key_size_lv);
       break;
     case 8:
       key_buff_lv =
           LL_BUILDER.CreateAlloca(llvm::Type::getInt64Ty(LL_CONTEXT), key_size_lv);
       break;
     default:
       CHECK(false);
   }
 
   const auto& inner_outer_pair = inner_outer_pairs_[0];
   const auto outer_geo = inner_outer_pair.second;
   const auto outer_geo_ti = outer_geo->get_type_info();
 
   llvm::Value* arr_ptr = nullptr;
   CodeGenerator code_generator(executor_);
   CHECK_EQ(inverse_bucket_sizes_for_dimension_.size(), static_cast<size_t>(2));
 
   if (outer_geo_ti.is_geometry()) {
     // TODO(adb): for points we will use the coords array, but for other geometries we
     // will need to use the bounding box. For now only support points.
     CHECK_EQ(outer_geo_ti.get_type(), kPOINT);
 
     if (const auto outer_geo_col = dynamic_cast<const Analyzer::ColumnVar*>(outer_geo)) {
       const auto outer_geo_col_lvs = code_generator.codegen(outer_geo_col, true, co);
       CHECK_EQ(outer_geo_col_lvs.size(), size_t(1));
       auto column_key = outer_geo_col->getColumnKey();
       column_key.column_id = column_key.column_id + 1;
       const auto coords_cd = Catalog_Namespace::get_metadata_for_column(column_key);
       CHECK(coords_cd);
 
       const auto array_ptr = executor_->cgen_state_->emitExternalCall(
           "array_buff",
           llvm::Type::getInt8PtrTy(executor_->cgen_state_->context_),
           {outer_geo_col_lvs.front(), code_generator.posArg(outer_geo_col)});
       CHECK(coords_cd->columnType.get_elem_type().get_type() == kTINYINT)
           << "Only TINYINT coordinates columns are supported in geo overlaps hash "
              "join.";
       arr_ptr = code_generator.castArrayPointer(array_ptr,
                                                 coords_cd->columnType.get_elem_type());
     } else if (const auto outer_geo_function_operator =
                    dynamic_cast<const Analyzer::GeoOperator*>(outer_geo)) {
       // Process points dynamically constructed by geo function operators
       const auto outer_geo_function_operator_lvs =
           code_generator.codegen(outer_geo_function_operator, true, co);
       CHECK_EQ(outer_geo_function_operator_lvs.size(), size_t(2));
       arr_ptr = outer_geo_function_operator_lvs.front();
     } else if (const auto outer_geo_expr =
                    dynamic_cast<const Analyzer::GeoExpr*>(outer_geo)) {
       UNREACHABLE() << outer_geo_expr->toString();
     }
   } else if (outer_geo_ti.is_fixlen_array()) {
     // Process dynamically constructed points
     const auto outer_geo_cast_coord_array =
         dynamic_cast<const Analyzer::UOper*>(outer_geo);
     CHECK_EQ(outer_geo_cast_coord_array->get_optype(), kCAST);
     const auto outer_geo_coord_array = dynamic_cast<const Analyzer::ArrayExpr*>(
         outer_geo_cast_coord_array->get_operand());
     CHECK(outer_geo_coord_array);
     CHECK(outer_geo_coord_array->isLocalAlloc());
     CHECK_EQ(outer_geo_coord_array->getElementCount(), 2);
     auto elem_size = (outer_geo_ti.get_compression() == kENCODING_GEOINT)
                          ? sizeof(int32_t)
                          : sizeof(double);
     CHECK_EQ(outer_geo_ti.get_size(), int(2 * elem_size));
     const auto outer_geo_constructed_lvs = code_generator.codegen(outer_geo, true, co);
     // CHECK_EQ(outer_geo_constructed_lvs.size(), size_t(2));     // Pointer and size
     const auto array_ptr = outer_geo_constructed_lvs.front();  // Just need the pointer
     arr_ptr = LL_BUILDER.CreateGEP(
         array_ptr->getType()->getScalarType()->getPointerElementType(),
         array_ptr,
         LL_INT(0));
     arr_ptr = code_generator.castArrayPointer(array_ptr, SQLTypeInfo(kTINYINT, true));
   }
   if (!arr_ptr) {
     LOG(FATAL) << "Overlaps key currently only supported for geospatial columns and "
                   "constructed points.";
   }
 
   for (size_t i = 0; i < 2; i++) {
     const auto key_comp_dest_lv = LL_BUILDER.CreateGEP(
         key_buff_lv->getType()->getScalarType()->getPointerElementType(),
         key_buff_lv,
         LL_INT(i));
 
     // Note that get_bucket_key_for_range_compressed will need to be specialized for
     // future compression schemes
     auto bucket_key =
         outer_geo_ti.get_compression() == kENCODING_GEOINT
             ? executor_->cgen_state_->emitExternalCall(
                   "get_bucket_key_for_range_compressed",
                   get_int_type(64, LL_CONTEXT),
                   {arr_ptr, LL_INT(i), LL_FP(inverse_bucket_sizes_for_dimension_[i])})
             : executor_->cgen_state_->emitExternalCall(
                   "get_bucket_key_for_range_double",
                   get_int_type(64, LL_CONTEXT),
                   {arr_ptr, LL_INT(i), LL_FP(inverse_bucket_sizes_for_dimension_[i])});
     const auto col_lv = LL_BUILDER.CreateSExt(
         bucket_key, get_int_type(key_component_width * 8, LL_CONTEXT));
     LL_BUILDER.CreateStore(col_lv, key_comp_dest_lv);
   }
   return key_buff_lv;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

std::vector< llvm::Value * > OverlapsJoinHashTable::codegenManyKey ( const CompilationOptions & co )

protected

Definition at line 1582 of file OverlapsJoinHashTable.cpp.

References AUTOMATIC_IR_METADATA, CHECK, CHECK_EQ, CodeGenerator::codegen(), executor_, Catalog_Namespace::get_metadata_for_column(), HashJoin::getHashTableForDevice(), getHashType(), getKeyComponentWidth(), inner_outer_pairs_, ManyToMany, CodeGenerator::posArg(), and VLOG.

Referenced by codegenMatchingSet().

                                   {
   AUTOMATIC_IR_METADATA(executor_->cgen_state_.get());
   const auto key_component_width = getKeyComponentWidth();
   CHECK(key_component_width == 4 || key_component_width == 8);
   auto hash_table = getHashTableForDevice(size_t(0));
   CHECK(hash_table);
   CHECK(getHashType() == HashType::ManyToMany);
 
   VLOG(1) << "Performing codgen for ManyToMany";
   const auto& inner_outer_pair = inner_outer_pairs_[0];
   const auto outer_col = inner_outer_pair.second;
 
   CodeGenerator code_generator(executor_);
   const auto col_lvs = code_generator.codegen(outer_col, true, co);
   CHECK_EQ(col_lvs.size(), size_t(1));
 
   const auto outer_col_var = dynamic_cast<const Analyzer::ColumnVar*>(outer_col);
   CHECK(outer_col_var);
   const auto coords_cd =
       Catalog_Namespace::get_metadata_for_column(outer_col_var->getColumnKey());
   CHECK(coords_cd);
 
   const auto array_ptr = executor_->cgen_state_->emitExternalCall(
       "array_buff",
       llvm::Type::getInt8PtrTy(executor_->cgen_state_->context_),
       {col_lvs.front(), code_generator.posArg(outer_col)});
 
   // TODO(jclay): this seems to cast to double, and causes the GPU build to fail.
   // const auto arr_ptr =
   //     code_generator.castArrayPointer(array_ptr,
   //     coords_cd->columnType.get_elem_type());
   array_ptr->setName("array_ptr");
 
   auto num_keys_lv = executor_->cgen_state_->emitExternalCall(
       "get_num_buckets_for_bounds",
       get_int_type(32, LL_CONTEXT),
       {array_ptr,
        LL_INT(0),
        LL_FP(inverse_bucket_sizes_for_dimension_[0]),
        LL_FP(inverse_bucket_sizes_for_dimension_[1])});
   num_keys_lv->setName("num_keys_lv");
 
   return {num_keys_lv, array_ptr};
 }

Here is the call graph for this function:

Here is the caller graph for this function:

HashJoinMatchingSet OverlapsJoinHashTable::codegenMatchingSet	(	const CompilationOptions &	co,
		const size_t	index
	)

overrideprotectedvirtual

Implements HashJoin.

Definition at line 1628 of file OverlapsJoinHashTable.cpp.

References AUTOMATIC_IR_METADATA, CHECK, HashJoin::codegenHashTableLoad(), codegenKey(), codegenManyKey(), HashJoin::codegenMatchingSet(), executor_, get_int_array_type(), get_int_type(), getComponentBufferSize(), getEntryCount(), getHashType(), getKeyComponentCount(), getKeyComponentWidth(), inverse_bucket_sizes_for_dimension_, LL_BUILDER, LL_CONTEXT, LL_FP, LL_INT, ManyToMany, offsetBufferOff(), OneToMany, to_string(), UNREACHABLE, and VLOG.

                         {
   AUTOMATIC_IR_METADATA(executor_->cgen_state_.get());
   if (getHashType() == HashType::ManyToMany) {
     VLOG(1) << "Building codegenMatchingSet for ManyToMany";
     const auto key_component_width = getKeyComponentWidth();
     CHECK(key_component_width == 4 || key_component_width == 8);
     auto many_to_many_args = codegenManyKey(co);
     auto hash_ptr = HashJoin::codegenHashTableLoad(index, executor_);
     const auto composite_dict_ptr_type =
         llvm::Type::getIntNPtrTy(LL_CONTEXT, key_component_width * 8);
     const auto composite_key_dict =
         hash_ptr->getType()->isPointerTy()
             ? LL_BUILDER.CreatePointerCast(hash_ptr, composite_dict_ptr_type)
             : LL_BUILDER.CreateIntToPtr(hash_ptr, composite_dict_ptr_type);
     const auto key_component_count = getKeyComponentCount();
 
     auto one_to_many_ptr = hash_ptr;
 
     if (one_to_many_ptr->getType()->isPointerTy()) {
       one_to_many_ptr =
           LL_BUILDER.CreatePtrToInt(hash_ptr, llvm::Type::getInt64Ty(LL_CONTEXT));
     } else {
       CHECK(one_to_many_ptr->getType()->isIntegerTy(64));
     }
 
     const auto composite_key_dict_size = offsetBufferOff();
     one_to_many_ptr =
         LL_BUILDER.CreateAdd(one_to_many_ptr, LL_INT(composite_key_dict_size));
 
     // NOTE(jclay): A fixed array of size 200 is allocated on the stack.
     // this is likely the maximum value we can do that is safe to use across
     // all supported GPU architectures.
     const int max_array_size = 200;
     const auto arr_type = get_int_array_type(32, max_array_size, LL_CONTEXT);
     const auto out_arr_lv = LL_BUILDER.CreateAlloca(arr_type);
     out_arr_lv->setName("out_arr");
 
     const auto casted_out_arr_lv =
         LL_BUILDER.CreatePointerCast(out_arr_lv, arr_type->getPointerTo());
 
     const auto element_ptr = LL_BUILDER.CreateGEP(arr_type, casted_out_arr_lv, LL_INT(0));
 
     auto rowid_ptr_i32 =
         LL_BUILDER.CreatePointerCast(element_ptr, llvm::Type::getInt32PtrTy(LL_CONTEXT));
 
     const auto candidate_count_lv = executor_->cgen_state_->emitExternalCall(
         "get_candidate_rows",
         llvm::Type::getInt64Ty(LL_CONTEXT),
         {
             rowid_ptr_i32,
             LL_INT(max_array_size),
             many_to_many_args[1],
             LL_INT(0),
             LL_FP(inverse_bucket_sizes_for_dimension_[0]),
             LL_FP(inverse_bucket_sizes_for_dimension_[1]),
             many_to_many_args[0],
             LL_INT(key_component_count),               // key_component_count
             composite_key_dict,                        // ptr to hash table
             LL_INT(getEntryCount()),                   // entry_count
             LL_INT(composite_key_dict_size),           // offset_buffer_ptr_offset
             LL_INT(getEntryCount() * sizeof(int32_t))  // sub_buff_size
         });
 
     const auto slot_lv = LL_INT(int64_t(0));
 
     return {rowid_ptr_i32, candidate_count_lv, slot_lv};
   } else {
     VLOG(1) << "Building codegenMatchingSet for Baseline";
     // TODO: duplicated w/ BaselineJoinHashTable -- push into the hash table builder?
     const auto key_component_width = getKeyComponentWidth();
     CHECK(key_component_width == 4 || key_component_width == 8);
     auto key_buff_lv = codegenKey(co);
     CHECK(getHashType() == HashType::OneToMany);
     auto hash_ptr = HashJoin::codegenHashTableLoad(index, executor_);
     const auto composite_dict_ptr_type =
         llvm::Type::getIntNPtrTy(LL_CONTEXT, key_component_width * 8);
     const auto composite_key_dict =
         hash_ptr->getType()->isPointerTy()
             ? LL_BUILDER.CreatePointerCast(hash_ptr, composite_dict_ptr_type)
             : LL_BUILDER.CreateIntToPtr(hash_ptr, composite_dict_ptr_type);
     const auto key_component_count = getKeyComponentCount();
     const auto key = executor_->cgen_state_->emitExternalCall(
         "get_composite_key_index_" + std::to_string(key_component_width * 8),
         get_int_type(64, LL_CONTEXT),
         {key_buff_lv,
          LL_INT(key_component_count),
          composite_key_dict,
          LL_INT(getEntryCount())});
     auto one_to_many_ptr = hash_ptr;
     if (one_to_many_ptr->getType()->isPointerTy()) {
       one_to_many_ptr =
           LL_BUILDER.CreatePtrToInt(hash_ptr, llvm::Type::getInt64Ty(LL_CONTEXT));
     } else {
       CHECK(one_to_many_ptr->getType()->isIntegerTy(64));
     }
     const auto composite_key_dict_size = offsetBufferOff();
     one_to_many_ptr =
         LL_BUILDER.CreateAdd(one_to_many_ptr, LL_INT(composite_key_dict_size));
     return HashJoin::codegenMatchingSet(
         std::vector<llvm::Value*>{
             one_to_many_ptr, key, LL_INT(int64_t(0)), LL_INT(getEntryCount() - 1)},
         false,
         false,
         false,
         getComponentBufferSize(),
         executor_);
   }
   UNREACHABLE();
   return HashJoinMatchingSet{};
 }

Here is the call graph for this function:

llvm::Value* OverlapsJoinHashTable::codegenSlot	(	const CompilationOptions &	,
		const size_t
	)

inlineoverrideprotectedvirtual

Implements HashJoin.

Definition at line 209 of file OverlapsJoinHashTable.h.

References UNREACHABLE.

                                                                            {
     UNREACHABLE();  // not applicable for overlaps join
     return nullptr;
   }

std::pair< size_t, size_t > OverlapsJoinHashTable::computeHashTableCounts	(	const size_t	shard_count,
		const std::vector< double > &	inverse_bucket_sizes_for_dimension,
		std::vector< ColumnsForDevice > &	columns_per_device,
		const size_t	chosen_max_hashtable_size,
		const double	chosen_bucket_threshold
	)

protectedvirtual

Definition at line 960 of file OverlapsJoinHashTable.cpp.

References approximateTupleCount(), CHECK, device_count_, get_entries_per_device(), and memory_level_.

Referenced by reifyWithLayout().

                                           {
   CHECK(!inverse_bucket_sizes_for_dimension.empty());
   const auto [tuple_count, emitted_keys_count] =
       approximateTupleCount(inverse_bucket_sizes_for_dimension,
                             columns_per_device,
                             chosen_max_hashtable_size,
                             chosen_bucket_threshold);
   const auto entry_count = 2 * std::max(tuple_count, size_t(1));
 
   return std::make_pair(
       get_entries_per_device(entry_count, shard_count, device_count_, memory_level_),
       emitted_keys_count);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

size_t OverlapsJoinHashTable::countBufferOff ( ) const

inlineoverrideprotectedvirtualnoexcept

Implements HashJoin.

Definition at line 267 of file OverlapsJoinHashTable.h.

References getComponentBufferSize(), getHashType(), getKeyBufferSize(), HashJoin::layoutRequiresAdditionalBuffers(), and offsetBufferOff().

Referenced by payloadBufferOff(), toSet(), and toString().

                                                   {
     if (layoutRequiresAdditionalBuffers(getHashType())) {
       return offsetBufferOff() + getComponentBufferSize();
     } else {
       return getKeyBufferSize();
     }
   }

Here is the call graph for this function:

Here is the caller graph for this function:

ColumnsForDevice OverlapsJoinHashTable::fetchColumnsForDevice	(	const std::vector< Fragmenter_Namespace::FragmentInfo > &	fragments,
		const int	device_id,
		DeviceAllocator *	dev_buff_owner
	)

protected

Definition at line 922 of file OverlapsJoinHashTable.cpp.

References CHECK, column_cache_, executor_, HashJoin::fetchJoinColumn(), get_column_descriptor_maybe(), get_join_column_type_kind(), getEffectiveMemoryLevel(), and inner_outer_pairs_.

Referenced by RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

                                      {
   const auto effective_memory_level = getEffectiveMemoryLevel(inner_outer_pairs_);
 
   std::vector<JoinColumn> join_columns;
   std::vector<std::shared_ptr<Chunk_NS::Chunk>> chunks_owner;
   std::vector<JoinColumnTypeInfo> join_column_types;
   std::vector<std::shared_ptr<void>> malloc_owner;
   for (const auto& inner_outer_pair : inner_outer_pairs_) {
     const auto inner_col = inner_outer_pair.first;
     const auto inner_cd = get_column_descriptor_maybe(inner_col->getColumnKey());
     if (inner_cd && inner_cd->isVirtualCol) {
       throw FailedToJoinOnVirtualColumn();
     }
     join_columns.emplace_back(fetchJoinColumn(inner_col,
                                               fragments,
                                               effective_memory_level,
                                               device_id,
                                               chunks_owner,
                                               dev_buff_owner,
                                               malloc_owner,
                                               executor_,
                                               &column_cache_));
     const auto& ti = inner_col->get_type_info();
     join_column_types.emplace_back(JoinColumnTypeInfo{static_cast<size_t>(ti.get_size()),
                                                       0,
                                                       0,
                                                       inline_int_null_value<int64_t>(),
                                                       false,
                                                       0,
                                                       get_join_column_type_kind(ti)});
     CHECK(ti.is_array()) << "Overlaps join currently only supported for arrays.";
   }
   return {join_columns, join_column_types, chunks_owner, {}, malloc_owner};
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void OverlapsJoinHashTable::generateCacheKey	(	const size_t	max_hashtable_size,
		const double	bucket_threshold,
		const std::vector< double > &	bucket_sizes,
		std::vector< std::vector< Fragmenter_Namespace::FragmentInfo >> &	fragments_per_device,
		int	device_count
	)

inlineprotected

Definition at line 339 of file OverlapsJoinHashTable.h.

References HashJoin::collectFragmentIds(), hash_table_cache_, hashtable_cache_key_, and table_keys_.

Referenced by RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

                         {
     for (int device_id = 0; device_id < device_count; ++device_id) {
       auto hash_val = boost::hash_value(hashtable_cache_key_[device_id]);
       boost::hash_combine(hash_val, max_hashtable_size);
       boost::hash_combine(hash_val, bucket_threshold);
       boost::hash_combine(hash_val, bucket_sizes);
       boost::hash_combine(hash_val,
                           HashJoin::collectFragmentIds(fragments_per_device[device_id]));
       hashtable_cache_key_[device_id] = hash_val;
       hash_table_cache_->addQueryPlanDagForTableKeys(hashtable_cache_key_[device_id],
                                                      table_keys_);
     }
   }

Here is the call graph for this function:

Here is the caller graph for this function:

QueryPlanHash OverlapsJoinHashTable::getAlternativeCacheKey ( AlternativeCacheKeyForOverlapsHashJoin & info )

inlineprotected

Definition at line 320 of file OverlapsJoinHashTable.h.

References OverlapsJoinHashTable::AlternativeCacheKeyForOverlapsHashJoin::bucket_threshold, OverlapsJoinHashTable::AlternativeCacheKeyForOverlapsHashJoin::chunk_key_hash, OverlapsJoinHashTable::AlternativeCacheKeyForOverlapsHashJoin::inner_outer_pairs, OverlapsJoinHashTable::AlternativeCacheKeyForOverlapsHashJoin::inverse_bucket_sizes, OverlapsJoinHashTable::AlternativeCacheKeyForOverlapsHashJoin::max_hashtable_size, OverlapsJoinHashTable::AlternativeCacheKeyForOverlapsHashJoin::num_elements, and OverlapsJoinHashTable::AlternativeCacheKeyForOverlapsHashJoin::optype.

Referenced by RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

                                                                                      {
     auto hash = info.chunk_key_hash;
     for (InnerOuter inner_outer : info.inner_outer_pairs) {
       auto inner_col = inner_outer.first;
       auto rhs_col_var = dynamic_cast<const Analyzer::ColumnVar*>(inner_outer.second);
       auto outer_col = rhs_col_var ? rhs_col_var : inner_col;
       boost::hash_combine(hash, inner_col->toString());
       if (inner_col->get_type_info().is_string()) {
         boost::hash_combine(hash, outer_col->toString());
       }
     }
     boost::hash_combine(hash, info.num_elements);
     boost::hash_combine(hash, info.optype);
     boost::hash_combine(hash, info.max_hashtable_size);
     boost::hash_combine(hash, info.bucket_threshold);
     boost::hash_combine(hash, info.inverse_bucket_sizes);
     return hash;
   }

Here is the caller graph for this function:

std::optional< std::pair< size_t, size_t > > OverlapsJoinHashTable::getApproximateTupleCountFromCache	(	QueryPlanHash	key,
		CacheItemType	item_type,
		DeviceIdentifier	device_identifier
	)

protected

Definition at line 1858 of file OverlapsJoinHashTable.cpp.

References CHECK, getOverlapsHashTableMetaInfo(), hash_table_cache_, and HashtableCacheMetaInfo::overlaps_meta_info.

Referenced by approximateTupleCount().

                                         {
   CHECK(hash_table_cache_);
   HashtableCacheMetaInfo metaInfo;
   metaInfo.overlaps_meta_info = getOverlapsHashTableMetaInfo();
   auto cached_hashtable =
       hash_table_cache_->getItemFromCache(key, item_type, device_identifier, metaInfo);
   if (cached_hashtable) {
     return std::make_pair(cached_hashtable->getEntryCount() / 2,
                           cached_hashtable->getEmittedKeysCount());
   }
   return std::nullopt;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

QueryPlanHash OverlapsJoinHashTable::getCacheKey ( int device_id ) const

inlineprotected

Definition at line 358 of file OverlapsJoinHashTable.h.

References hashtable_cache_key_.

                                                  {
     return hashtable_cache_key_[device_id];
   }

size_t OverlapsJoinHashTable::getComponentBufferSize ( ) const

inlineoverrideprotectedvirtualnoexcept

Implements HashJoin.

Definition at line 228 of file OverlapsJoinHashTable.h.

References CHECK, and HashJoin::hash_tables_for_device_.

Referenced by codegenMatchingSet(), RangeJoinHashTable::codegenMatchingSetWithOffset(), countBufferOff(), and payloadBufferOff().

                                                           {
     CHECK(!hash_tables_for_device_.empty());
     auto hash_table = hash_tables_for_device_.front();
     CHECK(hash_table);
     return hash_table->getEntryCount() * sizeof(int32_t);
   }

Here is the caller graph for this function:

int OverlapsJoinHashTable::getDeviceCount ( ) const

inlineoverrideprotectedvirtualnoexcept

Implements HashJoin.

Definition at line 170 of file OverlapsJoinHashTable.h.

References device_count_.

170 { return device_count_; };

OverlapsJoinHashTable::device_count_

const int device_count_

Definition: OverlapsJoinHashTable.h:385

Data_Namespace::MemoryLevel OverlapsJoinHashTable::getEffectiveMemoryLevel ( const std::vector< InnerOuter > & inner_outer_pairs ) const

protected

Definition at line 1819 of file OverlapsJoinHashTable.cpp.

References Data_Namespace::CPU_LEVEL, executor_, Data_Namespace::GPU_LEVEL, RegisteredQueryHint::isHintRegistered(), kOverlapsAllowGpuBuild, memory_level_, RegisteredQueryHint::overlaps_allow_gpu_build, and query_hints_.

Referenced by approximateTupleCount(), fetchColumnsForDevice(), reifyForDevice(), RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

                                                           {
   if (query_hints_.isHintRegistered(QueryHint::kOverlapsAllowGpuBuild) &&
       query_hints_.overlaps_allow_gpu_build &&
       this->executor_->getDataMgr()->gpusPresent() &&
       memory_level_ == Data_Namespace::MemoryLevel::GPU_LEVEL) {
     return Data_Namespace::MemoryLevel::GPU_LEVEL;
   }
   // otherwise, try to build on CPU
   return Data_Namespace::MemoryLevel::CPU_LEVEL;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

size_t OverlapsJoinHashTable::getEmittedKeysCount ( ) const

inlineprotected

Definition at line 222 of file OverlapsJoinHashTable.h.

References CHECK, and HashJoin::getHashTableForDevice().

                                      {
     auto hash_table = getHashTableForDevice(0);
     CHECK(hash_table);
     return hash_table->getEmittedKeysCount();
   }

Here is the call graph for this function:

size_t OverlapsJoinHashTable::getEntryCount ( ) const

inlineprotected

Definition at line 216 of file OverlapsJoinHashTable.h.

References CHECK, and HashJoin::getHashTableForDevice().

Referenced by codegenMatchingSet(), RangeJoinHashTable::codegenMatchingSetWithOffset(), and getKeyBufferSize().

                                {
     auto hash_table = getHashTableForDevice(0);
     CHECK(hash_table);
     return hash_table->getEntryCount();
   }

Here is the call graph for this function:

Here is the caller graph for this function:

std::string OverlapsJoinHashTable::getHashJoinType ( ) const

inlinefinalprotectedvirtual

Implements HashJoin.

Definition at line 283 of file OverlapsJoinHashTable.h.

283 { return "Overlaps"; }

static HashtableRecycler* OverlapsJoinHashTable::getHashTableCache ( )

inlinestatic

Definition at line 92 of file OverlapsJoinHashTable.h.

References CHECK, and hash_table_cache_.

Referenced by QueryRunner::QueryRunner::getCachedHashtableWithoutCacheKey(), QueryRunner::QueryRunner::getCacheItemMetric(), and QueryRunner::QueryRunner::getNumberOfCachedItem().

                                                 {
     CHECK(hash_table_cache_);
     return hash_table_cache_.get();
   }

Here is the caller graph for this function:

HashType OverlapsJoinHashTable::getHashType ( ) const

inlineoverrideprotectedvirtualnoexcept

Implements HashJoin.

Reimplemented in RangeJoinHashTable.

Definition at line 157 of file OverlapsJoinHashTable.h.

References CHECK, HashJoin::getHashTableForDevice(), and layout_override_.

Referenced by codegenManyKey(), codegenMatchingSet(), countBufferOff(), getKeyBufferSize(), payloadBufferOff(), toSet(), and toString().

                                                  {
     if (layout_override_) {
       return *layout_override_;
     }
     auto hash_table = getHashTableForDevice(0);
     CHECK(hash_table);
     return hash_table->getLayout();
   }

Here is the call graph for this function:

Here is the caller graph for this function:

const std::vector<InnerOuter>& OverlapsJoinHashTable::getInnerOuterPairs ( ) const

inlineprotected

Definition at line 362 of file OverlapsJoinHashTable.h.

References inner_outer_pairs_.

Referenced by RangeJoinHashTable::isProbeCompressed().

362 { return inner_outer_pairs_; }

OverlapsJoinHashTable::inner_outer_pairs_

std::vector< InnerOuter > inner_outer_pairs_

Definition: OverlapsJoinHashTable.h:384

Here is the caller graph for this function:

shared::TableKey OverlapsJoinHashTable::getInnerTableId ( ) const

overrideprotectedvirtualnoexcept

Implements HashJoin.

Definition at line 1831 of file OverlapsJoinHashTable.cpp.

References CHECK, HashJoin::getInnerTableId(), and inner_outer_pairs_.

Referenced by RangeJoinHashTable::reifyWithLayout().

                                                                      {
   try {
     return HashJoin::getInnerTableId(inner_outer_pairs_);
   } catch (...) {
     CHECK(false);
   }
   return {};
 }

Here is the call graph for this function:

Here is the caller graph for this function:

int OverlapsJoinHashTable::getInnerTableRteIdx ( ) const

inlineoverrideprotectedvirtualnoexcept

Implements HashJoin.

Definition at line 248 of file OverlapsJoinHashTable.h.

References CHECK, and inner_outer_pairs_.

                                                     {
     CHECK(!inner_outer_pairs_.empty());
     const auto first_inner_col = inner_outer_pairs_.front().first;
     return first_inner_col->get_rte_idx();
   }

std::shared_ptr< OverlapsJoinHashTable > OverlapsJoinHashTable::getInstance	(	const std::shared_ptr< Analyzer::BinOper >	condition,
		const std::vector< InputTableInfo > &	query_infos,
		const Data_Namespace::MemoryLevel	memory_level,
		const JoinType	join_type,
		const int	device_count,
		ColumnCacheMap &	column_cache,
		Executor *	executor,
		const HashTableBuildDagMap &	hashtable_build_dag_map,
		const RegisteredQueryHint &	query_hint,
		const TableIdToNodeMap &	table_id_to_node_map
	)

static

Make hash table from an in-flight SQL query's parse tree etc.

Definition at line 37 of file OverlapsJoinHashTable.cpp.

References CHECK, CHECK_EQ, get_inner_query_info(), HashJoin::getHashTypeString(), HashJoin::getInnerTableId(), RangeJoinHashTable::getInstance(), Fragmenter_Namespace::TableInfo::getNumTuplesUpperBound(), InputTableInfo::info, ManyToMany, HashJoin::normalizeColumnPairs(), OneToMany, VLOG, and VLOGGING.

Referenced by HashJoin::getInstance().

                                                   {
   decltype(std::chrono::steady_clock::now()) ts1, ts2;
 
   std::vector<InnerOuter> inner_outer_pairs;
 
   if (const auto range_expr =
           dynamic_cast<const Analyzer::RangeOper*>(condition->get_right_operand())) {
     return RangeJoinHashTable::getInstance(condition,
                                            range_expr,
                                            query_infos,
                                            memory_level,
                                            join_type,
                                            device_count,
                                            column_cache,
                                            executor,
                                            hashtable_build_dag_map,
                                            query_hints,
                                            table_id_to_node_map);
   } else {
     inner_outer_pairs =
         HashJoin::normalizeColumnPairs(condition.get(), executor->getTemporaryTables())
             .first;
   }
   CHECK(!inner_outer_pairs.empty());
 
   const auto getHashTableType =
       [](const std::shared_ptr<Analyzer::BinOper> condition,
          const std::vector<InnerOuter>& inner_outer_pairs) -> HashType {
     HashType layout = HashType::OneToMany;
     if (condition->is_overlaps_oper()) {
       CHECK_EQ(inner_outer_pairs.size(), size_t(1));
       if (inner_outer_pairs[0].first->get_type_info().is_array() &&
           inner_outer_pairs[0].second->get_type_info().is_array() &&
           // Bounds vs constructed points, former should yield ManyToMany
           inner_outer_pairs[0].second->get_type_info().get_size() == 32) {
         layout = HashType::ManyToMany;
       }
     }
     return layout;
   };
 
   const auto layout = getHashTableType(condition, inner_outer_pairs);
 
   if (VLOGGING(1)) {
     VLOG(1) << "Building geo hash table " << getHashTypeString(layout)
             << " for qual: " << condition->toString();
     ts1 = std::chrono::steady_clock::now();
   }
 
   const auto qi_0 = query_infos[0].info.getNumTuplesUpperBound();
   const auto qi_1 = query_infos[1].info.getNumTuplesUpperBound();
 
   VLOG(1) << "table_key = " << query_infos[0].table_key << " has " << qi_0 << " tuples.";
   VLOG(1) << "table_key = " << query_infos[1].table_key << " has " << qi_1 << " tuples.";
 
   const auto& query_info =
       get_inner_query_info(HashJoin::getInnerTableId(inner_outer_pairs), query_infos)
           .info;
   const auto total_entries = 2 * query_info.getNumTuplesUpperBound();
   if (total_entries > static_cast<size_t>(std::numeric_limits<int32_t>::max())) {
     throw TooManyHashEntries();
   }
 
   auto join_hash_table = std::make_shared<OverlapsJoinHashTable>(condition,
                                                                  join_type,
                                                                  query_infos,
                                                                  memory_level,
                                                                  column_cache,
                                                                  executor,
                                                                  inner_outer_pairs,
                                                                  device_count,
                                                                  query_hints,
                                                                  hashtable_build_dag_map,
                                                                  table_id_to_node_map);
   try {
     join_hash_table->reify(layout);
   } catch (const HashJoinFail& e) {
     throw HashJoinFail(std::string("Could not build a 1-to-1 correspondence for columns "
                                    "involved in overlaps join | ") +
                        e.what());
   } catch (const ColumnarConversionNotSupported& e) {
     throw HashJoinFail(std::string("Could not build hash tables for overlaps join | "
                                    "Inner table too big. Attempt manual table reordering "
                                    "or create a single fragment inner table. | ") +
                        e.what());
   } catch (const JoinHashTableTooBig& e) {
     throw e;
   } catch (const std::exception& e) {
     throw HashJoinFail(std::string("Failed to build hash tables for overlaps join | ") +
                        e.what());
   }
   if (VLOGGING(1)) {
     ts2 = std::chrono::steady_clock::now();
     VLOG(1) << "Built geo hash table " << getHashTypeString(layout) << " in "
             << std::chrono::duration_cast<std::chrono::milliseconds>(ts2 - ts1).count()
             << " ms";
   }
   return join_hash_table;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

size_t OverlapsJoinHashTable::getKeyBufferSize ( ) const

inlineprotectednoexcept

Definition at line 254 of file OverlapsJoinHashTable.h.

References CHECK, getEntryCount(), getHashType(), getKeyComponentCount(), getKeyComponentWidth(), and HashJoin::layoutRequiresAdditionalBuffers().

Referenced by countBufferOff(), offsetBufferOff(), and payloadBufferOff().

                                            {
     const auto key_component_width = getKeyComponentWidth();
     CHECK(key_component_width == 4 || key_component_width == 8);
     const auto key_component_count = getKeyComponentCount();
     if (layoutRequiresAdditionalBuffers(getHashType())) {
       return getEntryCount() * key_component_count * key_component_width;
     } else {
       return getEntryCount() * (key_component_count + 1) * key_component_width;
     }
   }

Here is the call graph for this function:

Here is the caller graph for this function:

size_t OverlapsJoinHashTable::getKeyComponentCount ( ) const

protected

Definition at line 1168 of file OverlapsJoinHashTable.cpp.

References CHECK, and inverse_bucket_sizes_for_dimension_.

Referenced by RangeJoinHashTable::codegenKey(), codegenKey(), codegenMatchingSet(), RangeJoinHashTable::codegenMatchingSetWithOffset(), getKeyBufferSize(), RangeJoinHashTable::initHashTableOnCpu(), initHashTableOnCpu(), toSet(), and toString().

                                                          {
   CHECK(!inverse_bucket_sizes_for_dimension_.empty());
   return inverse_bucket_sizes_for_dimension_.size();
 }

Here is the caller graph for this function:

size_t OverlapsJoinHashTable::getKeyComponentWidth ( ) const

protected

Definition at line 1164 of file OverlapsJoinHashTable.cpp.

Referenced by calculateHashTableSize(), RangeJoinHashTable::codegenKey(), codegenKey(), codegenManyKey(), codegenMatchingSet(), RangeJoinHashTable::codegenMatchingSetWithOffset(), getKeyBufferSize(), RangeJoinHashTable::initHashTableOnCpu(), initHashTableOnCpu(), RangeJoinHashTable::reifyForDevice(), reifyForDevice(), toSet(), and toString().

                                                          {
   return 8;
 }

Here is the caller graph for this function:

Data_Namespace::MemoryLevel OverlapsJoinHashTable::getMemoryLevel ( ) const

inlineoverrideprotectedvirtualnoexcept

Implements HashJoin.

Definition at line 166 of file OverlapsJoinHashTable.h.

References memory_level_.

                                                                      {
     return memory_level_;
   }

std::optional<OverlapsHashTableMetaInfo> OverlapsJoinHashTable::getOverlapsHashTableMetaInfo ( )

inlineprotected

Definition at line 306 of file OverlapsJoinHashTable.h.

References hashtable_cache_meta_info_, and HashtableCacheMetaInfo::overlaps_meta_info.

Referenced by getApproximateTupleCountFromCache(), initHashTableOnCpuFromCache(), and putHashTableOnCpuToCache().

                                                                         {
     return hashtable_cache_meta_info_.overlaps_meta_info;
   }

Here is the caller graph for this function:

static OverlapsTuningParamRecycler* OverlapsJoinHashTable::getOverlapsTuningParamCache ( )

inlinestatic

Definition at line 97 of file OverlapsJoinHashTable.h.

References auto_tuner_cache_, and CHECK.

Referenced by QueryRunner::QueryRunner::getNumberOfCachedItem().

                                                                     {
     CHECK(auto_tuner_cache_);
     return auto_tuner_cache_.get();
   }

Here is the caller graph for this function:

const RegisteredQueryHint& OverlapsJoinHashTable::getRegisteredQueryHint ( )

inlineprotected

Definition at line 214 of file OverlapsJoinHashTable.h.

References query_hints_.

214 { return query_hints_; }

OverlapsJoinHashTable::query_hints_

RegisteredQueryHint query_hints_

Definition: OverlapsJoinHashTable.h:386

std::shared_ptr< BaselineHashTable > OverlapsJoinHashTable::initHashTableOnCpu	(	const std::vector< JoinColumn > &	join_columns,
		const std::vector< JoinColumnTypeInfo > &	join_column_types,
		const std::vector< JoinBucketInfo > &	join_bucket_info,
		const HashType	layout,
		const size_t	entry_count,
		const size_t	emitted_keys_count,
		const bool	skip_hashtable_caching
	)

protected

Definition at line 1297 of file OverlapsJoinHashTable.cpp.

References CHECK, composite_key_info_, DataRecyclerUtil::CPU_DEVICE_IDENTIFIER, cpu_hash_table_buff_mutex_, DEBUG_TIMER, getKeyComponentCount(), getKeyComponentWidth(), hashtable_cache_key_, BaselineJoinHashTableBuilder::initHashTableOnCpu(), initHashTableOnCpuFromCache(), join_type_, layout_override_, HashJoin::layoutRequiresAdditionalBuffers(), ManyToMany, OneToMany, OVERLAPS_HT, putHashTableOnCpuToCache(), query_hints_, to_string(), and VLOG.

Referenced by reifyForDevice().

                                        {
   auto timer = DEBUG_TIMER(__func__);
   decltype(std::chrono::steady_clock::now()) ts1, ts2;
   ts1 = std::chrono::steady_clock::now();
   CHECK(!join_columns.empty());
   CHECK(!join_bucket_info.empty());
   std::lock_guard<std::mutex> cpu_hash_table_buff_lock(cpu_hash_table_buff_mutex_);
   if (auto generic_hash_table =
           initHashTableOnCpuFromCache(hashtable_cache_key_.front(),
                                       CacheItemType::OVERLAPS_HT,
                                       DataRecyclerUtil::CPU_DEVICE_IDENTIFIER)) {
     if (auto hash_table =
             std::dynamic_pointer_cast<BaselineHashTable>(generic_hash_table)) {
       VLOG(1) << "Using cached CPU hash table for initialization.";
       // See if a hash table of a different layout was returned.
       // If it was OneToMany, we can reuse it on ManyToMany.
       if (layout == HashType::ManyToMany &&
           hash_table->getLayout() == HashType::OneToMany) {
         // use the cached hash table
         layout_override_ = HashType::ManyToMany;
         return hash_table;
       }
       if (layout == hash_table->getLayout()) {
         return hash_table;
       }
     }
   }
   CHECK(layoutRequiresAdditionalBuffers(layout));
   const auto key_component_count =
       join_bucket_info[0].inverse_bucket_sizes_for_dimension.size();
 
   const auto key_handler =
       OverlapsKeyHandler(key_component_count,
                          &join_columns[0],
                          join_bucket_info[0].inverse_bucket_sizes_for_dimension.data());
   BaselineJoinHashTableBuilder builder;
   const StrProxyTranslationMapsPtrsAndOffsets
       dummy_str_proxy_translation_maps_ptrs_and_offsets;
   const auto err =
       builder.initHashTableOnCpu(&key_handler,
                                  composite_key_info_,
                                  join_columns,
                                  join_column_types,
                                  join_bucket_info,
                                  dummy_str_proxy_translation_maps_ptrs_and_offsets,
                                  entry_count,
                                  emitted_keys_count,
                                  layout,
                                  join_type_,
                                  getKeyComponentWidth(),
                                  getKeyComponentCount(),
                                  query_hints_);
   ts2 = std::chrono::steady_clock::now();
   if (err) {
     throw HashJoinFail(
         std::string("Unrecognized error when initializing CPU overlaps hash table (") +
         std::to_string(err) + std::string(")"));
   }
   std::shared_ptr<BaselineHashTable> hash_table = builder.getHashTable();
   if (skip_hashtable_caching) {
     VLOG(1) << "Skip to cache overlaps join hashtable";
   } else {
     auto hashtable_build_time =
         std::chrono::duration_cast<std::chrono::milliseconds>(ts2 - ts1).count();
     putHashTableOnCpuToCache(hashtable_cache_key_.front(),
                              CacheItemType::OVERLAPS_HT,
                              hash_table,
                              DataRecyclerUtil::CPU_DEVICE_IDENTIFIER,
                              hashtable_build_time);
   }
   return hash_table;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

std::shared_ptr< HashTable > OverlapsJoinHashTable::initHashTableOnCpuFromCache	(	QueryPlanHash	key,
		CacheItemType	item_type,
		DeviceIdentifier	device_identifier
	)

protected

Definition at line 1840 of file OverlapsJoinHashTable.cpp.

References CHECK, DEBUG_TIMER, getOverlapsHashTableMetaInfo(), hash_table_cache_, HashtableCacheMetaInfo::overlaps_meta_info, and VLOG.

Referenced by initHashTableOnCpu(), and RangeJoinHashTable::reifyWithLayout().

                                         {
   auto timer = DEBUG_TIMER(__func__);
   VLOG(1) << "Checking CPU hash table cache.";
   CHECK(hash_table_cache_);
   HashtableCacheMetaInfo meta_info;
   meta_info.overlaps_meta_info = getOverlapsHashTableMetaInfo();
   auto cached_hashtable =
       hash_table_cache_->getItemFromCache(key, item_type, device_identifier, meta_info);
   if (cached_hashtable) {
     return cached_hashtable;
   }
   return nullptr;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void OverlapsJoinHashTable::invalidateCache ( )

inlinestatic

Definition at line 67 of file OverlapsJoinHashTable.h.

References auto_tuner_cache_, CHECK, and hash_table_cache_.

                                 {
     CHECK(auto_tuner_cache_);
     auto_tuner_cache_->clearCache();
 
     CHECK(hash_table_cache_);
     hash_table_cache_->clearCache();
   }

bool OverlapsJoinHashTable::isBitwiseEq ( ) const

overrideprotectedvirtual

Implements HashJoin.

Definition at line 1895 of file OverlapsJoinHashTable.cpp.

References condition_, and kBW_EQ.

                                               {
   return condition_->get_optype() == kBW_EQ;
 }

static void OverlapsJoinHashTable::markCachedItemAsDirty ( size_t table_key )

inlinestatic

Definition at line 75 of file OverlapsJoinHashTable.h.

References auto_tuner_cache_, CHECK, DataRecyclerUtil::CPU_DEVICE_IDENTIFIER, hash_table_cache_, OVERLAPS_AUTO_TUNER_PARAM, and OVERLAPS_HT.

                                                       {
     CHECK(auto_tuner_cache_);
     CHECK(hash_table_cache_);
     auto candidate_table_keys =
         hash_table_cache_->getMappedQueryPlanDagsWithTableKey(table_key);
     if (candidate_table_keys.has_value()) {
       auto_tuner_cache_->markCachedItemAsDirty(table_key,
                                                *candidate_table_keys,
                                                CacheItemType::OVERLAPS_AUTO_TUNER_PARAM,
                                                DataRecyclerUtil::CPU_DEVICE_IDENTIFIER);
       hash_table_cache_->markCachedItemAsDirty(table_key,
                                                *candidate_table_keys,
                                                CacheItemType::OVERLAPS_HT,
                                                DataRecyclerUtil::CPU_DEVICE_IDENTIFIER);
     }
   }

size_t OverlapsJoinHashTable::offsetBufferOff ( ) const

inlineoverrideprotectedvirtualnoexcept

Implements HashJoin.

Definition at line 265 of file OverlapsJoinHashTable.h.

References getKeyBufferSize().

Referenced by codegenMatchingSet(), RangeJoinHashTable::codegenMatchingSetWithOffset(), countBufferOff(), toSet(), and toString().

265 { return getKeyBufferSize(); }

OverlapsJoinHashTable::getKeyBufferSize

size_t getKeyBufferSize() const noexcept

Definition: OverlapsJoinHashTable.h:254

Here is the call graph for this function:

Here is the caller graph for this function:

size_t OverlapsJoinHashTable::payloadBufferOff ( ) const

inlineoverrideprotectedvirtualnoexcept

Implements HashJoin.

Definition at line 275 of file OverlapsJoinHashTable.h.

References countBufferOff(), getComponentBufferSize(), getHashType(), getKeyBufferSize(), and HashJoin::layoutRequiresAdditionalBuffers().

Referenced by toSet(), and toString().

                                                     {
     if (layoutRequiresAdditionalBuffers(getHashType())) {
       return countBufferOff() + getComponentBufferSize();
     } else {
       return getKeyBufferSize();
     }
   }

Here is the call graph for this function:

Here is the caller graph for this function:

void OverlapsJoinHashTable::putHashTableOnCpuToCache	(	QueryPlanHash	key,
		CacheItemType	item_type,
		std::shared_ptr< HashTable >	hashtable_ptr,
		DeviceIdentifier	device_identifier,
		size_t	hashtable_building_time
	)

protected

Definition at line 1874 of file OverlapsJoinHashTable.cpp.

References CHECK, CPU, getOverlapsHashTableMetaInfo(), hash_table_cache_, HashtableCacheMetaInfo::overlaps_meta_info, and query_hints_.

Referenced by RangeJoinHashTable::initHashTableOnCpu(), and initHashTableOnCpu().

                                     {
   CHECK(hash_table_cache_);
   CHECK(hashtable_ptr && !hashtable_ptr->getGpuBuffer());
   HashtableCacheMetaInfo meta_info;
   meta_info.overlaps_meta_info = getOverlapsHashTableMetaInfo();
   meta_info.registered_query_hint = query_hints_;
   hash_table_cache_->putItemToCache(
       key,
       hashtable_ptr,
       item_type,
       device_identifier,
       hashtable_ptr->getHashTableBufferSize(ExecutorDeviceType::CPU),
       hashtable_building_time,
       meta_info);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void OverlapsJoinHashTable::reify ( const HashType preferred_layout )

protected

Definition at line 1173 of file OverlapsJoinHashTable.cpp.

References CHECK, CHECK_EQ, CHECK_LT, composite_key_info_, condition_, DEBUG_TIMER, device_count_, executor_, HashJoin::getCompositeKeyInfo(), inner_outer_pairs_, ManyToMany, OneToMany, reifyWithLayout(), and VLOG.

                                                                  {
   auto timer = DEBUG_TIMER(__func__);
   CHECK_LT(0, device_count_);
   composite_key_info_ = HashJoin::getCompositeKeyInfo(inner_outer_pairs_, executor_);
 
   CHECK(condition_->is_overlaps_oper());
   CHECK_EQ(inner_outer_pairs_.size(), size_t(1));
   HashType layout;
   if (inner_outer_pairs_[0].second->get_type_info().is_fixlen_array() &&
       inner_outer_pairs_[0].second->get_type_info().get_size() == 32) {
     // bounds array
     layout = HashType::ManyToMany;
   } else {
     layout = HashType::OneToMany;
   }
   try {
     reifyWithLayout(layout);
     return;
   } catch (const JoinHashTableTooBig& e) {
     throw e;
   } catch (const std::exception& e) {
     VLOG(1) << "Caught exception while building overlaps baseline hash table: "
             << e.what();
     throw;
   }
 }

Here is the call graph for this function:

void OverlapsJoinHashTable::reifyForDevice	(	const ColumnsForDevice &	columns_for_device,
		const HashType	layout,
		const size_t	entry_count,
		const size_t	emitted_keys_count,
		const bool	skip_hashtable_caching,
		const int	device_id,
		const logger::ThreadLocalIds	parent_thread_local_ids
	)

protected

Definition at line 1240 of file OverlapsJoinHashTable.cpp.

References CHECK, CHECK_EQ, CHECK_LT, Data_Namespace::CPU_LEVEL, DEBUG_TIMER_NEW_THREAD, getEffectiveMemoryLevel(), getKeyComponentWidth(), Data_Namespace::GPU_LEVEL, HashJoin::hash_tables_for_device_, initHashTableOnCpu(), inner_outer_pairs_, ColumnsForDevice::join_buckets, ColumnsForDevice::join_column_types, ColumnsForDevice::join_columns, HashJoin::layoutRequiresAdditionalBuffers(), memory_level_, logger::ThreadLocalIds::setNewThreadId(), logger::ThreadLocalIds::thread_id_, UNREACHABLE, and VLOG.

Referenced by reifyImpl().

                                                         {
   logger::LocalIdsScopeGuard lisg = parent_thread_local_ids.setNewThreadId();
   DEBUG_TIMER_NEW_THREAD(parent_thread_local_ids.thread_id_);
   CHECK_EQ(getKeyComponentWidth(), size_t(8));
   CHECK(layoutRequiresAdditionalBuffers(layout));
   const auto effective_memory_level = getEffectiveMemoryLevel(inner_outer_pairs_);
 
   if (effective_memory_level == Data_Namespace::MemoryLevel::CPU_LEVEL) {
     VLOG(1) << "Building overlaps join hash table on CPU.";
     auto hash_table = initHashTableOnCpu(columns_for_device.join_columns,
                                          columns_for_device.join_column_types,
                                          columns_for_device.join_buckets,
                                          layout,
                                          entry_count,
                                          emitted_keys_count,
                                          skip_hashtable_caching);
     CHECK(hash_table);
 
 #ifdef HAVE_CUDA
     if (memory_level_ == Data_Namespace::MemoryLevel::GPU_LEVEL) {
       auto gpu_hash_table = copyCpuHashTableToGpu(
           hash_table, layout, entry_count, emitted_keys_count, device_id);
       CHECK_LT(static_cast<size_t>(device_id), hash_tables_for_device_.size());
       hash_tables_for_device_[device_id] = std::move(gpu_hash_table);
     } else {
 #else
     CHECK_EQ(Data_Namespace::CPU_LEVEL, effective_memory_level);
 #endif
       CHECK_EQ(hash_tables_for_device_.size(), size_t(1));
       hash_tables_for_device_[0] = hash_table;
 #ifdef HAVE_CUDA
     }
 #endif
   } else {
 #ifdef HAVE_CUDA
     auto hash_table = initHashTableOnGpu(columns_for_device.join_columns,
                                          columns_for_device.join_column_types,
                                          columns_for_device.join_buckets,
                                          layout,
                                          entry_count,
                                          emitted_keys_count,
                                          device_id);
     CHECK_LT(static_cast<size_t>(device_id), hash_tables_for_device_.size());
     hash_tables_for_device_[device_id] = std::move(hash_table);
 #else
     UNREACHABLE();
 #endif
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void OverlapsJoinHashTable::reifyImpl	(	std::vector< ColumnsForDevice > &	columns_per_device,
		const Fragmenter_Namespace::TableInfo &	query_info,
		const HashType	layout,
		const size_t	shard_count,
		const size_t	entry_count,
		const size_t	emitted_keys_count,
		const bool	skip_hashtable_caching,
		const size_t	chosen_max_hashtable_size,
		const double	chosen_bucket_threshold
	)

protectedvirtual

Definition at line 1200 of file OverlapsJoinHashTable.cpp.

References threading_serial::async(), chosen_overlaps_bucket_threshold_, chosen_overlaps_max_table_size_bytes_, device_count_, Fragmenter_Namespace::TableInfo::fragments, inverse_bucket_sizes_for_dimension_, only_shards_for_device(), reifyForDevice(), setOverlapsHashtableMetaInfo(), and logger::thread_local_ids().

Referenced by reifyWithLayout().

                                                                             {
   std::vector<std::future<void>> init_threads;
   chosen_overlaps_bucket_threshold_ = chosen_bucket_threshold;
   chosen_overlaps_max_table_size_bytes_ = chosen_max_hashtable_size;
   setOverlapsHashtableMetaInfo(chosen_overlaps_bucket_threshold_,
                                chosen_overlaps_max_table_size_bytes_,
                                inverse_bucket_sizes_for_dimension_);
 
   for (int device_id = 0; device_id < device_count_; ++device_id) {
     const auto fragments =
         shard_count
             ? only_shards_for_device(query_info.fragments, device_id, device_count_)
             : query_info.fragments;
     init_threads.push_back(std::async(std::launch::async,
                                       &OverlapsJoinHashTable::reifyForDevice,
                                       this,
                                       columns_per_device[device_id],
                                       layout,
                                       entry_count,
                                       emitted_keys_count,
                                       skip_hashtable_caching,
                                       device_id,
                                       logger::thread_local_ids()));
   }
   for (auto& init_thread : init_threads) {
     init_thread.wait();
   }
   for (auto& init_thread : init_threads) {
     init_thread.get();
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void OverlapsJoinHashTable::reifyWithLayout ( const HashType layout )

protectedvirtual

Reimplemented in RangeJoinHashTable.

Definition at line 534 of file OverlapsJoinHashTable.cpp.

References gpu_enabled::accumulate(), auto_tuner_cache_, CompositeKeyInfo::cache_key_chunks, calculateHashTableSize(), CHECK, CHECK_EQ, CHECK_GE, HashJoin::collectFragmentIds(), composite_key_info_, computeHashTableCounts(), condition_, DataRecyclerUtil::CPU_DEVICE_IDENTIFIER, DEBUG_TIMER, device_count_, executor_, fetchColumnsForDevice(), g_overlaps_max_table_size_bytes, g_overlaps_target_entries_per_bin, generateCacheKey(), get_inner_query_info(), getAlternativeCacheKey(), DataRecyclerUtil::getAlternativeTableKeys(), getEffectiveMemoryLevel(), HashtableRecycler::getHashtableAccessPathInfo(), HashJoin::getHashTypeString(), HashJoin::getInnerTableId(), getQueryEngineCudaStreamForDevice(), Data_Namespace::GPU_LEVEL, hash_table_cache_, hashtable_build_dag_map_, hashtable_cache_key_, hashtable_cache_meta_info_, InputTableInfo::info, inner_outer_pairs_, inverse_bucket_sizes_for_dimension_, RegisteredQueryHint::isHintRegistered(), HashtableRecycler::isInvalidHashTableCacheKey(), join_type_, kOverlapsAllowGpuBuild, kOverlapsBucketThreshold, kOverlapsKeysPerBin, kOverlapsMaxSize, kOverlapsNoCache, HashJoin::layoutRequiresAdditionalBuffers(), memory_level_, only_shards_for_device(), RegisteredQueryHint::overlaps_allow_gpu_build, OVERLAPS_AUTO_TUNER_PARAM, RegisteredQueryHint::overlaps_bucket_threshold, OVERLAPS_HT, RegisteredQueryHint::overlaps_keys_per_bin, RegisteredQueryHint::overlaps_max_size, query_hints_, query_infos_, reifyImpl(), setInverseBucketSizeInfo(), setOverlapsHashtableMetaInfo(), shardCount(), table_keys_, and VLOG.

Referenced by reify().

                                                                  {
   auto timer = DEBUG_TIMER(__func__);
   CHECK(layoutRequiresAdditionalBuffers(layout));
   const auto& query_info =
       get_inner_query_info(HashJoin::getInnerTableId(inner_outer_pairs_), query_infos_)
           .info;
   auto [db_id, table_id] = HashJoin::getInnerTableId(inner_outer_pairs_);
   VLOG(1) << "Reify with layout " << getHashTypeString(layout) << "for db_id: " << db_id
           << ", table_id: " << table_id;
   if (query_info.fragments.empty()) {
     return;
   }
 
   auto overlaps_max_table_size_bytes = g_overlaps_max_table_size_bytes;
   std::optional<double> overlaps_threshold_override;
   double overlaps_target_entries_per_bin = g_overlaps_target_entries_per_bin;
   auto skip_hashtable_caching = false;
   if (query_hints_.isHintRegistered(QueryHint::kOverlapsBucketThreshold)) {
     VLOG(1) << "Setting overlaps bucket threshold "
                "\'overlaps_hashjoin_bucket_threshold\' via "
                "query hint: "
             << query_hints_.overlaps_bucket_threshold;
     overlaps_threshold_override = query_hints_.overlaps_bucket_threshold;
   }
   if (query_hints_.isHintRegistered(QueryHint::kOverlapsMaxSize)) {
     std::ostringstream oss;
     oss << "User requests to change a threshold \'overlaps_max_table_size_bytes\' via "
            "query hint";
     if (!overlaps_threshold_override.has_value()) {
       oss << ": " << overlaps_max_table_size_bytes << " -> "
           << query_hints_.overlaps_max_size;
       overlaps_max_table_size_bytes = query_hints_.overlaps_max_size;
     } else {
       oss << ", but is skipped since the query hint also changes the threshold "
              "\'overlaps_hashjoin_bucket_threshold\'";
     }
     VLOG(1) << oss.str();
   }
   if (query_hints_.isHintRegistered(QueryHint::kOverlapsNoCache)) {
     VLOG(1) << "User requests to skip caching overlaps join hashtable and its tuned "
                "parameters for this query";
     skip_hashtable_caching = true;
   }
   if (query_hints_.isHintRegistered(QueryHint::kOverlapsKeysPerBin)) {
     VLOG(1) << "User requests to change a threshold \'overlaps_keys_per_bin\' via query "
                "hint: "
             << overlaps_target_entries_per_bin << " -> "
             << query_hints_.overlaps_keys_per_bin;
     overlaps_target_entries_per_bin = query_hints_.overlaps_keys_per_bin;
   }
 
   auto data_mgr = executor_->getDataMgr();
   // we prioritize CPU when building an overlaps join hashtable, but if we have GPU and
   // user-given hint is given we selectively allow GPU to build it but even if we have GPU
   // but user foces to set CPU as execution device type we should not allow to use GPU for
   // building it
   auto allow_gpu_hashtable_build =
       query_hints_.isHintRegistered(QueryHint::kOverlapsAllowGpuBuild) &&
       query_hints_.overlaps_allow_gpu_build;
   if (allow_gpu_hashtable_build) {
     if (data_mgr->gpusPresent() &&
         memory_level_ == Data_Namespace::MemoryLevel::GPU_LEVEL) {
       VLOG(1) << "A user forces to build GPU hash table for this overlaps join operator";
     } else {
       allow_gpu_hashtable_build = false;
       VLOG(1) << "A user forces to build GPU hash table for this overlaps join operator "
                  "but we "
                  "skip it since either GPU is not presented or CPU execution mode is set";
     }
   }
 
   std::vector<ColumnsForDevice> columns_per_device;
   std::vector<std::unique_ptr<CudaAllocator>> dev_buff_owners;
   if (memory_level_ == Data_Namespace::MemoryLevel::GPU_LEVEL ||
       allow_gpu_hashtable_build) {
     for (int device_id = 0; device_id < device_count_; ++device_id) {
       dev_buff_owners.emplace_back(std::make_unique<CudaAllocator>(
           data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id)));
     }
   }
 
   std::vector<std::vector<Fragmenter_Namespace::FragmentInfo>> fragments_per_device;
   const auto shard_count = shardCount();
   size_t total_num_tuples = 0;
   for (int device_id = 0; device_id < device_count_; ++device_id) {
     fragments_per_device.emplace_back(
         shard_count
             ? only_shards_for_device(query_info.fragments, device_id, device_count_)
             : query_info.fragments);
     const size_t crt_num_tuples =
         std::accumulate(fragments_per_device.back().begin(),
                         fragments_per_device.back().end(),
                         size_t(0),
                         [](const auto& sum, const auto& fragment) {
                           return sum + fragment.getNumTuples();
                         });
     total_num_tuples += crt_num_tuples;
     const auto columns_for_device =
         fetchColumnsForDevice(fragments_per_device.back(),
                               device_id,
                               memory_level_ == Data_Namespace::MemoryLevel::GPU_LEVEL ||
                                       allow_gpu_hashtable_build
                                   ? dev_buff_owners[device_id].get()
                                   : nullptr);
     columns_per_device.push_back(columns_for_device);
   }
 
   // try to extract cache key for hash table and its relevant info
   auto hashtable_access_path_info =
       HashtableRecycler::getHashtableAccessPathInfo(inner_outer_pairs_,
                                                     {},
                                                     condition_->get_optype(),
                                                     join_type_,
                                                     hashtable_build_dag_map_,
                                                     device_count_,
                                                     shard_count,
                                                     fragments_per_device,
                                                     executor_);
   hashtable_cache_key_ = hashtable_access_path_info.hashed_query_plan_dag;
   hashtable_cache_meta_info_ = hashtable_access_path_info.meta_info;
   table_keys_ = hashtable_access_path_info.table_keys;
 
   auto get_inner_table_key = [this]() {
     auto col_var = inner_outer_pairs_.front().first;
     return col_var->getTableKey();
   };
 
   if (table_keys_.empty()) {
     const auto& table_key = get_inner_table_key();
     table_keys_ = DataRecyclerUtil::getAlternativeTableKeys(
         composite_key_info_.cache_key_chunks, table_key);
   }
   CHECK(!table_keys_.empty());
 
   if (overlaps_threshold_override) {
     // compute bucket sizes based on the user provided threshold
     BucketSizeTuner tuner(/*initial_threshold=*/*overlaps_threshold_override,
                           /*step=*/1.0,
                           /*min_threshold=*/0.0,
                           getEffectiveMemoryLevel(inner_outer_pairs_),
                           columns_per_device,
                           inner_outer_pairs_,
                           total_num_tuples,
                           executor_);
     const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
 
     auto [entry_count, emitted_keys_count] =
         computeHashTableCounts(shard_count,
                                inverse_bucket_sizes,
                                columns_per_device,
                                overlaps_max_table_size_bytes,
                                *overlaps_threshold_override);
     setInverseBucketSizeInfo(inverse_bucket_sizes, columns_per_device, device_count_);
     // reifyImpl will check the hash table cache for an appropriate hash table w/ those
     // bucket sizes (or within tolerances) if a hash table exists use it, otherwise build
     // one
     generateCacheKey(overlaps_max_table_size_bytes,
                      *overlaps_threshold_override,
                      inverse_bucket_sizes,
                      fragments_per_device,
                      device_count_);
     reifyImpl(columns_per_device,
               query_info,
               layout,
               shard_count,
               entry_count,
               emitted_keys_count,
               skip_hashtable_caching,
               overlaps_max_table_size_bytes,
               *overlaps_threshold_override);
   } else {
     double overlaps_bucket_threshold = std::numeric_limits<double>::max();
     generateCacheKey(overlaps_max_table_size_bytes,
                      overlaps_bucket_threshold,
                      {},
                      fragments_per_device,
                      device_count_);
     std::vector<size_t> per_device_chunk_key;
     if (HashtableRecycler::isInvalidHashTableCacheKey(hashtable_cache_key_) &&
         get_inner_table_key().table_id > 0) {
       for (int device_id = 0; device_id < device_count_; ++device_id) {
         auto chunk_key_hash = boost::hash_value(composite_key_info_.cache_key_chunks);
         boost::hash_combine(
             chunk_key_hash,
             HashJoin::collectFragmentIds(fragments_per_device[device_id]));
         per_device_chunk_key.push_back(chunk_key_hash);
         AlternativeCacheKeyForOverlapsHashJoin cache_key{
             inner_outer_pairs_,
             columns_per_device.front().join_columns.front().num_elems,
             chunk_key_hash,
             condition_->get_optype(),
             overlaps_max_table_size_bytes,
             overlaps_bucket_threshold,
             {}};
         hashtable_cache_key_[device_id] = getAlternativeCacheKey(cache_key);
         hash_table_cache_->addQueryPlanDagForTableKeys(hashtable_cache_key_[device_id],
                                                        table_keys_);
       }
     }
 
     auto cached_bucket_threshold =
         auto_tuner_cache_->getItemFromCache(hashtable_cache_key_.front(),
                                             CacheItemType::OVERLAPS_AUTO_TUNER_PARAM,
                                             DataRecyclerUtil::CPU_DEVICE_IDENTIFIER);
     if (cached_bucket_threshold) {
       overlaps_bucket_threshold = cached_bucket_threshold->bucket_threshold;
       auto inverse_bucket_sizes = cached_bucket_threshold->bucket_sizes;
       setOverlapsHashtableMetaInfo(
           overlaps_max_table_size_bytes, overlaps_bucket_threshold, inverse_bucket_sizes);
       generateCacheKey(overlaps_max_table_size_bytes,
                        overlaps_bucket_threshold,
                        inverse_bucket_sizes,
                        fragments_per_device,
                        device_count_);
 
       if (auto hash_table =
               hash_table_cache_->getItemFromCache(hashtable_cache_key_[device_count_],
                                                   CacheItemType::OVERLAPS_HT,
                                                   DataRecyclerUtil::CPU_DEVICE_IDENTIFIER,
                                                   std::nullopt)) {
         // if we already have a built hash table, we can skip the scans required for
         // computing bucket size and tuple count
         // reset as the hash table sizes can vary a bit
         setInverseBucketSizeInfo(inverse_bucket_sizes, columns_per_device, device_count_);
         CHECK(hash_table);
 
         VLOG(1) << "Using cached hash table bucket size";
 
         reifyImpl(columns_per_device,
                   query_info,
                   layout,
                   shard_count,
                   hash_table->getEntryCount(),
                   hash_table->getEmittedKeysCount(),
                   skip_hashtable_caching,
                   overlaps_max_table_size_bytes,
                   overlaps_bucket_threshold);
       } else {
         VLOG(1) << "Computing bucket size for cached bucket threshold";
         // compute bucket size using our cached tuner value
         BucketSizeTuner tuner(/*initial_threshold=*/overlaps_bucket_threshold,
                               /*step=*/1.0,
                               /*min_threshold=*/0.0,
                               getEffectiveMemoryLevel(inner_outer_pairs_),
                               columns_per_device,
                               inner_outer_pairs_,
                               total_num_tuples,
                               executor_);
 
         const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
 
         auto [entry_count, emitted_keys_count] =
             computeHashTableCounts(shard_count,
                                    inverse_bucket_sizes,
                                    columns_per_device,
                                    overlaps_max_table_size_bytes,
                                    overlaps_bucket_threshold);
         setInverseBucketSizeInfo(inverse_bucket_sizes, columns_per_device, device_count_);
 
         generateCacheKey(overlaps_max_table_size_bytes,
                          overlaps_bucket_threshold,
                          inverse_bucket_sizes,
                          fragments_per_device,
                          device_count_);
 
         reifyImpl(columns_per_device,
                   query_info,
                   layout,
                   shard_count,
                   entry_count,
                   emitted_keys_count,
                   skip_hashtable_caching,
                   overlaps_max_table_size_bytes,
                   overlaps_bucket_threshold);
       }
     } else {
       // compute bucket size using the auto tuner
       BucketSizeTuner tuner(
           /*initial_threshold=*/overlaps_bucket_threshold,
           /*step=*/2.0,
           /*min_threshold=*/1e-7,
           getEffectiveMemoryLevel(inner_outer_pairs_),
           columns_per_device,
           inner_outer_pairs_,
           total_num_tuples,
           executor_);
 
       VLOG(1) << "Running overlaps join size auto tune with parameters: " << tuner;
 
       // manages the tuning state machine
       TuningState tuning_state(overlaps_max_table_size_bytes,
                                overlaps_target_entries_per_bin);
       while (tuner.tuneOneStep(tuning_state.tuning_direction)) {
         const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
 
         const auto [crt_entry_count, crt_emitted_keys_count] =
             computeHashTableCounts(shard_count,
                                    inverse_bucket_sizes,
                                    columns_per_device,
                                    tuning_state.overlaps_max_table_size_bytes,
                                    tuning_state.chosen_overlaps_threshold);
         const size_t hash_table_size = calculateHashTableSize(
             inverse_bucket_sizes.size(), crt_emitted_keys_count, crt_entry_count);
         HashTableProps crt_props(crt_entry_count,
                                  crt_emitted_keys_count,
                                  hash_table_size,
                                  inverse_bucket_sizes);
         VLOG(1) << "Tuner output: " << tuner << " with properties " << crt_props;
 
         const auto should_continue = tuning_state(crt_props, tuner.getMinBucketSize());
         setInverseBucketSizeInfo(
             tuning_state.crt_props.bucket_sizes, columns_per_device, device_count_);
         if (!should_continue) {
           break;
         }
       }
 
       const auto& crt_props = tuning_state.crt_props;
       // sanity check that the hash table size has not changed. this is a fairly
       // inexpensive check to ensure the above algorithm is consistent
       const size_t hash_table_size =
           calculateHashTableSize(inverse_bucket_sizes_for_dimension_.size(),
                                  crt_props.emitted_keys_count,
                                  crt_props.entry_count);
       CHECK_EQ(crt_props.hash_table_size, hash_table_size);
 
       if (inverse_bucket_sizes_for_dimension_.empty() ||
           hash_table_size > overlaps_max_table_size_bytes) {
         VLOG(1) << "Could not find suitable overlaps join parameters to create hash "
                    "table under max allowed size ("
                 << overlaps_max_table_size_bytes << ") bytes.";
         throw OverlapsHashTableTooBig(overlaps_max_table_size_bytes);
       }
 
       VLOG(1) << "Final tuner output: " << tuner << " with properties " << crt_props;
       CHECK(!inverse_bucket_sizes_for_dimension_.empty());
       VLOG(1) << "Final bucket sizes: ";
       for (size_t dim = 0; dim < inverse_bucket_sizes_for_dimension_.size(); dim++) {
         VLOG(1) << "dim[" << dim
                 << "]: " << 1.0 / inverse_bucket_sizes_for_dimension_[dim];
       }
       CHECK_GE(tuning_state.chosen_overlaps_threshold, double(0));
       generateCacheKey(tuning_state.overlaps_max_table_size_bytes,
                        tuning_state.chosen_overlaps_threshold,
                        {},
                        fragments_per_device,
                        device_count_);
       const auto candidate_auto_tuner_cache_key = hashtable_cache_key_.front();
       if (skip_hashtable_caching) {
         VLOG(1) << "Skip to add tuned parameters to auto tuner";
       } else {
         AutoTunerMetaInfo meta_info{tuning_state.overlaps_max_table_size_bytes,
                                     tuning_state.chosen_overlaps_threshold,
                                     inverse_bucket_sizes_for_dimension_};
         auto_tuner_cache_->putItemToCache(candidate_auto_tuner_cache_key,
                                           meta_info,
                                           CacheItemType::OVERLAPS_AUTO_TUNER_PARAM,
                                           DataRecyclerUtil::CPU_DEVICE_IDENTIFIER,
                                           0,
                                           0);
       }
       overlaps_bucket_threshold = tuning_state.chosen_overlaps_threshold;
       reifyImpl(columns_per_device,
                 query_info,
                 layout,
                 shard_count,
                 crt_props.entry_count,
                 crt_props.emitted_keys_count,
                 skip_hashtable_caching,
                 overlaps_max_table_size_bytes,
                 overlaps_bucket_threshold);
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void OverlapsJoinHashTable::setInverseBucketSizeInfo	(	const std::vector< double > &	inverse_bucket_sizes,
		std::vector< ColumnsForDevice > &	columns_per_device,
		const size_t	device_count
	)

protected

Definition at line 1148 of file OverlapsJoinHashTable.cpp.

References CHECK_EQ, inner_outer_pairs_, and inverse_bucket_sizes_for_dimension_.

Referenced by RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

                                {
   // set global bucket size
   inverse_bucket_sizes_for_dimension_ = inverse_bucket_sizes;
 
   // re-compute bucket counts per device based on global bucket size
   CHECK_EQ(columns_per_device.size(), static_cast<size_t>(device_count));
   for (size_t device_id = 0; device_id < device_count; ++device_id) {
     auto& columns_for_device = columns_per_device[device_id];
     columns_for_device.setBucketInfo(inverse_bucket_sizes_for_dimension_,
                                      inner_outer_pairs_);
   }
 }

Here is the caller graph for this function:

void OverlapsJoinHashTable::setOverlapsHashtableMetaInfo	(	size_t	max_table_size_bytes,
		double	bucket_threshold,
		std::vector< double > &	bucket_sizes
	)

inlineprotected

Definition at line 364 of file OverlapsJoinHashTable.h.

References OverlapsHashTableMetaInfo::bucket_sizes, hashtable_cache_meta_info_, OverlapsHashTableMetaInfo::overlaps_bucket_threshold, OverlapsHashTableMetaInfo::overlaps_max_table_size_bytes, and HashtableCacheMetaInfo::overlaps_meta_info.

Referenced by reifyImpl(), RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

                                                                      {
     OverlapsHashTableMetaInfo overlaps_meta_info;
     overlaps_meta_info.bucket_sizes = bucket_sizes;
     overlaps_meta_info.overlaps_max_table_size_bytes = max_table_size_bytes;
     overlaps_meta_info.overlaps_bucket_threshold = bucket_threshold;
     HashtableCacheMetaInfo meta_info;
     meta_info.overlaps_meta_info = overlaps_meta_info;
     hashtable_cache_meta_info_ = meta_info;
   }

Here is the caller graph for this function:

size_t OverlapsJoinHashTable::shardCount ( ) const

inlineprotected

Definition at line 235 of file OverlapsJoinHashTable.h.

References condition_, executor_, BaselineJoinHashTable::getShardCountForCondition(), Data_Namespace::GPU_LEVEL, inner_outer_pairs_, and memory_level_.

Referenced by RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

                             {
     if (memory_level_ != Data_Namespace::GPU_LEVEL) {
       return 0;
     }
     return BaselineJoinHashTable::getShardCountForCondition(
         condition_.get(), executor_, inner_outer_pairs_);
   }

Here is the call graph for this function:

Here is the caller graph for this function:

std::set< DecodedJoinHashBufferEntry > OverlapsJoinHashTable::toSet	(	const ExecutorDeviceType	device_type,
		const int	device_id
	)		const

overrideprotectedvirtual

Implements HashJoin.

Definition at line 1783 of file OverlapsJoinHashTable.cpp.

References CHECK, countBufferOff(), executor_, HashJoin::getHashTableForDevice(), getHashType(), HashJoin::getJoinHashBuffer(), getKeyComponentCount(), getKeyComponentWidth(), getQueryEngineCudaStreamForDevice(), GPU, offsetBufferOff(), OneToOne, payloadBufferOff(), and HashTable::toSet().

                                {
   auto buffer = getJoinHashBuffer(device_type, device_id);
   auto hash_table = getHashTableForDevice(device_id);
   CHECK(hash_table);
   auto buffer_size = hash_table->getHashTableBufferSize(device_type);
 #ifdef HAVE_CUDA
   std::unique_ptr<int8_t[]> buffer_copy;
   if (device_type == ExecutorDeviceType::GPU) {
     buffer_copy = std::make_unique<int8_t[]>(buffer_size);
     CHECK(executor_);
     auto data_mgr = executor_->getDataMgr();
     auto allocator = std::make_unique<CudaAllocator>(
         data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id));
 
     allocator->copyFromDevice(buffer_copy.get(), buffer, buffer_size);
   }
   auto ptr1 = buffer_copy ? buffer_copy.get() : reinterpret_cast<const int8_t*>(buffer);
 #else
   auto ptr1 = reinterpret_cast<const int8_t*>(buffer);
 #endif  // HAVE_CUDA
   auto ptr2 = ptr1 + offsetBufferOff();
   auto ptr3 = ptr1 + countBufferOff();
   auto ptr4 = ptr1 + payloadBufferOff();
   const auto layout = getHashType();
   return HashTable::toSet(getKeyComponentCount() + (layout == HashType::OneToOne ? 1 : 0),
                           getKeyComponentWidth(),
                           hash_table->getEntryCount(),
                           ptr1,
                           ptr2,
                           ptr3,
                           ptr4,
                           buffer_size);
 }

Here is the call graph for this function:

std::string OverlapsJoinHashTable::toString	(	const ExecutorDeviceType	device_type,
		const int	device_id = `0`,
		bool	raw = `false`
	)		const

overrideprotectedvirtual

Implements HashJoin.

Definition at line 1741 of file OverlapsJoinHashTable.cpp.

References CHECK, CHECK_LT, countBufferOff(), executor_, getHashType(), HashJoin::getHashTypeString(), HashJoin::getJoinHashBuffer(), getKeyComponentCount(), getKeyComponentWidth(), getQueryEngineCudaStreamForDevice(), GPU, HashJoin::hash_tables_for_device_, offsetBufferOff(), OneToOne, payloadBufferOff(), and HashTable::toString().

                                                             {
   auto buffer = getJoinHashBuffer(device_type, device_id);
   CHECK_LT(static_cast<size_t>(device_id), hash_tables_for_device_.size());
   auto hash_table = hash_tables_for_device_[device_id];
   CHECK(hash_table);
   auto buffer_size = hash_table->getHashTableBufferSize(device_type);
 #ifdef HAVE_CUDA
   std::unique_ptr<int8_t[]> buffer_copy;
   if (device_type == ExecutorDeviceType::GPU) {
     buffer_copy = std::make_unique<int8_t[]>(buffer_size);
     CHECK(executor_);
     auto data_mgr = executor_->getDataMgr();
     auto device_allocator = std::make_unique<CudaAllocator>(
         data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id));
 
     device_allocator->copyFromDevice(buffer_copy.get(), buffer, buffer_size);
   }
   auto ptr1 = buffer_copy ? buffer_copy.get() : reinterpret_cast<const int8_t*>(buffer);
 #else
   auto ptr1 = reinterpret_cast<const int8_t*>(buffer);
 #endif  // HAVE_CUDA
   auto ptr2 = ptr1 + offsetBufferOff();
   auto ptr3 = ptr1 + countBufferOff();
   auto ptr4 = ptr1 + payloadBufferOff();
   CHECK(hash_table);
   const auto layout = getHashType();
   return HashTable::toString(
       "geo",
       getHashTypeString(layout),
       getKeyComponentCount() + (layout == HashType::OneToOne ? 1 : 0),
       getKeyComponentWidth(),
       hash_table->getEntryCount(),
       ptr1,
       ptr2,
       ptr3,
       ptr4,
       buffer_size,
       raw);
 }

Here is the call graph for this function:

Member Data Documentation

std::unique_ptr< OverlapsTuningParamRecycler > OverlapsJoinHashTable::auto_tuner_cache_

staticprotected

Initial value:

=

std::make_unique<OverlapsTuningParamRecycler>()

Definition at line 407 of file OverlapsJoinHashTable.h.

Referenced by getOverlapsTuningParamCache(), invalidateCache(), markCachedItemAsDirty(), and reifyWithLayout().

double OverlapsJoinHashTable::chosen_overlaps_bucket_threshold_

protected

Definition at line 389 of file OverlapsJoinHashTable.h.

Referenced by reifyImpl().

size_t OverlapsJoinHashTable::chosen_overlaps_max_table_size_bytes_

protected

Definition at line 390 of file OverlapsJoinHashTable.h.

Referenced by reifyImpl().

ColumnCacheMap& OverlapsJoinHashTable::column_cache_

protected

Definition at line 382 of file OverlapsJoinHashTable.h.

Referenced by fetchColumnsForDevice().

CompositeKeyInfo OverlapsJoinHashTable::composite_key_info_

protected

Definition at line 391 of file OverlapsJoinHashTable.h.

Referenced by initHashTableOnCpu(), reify(), RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

const std::shared_ptr<Analyzer::BinOper> OverlapsJoinHashTable::condition_

protected

Definition at line 376 of file OverlapsJoinHashTable.h.

Referenced by isBitwiseEq(), reify(), RangeJoinHashTable::reifyWithLayout(), reifyWithLayout(), and shardCount().

std::mutex OverlapsJoinHashTable::cpu_hash_table_buff_mutex_

protected

Definition at line 396 of file OverlapsJoinHashTable.h.

Referenced by initHashTableOnCpu(), and RangeJoinHashTable::reifyWithLayout().

const int OverlapsJoinHashTable::device_count_

protected

Definition at line 385 of file OverlapsJoinHashTable.h.

Referenced by RangeJoinHashTable::approximateTupleCount(), approximateTupleCount(), computeHashTableCounts(), RangeJoinHashTable::computeRangeHashTableCounts(), getDeviceCount(), OverlapsJoinHashTable(), reify(), reifyImpl(), RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

Executor* OverlapsJoinHashTable::executor_

protected

Definition at line 381 of file OverlapsJoinHashTable.h.

Referenced by RangeJoinHashTable::approximateTupleCount(), approximateTupleCount(), RangeJoinHashTable::codegenKey(), codegenKey(), codegenManyKey(), codegenMatchingSet(), RangeJoinHashTable::codegenMatchingSetWithOffset(), fetchColumnsForDevice(), getEffectiveMemoryLevel(), RangeJoinHashTable::initHashTableOnCpu(), reify(), RangeJoinHashTable::reifyWithLayout(), reifyWithLayout(), shardCount(), toSet(), and toString().

std::unique_ptr< HashtableRecycler > OverlapsJoinHashTable::hash_table_cache_

staticprotected

Initial value:

=
    std::make_unique<HashtableRecycler>(CacheItemType::OVERLAPS_HT,
                                        DataRecyclerUtil::CPU_DEVICE_IDENTIFIER)

Definition at line 405 of file OverlapsJoinHashTable.h.

Referenced by generateCacheKey(), getApproximateTupleCountFromCache(), getHashTableCache(), initHashTableOnCpuFromCache(), invalidateCache(), markCachedItemAsDirty(), putHashTableOnCpuToCache(), RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

HashTableBuildDagMap OverlapsJoinHashTable::hashtable_build_dag_map_

protected

Definition at line 409 of file OverlapsJoinHashTable.h.

Referenced by RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

std::vector<QueryPlanHash> OverlapsJoinHashTable::hashtable_cache_key_

protected

Definition at line 411 of file OverlapsJoinHashTable.h.

Referenced by approximateTupleCount(), generateCacheKey(), getCacheKey(), RangeJoinHashTable::initHashTableOnCpu(), initHashTableOnCpu(), RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

HashtableCacheMetaInfo OverlapsJoinHashTable::hashtable_cache_meta_info_

protected

Definition at line 412 of file OverlapsJoinHashTable.h.

Referenced by getOverlapsHashTableMetaInfo(), reifyWithLayout(), and setOverlapsHashtableMetaInfo().

std::vector<InnerOuter> OverlapsJoinHashTable::inner_outer_pairs_

protected

Definition at line 384 of file OverlapsJoinHashTable.h.

Referenced by RangeJoinHashTable::approximateTupleCount(), approximateTupleCount(), RangeJoinHashTable::codegenKey(), codegenKey(), codegenManyKey(), fetchColumnsForDevice(), getInnerOuterPairs(), getInnerTableId(), getInnerTableRteIdx(), RangeJoinHashTable::initHashTableOnCpu(), reify(), reifyForDevice(), RangeJoinHashTable::reifyWithLayout(), reifyWithLayout(), setInverseBucketSizeInfo(), and shardCount().

std::vector<double> OverlapsJoinHashTable::inverse_bucket_sizes_for_dimension_

protected

Definition at line 388 of file OverlapsJoinHashTable.h.

Referenced by RangeJoinHashTable::codegenKey(), codegenKey(), codegenMatchingSet(), RangeJoinHashTable::computeRangeHashTableCounts(), getKeyComponentCount(), reifyImpl(), RangeJoinHashTable::reifyWithLayout(), reifyWithLayout(), and setInverseBucketSizeInfo().

const JoinType OverlapsJoinHashTable::join_type_

protected

Definition at line 377 of file OverlapsJoinHashTable.h.

Referenced by RangeJoinHashTable::initHashTableOnCpu(), initHashTableOnCpu(), RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

std::optional<HashType> OverlapsJoinHashTable::layout_override_

protected

Definition at line 394 of file OverlapsJoinHashTable.h.

Referenced by getHashType(), initHashTableOnCpu(), and RangeJoinHashTable::reifyWithLayout().

const Data_Namespace::MemoryLevel OverlapsJoinHashTable::memory_level_

protected

Definition at line 379 of file OverlapsJoinHashTable.h.

Referenced by computeHashTableCounts(), RangeJoinHashTable::computeRangeHashTableCounts(), getEffectiveMemoryLevel(), getMemoryLevel(), RangeJoinHashTable::reifyForDevice(), reifyForDevice(), RangeJoinHashTable::reifyWithLayout(), reifyWithLayout(), and shardCount().

RegisteredQueryHint OverlapsJoinHashTable::query_hints_

protected

Definition at line 386 of file OverlapsJoinHashTable.h.

Referenced by getEffectiveMemoryLevel(), getRegisteredQueryHint(), RangeJoinHashTable::initHashTableOnCpu(), initHashTableOnCpu(), putHashTableOnCpuToCache(), and reifyWithLayout().

const std::vector<InputTableInfo>& OverlapsJoinHashTable::query_infos_

protected

Definition at line 378 of file OverlapsJoinHashTable.h.

Referenced by RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

QueryPlanDAG OverlapsJoinHashTable::query_plan_dag_

protected

Definition at line 410 of file OverlapsJoinHashTable.h.

const TableIdToNodeMap OverlapsJoinHashTable::table_id_to_node_map_

protected

Definition at line 414 of file OverlapsJoinHashTable.h.

std::unordered_set<size_t> OverlapsJoinHashTable::table_keys_

protected

Definition at line 413 of file OverlapsJoinHashTable.h.

Referenced by generateCacheKey(), RangeJoinHashTable::reifyWithLayout(), and reifyWithLayout().

The documentation for this class was generated from the following files:

/home/jenkins-slave/workspace/core-os-doxygen/QueryEngine/JoinHashTable/OverlapsJoinHashTable.h
/home/jenkins-slave/workspace/core-os-doxygen/QueryEngine/JoinHashTable/OverlapsJoinHashTable.cpp

Classes

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation