OmniSciDB  0264ff685a
BaselineJoinHashTable.h
Go to the documentation of this file.
1 /*
2  * Copyright 2020 OmniSci, 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"
38 
39 class Executor;
40 
42  const size_t num_elements;
43  const std::vector<ChunkKey> chunk_keys;
44  const SQLOps optype;
45  const boost::optional<double> overlaps_hashjoin_bucket_threshold;
46 
47  bool operator==(const struct HashTableCacheKey& that) const {
48  bool oeq;
49  if (overlaps_hashjoin_bucket_threshold && that.overlaps_hashjoin_bucket_threshold) {
50  oeq = (std::abs(*overlaps_hashjoin_bucket_threshold -
51  *that.overlaps_hashjoin_bucket_threshold) <= 0.00000001);
52  } else {
53  oeq =
54  (overlaps_hashjoin_bucket_threshold == that.overlaps_hashjoin_bucket_threshold);
55  }
56  return num_elements == that.num_elements && chunk_keys == that.chunk_keys &&
57  optype == that.optype && oeq;
58  }
59 
60  bool operator<(const struct HashTableCacheKey& that) const {
61  bool oeq;
62  if (overlaps_hashjoin_bucket_threshold && that.overlaps_hashjoin_bucket_threshold) {
63  oeq = (std::abs(*overlaps_hashjoin_bucket_threshold -
64  *that.overlaps_hashjoin_bucket_threshold) <= 0.00000001);
65  } else {
66  oeq =
67  (overlaps_hashjoin_bucket_threshold == that.overlaps_hashjoin_bucket_threshold);
68  }
69  return num_elements < that.num_elements && chunk_keys < that.chunk_keys &&
70  optype < that.optype && !oeq &&
71  overlaps_hashjoin_bucket_threshold < that.overlaps_hashjoin_bucket_threshold;
72  }
73 };
74 
76  public:
77  static void set(const std::vector<ChunkKey>& key, const HashType hash_type);
78 
79  static std::pair<HashType, bool> get(const std::vector<ChunkKey>& key);
80 
81  static void clear();
82 
83  private:
84  static std::map<std::vector<ChunkKey>, HashType> hash_type_cache_;
85  static std::mutex hash_type_cache_mutex_;
86 };
87 
88 // Representation for a hash table using the baseline layout: an open-addressing
89 // hash with a fill rate of 50%. It is used for equi-joins on multiple columns and
90 // on single sparse columns (with very wide range), typically big integer. As of
91 // now, such tuples must be unique within the inner table.
93  public:
95  static std::shared_ptr<BaselineJoinHashTable> getInstance(
96  const std::shared_ptr<Analyzer::BinOper> condition,
97  const std::vector<InputTableInfo>& query_infos,
98  const Data_Namespace::MemoryLevel memory_level,
99  const HashType preferred_hash_type,
100  const int device_count,
101  ColumnCacheMap& column_cache,
102  Executor* executor);
103 
104  static size_t getShardCountForCondition(
105  const Analyzer::BinOper* condition,
106  const Executor* executor,
107  const std::vector<InnerOuter>& inner_outer_pairs);
108 
109  std::string toString(const ExecutorDeviceType device_type,
110  const int device_id = 0,
111  bool raw = false) const override;
112 
113  std::set<DecodedJoinHashBufferEntry> toSet(const ExecutorDeviceType device_type,
114  const int device_id) const override;
115 
116  llvm::Value* codegenSlot(const CompilationOptions&, const size_t) override;
117 
118  HashJoinMatchingSet codegenMatchingSet(const CompilationOptions&,
119  const size_t) override;
120 
121  int getInnerTableId() const noexcept override;
122 
123  int getInnerTableRteIdx() const noexcept override;
124 
125  HashType getHashType() const noexcept override;
126 
127  Data_Namespace::MemoryLevel getMemoryLevel() const noexcept override {
128  return memory_level_;
129  };
130 
131  int getDeviceCount() const noexcept override { return device_count_; };
132 
133  size_t offsetBufferOff() const noexcept override;
134 
135  size_t countBufferOff() const noexcept override;
136 
137  size_t payloadBufferOff() const noexcept override;
138 
139  std::string getHashJoinType() const final { return "Baseline"; }
140 
141  static auto getCacheInvalidator() -> std::function<void()> {
142  return []() -> void {
143  // TODO: make hash type cache part of the main cache
144  CHECK(hash_table_cache_);
145  hash_table_cache_->clear();
147  };
148  }
149 
150  static auto* getHashTableCache() {
151  CHECK(hash_table_cache_);
152  return hash_table_cache_.get();
153  }
154 
156 
157  protected:
158  BaselineJoinHashTable(const std::shared_ptr<Analyzer::BinOper> condition,
159  const std::vector<InputTableInfo>& query_infos,
160  const Data_Namespace::MemoryLevel memory_level,
161  ColumnCacheMap& column_cache,
162  Executor* executor,
163  const std::vector<InnerOuter>& inner_outer_pairs,
164  const int device_count);
165 
166  size_t getComponentBufferSize() const noexcept override;
167 
168  size_t getKeyBufferSize() const noexcept;
169 
170  static int getInnerTableId(const std::vector<InnerOuter>& inner_outer_pairs);
171 
172  virtual void reifyWithLayout(const HashType layout);
173 
174  virtual ColumnsForDevice fetchColumnsForDevice(
175  const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
176  const int device_id,
177  DeviceAllocator* dev_buff_owner);
178 
179  virtual std::pair<size_t, size_t> approximateTupleCount(
180  const std::vector<ColumnsForDevice>&) const;
181 
182  virtual size_t getKeyComponentWidth() const;
183 
184  virtual size_t getKeyComponentCount() const;
185 
186  virtual llvm::Value* codegenKey(const CompilationOptions&);
187 
188  size_t shardCount() const;
189 
190  Data_Namespace::MemoryLevel getEffectiveMemoryLevel(
191  const std::vector<InnerOuter>& inner_outer_pairs) const;
192 
193  void reify(const HashType preferred_layout);
194 
195  virtual void reifyForDevice(const ColumnsForDevice& columns_for_device,
196  const HashType layout,
197  const int device_id,
198  const size_t entry_count,
199  const size_t emitted_keys_count,
200  const logger::ThreadId parent_thread_id);
201 
202  virtual int initHashTableForDevice(
203  const std::vector<JoinColumn>& join_columns,
204  const std::vector<JoinColumnTypeInfo>& join_column_types,
205  const std::vector<JoinBucketInfo>& join_buckets,
206  const HashType layout,
207  const Data_Namespace::MemoryLevel effective_memory_level,
208  const size_t entry_count,
209  const size_t emitted_keys_count,
210  const int device_id);
211 
212  llvm::Value* hashPtr(const size_t index);
213 
214  std::shared_ptr<HashTable> initHashTableOnCpuFromCache(const HashTableCacheKey&);
215 
216  void putHashTableOnCpuToCache(const HashTableCacheKey&,
217  std::shared_ptr<HashTable>& hash_table);
218 
219  std::pair<std::optional<size_t>, size_t> getApproximateTupleCountFromCache(
220  const HashTableCacheKey&) const;
221 
222  bool isBitwiseEq() const;
223 
224  const std::shared_ptr<Analyzer::BinOper> condition_;
225  const std::vector<InputTableInfo>& query_infos_;
227  Executor* executor_;
230 
231  std::vector<InnerOuter> inner_outer_pairs_;
233  const int device_count_;
234 
235  std::optional<HashType>
236  layout_override_; // allows us to use a 1:many hash table for many:many
237 
238  using HashTableCacheValue = std::shared_ptr<HashTable>;
239  static std::unique_ptr<HashTableCache<HashTableCacheKey, HashTableCacheValue>>
241 };
Defines data structures for the semantic analysis phase of query processing.
static std::unique_ptr< HashTableCache< HashTableCacheKey, HashTableCacheValue > > hash_table_cache_
std::string toString(const ExtArgumentType &sig_type)
class for a per-database catalog. also includes metadata for the current database and the current use...
Definition: Catalog.h:101
static std::mutex hash_type_cache_mutex_
ExecutorDeviceType
std::unordered_map< int, std::unordered_map< int, std::shared_ptr< const ColumnarResults > >> ColumnCacheMap
std::shared_ptr< HashTable > HashTableCacheValue
static std::map< std::vector< ChunkKey >, HashType > hash_type_cache_
SQLOps
Definition: sqldefs.h:29
Data_Namespace::MemoryLevel getMemoryLevel() const noexcept override
const std::vector< InputTableInfo > & query_infos_
static auto * getHashTableCache()
std::vector< InnerOuter > inner_outer_pairs_
ColumnCacheMap & column_cache_
std::string getHashJoinType() const final
bool operator==(const struct HashTableCacheKey &that) const
std::optional< HashType > layout_override_
const boost::optional< double > overlaps_hashjoin_bucket_threshold
bool operator<(const struct HashTableCacheKey &that) const
const Catalog_Namespace::Catalog * catalog_
uint64_t ThreadId
Definition: Logger.h:306
const Data_Namespace::MemoryLevel memory_level_
#define CHECK(condition)
Definition: Logger.h:197
int getDeviceCount() const noexcept override
Executor(const ExecutorId id, 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:137
static auto getCacheInvalidator() -> std::function< void()>
HashType
Definition: HashTable.h:19
const std::shared_ptr< Analyzer::BinOper > condition_
const std::vector< ChunkKey > chunk_keys