OmniSciDB  c1a53651b2
 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 RegisteredQueryHint& query_hints,
63  const TableIdToNodeMap& table_id_to_node_map);
64 
65  static size_t getShardCountForCondition(
66  const Analyzer::BinOper* condition,
67  const Executor* executor,
68  const std::vector<InnerOuter>& inner_outer_pairs);
69 
70  std::string toString(const ExecutorDeviceType device_type,
71  const int device_id = 0,
72  bool raw = false) const override;
73 
74  std::set<DecodedJoinHashBufferEntry> toSet(const ExecutorDeviceType device_type,
75  const int device_id) const override;
76 
77  llvm::Value* codegenSlot(const CompilationOptions&, const size_t) override;
78 
80  const size_t) override;
81 
82  shared::TableKey getInnerTableId() const noexcept override;
83 
84  int getInnerTableRteIdx() const noexcept override;
85 
86  HashType getHashType() const noexcept override;
87 
88  Data_Namespace::MemoryLevel getMemoryLevel() const noexcept override {
89  return memory_level_;
90  };
91 
92  int getDeviceCount() const noexcept override { return device_count_; };
93 
94  size_t offsetBufferOff() const noexcept override;
95 
96  size_t countBufferOff() const noexcept override;
97 
98  size_t payloadBufferOff() const noexcept override;
99 
100  std::string getHashJoinType() const final { return "Baseline"; }
101 
102  static void invalidateCache() {
104  hash_table_cache_->clearCache();
105 
107  hash_table_layout_cache_->clearCache();
108  }
109 
110  static void markCachedItemAsDirty(size_t table_key) {
113  auto candidate_table_keys =
114  hash_table_cache_->getMappedQueryPlanDagsWithTableKey(table_key);
115  if (candidate_table_keys.has_value()) {
116  hash_table_layout_cache_->markCachedItemAsDirty(
117  table_key,
118  *candidate_table_keys,
121  hash_table_cache_->markCachedItemAsDirty(table_key,
122  *candidate_table_keys,
125  }
126  }
127 
130  return hash_table_cache_.get();
131  }
134  return hash_table_layout_cache_.get();
135  }
136 
138 
140 
141  protected:
143  const std::shared_ptr<Analyzer::BinOper> condition,
144  const JoinType join_type,
145  const std::vector<InputTableInfo>& query_infos,
146  const Data_Namespace::MemoryLevel memory_level,
147  ColumnCacheMap& column_cache,
148  Executor* executor,
149  const std::vector<InnerOuter>& inner_outer_pairs,
150  const std::vector<InnerOuterStringOpInfos>& col_pairs_string_op_infos,
151  const int device_count,
152  const RegisteredQueryHint& query_hints,
153  const HashTableBuildDagMap& hashtable_build_dag_map,
154  const TableIdToNodeMap& table_id_to_node_map);
155 
156  size_t getComponentBufferSize() const noexcept override;
157 
158  size_t getKeyBufferSize() const noexcept;
159 
160  static shared::TableKey getInnerTableId(
161  const std::vector<InnerOuter>& inner_outer_pairs);
162 
163  virtual void reifyWithLayout(const HashType layout);
164 
166  const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
167  const int device_id,
168  DeviceAllocator* dev_buff_owner);
169 
170  virtual std::pair<size_t, size_t> approximateTupleCount(
171  const std::vector<ColumnsForDevice>&) const;
172 
173  virtual size_t getKeyComponentWidth() const;
174 
175  virtual size_t getKeyComponentCount() const;
176 
177  virtual llvm::Value* codegenKey(const CompilationOptions&);
178 
179  size_t shardCount() const;
180 
181  Data_Namespace::MemoryLevel getEffectiveMemoryLevel(
182  const std::vector<InnerOuter>& inner_outer_pairs) const;
183 
184  void reify(const HashType preferred_layout);
185 
186  void copyCpuHashTableToGpu(std::shared_ptr<BaselineHashTable>& cpu_hash_table,
187  const int device_id,
188  Data_Namespace::DataMgr* data_mgr);
189 
190  virtual void reifyForDevice(const ColumnsForDevice& columns_for_device,
191  const HashType layout,
192  const int device_id,
193  const size_t entry_count,
194  const size_t emitted_keys_count,
195  const logger::ThreadLocalIds parent_thread_local_ids);
196 
197  virtual int initHashTableForDevice(
198  const std::vector<JoinColumn>& join_columns,
199  const std::vector<JoinColumnTypeInfo>& join_column_types,
200  const std::vector<JoinBucketInfo>& join_buckets,
201  const HashType layout,
202  const Data_Namespace::MemoryLevel effective_memory_level,
203  const size_t entry_count,
204  const size_t emitted_keys_count,
205  const int device_id);
206 
207  llvm::Value* hashPtr(const size_t index);
208 
209  std::shared_ptr<HashTable> initHashTableOnCpuFromCache(
210  QueryPlanHash key,
211  CacheItemType item_type,
212  DeviceIdentifier device_identifier);
213 
215  CacheItemType item_type,
216  std::shared_ptr<HashTable> hashtable_ptr,
217  DeviceIdentifier device_identifier,
218  size_t hashtable_building_time);
219 
220  bool isBitwiseEq() const override;
221 
223  const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments) const;
224 
226  std::vector<InnerOuter> inner_outer_pairs;
227  std::vector<InnerOuterStringOpInfos> inner_outer_string_op_infos_pairs;
228  const size_t num_elements;
229  const SQLOps optype;
232  };
233 
236  auto hash = boost::hash_value(::toString(info.optype));
237  for (InnerOuter inner_outer : info.inner_outer_pairs) {
238  auto inner_col = inner_outer.first;
239  auto rhs_col_var = dynamic_cast<const Analyzer::ColumnVar*>(inner_outer.second);
240  auto outer_col = rhs_col_var ? rhs_col_var : inner_col;
241  boost::hash_combine(hash, inner_col->toString());
242  if (inner_col->get_type_info().is_string()) {
243  boost::hash_combine(hash, outer_col->toString());
244  }
245  }
246  if (info.inner_outer_string_op_infos_pairs.size()) {
247  boost::hash_combine(hash, ::toString(info.inner_outer_string_op_infos_pairs));
248  }
249  boost::hash_combine(hash, info.num_elements);
250  boost::hash_combine(hash, info.join_type);
251  return hash;
252  }
253 
254  const std::shared_ptr<Analyzer::BinOper> condition_;
256  const std::vector<InputTableInfo>& query_infos_;
258  Executor* executor_;
262  std::vector<const StringDictionaryProxy::IdMap*> str_proxy_translation_maps_;
263 
264  std::vector<InnerOuter> inner_outer_pairs_;
265  std::vector<InnerOuterStringOpInfos> inner_outer_string_op_infos_pairs_;
266  const int device_count_;
269  std::optional<HashType>
270  layout_override_; // allows us to use a 1:many hash table for many:many
271 
273  // per-device cache key to cover hash table for sharded table
274  std::vector<QueryPlanHash> hashtable_cache_key_;
276  std::unordered_set<size_t> table_keys_;
278 
279  static std::unique_ptr<HashtableRecycler> hash_table_cache_;
280  static std::unique_ptr<HashingSchemeRecycler> hash_table_layout_cache_;
281 };
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:165
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
std::vector< QueryPlanHash > hashtable_cache_key_
std::pair< const Analyzer::ColumnVar *, const Analyzer::Expr * > InnerOuter
Definition: HashJoin.h:106
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
HashTableBuildDagMap hashtable_build_dag_map_
size_t getKeyBufferSize() const noexcept
const TableIdToNodeMap table_id_to_node_map_
size_t getComponentBufferSize() const noexceptoverride
RegisteredQueryHint query_hints_
int getInnerTableRteIdx() const noexceptoverride
std::unordered_set< size_t > table_keys_
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::string getHashJoinType() const final
Data_Namespace::MemoryLevel getMemoryLevel() const noexceptoverride
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 RegisteredQueryHint &query_hints, const HashTableBuildDagMap &hashtable_build_dag_map, const TableIdToNodeMap &table_id_to_node_map)
virtual std::pair< size_t, size_t > approximateTupleCount(const std::vector< ColumnsForDevice > &) const
HashtableCacheMetaInfo hashtable_cache_meta_info_
virtual void reifyWithLayout(const HashType layout)
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
std::unordered_map< shared::TableKey, const RelAlgNode * > TableIdToNodeMap
std::pair< std::vector< const int32_t * >, std::vector< int32_t >> StrProxyTranslationMapsPtrsAndOffsets
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::ThreadLocalIds parent_thread_local_ids)
static HashingSchemeRecycler * getHashingSchemeCache()
std::optional< HashType > layout_override_
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 RegisteredQueryHint &query_hints, const TableIdToNodeMap &table_id_to_node_map)
Make hash table from an in-flight SQL query&#39;s parse tree etc.
std::unordered_map< shared::TableKey, std::unordered_map< int, std::shared_ptr< const ColumnarResults >>> ColumnCacheMap
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)
const RegisteredQueryHint & getRegisteredQueryHint()
llvm::Value * codegenSlot(const CompilationOptions &, const size_t) override
bool isBitwiseEq() const override
#define CHECK(condition)
Definition: Logger.h:291
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
shared::TableKey getInnerTableId() const noexceptoverride
HashType
Definition: HashTable.h:19
const std::shared_ptr< Analyzer::BinOper > condition_
size_t countBufferOff() const noexceptoverride