OmniSciDB  c0231cc57d
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
BaselineJoinHashTable.h
Go to the documentation of this file.
1 /*
2  * Copyright 2022 HEAVY.AI, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #ifdef HAVE_CUDA
20 #include <cuda.h>
21 #endif
22 #include <cstdint>
23 #include <map>
24 #include <mutex>
25 #include <thread>
26 #include <unordered_set>
27 #include <vector>
28 
29 #include "Analyzer/Analyzer.h"
30 #include "DataMgr/MemoryLevel.h"
39 
40 class Executor;
41 
43  std::pair<std::vector<const int32_t*>, std::vector<int32_t>>;
44 
45 // Representation for a hash table using the baseline layout: an open-addressing
46 // hash with a fill rate of 50%. It is used for equi-joins on multiple columns and
47 // on single sparse columns (with very wide range), typically big integer. As of
48 // now, such tuples must be unique within the inner table.
50  public:
52  static std::shared_ptr<BaselineJoinHashTable> getInstance(
53  const std::shared_ptr<Analyzer::BinOper> condition,
54  const std::vector<InputTableInfo>& query_infos,
55  const Data_Namespace::MemoryLevel memory_level,
56  const JoinType join_type,
57  const HashType preferred_hash_type,
58  const int device_count,
59  ColumnCacheMap& column_cache,
60  Executor* executor,
61  const HashTableBuildDagMap& hashtable_build_dag_map,
62  const TableIdToNodeMap& table_id_to_node_map);
63 
64  static size_t getShardCountForCondition(
65  const Analyzer::BinOper* condition,
66  const Executor* executor,
67  const std::vector<InnerOuter>& inner_outer_pairs);
68 
69  std::string toString(const ExecutorDeviceType device_type,
70  const int device_id = 0,
71  bool raw = false) const override;
72 
73  std::set<DecodedJoinHashBufferEntry> toSet(const ExecutorDeviceType device_type,
74  const int device_id) const override;
75 
76  llvm::Value* codegenSlot(const CompilationOptions&, const size_t) override;
77 
79  const size_t) override;
80 
81  int getInnerTableId() const noexcept override;
82 
83  int getInnerTableRteIdx() const noexcept override;
84 
85  HashType getHashType() const noexcept override;
86 
87  Data_Namespace::MemoryLevel getMemoryLevel() const noexcept override {
88  return memory_level_;
89  };
90 
91  int getDeviceCount() const noexcept override { return device_count_; };
92 
93  size_t offsetBufferOff() const noexcept override;
94 
95  size_t countBufferOff() const noexcept override;
96 
97  size_t payloadBufferOff() const noexcept override;
98 
99  std::string getHashJoinType() const final { return "Baseline"; }
100 
101  static void invalidateCache() {
103  hash_table_cache_->clearCache();
104 
106  hash_table_layout_cache_->clearCache();
107  }
108 
109  static void markCachedItemAsDirty(size_t table_key) {
112  auto candidate_table_keys =
113  hash_table_cache_->getMappedQueryPlanDagsWithTableKey(table_key);
114  if (candidate_table_keys.has_value()) {
115  hash_table_layout_cache_->markCachedItemAsDirty(
116  table_key,
117  *candidate_table_keys,
120  hash_table_cache_->markCachedItemAsDirty(table_key,
121  *candidate_table_keys,
124  }
125  }
126 
129  return hash_table_cache_.get();
130  }
133  return hash_table_layout_cache_.get();
134  }
135 
137 
138  protected:
140  const std::shared_ptr<Analyzer::BinOper> condition,
141  const JoinType join_type,
142  const std::vector<InputTableInfo>& query_infos,
143  const Data_Namespace::MemoryLevel memory_level,
144  ColumnCacheMap& column_cache,
145  Executor* executor,
146  const std::vector<InnerOuter>& inner_outer_pairs,
147  const std::vector<InnerOuterStringOpInfos>& col_pairs_string_op_infos,
148  const int device_count,
149  const HashTableBuildDagMap& hashtable_build_dag_map,
150  const TableIdToNodeMap& table_id_to_node_map);
151 
152  size_t getComponentBufferSize() const noexcept override;
153 
154  size_t getKeyBufferSize() const noexcept;
155 
156  static int getInnerTableId(const std::vector<InnerOuter>& inner_outer_pairs);
157 
158  virtual void reifyWithLayout(const HashType layout);
159 
161  const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
162  const int device_id,
163  DeviceAllocator* dev_buff_owner);
164 
165  virtual std::pair<size_t, size_t> approximateTupleCount(
166  const std::vector<ColumnsForDevice>&) const;
167 
168  virtual size_t getKeyComponentWidth() const;
169 
170  virtual size_t getKeyComponentCount() const;
171 
172  virtual llvm::Value* codegenKey(const CompilationOptions&);
173 
174  size_t shardCount() const;
175 
176  Data_Namespace::MemoryLevel getEffectiveMemoryLevel(
177  const std::vector<InnerOuter>& inner_outer_pairs) const;
178 
179  void reify(const HashType preferred_layout);
180 
181  void copyCpuHashTableToGpu(std::shared_ptr<BaselineHashTable>& cpu_hash_table,
182  const int device_id,
183  Data_Namespace::DataMgr* data_mgr);
184 
185  virtual void reifyForDevice(const ColumnsForDevice& columns_for_device,
186  const HashType layout,
187  const int device_id,
188  const size_t entry_count,
189  const size_t emitted_keys_count,
190  const logger::ThreadId parent_thread_id);
191 
192  virtual int initHashTableForDevice(
193  const std::vector<JoinColumn>& join_columns,
194  const std::vector<JoinColumnTypeInfo>& join_column_types,
195  const std::vector<JoinBucketInfo>& join_buckets,
196  const HashType layout,
197  const Data_Namespace::MemoryLevel effective_memory_level,
198  const size_t entry_count,
199  const size_t emitted_keys_count,
200  const int device_id);
201 
202  llvm::Value* hashPtr(const size_t index);
203 
204  std::shared_ptr<HashTable> initHashTableOnCpuFromCache(
205  QueryPlanHash key,
206  CacheItemType item_type,
207  DeviceIdentifier device_identifier);
208 
210  CacheItemType item_type,
211  std::shared_ptr<HashTable> hashtable_ptr,
212  DeviceIdentifier device_identifier,
213  size_t hashtable_building_time);
214 
215  bool isBitwiseEq() const override;
216 
218  const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments) const;
219 
221  std::vector<InnerOuter> inner_outer_pairs;
222  std::vector<InnerOuterStringOpInfos> inner_outer_string_op_infos_pairs;
223  const size_t num_elements;
224  const SQLOps optype;
227  };
228 
231  auto hash = boost::hash_value(::toString(info.optype));
232  for (InnerOuter inner_outer : info.inner_outer_pairs) {
233  auto inner_col = inner_outer.first;
234  auto rhs_col_var = dynamic_cast<const Analyzer::ColumnVar*>(inner_outer.second);
235  auto outer_col = rhs_col_var ? rhs_col_var : inner_col;
236  boost::hash_combine(hash, inner_col->toString());
237  if (inner_col->get_type_info().is_string()) {
238  boost::hash_combine(hash, outer_col->toString());
239  }
240  }
241  if (info.inner_outer_string_op_infos_pairs.size()) {
242  boost::hash_combine(hash, ::toString(info.inner_outer_string_op_infos_pairs));
243  }
244  boost::hash_combine(hash, info.num_elements);
245  boost::hash_combine(hash, info.join_type);
246  return hash;
247  }
248 
249  const std::shared_ptr<Analyzer::BinOper> condition_;
251  const std::vector<InputTableInfo>& query_infos_;
253  Executor* executor_;
257  std::vector<const StringDictionaryProxy::IdMap*> str_proxy_translation_maps_;
258 
259  std::vector<InnerOuter> inner_outer_pairs_;
260  std::vector<InnerOuterStringOpInfos> inner_outer_string_op_infos_pairs_;
262  const int device_count_;
264  std::optional<HashType>
265  layout_override_; // allows us to use a 1:many hash table for many:many
266 
268  // per-device cache key to cover hash table for sharded table
269  std::vector<QueryPlanHash> hashtable_cache_key_;
271  std::unordered_set<size_t> table_keys_;
273 
274  static std::unique_ptr<HashtableRecycler> hash_table_cache_;
275  static std::unique_ptr<HashingSchemeRecycler> hash_table_layout_cache_;
276 };
Defines data structures for the semantic analysis phase of query processing.
size_t offsetBufferOff() const noexceptoverride
std::set< DecodedJoinHashBufferEntry > toSet(const ExecutorDeviceType device_type, const int device_id) const override
std::vector< int > ChunkKey
Definition: types.h:36
void putHashTableOnCpuToCache(QueryPlanHash key, CacheItemType item_type, std::shared_ptr< HashTable > hashtable_ptr, DeviceIdentifier device_identifier, size_t hashtable_building_time)
size_t DeviceIdentifier
Definition: DataRecycler.h:129
JoinType
Definition: sqldefs.h:156
std::vector< InnerOuterStringOpInfos > inner_outer_string_op_infos_pairs
std::string toString(const ExecutorDeviceType device_type, const int device_id=0, bool raw=false) const override
class for a per-database catalog. also includes metadata for the current database and the current use...
Definition: Catalog.h:132
std::vector< QueryPlanHash > hashtable_cache_key_
std::pair< const Analyzer::ColumnVar *, const Analyzer::Expr * > InnerOuter
Definition: HashJoin.h:95
Data_Namespace::MemoryLevel getEffectiveMemoryLevel(const std::vector< InnerOuter > &inner_outer_pairs) const
ExecutorDeviceType
HashJoinMatchingSet codegenMatchingSet(const CompilationOptions &, const size_t) override
SQLOps
Definition: sqldefs.h:28
BaselineJoinHashTable(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 std::vector< InnerOuterStringOpInfos > &col_pairs_string_op_infos, const int device_count, const HashTableBuildDagMap &hashtable_build_dag_map, const TableIdToNodeMap &table_id_to_node_map)
HashTableBuildDagMap hashtable_build_dag_map_
size_t getKeyBufferSize() const noexcept
const TableIdToNodeMap table_id_to_node_map_
size_t getComponentBufferSize() const noexceptoverride
int getInnerTableRteIdx() const noexceptoverride
std::unordered_set< size_t > table_keys_
virtual void reifyForDevice(const ColumnsForDevice &columns_for_device, const HashType layout, const int device_id, const size_t entry_count, const size_t emitted_keys_count, const logger::ThreadId parent_thread_id)
virtual ColumnsForDevice fetchColumnsForDevice(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments, const int device_id, DeviceAllocator *dev_buff_owner)
const std::vector< InputTableInfo > & query_infos_
virtual llvm::Value * codegenKey(const CompilationOptions &)
std::shared_ptr< HashTable > initHashTableOnCpuFromCache(QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier)
size_t payloadBufferOff() const noexceptoverride
std::vector< InnerOuter > inner_outer_pairs_
void reify(const HashType preferred_layout)
std::unordered_map< size_t, HashTableBuildDag > HashTableBuildDagMap
HashType getHashType() const noexceptoverride
static QueryPlanHash getAlternativeCacheKey(AlternativeCacheKeyForBaselineHashJoin &info)
CacheItemType
Definition: DataRecycler.h:38
std::vector< InnerOuterStringOpInfos > inner_outer_string_op_infos_pairs_
static std::unique_ptr< HashtableRecycler > hash_table_cache_
ColumnCacheMap & column_cache_
std::unordered_map< int, const RelAlgNode * > TableIdToNodeMap
std::string getHashJoinType() const final
Data_Namespace::MemoryLevel getMemoryLevel() const noexceptoverride
virtual std::pair< size_t, size_t > approximateTupleCount(const std::vector< ColumnsForDevice > &) const
HashtableCacheMetaInfo hashtable_cache_meta_info_
virtual void reifyWithLayout(const HashType layout)
std::unordered_map< int, std::unordered_map< int, std::shared_ptr< const ColumnarResults >>> ColumnCacheMap
Executor(const ExecutorId id, Data_Namespace::DataMgr *data_mgr, const size_t block_size_x, const size_t grid_size_x, const size_t max_gpu_slab_size, const std::string &debug_dir, const std::string &debug_file)
Definition: Execute.cpp:244
static std::shared_ptr< BaselineJoinHashTable > 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 HashType preferred_hash_type, const int device_count, ColumnCacheMap &column_cache, Executor *executor, const HashTableBuildDagMap &hashtable_build_dag_map, const TableIdToNodeMap &table_id_to_node_map)
Make hash table from an in-flight SQL query&#39;s parse tree etc.
int getInnerTableId() const noexceptoverride
std::pair< std::vector< const int32_t * >, std::vector< int32_t >> StrProxyTranslationMapsPtrsAndOffsets
static HashingSchemeRecycler * getHashingSchemeCache()
std::optional< HashType > layout_override_
const Catalog_Namespace::Catalog * catalog_
uint64_t ThreadId
Definition: Logger.h:364
size_t QueryPlanHash
const Data_Namespace::MemoryLevel memory_level_
llvm::Value * hashPtr(const size_t index)
virtual int initHashTableForDevice(const std::vector< JoinColumn > &join_columns, const std::vector< JoinColumnTypeInfo > &join_column_types, const std::vector< JoinBucketInfo > &join_buckets, const HashType layout, const Data_Namespace::MemoryLevel effective_memory_level, const size_t entry_count, const size_t emitted_keys_count, const int device_id)
llvm::Value * codegenSlot(const CompilationOptions &, const size_t) override
bool isBitwiseEq() const override
#define CHECK(condition)
Definition: Logger.h:222
static HashtableRecycler * getHashTableCache()
static void markCachedItemAsDirty(size_t table_key)
virtual size_t getKeyComponentCount() const
void copyCpuHashTableToGpu(std::shared_ptr< BaselineHashTable > &cpu_hash_table, const int device_id, Data_Namespace::DataMgr *data_mgr)
ChunkKey genChunkKey(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments) const
std::vector< const StringDictionaryProxy::IdMap * > str_proxy_translation_maps_
virtual size_t getKeyComponentWidth() const
static size_t getShardCountForCondition(const Analyzer::BinOper *condition, const Executor *executor, const std::vector< InnerOuter > &inner_outer_pairs)
static std::unique_ptr< HashingSchemeRecycler > hash_table_layout_cache_
static constexpr DeviceIdentifier CPU_DEVICE_IDENTIFIER
Definition: DataRecycler.h:136
int getDeviceCount() const noexceptoverride
HashType
Definition: HashTable.h:19
const std::shared_ptr< Analyzer::BinOper > condition_
size_t countBufferOff() const noexceptoverride