OmniSciDB  bf83d84833
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
OverlapsJoinHashTable.h
Go to the documentation of this file.
1 /*
2  * Copyright 2018 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 #include "QueryEngine/JoinHashTable/BaselineJoinHashTable.h" // HashTableCacheKey
21 
23  public:
24  OverlapsJoinHashTable(const std::shared_ptr<Analyzer::BinOper> condition,
25  const std::vector<InputTableInfo>& query_infos,
26  const Data_Namespace::MemoryLevel memory_level,
27  HashType hash_layout_type,
28  const size_t entry_count,
29  ColumnCacheMap& column_cache,
30  Executor* executor,
31  const std::vector<InnerOuter>& inner_outer_pairs,
32  const int device_count)
33  : condition_(condition)
34  , query_infos_(query_infos)
35  , memory_level_(memory_level)
36  , executor_(executor)
37  , column_cache_(column_cache)
38  , inner_outer_pairs_(inner_outer_pairs)
39  , device_count_(device_count) {
41  hash_tables_for_device_.resize(std::max(device_count_, 1));
42  }
43 
45 
47  static std::shared_ptr<OverlapsJoinHashTable> getInstance(
48  const std::shared_ptr<Analyzer::BinOper> condition,
49  const std::vector<InputTableInfo>& query_infos,
50  const Data_Namespace::MemoryLevel memory_level,
51  const int device_count,
52  ColumnCacheMap& column_cache,
53  Executor* executor);
54 
55  static auto getCacheInvalidator() -> std::function<void()> {
56  VLOG(1) << "Invalidate " << auto_tuner_cache_.size() << " cached overlaps hashtable.";
57  return []() -> void {
58  std::lock_guard<std::mutex> guard(auto_tuner_cache_mutex_);
59  auto_tuner_cache_.clear();
60  };
61  }
62 
63  protected:
64  void reify(const HashType preferred_layout);
65 
66  void reifyForDevice(const ColumnsForDevice& columns_for_device,
67  const HashType layout,
68  const size_t entry_count,
69  const size_t emitted_keys_count,
70  const int device_id,
71  const logger::ThreadId parent_thread_id);
72 
73  void reifyWithLayout(const HashType layout);
74 
75  std::pair<size_t, size_t> calculateCounts(
76  size_t shard_count,
77  const Fragmenter_Namespace::TableInfo& query_info,
78  std::vector<ColumnsForDevice>& columns_per_device);
79 
80  size_t calculateHashTableSize(size_t number_of_dimensions,
81  size_t emitted_keys_count,
82  size_t entry_count) const;
83 
85  const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
86  const int device_id,
87  DeviceAllocator* dev_buff_owner);
88 
89  std::vector<JoinBucketInfo> computeBucketInfo(
90  const std::vector<JoinColumn>& join_columns,
91  const std::vector<JoinColumnTypeInfo>& join_column_types,
92  const int device_id);
93 
94  std::pair<size_t, size_t> approximateTupleCount(
95  const std::vector<ColumnsForDevice>&) const;
96 
97  size_t getKeyComponentWidth() const;
98 
99  size_t getKeyComponentCount() const;
100 
101  HashType getHashType() const noexcept override {
102  if (layout_override_) {
103  return *layout_override_;
104  }
105  auto hash_table = getHashTableForDevice(0);
106  CHECK(hash_table);
107  return hash_table->getLayout();
108  }
109 
110  Data_Namespace::MemoryLevel getMemoryLevel() const noexcept override {
111  return memory_level_;
112  }
113 
114  int getDeviceCount() const noexcept override { return device_count_; };
115 
116  void initHashTableOnCpu(const std::vector<JoinColumn>& join_columns,
117  const std::vector<JoinColumnTypeInfo>& join_column_types,
118  const std::vector<JoinBucketInfo>& join_bucket_info,
119  const HashType layout,
120  const size_t entry_count,
121  const size_t emitted_keys_count);
122 
124  const size_t) override;
125 
126  std::string toString(const ExecutorDeviceType device_type,
127  const int device_id = 0,
128  bool raw = false) const override;
129 
131  const int device_id) const override;
132 
133  llvm::Value* codegenSlot(const CompilationOptions&, const size_t) override {
134  UNREACHABLE(); // not applicable for overlaps join
135  return nullptr;
136  }
137 
138  static std::map<HashTableCacheKey, double> auto_tuner_cache_;
139  static std::mutex auto_tuner_cache_mutex_;
140 
141  private:
142  size_t getEntryCount() const {
143  auto hash_table = getHashTableForDevice(0);
144  CHECK(hash_table);
145  return hash_table->getEntryCount();
146  }
147 
148  size_t getEmittedKeysCount() const {
149  auto hash_table = getHashTableForDevice(0);
150  CHECK(hash_table);
151  return hash_table->getEmittedKeysCount();
152  }
153 
154  size_t getComponentBufferSize() const noexcept override {
155  CHECK(!hash_tables_for_device_.empty());
156  auto hash_table = hash_tables_for_device_.front();
157  CHECK(hash_table);
158  return hash_table->getEntryCount() * sizeof(int32_t);
159  }
160 
161  size_t shardCount() const {
163  return 0;
164  }
167  }
168 
170  const std::vector<InnerOuter>& inner_outer_pairs) const {
171  return memory_level_;
172  }
173 
174  int getInnerTableId() const noexcept override;
175 
176  int getInnerTableRteIdx() const noexcept override {
177  CHECK(!inner_outer_pairs_.empty());
178  const auto first_inner_col = inner_outer_pairs_.front().first;
179  return first_inner_col->get_rte_idx();
180  }
181 
182  size_t getKeyBufferSize() const noexcept {
183  const auto key_component_width = getKeyComponentWidth();
184  CHECK(key_component_width == 4 || key_component_width == 8);
185  const auto key_component_count = getKeyComponentCount();
187  return getEntryCount() * key_component_count * key_component_width;
188  } else {
189  return getEntryCount() * (key_component_count + 1) * key_component_width;
190  }
191  }
192 
193  size_t offsetBufferOff() const noexcept override { return getKeyBufferSize(); }
194 
195  size_t countBufferOff() const noexcept override {
198  } else {
199  return getKeyBufferSize();
200  }
201  }
202 
203  size_t payloadBufferOff() const noexcept override {
206  } else {
207  return getKeyBufferSize();
208  }
209  }
210 
211  std::string getHashJoinType() const final { return "Overlaps"; }
212 
213  std::shared_ptr<HashTable> initHashTableOnCpuFromCache(const HashTableCacheKey& key);
214 
215  std::pair<std::optional<size_t>, size_t> getApproximateTupleCountFromCache(
216  const HashTableCacheKey&) const;
217 
219  std::shared_ptr<HashTable>& hash_table);
220 
221  void computeBucketSizes(std::vector<double>& bucket_sizes_for_dimension,
222  const JoinColumn& join_column,
223  const JoinColumnTypeInfo& join_column_type,
224  const std::vector<InnerOuter>& inner_outer_pairs);
225 
226  llvm::Value* codegenKey(const CompilationOptions&);
227  std::vector<llvm::Value*> codegenManyKey(const CompilationOptions&);
228 
229  const std::shared_ptr<Analyzer::BinOper> condition_;
230  const std::vector<InputTableInfo>& query_infos_;
232 
233  Executor* executor_;
235 
236  std::vector<InnerOuter> inner_outer_pairs_;
237  const int device_count_;
238 
239  std::vector<double> bucket_sizes_for_dimension_;
241 
242  std::optional<HashType>
243  layout_override_; // allows us to use a 1:many hash table for many:many
244 
245  using HashTableCacheValue = std::shared_ptr<HashTable>;
246  static std::unique_ptr<HashTableCache<HashTableCacheKey, HashTableCacheValue>>
248 };
llvm::Value * codegenKey(const CompilationOptions &)
std::shared_ptr< HashTable > initHashTableOnCpuFromCache(const HashTableCacheKey &key)
static std::unique_ptr< HashTableCache< HashTableCacheKey, HashTableCacheValue > > hash_table_cache_
std::vector< double > bucket_sizes_for_dimension_
int getInnerTableId() const noexceptoverride
void reifyWithLayout(const HashType layout)
std::string toString(const ExecutorDeviceType device_type, const int device_id=0, bool raw=false) const override
ExecutorDeviceType
static std::mutex auto_tuner_cache_mutex_
std::string getHashJoinType() const final
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 int device_count, ColumnCacheMap &column_cache, Executor *executor)
Make hash table from an in-flight SQL query&#39;s parse tree etc.
void reifyForDevice(const ColumnsForDevice &columns_for_device, const HashType layout, const size_t entry_count, const size_t emitted_keys_count, const int device_id, const logger::ThreadId parent_thread_id)
int getInnerTableRteIdx() const noexceptoverride
std::pair< size_t, size_t > calculateCounts(size_t shard_count, const Fragmenter_Namespace::TableInfo &query_info, std::vector< ColumnsForDevice > &columns_per_device)
std::vector< std::shared_ptr< HashTable > > hash_tables_for_device_
Definition: HashJoin.h:257
#define UNREACHABLE()
Definition: Logger.h:241
void 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)
Data_Namespace::MemoryLevel getMemoryLevel() const noexceptoverride
#define CHECK_GT(x, y)
Definition: Logger.h:209
HashType getHashType() const noexceptoverride
size_t calculateHashTableSize(size_t number_of_dimensions, size_t emitted_keys_count, size_t entry_count) const
const std::shared_ptr< Analyzer::BinOper > condition_
int getDeviceCount() const noexceptoverride
std::vector< JoinBucketInfo > computeBucketInfo(const std::vector< JoinColumn > &join_columns, const std::vector< JoinColumnTypeInfo > &join_column_types, const int device_id)
void reify(const HashType preferred_layout)
void computeBucketSizes(std::vector< double > &bucket_sizes_for_dimension, const JoinColumn &join_column, const JoinColumnTypeInfo &join_column_type, const std::vector< InnerOuter > &inner_outer_pairs)
ColumnCacheMap & column_cache_
const std::vector< InputTableInfo > & query_infos_
size_t payloadBufferOff() const noexceptoverride
DecodedJoinHashBufferSet toSet(const ExecutorDeviceType device_type, const int device_id) const override
void putHashTableOnCpuToCache(const HashTableCacheKey &key, std::shared_ptr< HashTable > &hash_table)
static std::map< HashTableCacheKey, double > auto_tuner_cache_
std::vector< llvm::Value * > codegenManyKey(const CompilationOptions &)
std::shared_ptr< HashTable > HashTableCacheValue
std::unordered_map< int, std::unordered_map< int, std::shared_ptr< const ColumnarResults >>> ColumnCacheMap
HashTable * getHashTableForDevice(const size_t device_id) const
Definition: HashJoin.h:202
std::optional< HashType > layout_override_
llvm::Value * codegenSlot(const CompilationOptions &, const size_t) override
std::set< DecodedJoinHashBufferEntry > DecodedJoinHashBufferSet
Definition: HashTable.h:34
ColumnsForDevice fetchColumnsForDevice(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments, const int device_id, DeviceAllocator *dev_buff_owner)
size_t getKeyComponentCount() const
HashJoinMatchingSet codegenMatchingSet(const CompilationOptions &, const size_t) override
uint64_t ThreadId
Definition: Logger.h:306
size_t offsetBufferOff() const noexceptoverride
size_t countBufferOff() const noexceptoverride
std::pair< std::optional< size_t >, size_t > getApproximateTupleCountFromCache(const HashTableCacheKey &) const
#define CHECK(condition)
Definition: Logger.h:197
std::pair< size_t, size_t > approximateTupleCount(const std::vector< ColumnsForDevice > &) const
const Data_Namespace::MemoryLevel memory_level_
size_t getEmittedKeysCount() const
size_t getComponentBufferSize() const noexceptoverride
std::vector< InnerOuter > inner_outer_pairs_
static auto getCacheInvalidator() -> std::function< void()>
static size_t getShardCountForCondition(const Analyzer::BinOper *condition, const Executor *executor, const std::vector< InnerOuter > &inner_outer_pairs)
Data_Namespace::MemoryLevel getEffectiveMemoryLevel(const std::vector< InnerOuter > &inner_outer_pairs) const
OverlapsJoinHashTable(const std::shared_ptr< Analyzer::BinOper > condition, const std::vector< InputTableInfo > &query_infos, const Data_Namespace::MemoryLevel memory_level, HashType hash_layout_type, const size_t entry_count, ColumnCacheMap &column_cache, Executor *executor, const std::vector< InnerOuter > &inner_outer_pairs, const int device_count)
size_t getKeyComponentWidth() const
HashType
Definition: HashTable.h:19
#define VLOG(n)
Definition: Logger.h:291
size_t getKeyBufferSize() const noexcept
static bool layoutRequiresAdditionalBuffers(HashType layout) noexcept
Definition: HashJoin.h:118