OmniSciDB  ca0c39ec8f
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
PerfectJoinHashTable.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 
23 #pragma once
24 
25 #include "Analyzer/Analyzer.h"
27 #include "DataMgr/Chunk/Chunk.h"
37 
38 #include <llvm/IR/Value.h>
39 
40 #ifdef HAVE_CUDA
41 #include <cuda.h>
42 #endif
43 #include <functional>
44 #include <memory>
45 #include <mutex>
46 #include <stdexcept>
47 
48 struct HashEntryInfo;
49 
51  public:
53  static std::shared_ptr<PerfectJoinHashTable> getInstance(
54  const std::shared_ptr<Analyzer::BinOper> qual_bin_oper,
55  const std::vector<InputTableInfo>& query_infos,
56  const Data_Namespace::MemoryLevel memory_level,
57  const JoinType join_type,
58  const HashType preferred_hash_type,
59  const int device_count,
60  ColumnCacheMap& column_cache,
61  Executor* executor,
62  const HashTableBuildDagMap& hashtable_build_dag_map,
63  const TableIdToNodeMap& table_id_to_node_map);
64 
65  std::string toString(const ExecutorDeviceType device_type,
66  const int device_id = 0,
67  bool raw = false) const override;
68 
69  std::set<DecodedJoinHashBufferEntry> toSet(const ExecutorDeviceType device_type,
70  const int device_id) const override;
71 
72  llvm::Value* codegenSlot(const CompilationOptions&, const size_t) override;
73 
75  const size_t) override;
76 
77  int getInnerTableId() const noexcept override {
78  return col_var_.get()->get_table_id();
79  };
80 
81  int getInnerTableRteIdx() const noexcept override {
82  return col_var_.get()->get_rte_idx();
83  };
84 
85  HashType getHashType() const noexcept override { return hash_type_; }
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 "Perfect"; }
100 
103  return hash_table_cache_.get();
104  }
107  return hash_table_layout_cache_.get();
108  }
109 
110  static void invalidateCache() {
112  hash_table_layout_cache_->clearCache();
113 
115  hash_table_cache_->clearCache();
116  }
117 
118  static void markCachedItemAsDirty(size_t table_key) {
121  auto candidate_table_keys =
122  hash_table_cache_->getMappedQueryPlanDagsWithTableKey(table_key);
123  if (candidate_table_keys.has_value()) {
124  hash_table_layout_cache_->markCachedItemAsDirty(
125  table_key,
126  *candidate_table_keys,
129  hash_table_cache_->markCachedItemAsDirty(table_key,
130  *candidate_table_keys,
133  }
134  }
135 
137 
138  private:
139  // Equijoin API
141  const std::vector<ColumnsForDevice>& columns_per_device) const;
142 
144  const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
145  const int device_id,
146  DeviceAllocator* dev_buff_owner,
147  const Catalog_Namespace::Catalog& catalog);
148 
149  void reifyForDevice(const ChunkKey& hash_table_key,
150  const ColumnsForDevice& columns_for_device,
151  const HashType layout,
152  const int device_id,
153  const logger::ThreadId parent_thread_id);
154 
155  int initHashTableForDevice(const ChunkKey& chunk_key,
156  const JoinColumn& join_column,
157  const InnerOuter& cols,
158  const HashType layout,
159  const Data_Namespace::MemoryLevel effective_memory_level,
160  const int device_id);
161 
163  const std::vector<InnerOuter>& inner_outer_pairs) const;
164 
165  std::vector<InnerOuter> inner_outer_pairs_;
166 
167  PerfectJoinHashTable(const std::shared_ptr<Analyzer::BinOper> qual_bin_oper,
168  const Analyzer::ColumnVar* col_var,
169  const std::vector<InputTableInfo>& query_infos,
170  const Data_Namespace::MemoryLevel memory_level,
171  const JoinType join_type,
172  const HashType preferred_hash_type,
173  const ExpressionRange& col_range,
174  const ExpressionRange& rhs_source_col_range,
175  ColumnCacheMap& column_cache,
176  Executor* executor,
177  const int device_count,
178  const HashTableBuildDagMap& hashtable_build_dag_map,
179  const TableIdToNodeMap& table_id_to_node_map,
180  const InnerOuterStringOpInfos& inner_outer_string_op_infos = {})
181  : qual_bin_oper_(qual_bin_oper)
182  , join_type_(join_type)
183  , col_var_(std::dynamic_pointer_cast<Analyzer::ColumnVar>(col_var->deep_copy()))
184  , query_infos_(query_infos)
185  , memory_level_(memory_level)
186  , hash_type_(preferred_hash_type)
187  , col_range_(col_range)
188  , rhs_source_col_range_(rhs_source_col_range)
189  , executor_(executor)
190  , column_cache_(column_cache)
191  , device_count_(device_count)
192  , needs_dict_translation_(false)
193  , hashtable_build_dag_map_(hashtable_build_dag_map)
194  , table_id_to_node_map_(table_id_to_node_map)
195  , inner_outer_string_op_infos_(inner_outer_string_op_infos) {
199  }
200 
201  ChunkKey genChunkKey(const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
202  const Analyzer::Expr* outer_col,
203  const Analyzer::ColumnVar* inner_col) const;
204 
205  void reify();
206  std::shared_ptr<PerfectHashTable> initHashTableOnCpuFromCache(
207  QueryPlanHash key,
208  CacheItemType item_type,
209  DeviceIdentifier device_identifier);
211  CacheItemType item_type,
212  std::shared_ptr<PerfectHashTable> hashtable_ptr,
213  DeviceIdentifier device_identifier,
214  size_t hashtable_building_time);
215 
216  const InputTableInfo& getInnerQueryInfo(const Analyzer::ColumnVar* inner_col) const;
217 
218  size_t shardCount() const;
219 
220  llvm::Value* codegenHashTableLoad(const size_t table_idx);
221 
222  std::vector<llvm::Value*> getHashJoinArgs(llvm::Value* hash_ptr,
223  llvm::Value* key_lvs,
224  const Analyzer::Expr* key_col,
225  const int shard_count,
226  const CompilationOptions& co);
227 
228  bool isBitwiseEq() const override;
229 
230  size_t getComponentBufferSize() const noexcept override;
231 
232  HashTable* getHashTableForDevice(const size_t device_id) const;
233 
234  void copyCpuHashTableToGpu(std::shared_ptr<PerfectHashTable>& cpu_hash_table,
235  const int device_id,
236  Data_Namespace::DataMgr* data_mgr);
237 
244  const size_t num_elements;
245  const SQLOps optype;
247  };
248 
251  auto hash = boost::hash_value(::toString(info.chunk_key));
252  boost::hash_combine(hash, info.inner_col->toString());
253  if (info.inner_col->get_type_info().is_string()) {
254  boost::hash_combine(hash, info.outer_col->toString());
255  }
256  boost::hash_combine(hash, ::toString(info.inner_outer_string_op_infos));
257  boost::hash_combine(hash, info.col_range.toString());
258  boost::hash_combine(hash, info.num_elements);
259  boost::hash_combine(hash, info.optype);
260  boost::hash_combine(hash, info.join_type);
261  return hash;
262  }
263 
264  std::shared_ptr<Analyzer::BinOper> qual_bin_oper_;
266  std::shared_ptr<Analyzer::ColumnVar> col_var_;
267  const std::vector<InputTableInfo>& query_infos_;
275  Executor* executor_;
277  const int device_count_;
280  // per-device cache key to cover hash table for sharded table
281  std::vector<QueryPlanHash> hashtable_cache_key_;
283  std::unordered_set<size_t> table_keys_;
286 
287  static std::unique_ptr<HashtableRecycler> hash_table_cache_;
288  static std::unique_ptr<HashingSchemeRecycler> hash_table_layout_cache_;
289 };
290 
292  const InnerOuter& inner_outer_col_pair,
293  const InnerOuterStringOpInfos& inner_outer_string_op_infos,
294  const Executor* executor);
295 
297  const Data_Namespace::MemoryLevel memory_level,
298  const bool needs_dict_translation) {
299  if (needs_dict_translation) {
301  }
302  return memory_level;
303 }
304 
305 std::vector<Fragmenter_Namespace::FragmentInfo> only_shards_for_device(
306  const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
307  const int device_id,
308  const int device_count);
309 
311  const int inner_table_id,
312  const std::vector<InputTableInfo>& query_infos);
313 
314 size_t get_entries_per_device(const size_t total_entries,
315  const size_t shard_count,
316  const size_t device_count,
317  const Data_Namespace::MemoryLevel memory_level);
Defines data structures for the semantic analysis phase of query processing.
llvm::Value * codegenHashTableLoad(const size_t table_idx)
void reifyForDevice(const ChunkKey &hash_table_key, const ColumnsForDevice &columns_for_device, const HashType layout, const int device_id, const logger::ThreadId parent_thread_id)
std::string toString() const
std::vector< int > ChunkKey
Definition: types.h:36
size_t DeviceIdentifier
Definition: DataRecycler.h:129
JoinType
Definition: sqldefs.h:157
Data_Namespace::MemoryLevel getEffectiveMemoryLevel(const std::vector< InnerOuter > &inner_outer_pairs) const
ExpressionRange rhs_source_col_range_
class for a per-database catalog. also includes metadata for the current database and the current use...
Definition: Catalog.h:132
std::pair< const Analyzer::ColumnVar *, const Analyzer::Expr * > InnerOuter
Definition: HashJoin.h:95
const Data_Namespace::MemoryLevel memory_level_
size_t getComponentBufferSize() const noexceptoverride
ExecutorDeviceType
std::shared_ptr< Analyzer::BinOper > qual_bin_oper_
std::mutex str_proxy_translation_mutex_
ChunkKey genChunkKey(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments, const Analyzer::Expr *outer_col, const Analyzer::ColumnVar *inner_col) const
const TableIdToNodeMap table_id_to_node_map_
SQLOps
Definition: sqldefs.h:28
size_t offsetBufferOff() const noexceptoverride
std::vector< std::shared_ptr< HashTable > > hash_tables_for_device_
Definition: HashJoin.h:351
HashTableBuildDagMap hashtable_build_dag_map_
Data_Namespace::MemoryLevel get_effective_memory_level(const Data_Namespace::MemoryLevel memory_level, const bool needs_dict_translation)
int getDeviceCount() const noexceptoverride
const InputTableInfo & getInnerQueryInfo(const Analyzer::ColumnVar *inner_col) const
size_t payloadBufferOff() const noexceptoverride
std::shared_ptr< Analyzer::Expr > deep_copy() const override
Definition: Analyzer.cpp:66
std::shared_ptr< PerfectHashTable > initHashTableOnCpuFromCache(QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier)
bool needs_dictionary_translation(const std::vector< InnerOuter > &inner_outer_pairs, const std::vector< InnerOuterStringOpInfos > &inner_outer_string_op_infos_pairs, const Executor *executor)
#define CHECK_GT(x, y)
Definition: Logger.h:234
HashType getHashType() const noexceptoverride
void copyCpuHashTableToGpu(std::shared_ptr< PerfectHashTable > &cpu_hash_table, const int device_id, Data_Namespace::DataMgr *data_mgr)
HashtableCacheMetaInfo hashtable_cache_meta_info_
static std::unique_ptr< HashtableRecycler > hash_table_cache_
ColumnsForDevice fetchColumnsForDevice(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments, const int device_id, DeviceAllocator *dev_buff_owner, const Catalog_Namespace::Catalog &catalog)
std::string getHashJoinType() const final
std::unordered_map< size_t, HashTableBuildDag > HashTableBuildDagMap
CacheItemType
Definition: DataRecycler.h:38
static HashtableRecycler * getHashTableCache()
std::string toString() const override
Definition: Analyzer.cpp:2590
std::unordered_map< int, const RelAlgNode * > TableIdToNodeMap
std::vector< Fragmenter_Namespace::FragmentInfo > only_shards_for_device(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments, const int device_id, const int device_count)
bool isOneToOneHashPossible(const std::vector< ColumnsForDevice > &columns_per_device) const
static HashingSchemeRecycler * getHashingSchemeCache()
const SQLTypeInfo & get_type_info() const
Definition: Analyzer.h:82
std::vector< llvm::Value * > getHashJoinArgs(llvm::Value *hash_ptr, llvm::Value *key_lvs, const Analyzer::Expr *key_col, const int shard_count, const CompilationOptions &co)
std::vector< InnerOuter > inner_outer_pairs_
PerfectJoinHashTable(const std::shared_ptr< Analyzer::BinOper > qual_bin_oper, const Analyzer::ColumnVar *col_var, const std::vector< InputTableInfo > &query_infos, const Data_Namespace::MemoryLevel memory_level, const JoinType join_type, const HashType preferred_hash_type, const ExpressionRange &col_range, const ExpressionRange &rhs_source_col_range, ColumnCacheMap &column_cache, Executor *executor, const int device_count, const HashTableBuildDagMap &hashtable_build_dag_map, const TableIdToNodeMap &table_id_to_node_map, const InnerOuterStringOpInfos &inner_outer_string_op_infos={})
std::unordered_map< int, std::unordered_map< int, std::shared_ptr< const ColumnarResults >>> ColumnCacheMap
static std::unique_ptr< HashingSchemeRecycler > hash_table_layout_cache_
const InputTableInfo & get_inner_query_info(const int inner_table_id, const std::vector< InputTableInfo > &query_infos)
static QueryPlanHash getAlternativeCacheKey(AlternativeCacheKeyForPerfectHashJoin &info)
const std::vector< InputTableInfo > & query_infos_
static std::shared_ptr< PerfectJoinHashTable > 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 TableIdToNodeMap &table_id_to_node_map)
Make hash table from an in-flight SQL query&#39;s parse tree etc.
int getInnerTableId() const noexceptoverride
void putHashTableOnCpuToCache(QueryPlanHash key, CacheItemType item_type, std::shared_ptr< PerfectHashTable > hashtable_ptr, DeviceIdentifier device_identifier, size_t hashtable_building_time)
std::string toString(const ExecutorDeviceType device_type, const int device_id=0, bool raw=false) const override
ColumnCacheMap & column_cache_
size_t get_entries_per_device(const size_t total_entries, const size_t shard_count, const size_t device_count, const Data_Namespace::MemoryLevel memory_level)
std::shared_ptr< Analyzer::ColumnVar > col_var_
uint64_t ThreadId
Definition: Logger.h:364
size_t QueryPlanHash
const InnerOuterStringOpInfos inner_outer_string_op_infos_
llvm::Value * codegenSlot(const CompilationOptions &, const size_t) override
ExpressionRangeType getType() const
std::pair< std::vector< StringOps_Namespace::StringOpInfo >, std::vector< StringOps_Namespace::StringOpInfo >> InnerOuterStringOpInfos
Definition: HashJoin.h:97
#define CHECK(condition)
Definition: Logger.h:222
size_t countBufferOff() const noexceptoverride
int initHashTableForDevice(const ChunkKey &chunk_key, const JoinColumn &join_column, const InnerOuter &cols, const HashType layout, const Data_Namespace::MemoryLevel effective_memory_level, const int device_id)
std::vector< QueryPlanHash > hashtable_cache_key_
bool is_string() const
Definition: sqltypes.h:575
HashTable * getHashTableForDevice(const size_t device_id) const
Data_Namespace::MemoryLevel getMemoryLevel() const noexceptoverride
static constexpr DeviceIdentifier CPU_DEVICE_IDENTIFIER
Definition: DataRecycler.h:136
std::set< DecodedJoinHashBufferEntry > toSet(const ExecutorDeviceType device_type, const int device_id) const override
HashType
Definition: HashTable.h:19
static void markCachedItemAsDirty(size_t table_key)
const StringDictionaryProxy::IdMap * str_proxy_translation_map_
std::unordered_set< size_t > table_keys_
HashJoinMatchingSet codegenMatchingSet(const CompilationOptions &, const size_t) override
bool isBitwiseEq() const override
int getInnerTableRteIdx() const noexceptoverride