OmniSciDB  a987f07e93
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
OverlapsJoinHashTable.cpp
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 
18 
21 #include "QueryEngine/Execute.h"
29 
30 std::unique_ptr<HashtableRecycler> OverlapsJoinHashTable::hash_table_cache_ =
31  std::make_unique<HashtableRecycler>(CacheItemType::OVERLAPS_HT,
33 std::unique_ptr<OverlapsTuningParamRecycler> OverlapsJoinHashTable::auto_tuner_cache_ =
34  std::make_unique<OverlapsTuningParamRecycler>();
35 
37 std::shared_ptr<OverlapsJoinHashTable> OverlapsJoinHashTable::getInstance(
38  const std::shared_ptr<Analyzer::BinOper> condition,
39  const std::vector<InputTableInfo>& query_infos,
40  const Data_Namespace::MemoryLevel memory_level,
41  const JoinType join_type,
42  const int device_count,
43  ColumnCacheMap& column_cache,
44  Executor* executor,
45  const HashTableBuildDagMap& hashtable_build_dag_map,
46  const RegisteredQueryHint& query_hints,
47  const TableIdToNodeMap& table_id_to_node_map) {
48  decltype(std::chrono::steady_clock::now()) ts1, ts2;
49 
50  std::vector<InnerOuter> inner_outer_pairs;
51 
52  if (const auto range_expr =
53  dynamic_cast<const Analyzer::RangeOper*>(condition->get_right_operand())) {
54  return RangeJoinHashTable::getInstance(condition,
55  range_expr,
56  query_infos,
57  memory_level,
58  join_type,
59  device_count,
60  column_cache,
61  executor,
62  hashtable_build_dag_map,
63  query_hints,
64  table_id_to_node_map);
65  } else {
66  inner_outer_pairs =
68  condition.get(), *executor->getCatalog(), executor->getTemporaryTables())
69  .first;
70  }
71  CHECK(!inner_outer_pairs.empty());
72 
73  const auto getHashTableType =
74  [](const std::shared_ptr<Analyzer::BinOper> condition,
75  const std::vector<InnerOuter>& inner_outer_pairs) -> HashType {
77  if (condition->is_overlaps_oper()) {
78  CHECK_EQ(inner_outer_pairs.size(), size_t(1));
79  if (inner_outer_pairs[0].first->get_type_info().is_array() &&
80  inner_outer_pairs[0].second->get_type_info().is_array() &&
81  // Bounds vs constructed points, former should yield ManyToMany
82  inner_outer_pairs[0].second->get_type_info().get_size() == 32) {
83  layout = HashType::ManyToMany;
84  }
85  }
86  return layout;
87  };
88 
89  const auto layout = getHashTableType(condition, inner_outer_pairs);
90 
91  if (VLOGGING(1)) {
92  VLOG(1) << "Building geo hash table " << getHashTypeString(layout)
93  << " for qual: " << condition->toString();
94  ts1 = std::chrono::steady_clock::now();
95  }
96 
97  const auto qi_0 = query_infos[0].info.getNumTuplesUpperBound();
98  const auto qi_1 = query_infos[1].info.getNumTuplesUpperBound();
99 
100  VLOG(1) << "table_id = " << query_infos[0].table_id << " has " << qi_0 << " tuples.";
101  VLOG(1) << "table_id = " << query_infos[1].table_id << " has " << qi_1 << " tuples.";
102 
103  const auto& query_info =
104  get_inner_query_info(HashJoin::getInnerTableId(inner_outer_pairs), query_infos)
105  .info;
106  const auto total_entries = 2 * query_info.getNumTuplesUpperBound();
107  if (total_entries > static_cast<size_t>(std::numeric_limits<int32_t>::max())) {
108  throw TooManyHashEntries();
109  }
110 
111  auto join_hash_table = std::make_shared<OverlapsJoinHashTable>(condition,
112  join_type,
113  query_infos,
114  memory_level,
115  column_cache,
116  executor,
117  inner_outer_pairs,
118  device_count,
119  query_hints,
120  hashtable_build_dag_map,
121  table_id_to_node_map);
122  try {
123  join_hash_table->reify(layout);
124  } catch (const HashJoinFail& e) {
125  throw HashJoinFail(std::string("Could not build a 1-to-1 correspondence for columns "
126  "involved in overlaps join | ") +
127  e.what());
128  } catch (const ColumnarConversionNotSupported& e) {
129  throw HashJoinFail(std::string("Could not build hash tables for overlaps join | "
130  "Inner table too big. Attempt manual table reordering "
131  "or create a single fragment inner table. | ") +
132  e.what());
133  } catch (const JoinHashTableTooBig& e) {
134  throw e;
135  } catch (const std::exception& e) {
136  throw HashJoinFail(std::string("Failed to build hash tables for overlaps join | ") +
137  e.what());
138  }
139  if (VLOGGING(1)) {
140  ts2 = std::chrono::steady_clock::now();
141  VLOG(1) << "Built geo hash table " << getHashTypeString(layout) << " in "
142  << std::chrono::duration_cast<std::chrono::milliseconds>(ts2 - ts1).count()
143  << " ms";
144  }
145  return join_hash_table;
146 }
147 
148 namespace {
149 
151  const std::vector<double>& bucket_sizes,
152  const std::vector<double>& bucket_thresholds,
153  const double initial_value) {
154  std::vector<double> corrected_bucket_sizes(bucket_sizes);
155  for (size_t i = 0; i != bucket_sizes.size(); ++i) {
156  if (bucket_sizes[i] == initial_value) {
157  corrected_bucket_sizes[i] = bucket_thresholds[i];
158  }
159  }
160  return corrected_bucket_sizes;
161 }
162 
163 std::vector<double> compute_bucket_sizes(
164  const std::vector<double>& bucket_thresholds,
165  const Data_Namespace::MemoryLevel effective_memory_level,
166  const JoinColumn& join_column,
167  const JoinColumnTypeInfo& join_column_type,
168  const std::vector<InnerOuter>& inner_outer_pairs,
169  const Executor* executor) {
170  // No coalesced keys for overlaps joins yet
171  CHECK_EQ(inner_outer_pairs.size(), 1u);
172 
173  const auto col = inner_outer_pairs[0].first;
174  CHECK(col);
175  const auto col_ti = col->get_type_info();
176  CHECK(col_ti.is_array());
177 
178  // TODO: Compute the number of dimensions for this overlaps key
179  const size_t num_dims{2};
180  const double initial_bin_value{0.0};
181  std::vector<double> bucket_sizes(num_dims, initial_bin_value);
182  CHECK_EQ(bucket_thresholds.size(), num_dims);
183 
184  VLOG(1)
185  << "Computing x and y bucket sizes for overlaps hash join with maximum bucket size "
186  << std::to_string(bucket_thresholds[0]) << ", "
187  << std::to_string(bucket_thresholds[1]);
188 
189  if (effective_memory_level == Data_Namespace::MemoryLevel::CPU_LEVEL) {
190  const int thread_count = cpu_threads();
192  bucket_sizes, join_column, join_column_type, bucket_thresholds, thread_count);
193  }
194 #ifdef HAVE_CUDA
195  else {
196  // Note that we compute the bucket sizes using only a single GPU
197  const int device_id = 0;
198  auto data_mgr = executor->getDataMgr();
199  CudaAllocator allocator(
200  data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id));
201  auto device_bucket_sizes_gpu =
202  transfer_vector_of_flat_objects_to_gpu(bucket_sizes, allocator);
203  auto join_column_gpu = transfer_flat_object_to_gpu(join_column, allocator);
204  auto join_column_type_gpu = transfer_flat_object_to_gpu(join_column_type, allocator);
205  auto device_bucket_thresholds_gpu =
206  transfer_vector_of_flat_objects_to_gpu(bucket_thresholds, allocator);
207 
208  compute_bucket_sizes_on_device(device_bucket_sizes_gpu,
209  join_column_gpu,
210  join_column_type_gpu,
211  device_bucket_thresholds_gpu);
212  allocator.copyFromDevice(reinterpret_cast<int8_t*>(bucket_sizes.data()),
213  reinterpret_cast<int8_t*>(device_bucket_sizes_gpu),
214  bucket_sizes.size() * sizeof(double));
215  }
216 #endif
217  const auto corrected_bucket_sizes = correct_uninitialized_bucket_sizes_to_thresholds(
218  bucket_sizes, bucket_thresholds, initial_bin_value);
219 
220  VLOG(1) << "Computed x and y bucket sizes for overlaps hash join: ("
221  << corrected_bucket_sizes[0] << ", " << corrected_bucket_sizes[1] << ")";
222 
223  return corrected_bucket_sizes;
224 }
225 
227  HashTableProps(const size_t entry_count,
228  const size_t emitted_keys_count,
229  const size_t hash_table_size,
230  const std::vector<double>& bucket_sizes)
231  : entry_count(entry_count)
232  , emitted_keys_count(emitted_keys_count)
233  , keys_per_bin(entry_count == 0 ? std::numeric_limits<double>::max()
234  : emitted_keys_count / (entry_count / 2.0))
235  , hash_table_size(hash_table_size)
236  , bucket_sizes(bucket_sizes) {}
237 
238  static HashTableProps invalid() { return HashTableProps(0, 0, 0, {}); }
239 
240  size_t entry_count;
242  double keys_per_bin;
244  std::vector<double> bucket_sizes;
245 };
246 
247 std::ostream& operator<<(std::ostream& os, const HashTableProps& props) {
248  os << " entry_count: " << props.entry_count << ", emitted_keys "
249  << props.emitted_keys_count << ", hash table size " << props.hash_table_size
250  << ", keys per bin " << props.keys_per_bin;
251  return os;
252 }
253 
254 struct TuningState {
255  TuningState(const size_t overlaps_max_table_size_bytes,
256  const double overlaps_target_entries_per_bin)
257  : crt_props(HashTableProps::invalid())
258  , prev_props(HashTableProps::invalid())
259  , chosen_overlaps_threshold(-1)
260  , crt_step(0)
261  , crt_reverse_search_iteration(0)
262  , overlaps_max_table_size_bytes(overlaps_max_table_size_bytes)
263  , overlaps_target_entries_per_bin(overlaps_target_entries_per_bin) {}
264 
265  // current and previous props, allows for easy backtracking
268 
269  // value we are tuning for
271  enum class TuningDirection { SMALLER, LARGER };
272  TuningDirection tuning_direction{TuningDirection::SMALLER};
273 
274  // various constants / state
275  size_t crt_step; // 1 indexed
276  size_t crt_reverse_search_iteration; // 1 indexed
279  const size_t max_reverse_search_iterations{8};
280 
285  bool operator()(const HashTableProps& new_props, const bool new_overlaps_threshold) {
286  prev_props = crt_props;
287  crt_props = new_props;
288  crt_step++;
289 
290  if (hashTableTooBig() || keysPerBinIncreasing()) {
291  if (hashTableTooBig()) {
292  VLOG(1) << "Reached hash table size limit: " << overlaps_max_table_size_bytes
293  << " with " << crt_props.hash_table_size << " byte hash table, "
294  << crt_props.keys_per_bin << " keys per bin.";
295  } else if (keysPerBinIncreasing()) {
296  VLOG(1) << "Keys per bin increasing from " << prev_props.keys_per_bin << " to "
297  << crt_props.keys_per_bin;
298  CHECK(previousIterationValid());
299  }
300  if (previousIterationValid()) {
301  VLOG(1) << "Using previous threshold value " << chosen_overlaps_threshold;
302  crt_props = prev_props;
303  return false;
304  } else {
305  CHECK(hashTableTooBig());
306  crt_reverse_search_iteration++;
307  chosen_overlaps_threshold = new_overlaps_threshold;
308 
309  if (crt_reverse_search_iteration == max_reverse_search_iterations) {
310  VLOG(1) << "Hit maximum number (" << max_reverse_search_iterations
311  << ") of reverse tuning iterations. Aborting tuning";
312  // use the crt props, but don't bother trying to tune any farther
313  return false;
314  }
315 
316  if (crt_reverse_search_iteration > 1 &&
317  crt_props.hash_table_size == prev_props.hash_table_size) {
318  // hash table size is not changing, bail
319  VLOG(1) << "Hash table size not decreasing (" << crt_props.hash_table_size
320  << " bytes) and still above maximum allowed size ("
321  << overlaps_max_table_size_bytes << " bytes). Aborting tuning";
322  return false;
323  }
324 
325  // if the hash table is too big on the very first step, change direction towards
326  // larger bins to see if a slightly smaller hash table will fit
327  if (crt_step == 1 && crt_reverse_search_iteration == 1) {
328  VLOG(1)
329  << "First iteration of overlaps tuning led to hash table size over "
330  "limit. Reversing search to try larger bin sizes (previous threshold: "
331  << chosen_overlaps_threshold << ")";
332  // Need to change direction of tuning to tune "up" towards larger bins
333  tuning_direction = TuningDirection::LARGER;
334  }
335  return true;
336  }
337  UNREACHABLE();
338  }
339 
340  chosen_overlaps_threshold = new_overlaps_threshold;
341 
342  if (keysPerBinUnderThreshold()) {
343  VLOG(1) << "Hash table reached size " << crt_props.hash_table_size
344  << " with keys per bin " << crt_props.keys_per_bin << " under threshold "
345  << overlaps_target_entries_per_bin << ". Terminating bucket size loop.";
346  return false;
347  }
348 
349  if (crt_reverse_search_iteration > 0) {
350  // We always take the first tuning iteration that succeeds when reversing
351  // direction, as if we're here we haven't had a successful iteration and we're
352  // "backtracking" our search by making bin sizes larger
353  VLOG(1) << "On reverse (larger tuning direction) search found workable "
354  << " hash table size of " << crt_props.hash_table_size
355  << " with keys per bin " << crt_props.keys_per_bin
356  << ". Terminating bucket size loop.";
357  return false;
358  }
359 
360  return true;
361  }
362 
363  bool hashTableTooBig() const {
364  return crt_props.hash_table_size > overlaps_max_table_size_bytes;
365  }
366 
367  bool keysPerBinIncreasing() const {
368  return crt_props.keys_per_bin > prev_props.keys_per_bin;
369  }
370 
371  bool previousIterationValid() const {
372  return tuning_direction == TuningDirection::SMALLER && crt_step > 1;
373  }
374 
376  return crt_props.keys_per_bin < overlaps_target_entries_per_bin;
377  }
378 };
379 
381  public:
382  BucketSizeTuner(const double bucket_threshold,
383  const double step,
384  const double min_threshold,
385  const Data_Namespace::MemoryLevel effective_memory_level,
386  const std::vector<ColumnsForDevice>& columns_per_device,
387  const std::vector<InnerOuter>& inner_outer_pairs,
388  const size_t table_tuple_count,
389  const Executor* executor)
390  : num_dims_(2) // Todo: allow varying number of dims
391  , bucket_thresholds_(/*count=*/num_dims_, /*value=*/bucket_threshold)
392  , step_(step)
393  , min_threshold_(min_threshold)
394  , effective_memory_level_(effective_memory_level)
395  , columns_per_device_(columns_per_device)
396  , inner_outer_pairs_(inner_outer_pairs)
397  , table_tuple_count_(table_tuple_count)
398  , executor_(executor) {
399  CHECK(!columns_per_device_.empty());
400  }
401 
402  bool tuneOneStep() { return tuneOneStep(TuningState::TuningDirection::SMALLER, step_); }
403 
404  bool tuneOneStep(const TuningState::TuningDirection tuning_direction) {
405  return tuneOneStep(tuning_direction, step_);
406  }
407 
408  bool tuneOneStep(const TuningState::TuningDirection tuning_direction,
409  const double step_overide) {
410  if (table_tuple_count_ == 0) {
411  return false;
412  }
413  if (tuning_direction == TuningState::TuningDirection::SMALLER) {
414  return tuneSmallerOneStep(step_overide);
415  }
416  return tuneLargerOneStep(step_overide);
417  }
418 
419  auto getMinBucketSize() const {
420  return *std::min_element(bucket_thresholds_.begin(), bucket_thresholds_.end());
421  }
422 
429  std::vector<double> getInverseBucketSizes() {
430  if (num_steps_ == 0) {
431  CHECK_EQ(current_bucket_sizes_.size(), static_cast<size_t>(0));
432  current_bucket_sizes_ = computeBucketSizes();
433  }
434  CHECK_EQ(current_bucket_sizes_.size(), num_dims_);
435  std::vector<double> inverse_bucket_sizes;
436  for (const auto s : current_bucket_sizes_) {
437  inverse_bucket_sizes.emplace_back(1.0 / s);
438  }
439  return inverse_bucket_sizes;
440  }
441 
442  private:
444  for (const auto& t : bucket_thresholds_) {
445  if (t < min_threshold_) {
446  return true;
447  }
448  }
449  return false;
450  }
451 
452  std::vector<double> computeBucketSizes() const {
453  if (table_tuple_count_ == 0) {
454  return std::vector<double>(/*count=*/num_dims_, /*val=*/0);
455  }
456  return compute_bucket_sizes(bucket_thresholds_,
457  effective_memory_level_,
458  columns_per_device_.front().join_columns[0],
459  columns_per_device_.front().join_column_types[0],
460  inner_outer_pairs_,
461  executor_);
462  }
463 
464  bool tuneSmallerOneStep(const double step_overide) {
465  if (!current_bucket_sizes_.empty()) {
466  CHECK_EQ(current_bucket_sizes_.size(), bucket_thresholds_.size());
467  bucket_thresholds_ = current_bucket_sizes_;
468  for (auto& t : bucket_thresholds_) {
469  t /= step_overide;
470  }
471  }
472  if (bucketThresholdsBelowMinThreshold()) {
473  VLOG(1) << "Aborting overlaps tuning as at least one bucket size is below min "
474  "threshold";
475  return false;
476  }
477  const auto next_bucket_sizes = computeBucketSizes();
478  if (next_bucket_sizes == current_bucket_sizes_) {
479  VLOG(1) << "Aborting overlaps tuning as bucket size is no longer changing.";
480  return false;
481  }
482 
483  current_bucket_sizes_ = next_bucket_sizes;
484  num_steps_++;
485  return true;
486  }
487 
488  bool tuneLargerOneStep(const double step_overide) {
489  if (!current_bucket_sizes_.empty()) {
490  CHECK_EQ(current_bucket_sizes_.size(), bucket_thresholds_.size());
491  bucket_thresholds_ = current_bucket_sizes_;
492  }
493  // If current_bucket_sizes was empty, we will start from our initial threshold
494  for (auto& t : bucket_thresholds_) {
495  t *= step_overide;
496  }
497  // When tuning up, do not dynamically compute bucket_sizes, as compute_bucket_sizes as
498  // written will pick the largest bin size below the threshold, meaning our bucket_size
499  // will never increase beyond the size of the largest polygon. This could mean that we
500  // can never make the bucket sizes large enough to get our hash table below the
501  // maximum size Possible todo: enable templated version of compute_bucket_sizes that
502  // allows for optionally finding smallest extent above threshold, to mirror default
503  // behavior finding largest extent below threshold, and use former variant here
504  current_bucket_sizes_ = bucket_thresholds_;
505  num_steps_++;
506  return true;
507  }
508 
509  size_t num_dims_;
510  std::vector<double> bucket_thresholds_;
511  size_t num_steps_{0};
512  const double step_;
513  const double min_threshold_;
515  const std::vector<ColumnsForDevice>& columns_per_device_;
516  const std::vector<InnerOuter>& inner_outer_pairs_;
517  const size_t table_tuple_count_;
518  const Executor* executor_;
519 
520  std::vector<double> current_bucket_sizes_;
521 
522  friend std::ostream& operator<<(std::ostream& os, const BucketSizeTuner& tuner);
523 };
524 
525 std::ostream& operator<<(std::ostream& os, const BucketSizeTuner& tuner) {
526  os << "Step Num: " << tuner.num_steps_ << ", Threshold: " << std::fixed << "("
527  << tuner.bucket_thresholds_[0] << ", " << tuner.bucket_thresholds_[1] << ")"
528  << ", Step Size: " << std::fixed << tuner.step_ << ", Min: " << std::fixed
529  << tuner.min_threshold_;
530  return os;
531 }
532 
533 } // namespace
534 
536  auto timer = DEBUG_TIMER(__func__);
538  const auto& query_info =
540  .info;
541  VLOG(1) << "Reify with layout " << getHashTypeString(layout)
542  << "for table_id: " << HashJoin::getInnerTableId(inner_outer_pairs_);
543  if (query_info.fragments.empty()) {
544  return;
545  }
546 
547  auto overlaps_max_table_size_bytes = g_overlaps_max_table_size_bytes;
548  std::optional<double> overlaps_threshold_override;
549  double overlaps_target_entries_per_bin = g_overlaps_target_entries_per_bin;
550  auto skip_hashtable_caching = false;
552  VLOG(1) << "Setting overlaps bucket threshold "
553  "\'overlaps_hashjoin_bucket_threshold\' via "
554  "query hint: "
556  overlaps_threshold_override = query_hints_.overlaps_bucket_threshold;
557  }
559  std::ostringstream oss;
560  oss << "User requests to change a threshold \'overlaps_max_table_size_bytes\' via "
561  "query hint";
562  if (!overlaps_threshold_override.has_value()) {
563  oss << ": " << overlaps_max_table_size_bytes << " -> "
565  overlaps_max_table_size_bytes = query_hints_.overlaps_max_size;
566  } else {
567  oss << ", but is skipped since the query hint also changes the threshold "
568  "\'overlaps_hashjoin_bucket_threshold\'";
569  }
570  VLOG(1) << oss.str();
571  }
573  VLOG(1) << "User requests to skip caching overlaps join hashtable and its tuned "
574  "parameters for this query";
575  skip_hashtable_caching = true;
576  }
578  VLOG(1) << "User requests to change a threshold \'overlaps_keys_per_bin\' via query "
579  "hint: "
580  << overlaps_target_entries_per_bin << " -> "
582  overlaps_target_entries_per_bin = query_hints_.overlaps_keys_per_bin;
583  }
584 
585  auto data_mgr = executor_->getDataMgr();
586  // we prioritize CPU when building an overlaps join hashtable, but if we have GPU and
587  // user-given hint is given we selectively allow GPU to build it but even if we have GPU
588  // but user foces to set CPU as execution device type we should not allow to use GPU for
589  // building it
590  auto allow_gpu_hashtable_build =
593  if (allow_gpu_hashtable_build) {
594  if (data_mgr->gpusPresent() &&
596  VLOG(1) << "A user forces to build GPU hash table for this overlaps join operator";
597  } else {
598  allow_gpu_hashtable_build = false;
599  VLOG(1) << "A user forces to build GPU hash table for this overlaps join operator "
600  "but we "
601  "skip it since either GPU is not presented or CPU execution mode is set";
602  }
603  }
604 
605  std::vector<ColumnsForDevice> columns_per_device;
606  std::vector<std::unique_ptr<CudaAllocator>> dev_buff_owners;
608  allow_gpu_hashtable_build) {
609  for (int device_id = 0; device_id < device_count_; ++device_id) {
610  dev_buff_owners.emplace_back(std::make_unique<CudaAllocator>(
611  data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id)));
612  }
613  }
614 
615  std::vector<std::vector<Fragmenter_Namespace::FragmentInfo>> fragments_per_device;
616  const auto shard_count = shardCount();
617  size_t total_num_tuples = 0;
618  for (int device_id = 0; device_id < device_count_; ++device_id) {
619  fragments_per_device.emplace_back(
620  shard_count
621  ? only_shards_for_device(query_info.fragments, device_id, device_count_)
622  : query_info.fragments);
623  const size_t crt_num_tuples =
624  std::accumulate(fragments_per_device.back().begin(),
625  fragments_per_device.back().end(),
626  size_t(0),
627  [](const auto& sum, const auto& fragment) {
628  return sum + fragment.getNumTuples();
629  });
630  total_num_tuples += crt_num_tuples;
631  const auto columns_for_device =
632  fetchColumnsForDevice(fragments_per_device.back(),
633  device_id,
635  allow_gpu_hashtable_build
636  ? dev_buff_owners[device_id].get()
637  : nullptr);
638  columns_per_device.push_back(columns_for_device);
639  }
640 
641  // try to extract cache key for hash table and its relevant info
642  auto hashtable_access_path_info =
644  {},
645  condition_->get_optype(),
646  join_type_,
649  shard_count,
650  fragments_per_device,
651  executor_);
652  hashtable_cache_key_ = hashtable_access_path_info.hashed_query_plan_dag;
653  hashtable_cache_meta_info_ = hashtable_access_path_info.meta_info;
654  table_keys_ = hashtable_access_path_info.table_keys;
655 
656  auto get_inner_table_id = [this]() {
657  return inner_outer_pairs_.front().first->get_table_id();
658  };
659 
660  if (table_keys_.empty()) {
663  executor_->getCatalog()->getDatabaseId(),
664  get_inner_table_id());
665  }
666  CHECK(!table_keys_.empty());
667 
668  if (overlaps_threshold_override) {
669  // compute bucket sizes based on the user provided threshold
670  BucketSizeTuner tuner(/*initial_threshold=*/*overlaps_threshold_override,
671  /*step=*/1.0,
672  /*min_threshold=*/0.0,
674  columns_per_device,
676  total_num_tuples,
677  executor_);
678  const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
679 
680  auto [entry_count, emitted_keys_count] =
681  computeHashTableCounts(shard_count,
682  inverse_bucket_sizes,
683  columns_per_device,
684  overlaps_max_table_size_bytes,
685  *overlaps_threshold_override);
686  setInverseBucketSizeInfo(inverse_bucket_sizes, columns_per_device, device_count_);
687  // reifyImpl will check the hash table cache for an appropriate hash table w/ those
688  // bucket sizes (or within tolerances) if a hash table exists use it, otherwise build
689  // one
690  generateCacheKey(overlaps_max_table_size_bytes,
691  *overlaps_threshold_override,
692  inverse_bucket_sizes,
693  fragments_per_device,
694  device_count_);
695  reifyImpl(columns_per_device,
696  query_info,
697  layout,
698  shard_count,
699  entry_count,
700  emitted_keys_count,
701  skip_hashtable_caching,
702  overlaps_max_table_size_bytes,
703  *overlaps_threshold_override);
704  } else {
705  double overlaps_bucket_threshold = std::numeric_limits<double>::max();
706  generateCacheKey(overlaps_max_table_size_bytes,
707  overlaps_bucket_threshold,
708  {},
709  fragments_per_device,
710  device_count_);
711  std::vector<size_t> per_device_chunk_key;
712  if (HashtableRecycler::isInvalidHashTableCacheKey(hashtable_cache_key_) &&
713  get_inner_table_id() > 0) {
714  for (int device_id = 0; device_id < device_count_; ++device_id) {
715  auto chunk_key_hash = boost::hash_value(composite_key_info_.cache_key_chunks);
716  boost::hash_combine(
717  chunk_key_hash,
718  HashJoin::collectFragmentIds(fragments_per_device[device_id]));
719  per_device_chunk_key.push_back(chunk_key_hash);
722  columns_per_device.front().join_columns.front().num_elems,
723  chunk_key_hash,
724  condition_->get_optype(),
725  overlaps_max_table_size_bytes,
726  overlaps_bucket_threshold,
727  {}};
728  hashtable_cache_key_[device_id] = getAlternativeCacheKey(cache_key);
729  hash_table_cache_->addQueryPlanDagForTableKeys(hashtable_cache_key_[device_id],
730  table_keys_);
731  }
732  }
733 
734  auto cached_bucket_threshold =
735  auto_tuner_cache_->getItemFromCache(hashtable_cache_key_.front(),
738  if (cached_bucket_threshold) {
739  overlaps_bucket_threshold = cached_bucket_threshold->bucket_threshold;
740  auto inverse_bucket_sizes = cached_bucket_threshold->bucket_sizes;
742  overlaps_max_table_size_bytes, overlaps_bucket_threshold, inverse_bucket_sizes);
743  generateCacheKey(overlaps_max_table_size_bytes,
744  overlaps_bucket_threshold,
745  inverse_bucket_sizes,
746  fragments_per_device,
747  device_count_);
748 
749  if (auto hash_table =
750  hash_table_cache_->getItemFromCache(hashtable_cache_key_[device_count_],
753  std::nullopt)) {
754  // if we already have a built hash table, we can skip the scans required for
755  // computing bucket size and tuple count
756  // reset as the hash table sizes can vary a bit
757  setInverseBucketSizeInfo(inverse_bucket_sizes, columns_per_device, device_count_);
758  CHECK(hash_table);
759 
760  VLOG(1) << "Using cached hash table bucket size";
761 
762  reifyImpl(columns_per_device,
763  query_info,
764  layout,
765  shard_count,
766  hash_table->getEntryCount(),
767  hash_table->getEmittedKeysCount(),
768  skip_hashtable_caching,
769  overlaps_max_table_size_bytes,
770  overlaps_bucket_threshold);
771  } else {
772  VLOG(1) << "Computing bucket size for cached bucket threshold";
773  // compute bucket size using our cached tuner value
774  BucketSizeTuner tuner(/*initial_threshold=*/overlaps_bucket_threshold,
775  /*step=*/1.0,
776  /*min_threshold=*/0.0,
778  columns_per_device,
780  total_num_tuples,
781  executor_);
782 
783  const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
784 
785  auto [entry_count, emitted_keys_count] =
786  computeHashTableCounts(shard_count,
787  inverse_bucket_sizes,
788  columns_per_device,
789  overlaps_max_table_size_bytes,
790  overlaps_bucket_threshold);
791  setInverseBucketSizeInfo(inverse_bucket_sizes, columns_per_device, device_count_);
792 
793  generateCacheKey(overlaps_max_table_size_bytes,
794  overlaps_bucket_threshold,
795  inverse_bucket_sizes,
796  fragments_per_device,
797  device_count_);
798 
799  reifyImpl(columns_per_device,
800  query_info,
801  layout,
802  shard_count,
803  entry_count,
804  emitted_keys_count,
805  skip_hashtable_caching,
806  overlaps_max_table_size_bytes,
807  overlaps_bucket_threshold);
808  }
809  } else {
810  // compute bucket size using the auto tuner
811  BucketSizeTuner tuner(
812  /*initial_threshold=*/overlaps_bucket_threshold,
813  /*step=*/2.0,
814  /*min_threshold=*/1e-7,
816  columns_per_device,
818  total_num_tuples,
819  executor_);
820 
821  VLOG(1) << "Running overlaps join size auto tune with parameters: " << tuner;
822 
823  // manages the tuning state machine
824  TuningState tuning_state(overlaps_max_table_size_bytes,
825  overlaps_target_entries_per_bin);
826  while (tuner.tuneOneStep(tuning_state.tuning_direction)) {
827  const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
828 
829  const auto [crt_entry_count, crt_emitted_keys_count] =
830  computeHashTableCounts(shard_count,
831  inverse_bucket_sizes,
832  columns_per_device,
833  tuning_state.overlaps_max_table_size_bytes,
834  tuning_state.chosen_overlaps_threshold);
835  const size_t hash_table_size = calculateHashTableSize(
836  inverse_bucket_sizes.size(), crt_emitted_keys_count, crt_entry_count);
837  HashTableProps crt_props(crt_entry_count,
838  crt_emitted_keys_count,
839  hash_table_size,
840  inverse_bucket_sizes);
841  VLOG(1) << "Tuner output: " << tuner << " with properties " << crt_props;
842 
843  const auto should_continue = tuning_state(crt_props, tuner.getMinBucketSize());
845  tuning_state.crt_props.bucket_sizes, columns_per_device, device_count_);
846  if (!should_continue) {
847  break;
848  }
849  }
850 
851  const auto& crt_props = tuning_state.crt_props;
852  // sanity check that the hash table size has not changed. this is a fairly
853  // inexpensive check to ensure the above algorithm is consistent
854  const size_t hash_table_size =
856  crt_props.emitted_keys_count,
857  crt_props.entry_count);
858  CHECK_EQ(crt_props.hash_table_size, hash_table_size);
859 
861  hash_table_size > overlaps_max_table_size_bytes) {
862  VLOG(1) << "Could not find suitable overlaps join parameters to create hash "
863  "table under max allowed size ("
864  << overlaps_max_table_size_bytes << ") bytes.";
865  throw OverlapsHashTableTooBig(overlaps_max_table_size_bytes);
866  }
867 
868  VLOG(1) << "Final tuner output: " << tuner << " with properties " << crt_props;
870  VLOG(1) << "Final bucket sizes: ";
871  for (size_t dim = 0; dim < inverse_bucket_sizes_for_dimension_.size(); dim++) {
872  VLOG(1) << "dim[" << dim
873  << "]: " << 1.0 / inverse_bucket_sizes_for_dimension_[dim];
874  }
875  CHECK_GE(tuning_state.chosen_overlaps_threshold, double(0));
876  generateCacheKey(tuning_state.overlaps_max_table_size_bytes,
877  tuning_state.chosen_overlaps_threshold,
878  {},
879  fragments_per_device,
880  device_count_);
881  const auto candidate_auto_tuner_cache_key = hashtable_cache_key_.front();
882  if (skip_hashtable_caching) {
883  VLOG(1) << "Skip to add tuned parameters to auto tuner";
884  } else {
885  AutoTunerMetaInfo meta_info{tuning_state.overlaps_max_table_size_bytes,
886  tuning_state.chosen_overlaps_threshold,
888  auto_tuner_cache_->putItemToCache(candidate_auto_tuner_cache_key,
889  meta_info,
892  0,
893  0);
894  }
895  overlaps_bucket_threshold = tuning_state.chosen_overlaps_threshold;
896  reifyImpl(columns_per_device,
897  query_info,
898  layout,
899  shard_count,
900  crt_props.entry_count,
901  crt_props.emitted_keys_count,
902  skip_hashtable_caching,
903  overlaps_max_table_size_bytes,
904  overlaps_bucket_threshold);
905  }
906  }
907 }
908 
909 size_t OverlapsJoinHashTable::calculateHashTableSize(size_t number_of_dimensions,
910  size_t emitted_keys_count,
911  size_t entry_count) const {
912  const auto key_component_width = getKeyComponentWidth();
913  const auto key_component_count = number_of_dimensions;
914  const auto entry_size = key_component_count * key_component_width;
915  const auto keys_for_all_rows = emitted_keys_count;
916  const size_t one_to_many_hash_entries = 2 * entry_count + keys_for_all_rows;
917  const size_t hash_table_size =
918  entry_size * entry_count + one_to_many_hash_entries * sizeof(int32_t);
919  return hash_table_size;
920 }
921 
923  const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
924  const int device_id,
925  DeviceAllocator* dev_buff_owner) {
926  const auto& catalog = *executor_->getCatalog();
927  const auto effective_memory_level = getEffectiveMemoryLevel(inner_outer_pairs_);
928 
929  std::vector<JoinColumn> join_columns;
930  std::vector<std::shared_ptr<Chunk_NS::Chunk>> chunks_owner;
931  std::vector<JoinColumnTypeInfo> join_column_types;
932  std::vector<std::shared_ptr<void>> malloc_owner;
933  for (const auto& inner_outer_pair : inner_outer_pairs_) {
934  const auto inner_col = inner_outer_pair.first;
935  const auto inner_cd = get_column_descriptor_maybe(
936  inner_col->get_column_id(), inner_col->get_table_id(), catalog);
937  if (inner_cd && inner_cd->isVirtualCol) {
939  }
940  join_columns.emplace_back(fetchJoinColumn(inner_col,
941  fragments,
942  effective_memory_level,
943  device_id,
944  chunks_owner,
945  dev_buff_owner,
946  malloc_owner,
947  executor_,
948  &column_cache_));
949  const auto& ti = inner_col->get_type_info();
950  join_column_types.emplace_back(JoinColumnTypeInfo{static_cast<size_t>(ti.get_size()),
951  0,
952  0,
953  inline_int_null_value<int64_t>(),
954  false,
955  0,
957  CHECK(ti.is_array()) << "Overlaps join currently only supported for arrays.";
958  }
959  return {join_columns, join_column_types, chunks_owner, {}, malloc_owner};
960 }
961 
963  const size_t shard_count,
964  const std::vector<double>& inverse_bucket_sizes_for_dimension,
965  std::vector<ColumnsForDevice>& columns_per_device,
966  const size_t chosen_max_hashtable_size,
967  const double chosen_bucket_threshold) {
968  CHECK(!inverse_bucket_sizes_for_dimension.empty());
969  const auto [tuple_count, emitted_keys_count] =
970  approximateTupleCount(inverse_bucket_sizes_for_dimension,
971  columns_per_device,
972  chosen_max_hashtable_size,
973  chosen_bucket_threshold);
974  const auto entry_count = 2 * std::max(tuple_count, size_t(1));
975 
976  return std::make_pair(
977  get_entries_per_device(entry_count, shard_count, device_count_, memory_level_),
978  emitted_keys_count);
979 }
980 
982  const std::vector<double>& inverse_bucket_sizes_for_dimension,
983  std::vector<ColumnsForDevice>& columns_per_device,
984  const size_t chosen_max_hashtable_size,
985  const double chosen_bucket_threshold) {
986  const auto effective_memory_level = getEffectiveMemoryLevel(inner_outer_pairs_);
987  CountDistinctDescriptor count_distinct_desc{
989  0,
990  11,
991  true,
992  effective_memory_level == Data_Namespace::MemoryLevel::GPU_LEVEL
995  1};
996  const auto padded_size_bytes = count_distinct_desc.bitmapPaddedSizeBytes();
997 
998  CHECK(!columns_per_device.empty() && !columns_per_device.front().join_columns.empty());
999  if (columns_per_device.front().join_columns.front().num_elems == 0) {
1000  return std::make_pair(0, 0);
1001  }
1002 
1003  // TODO: state management in here should be revisited, but this should be safe enough
1004  // for now
1005  // re-compute bucket counts per device based on global bucket size
1006  for (size_t device_id = 0; device_id < columns_per_device.size(); ++device_id) {
1007  auto& columns_for_device = columns_per_device[device_id];
1008  columns_for_device.setBucketInfo(inverse_bucket_sizes_for_dimension,
1010  }
1011 
1012  // Number of keys must match dimension of buckets
1013  CHECK_EQ(columns_per_device.front().join_columns.size(),
1014  columns_per_device.front().join_buckets.size());
1015  if (effective_memory_level == Data_Namespace::MemoryLevel::CPU_LEVEL) {
1016  // Note that this path assumes each device has the same hash table (for GPU hash
1017  // join w/ hash table built on CPU)
1018  const auto cached_count_info =
1022  if (cached_count_info) {
1023  VLOG(1) << "Using a cached tuple count: " << cached_count_info->first
1024  << ", emitted keys count: " << cached_count_info->second;
1025  return *cached_count_info;
1026  }
1027  int thread_count = cpu_threads();
1028  std::vector<uint8_t> hll_buffer_all_cpus(thread_count * padded_size_bytes);
1029  auto hll_result = &hll_buffer_all_cpus[0];
1030 
1031  std::vector<int32_t> num_keys_for_row;
1032  // TODO(adb): support multi-column overlaps join
1033  num_keys_for_row.resize(columns_per_device.front().join_columns[0].num_elems);
1034 
1036  num_keys_for_row,
1037  count_distinct_desc.bitmap_sz_bits,
1038  padded_size_bytes,
1039  columns_per_device.front().join_columns,
1040  columns_per_device.front().join_column_types,
1041  columns_per_device.front().join_buckets,
1042  thread_count);
1043  for (int i = 1; i < thread_count; ++i) {
1044  hll_unify(hll_result,
1045  hll_result + i * padded_size_bytes,
1046  1 << count_distinct_desc.bitmap_sz_bits);
1047  }
1048  return std::make_pair(
1049  hll_size(hll_result, count_distinct_desc.bitmap_sz_bits),
1050  static_cast<size_t>(num_keys_for_row.size() > 0 ? num_keys_for_row.back() : 0));
1051  }
1052 #ifdef HAVE_CUDA
1053  auto data_mgr = executor_->getDataMgr();
1054  std::vector<std::vector<uint8_t>> host_hll_buffers(device_count_);
1055  for (auto& host_hll_buffer : host_hll_buffers) {
1056  host_hll_buffer.resize(count_distinct_desc.bitmapPaddedSizeBytes());
1057  }
1058  std::vector<size_t> emitted_keys_count_device_threads(device_count_, 0);
1059  std::vector<std::future<void>> approximate_distinct_device_threads;
1060  for (int device_id = 0; device_id < device_count_; ++device_id) {
1061  approximate_distinct_device_threads.emplace_back(std::async(
1063  [device_id,
1064  &columns_per_device,
1065  &count_distinct_desc,
1066  data_mgr,
1067  &host_hll_buffers,
1068  &emitted_keys_count_device_threads] {
1069  auto allocator = std::make_unique<CudaAllocator>(
1070  data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id));
1071  auto device_hll_buffer =
1072  allocator->alloc(count_distinct_desc.bitmapPaddedSizeBytes());
1073  data_mgr->getCudaMgr()->zeroDeviceMem(
1074  device_hll_buffer,
1075  count_distinct_desc.bitmapPaddedSizeBytes(),
1076  device_id,
1078  const auto& columns_for_device = columns_per_device[device_id];
1079  auto join_columns_gpu = transfer_vector_of_flat_objects_to_gpu(
1080  columns_for_device.join_columns, *allocator);
1081 
1082  CHECK_GT(columns_for_device.join_buckets.size(), 0u);
1083  const auto& inverse_bucket_sizes_for_dimension =
1084  columns_for_device.join_buckets[0].inverse_bucket_sizes_for_dimension;
1085  auto inverse_bucket_sizes_gpu = allocator->alloc(
1086  inverse_bucket_sizes_for_dimension.size() * sizeof(double));
1087  allocator->copyToDevice(
1088  inverse_bucket_sizes_gpu,
1089  inverse_bucket_sizes_for_dimension.data(),
1090  inverse_bucket_sizes_for_dimension.size() * sizeof(double));
1091  const size_t row_counts_buffer_sz =
1092  columns_per_device.front().join_columns[0].num_elems * sizeof(int32_t);
1093  auto row_counts_buffer = allocator->alloc(row_counts_buffer_sz);
1094  data_mgr->getCudaMgr()->zeroDeviceMem(
1095  row_counts_buffer,
1096  row_counts_buffer_sz,
1097  device_id,
1099  const auto key_handler =
1100  OverlapsKeyHandler(inverse_bucket_sizes_for_dimension.size(),
1101  join_columns_gpu,
1102  reinterpret_cast<double*>(inverse_bucket_sizes_gpu));
1103  const auto key_handler_gpu =
1104  transfer_flat_object_to_gpu(key_handler, *allocator);
1106  reinterpret_cast<uint8_t*>(device_hll_buffer),
1107  count_distinct_desc.bitmap_sz_bits,
1108  reinterpret_cast<int32_t*>(row_counts_buffer),
1109  key_handler_gpu,
1110  columns_for_device.join_columns[0].num_elems);
1111 
1112  auto& host_emitted_keys_count = emitted_keys_count_device_threads[device_id];
1113  allocator->copyFromDevice(
1114  &host_emitted_keys_count,
1115  row_counts_buffer +
1116  (columns_per_device.front().join_columns[0].num_elems - 1) *
1117  sizeof(int32_t),
1118  sizeof(int32_t));
1119 
1120  auto& host_hll_buffer = host_hll_buffers[device_id];
1121  allocator->copyFromDevice(&host_hll_buffer[0],
1122  device_hll_buffer,
1123  count_distinct_desc.bitmapPaddedSizeBytes());
1124  }));
1125  }
1126  for (auto& child : approximate_distinct_device_threads) {
1127  child.get();
1128  }
1129  CHECK_EQ(Data_Namespace::MemoryLevel::GPU_LEVEL, effective_memory_level);
1130  auto& result_hll_buffer = host_hll_buffers.front();
1131  auto hll_result = reinterpret_cast<int32_t*>(&result_hll_buffer[0]);
1132  for (int device_id = 1; device_id < device_count_; ++device_id) {
1133  auto& host_hll_buffer = host_hll_buffers[device_id];
1134  hll_unify(hll_result,
1135  reinterpret_cast<int32_t*>(&host_hll_buffer[0]),
1136  1 << count_distinct_desc.bitmap_sz_bits);
1137  }
1138  const size_t emitted_keys_count =
1139  std::accumulate(emitted_keys_count_device_threads.begin(),
1140  emitted_keys_count_device_threads.end(),
1141  0);
1142  return std::make_pair(hll_size(hll_result, count_distinct_desc.bitmap_sz_bits),
1143  emitted_keys_count);
1144 #else
1145  UNREACHABLE();
1146  return {0, 0};
1147 #endif // HAVE_CUDA
1148 }
1149 
1151  const std::vector<double>& inverse_bucket_sizes,
1152  std::vector<ColumnsForDevice>& columns_per_device,
1153  const size_t device_count) {
1154  // set global bucket size
1155  inverse_bucket_sizes_for_dimension_ = inverse_bucket_sizes;
1156 
1157  // re-compute bucket counts per device based on global bucket size
1158  CHECK_EQ(columns_per_device.size(), static_cast<size_t>(device_count));
1159  for (size_t device_id = 0; device_id < device_count; ++device_id) {
1160  auto& columns_for_device = columns_per_device[device_id];
1161  columns_for_device.setBucketInfo(inverse_bucket_sizes_for_dimension_,
1163  }
1164 }
1165 
1167  return 8;
1168 }
1169 
1173 }
1174 
1175 void OverlapsJoinHashTable::reify(const HashType preferred_layout) {
1176  auto timer = DEBUG_TIMER(__func__);
1177  CHECK_LT(0, device_count_);
1179 
1180  CHECK(condition_->is_overlaps_oper());
1181  CHECK_EQ(inner_outer_pairs_.size(), size_t(1));
1182  HashType layout;
1183  if (inner_outer_pairs_[0].second->get_type_info().is_fixlen_array() &&
1184  inner_outer_pairs_[0].second->get_type_info().get_size() == 32) {
1185  // bounds array
1186  layout = HashType::ManyToMany;
1187  } else {
1188  layout = HashType::OneToMany;
1189  }
1190  try {
1191  reifyWithLayout(layout);
1192  return;
1193  } catch (const JoinHashTableTooBig& e) {
1194  throw e;
1195  } catch (const std::exception& e) {
1196  VLOG(1) << "Caught exception while building overlaps baseline hash table: "
1197  << e.what();
1198  throw;
1199  }
1200 }
1201 
1202 void OverlapsJoinHashTable::reifyImpl(std::vector<ColumnsForDevice>& columns_per_device,
1203  const Fragmenter_Namespace::TableInfo& query_info,
1204  const HashType layout,
1205  const size_t shard_count,
1206  const size_t entry_count,
1207  const size_t emitted_keys_count,
1208  const bool skip_hashtable_caching,
1209  const size_t chosen_max_hashtable_size,
1210  const double chosen_bucket_threshold) {
1211  std::vector<std::future<void>> init_threads;
1212  chosen_overlaps_bucket_threshold_ = chosen_bucket_threshold;
1213  chosen_overlaps_max_table_size_bytes_ = chosen_max_hashtable_size;
1217 
1218  for (int device_id = 0; device_id < device_count_; ++device_id) {
1219  const auto fragments =
1220  shard_count
1221  ? only_shards_for_device(query_info.fragments, device_id, device_count_)
1222  : query_info.fragments;
1223  init_threads.push_back(std::async(std::launch::async,
1225  this,
1226  columns_per_device[device_id],
1227  layout,
1228  entry_count,
1229  emitted_keys_count,
1230  skip_hashtable_caching,
1231  device_id,
1233  }
1234  for (auto& init_thread : init_threads) {
1235  init_thread.wait();
1236  }
1237  for (auto& init_thread : init_threads) {
1238  init_thread.get();
1239  }
1240 }
1241 
1243  const ColumnsForDevice& columns_for_device,
1244  const HashType layout,
1245  const size_t entry_count,
1246  const size_t emitted_keys_count,
1247  const bool skip_hashtable_caching,
1248  const int device_id,
1249  const logger::ThreadLocalIds parent_thread_local_ids) {
1250  logger::LocalIdsScopeGuard lisg = parent_thread_local_ids.setNewThreadId();
1251  DEBUG_TIMER_NEW_THREAD(parent_thread_local_ids.thread_id_);
1252  CHECK_EQ(getKeyComponentWidth(), size_t(8));
1254  const auto effective_memory_level = getEffectiveMemoryLevel(inner_outer_pairs_);
1255 
1256  if (effective_memory_level == Data_Namespace::MemoryLevel::CPU_LEVEL) {
1257  VLOG(1) << "Building overlaps join hash table on CPU.";
1258  auto hash_table = initHashTableOnCpu(columns_for_device.join_columns,
1259  columns_for_device.join_column_types,
1260  columns_for_device.join_buckets,
1261  layout,
1262  entry_count,
1263  emitted_keys_count,
1264  skip_hashtable_caching);
1265  CHECK(hash_table);
1266 
1267 #ifdef HAVE_CUDA
1269  auto gpu_hash_table = copyCpuHashTableToGpu(
1270  hash_table, layout, entry_count, emitted_keys_count, device_id);
1271  CHECK_LT(static_cast<size_t>(device_id), hash_tables_for_device_.size());
1272  hash_tables_for_device_[device_id] = std::move(gpu_hash_table);
1273  } else {
1274 #else
1275  CHECK_EQ(Data_Namespace::CPU_LEVEL, effective_memory_level);
1276 #endif
1277  CHECK_EQ(hash_tables_for_device_.size(), size_t(1));
1278  hash_tables_for_device_[0] = hash_table;
1279 #ifdef HAVE_CUDA
1280  }
1281 #endif
1282  } else {
1283 #ifdef HAVE_CUDA
1284  auto hash_table = initHashTableOnGpu(columns_for_device.join_columns,
1285  columns_for_device.join_column_types,
1286  columns_for_device.join_buckets,
1287  layout,
1288  entry_count,
1289  emitted_keys_count,
1290  device_id);
1291  CHECK_LT(static_cast<size_t>(device_id), hash_tables_for_device_.size());
1292  hash_tables_for_device_[device_id] = std::move(hash_table);
1293 #else
1294  UNREACHABLE();
1295 #endif
1296  }
1297 }
1298 
1299 std::shared_ptr<BaselineHashTable> OverlapsJoinHashTable::initHashTableOnCpu(
1300  const std::vector<JoinColumn>& join_columns,
1301  const std::vector<JoinColumnTypeInfo>& join_column_types,
1302  const std::vector<JoinBucketInfo>& join_bucket_info,
1303  const HashType layout,
1304  const size_t entry_count,
1305  const size_t emitted_keys_count,
1306  const bool skip_hashtable_caching) {
1307  auto timer = DEBUG_TIMER(__func__);
1308  decltype(std::chrono::steady_clock::now()) ts1, ts2;
1309  ts1 = std::chrono::steady_clock::now();
1310  CHECK(!join_columns.empty());
1311  CHECK(!join_bucket_info.empty());
1312  std::lock_guard<std::mutex> cpu_hash_table_buff_lock(cpu_hash_table_buff_mutex_);
1313  if (auto generic_hash_table =
1317  if (auto hash_table =
1318  std::dynamic_pointer_cast<BaselineHashTable>(generic_hash_table)) {
1319  VLOG(1) << "Using cached CPU hash table for initialization.";
1320  // See if a hash table of a different layout was returned.
1321  // If it was OneToMany, we can reuse it on ManyToMany.
1322  if (layout == HashType::ManyToMany &&
1323  hash_table->getLayout() == HashType::OneToMany) {
1324  // use the cached hash table
1326  return hash_table;
1327  }
1328  if (layout == hash_table->getLayout()) {
1329  return hash_table;
1330  }
1331  }
1332  }
1334  const auto key_component_count =
1335  join_bucket_info[0].inverse_bucket_sizes_for_dimension.size();
1336 
1337  const auto key_handler =
1338  OverlapsKeyHandler(key_component_count,
1339  &join_columns[0],
1340  join_bucket_info[0].inverse_bucket_sizes_for_dimension.data());
1343  dummy_str_proxy_translation_maps_ptrs_and_offsets;
1344  const auto err =
1345  builder.initHashTableOnCpu(&key_handler,
1347  join_columns,
1348  join_column_types,
1349  join_bucket_info,
1350  dummy_str_proxy_translation_maps_ptrs_and_offsets,
1351  entry_count,
1352  emitted_keys_count,
1353  layout,
1354  join_type_,
1357  query_hints_);
1358  ts2 = std::chrono::steady_clock::now();
1359  if (err) {
1360  throw HashJoinFail(
1361  std::string("Unrecognized error when initializing CPU overlaps hash table (") +
1362  std::to_string(err) + std::string(")"));
1363  }
1364  std::shared_ptr<BaselineHashTable> hash_table = builder.getHashTable();
1365  if (skip_hashtable_caching) {
1366  VLOG(1) << "Skip to cache overlaps join hashtable";
1367  } else {
1368  auto hashtable_build_time =
1369  std::chrono::duration_cast<std::chrono::milliseconds>(ts2 - ts1).count();
1372  hash_table,
1374  hashtable_build_time);
1375  }
1376  return hash_table;
1377 }
1378 
1379 #ifdef HAVE_CUDA
1380 
1381 std::shared_ptr<BaselineHashTable> OverlapsJoinHashTable::initHashTableOnGpu(
1382  const std::vector<JoinColumn>& join_columns,
1383  const std::vector<JoinColumnTypeInfo>& join_column_types,
1384  const std::vector<JoinBucketInfo>& join_bucket_info,
1385  const HashType layout,
1386  const size_t entry_count,
1387  const size_t emitted_keys_count,
1388  const size_t device_id) {
1390 
1391  VLOG(1) << "Building overlaps join hash table on GPU.";
1392 
1394  auto data_mgr = executor_->getDataMgr();
1395  CudaAllocator allocator(
1396  data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id));
1397  auto join_columns_gpu = transfer_vector_of_flat_objects_to_gpu(join_columns, allocator);
1398  CHECK_EQ(join_columns.size(), 1u);
1399  CHECK(!join_bucket_info.empty());
1400  auto& inverse_bucket_sizes_for_dimension =
1401  join_bucket_info[0].inverse_bucket_sizes_for_dimension;
1402  auto inverse_bucket_sizes_gpu = transfer_vector_of_flat_objects_to_gpu(
1403  inverse_bucket_sizes_for_dimension, allocator);
1404  const auto key_handler = OverlapsKeyHandler(inverse_bucket_sizes_for_dimension.size(),
1405  join_columns_gpu,
1406  inverse_bucket_sizes_gpu);
1407 
1408  const auto err = builder.initHashTableOnGpu(&key_handler,
1409  join_columns,
1410  layout,
1411  join_type_,
1414  entry_count,
1415  emitted_keys_count,
1416  device_id,
1417  executor_,
1418  query_hints_);
1419  if (err) {
1420  throw HashJoinFail(
1421  std::string("Unrecognized error when initializing GPU overlaps hash table (") +
1422  std::to_string(err) + std::string(")"));
1423  }
1424  return builder.getHashTable();
1425 }
1426 
1427 std::shared_ptr<BaselineHashTable> OverlapsJoinHashTable::copyCpuHashTableToGpu(
1428  std::shared_ptr<BaselineHashTable>& cpu_hash_table,
1429  const HashType layout,
1430  const size_t entry_count,
1431  const size_t emitted_keys_count,
1432  const size_t device_id) {
1434 
1435  auto data_mgr = executor_->getDataMgr();
1436 
1437  // copy hash table to GPU
1438  BaselineJoinHashTableBuilder gpu_builder;
1439  gpu_builder.allocateDeviceMemory(layout,
1442  entry_count,
1443  emitted_keys_count,
1444  device_id,
1445  executor_,
1446  query_hints_);
1447  std::shared_ptr<BaselineHashTable> gpu_hash_table = gpu_builder.getHashTable();
1448  CHECK(gpu_hash_table);
1449  auto gpu_buffer_ptr = gpu_hash_table->getGpuBuffer();
1450  CHECK(gpu_buffer_ptr);
1451 
1452  CHECK_LE(cpu_hash_table->getHashTableBufferSize(ExecutorDeviceType::CPU),
1453  gpu_hash_table->getHashTableBufferSize(ExecutorDeviceType::GPU));
1454  auto device_allocator = std::make_unique<CudaAllocator>(
1455  data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id));
1456  device_allocator->copyToDevice(
1457  gpu_buffer_ptr,
1458  cpu_hash_table->getCpuBuffer(),
1459  cpu_hash_table->getHashTableBufferSize(ExecutorDeviceType::CPU));
1460  return gpu_hash_table;
1461 }
1462 
1463 #endif // HAVE_CUDA
1464 
1465 #define LL_CONTEXT executor_->cgen_state_->context_
1466 #define LL_BUILDER executor_->cgen_state_->ir_builder_
1467 #define LL_INT(v) executor_->cgen_state_->llInt(v)
1468 #define LL_FP(v) executor_->cgen_state_->llFp(v)
1469 #define ROW_FUNC executor_->cgen_state_->row_func_
1470 
1472  AUTOMATIC_IR_METADATA(executor_->cgen_state_.get());
1473  const auto key_component_width = getKeyComponentWidth();
1474  CHECK(key_component_width == 4 || key_component_width == 8);
1475  const auto key_size_lv = LL_INT(getKeyComponentCount() * key_component_width);
1476  llvm::Value* key_buff_lv{nullptr};
1477  switch (key_component_width) {
1478  case 4:
1479  key_buff_lv =
1480  LL_BUILDER.CreateAlloca(llvm::Type::getInt32Ty(LL_CONTEXT), key_size_lv);
1481  break;
1482  case 8:
1483  key_buff_lv =
1484  LL_BUILDER.CreateAlloca(llvm::Type::getInt64Ty(LL_CONTEXT), key_size_lv);
1485  break;
1486  default:
1487  CHECK(false);
1488  }
1489 
1490  const auto& inner_outer_pair = inner_outer_pairs_[0];
1491  const auto outer_geo = inner_outer_pair.second;
1492  const auto outer_geo_ti = outer_geo->get_type_info();
1493 
1494  llvm::Value* arr_ptr = nullptr;
1495  CodeGenerator code_generator(executor_);
1496  CHECK_EQ(inverse_bucket_sizes_for_dimension_.size(), static_cast<size_t>(2));
1497 
1498  if (outer_geo_ti.is_geometry()) {
1499  // TODO(adb): for points we will use the coords array, but for other geometries we
1500  // will need to use the bounding box. For now only support points.
1501  CHECK_EQ(outer_geo_ti.get_type(), kPOINT);
1502 
1503  if (const auto outer_geo_col = dynamic_cast<const Analyzer::ColumnVar*>(outer_geo)) {
1504  const auto outer_geo_col_lvs = code_generator.codegen(outer_geo_col, true, co);
1505  CHECK_EQ(outer_geo_col_lvs.size(), size_t(1));
1506  const auto coords_cd = executor_->getCatalog()->getMetadataForColumn(
1507  outer_geo_col->get_table_id(), outer_geo_col->get_column_id() + 1);
1508  CHECK(coords_cd);
1509 
1510  const auto array_ptr = executor_->cgen_state_->emitExternalCall(
1511  "array_buff",
1512  llvm::Type::getInt8PtrTy(executor_->cgen_state_->context_),
1513  {outer_geo_col_lvs.front(), code_generator.posArg(outer_geo_col)});
1514  CHECK(coords_cd->columnType.get_elem_type().get_type() == kTINYINT)
1515  << "Only TINYINT coordinates columns are supported in geo overlaps hash "
1516  "join.";
1517  arr_ptr = code_generator.castArrayPointer(array_ptr,
1518  coords_cd->columnType.get_elem_type());
1519  } else if (const auto outer_geo_function_operator =
1520  dynamic_cast<const Analyzer::GeoOperator*>(outer_geo)) {
1521  // Process points dynamically constructed by geo function operators
1522  const auto outer_geo_function_operator_lvs =
1523  code_generator.codegen(outer_geo_function_operator, true, co);
1524  CHECK_EQ(outer_geo_function_operator_lvs.size(), size_t(2));
1525  arr_ptr = outer_geo_function_operator_lvs.front();
1526  } else if (const auto outer_geo_expr =
1527  dynamic_cast<const Analyzer::GeoExpr*>(outer_geo)) {
1528  UNREACHABLE() << outer_geo_expr->toString();
1529  }
1530  } else if (outer_geo_ti.is_fixlen_array()) {
1531  // Process dynamically constructed points
1532  const auto outer_geo_cast_coord_array =
1533  dynamic_cast<const Analyzer::UOper*>(outer_geo);
1534  CHECK_EQ(outer_geo_cast_coord_array->get_optype(), kCAST);
1535  const auto outer_geo_coord_array = dynamic_cast<const Analyzer::ArrayExpr*>(
1536  outer_geo_cast_coord_array->get_operand());
1537  CHECK(outer_geo_coord_array);
1538  CHECK(outer_geo_coord_array->isLocalAlloc());
1539  CHECK_EQ(outer_geo_coord_array->getElementCount(), 2);
1540  auto elem_size = (outer_geo_ti.get_compression() == kENCODING_GEOINT)
1541  ? sizeof(int32_t)
1542  : sizeof(double);
1543  CHECK_EQ(outer_geo_ti.get_size(), int(2 * elem_size));
1544  const auto outer_geo_constructed_lvs = code_generator.codegen(outer_geo, true, co);
1545  // CHECK_EQ(outer_geo_constructed_lvs.size(), size_t(2)); // Pointer and size
1546  const auto array_ptr = outer_geo_constructed_lvs.front(); // Just need the pointer
1547  arr_ptr = LL_BUILDER.CreateGEP(
1548  array_ptr->getType()->getScalarType()->getPointerElementType(),
1549  array_ptr,
1550  LL_INT(0));
1551  arr_ptr = code_generator.castArrayPointer(array_ptr, SQLTypeInfo(kTINYINT, true));
1552  }
1553  if (!arr_ptr) {
1554  LOG(FATAL) << "Overlaps key currently only supported for geospatial columns and "
1555  "constructed points.";
1556  }
1557 
1558  for (size_t i = 0; i < 2; i++) {
1559  const auto key_comp_dest_lv = LL_BUILDER.CreateGEP(
1560  key_buff_lv->getType()->getScalarType()->getPointerElementType(),
1561  key_buff_lv,
1562  LL_INT(i));
1563 
1564  // Note that get_bucket_key_for_range_compressed will need to be specialized for
1565  // future compression schemes
1566  auto bucket_key =
1567  outer_geo_ti.get_compression() == kENCODING_GEOINT
1568  ? executor_->cgen_state_->emitExternalCall(
1569  "get_bucket_key_for_range_compressed",
1570  get_int_type(64, LL_CONTEXT),
1571  {arr_ptr, LL_INT(i), LL_FP(inverse_bucket_sizes_for_dimension_[i])})
1572  : executor_->cgen_state_->emitExternalCall(
1573  "get_bucket_key_for_range_double",
1574  get_int_type(64, LL_CONTEXT),
1575  {arr_ptr, LL_INT(i), LL_FP(inverse_bucket_sizes_for_dimension_[i])});
1576  const auto col_lv = LL_BUILDER.CreateSExt(
1577  bucket_key, get_int_type(key_component_width * 8, LL_CONTEXT));
1578  LL_BUILDER.CreateStore(col_lv, key_comp_dest_lv);
1579  }
1580  return key_buff_lv;
1581 }
1582 
1583 std::vector<llvm::Value*> OverlapsJoinHashTable::codegenManyKey(
1584  const CompilationOptions& co) {
1585  AUTOMATIC_IR_METADATA(executor_->cgen_state_.get());
1586  const auto key_component_width = getKeyComponentWidth();
1587  CHECK(key_component_width == 4 || key_component_width == 8);
1588  auto hash_table = getHashTableForDevice(size_t(0));
1589  CHECK(hash_table);
1591 
1592  VLOG(1) << "Performing codgen for ManyToMany";
1593  const auto& inner_outer_pair = inner_outer_pairs_[0];
1594  const auto outer_col = inner_outer_pair.second;
1595 
1596  CodeGenerator code_generator(executor_);
1597  const auto col_lvs = code_generator.codegen(outer_col, true, co);
1598  CHECK_EQ(col_lvs.size(), size_t(1));
1599 
1600  const auto outer_col_var = dynamic_cast<const Analyzer::ColumnVar*>(outer_col);
1601  CHECK(outer_col_var);
1602  const auto coords_cd = executor_->getCatalog()->getMetadataForColumn(
1603  outer_col_var->get_table_id(), outer_col_var->get_column_id());
1604  CHECK(coords_cd);
1605 
1606  const auto array_ptr = executor_->cgen_state_->emitExternalCall(
1607  "array_buff",
1608  llvm::Type::getInt8PtrTy(executor_->cgen_state_->context_),
1609  {col_lvs.front(), code_generator.posArg(outer_col)});
1610 
1611  // TODO(jclay): this seems to cast to double, and causes the GPU build to fail.
1612  // const auto arr_ptr =
1613  // code_generator.castArrayPointer(array_ptr,
1614  // coords_cd->columnType.get_elem_type());
1615  array_ptr->setName("array_ptr");
1616 
1617  auto num_keys_lv = executor_->cgen_state_->emitExternalCall(
1618  "get_num_buckets_for_bounds",
1619  get_int_type(32, LL_CONTEXT),
1620  {array_ptr,
1621  LL_INT(0),
1622  LL_FP(inverse_bucket_sizes_for_dimension_[0]),
1623  LL_FP(inverse_bucket_sizes_for_dimension_[1])});
1624  num_keys_lv->setName("num_keys_lv");
1625 
1626  return {num_keys_lv, array_ptr};
1627 }
1628 
1630  const CompilationOptions& co,
1631  const size_t index) {
1632  AUTOMATIC_IR_METADATA(executor_->cgen_state_.get());
1633  if (getHashType() == HashType::ManyToMany) {
1634  VLOG(1) << "Building codegenMatchingSet for ManyToMany";
1635  const auto key_component_width = getKeyComponentWidth();
1636  CHECK(key_component_width == 4 || key_component_width == 8);
1637  auto many_to_many_args = codegenManyKey(co);
1638  auto hash_ptr = HashJoin::codegenHashTableLoad(index, executor_);
1639  const auto composite_dict_ptr_type =
1640  llvm::Type::getIntNPtrTy(LL_CONTEXT, key_component_width * 8);
1641  const auto composite_key_dict =
1642  hash_ptr->getType()->isPointerTy()
1643  ? LL_BUILDER.CreatePointerCast(hash_ptr, composite_dict_ptr_type)
1644  : LL_BUILDER.CreateIntToPtr(hash_ptr, composite_dict_ptr_type);
1645  const auto key_component_count = getKeyComponentCount();
1646 
1647  auto one_to_many_ptr = hash_ptr;
1648 
1649  if (one_to_many_ptr->getType()->isPointerTy()) {
1650  one_to_many_ptr =
1651  LL_BUILDER.CreatePtrToInt(hash_ptr, llvm::Type::getInt64Ty(LL_CONTEXT));
1652  } else {
1653  CHECK(one_to_many_ptr->getType()->isIntegerTy(64));
1654  }
1655 
1656  const auto composite_key_dict_size = offsetBufferOff();
1657  one_to_many_ptr =
1658  LL_BUILDER.CreateAdd(one_to_many_ptr, LL_INT(composite_key_dict_size));
1659 
1660  // NOTE(jclay): A fixed array of size 200 is allocated on the stack.
1661  // this is likely the maximum value we can do that is safe to use across
1662  // all supported GPU architectures.
1663  const int max_array_size = 200;
1664  const auto arr_type = get_int_array_type(32, max_array_size, LL_CONTEXT);
1665  const auto out_arr_lv = LL_BUILDER.CreateAlloca(arr_type);
1666  out_arr_lv->setName("out_arr");
1667 
1668  const auto casted_out_arr_lv =
1669  LL_BUILDER.CreatePointerCast(out_arr_lv, arr_type->getPointerTo());
1670 
1671  const auto element_ptr = LL_BUILDER.CreateGEP(arr_type, casted_out_arr_lv, LL_INT(0));
1672 
1673  auto rowid_ptr_i32 =
1674  LL_BUILDER.CreatePointerCast(element_ptr, llvm::Type::getInt32PtrTy(LL_CONTEXT));
1675 
1676  const auto candidate_count_lv = executor_->cgen_state_->emitExternalCall(
1677  "get_candidate_rows",
1678  llvm::Type::getInt64Ty(LL_CONTEXT),
1679  {
1680  rowid_ptr_i32,
1681  LL_INT(max_array_size),
1682  many_to_many_args[1],
1683  LL_INT(0),
1686  many_to_many_args[0],
1687  LL_INT(key_component_count), // key_component_count
1688  composite_key_dict, // ptr to hash table
1689  LL_INT(getEntryCount()), // entry_count
1690  LL_INT(composite_key_dict_size), // offset_buffer_ptr_offset
1691  LL_INT(getEntryCount() * sizeof(int32_t)) // sub_buff_size
1692  });
1693 
1694  const auto slot_lv = LL_INT(int64_t(0));
1695 
1696  return {rowid_ptr_i32, candidate_count_lv, slot_lv};
1697  } else {
1698  VLOG(1) << "Building codegenMatchingSet for Baseline";
1699  // TODO: duplicated w/ BaselineJoinHashTable -- push into the hash table builder?
1700  const auto key_component_width = getKeyComponentWidth();
1701  CHECK(key_component_width == 4 || key_component_width == 8);
1702  auto key_buff_lv = codegenKey(co);
1704  auto hash_ptr = HashJoin::codegenHashTableLoad(index, executor_);
1705  const auto composite_dict_ptr_type =
1706  llvm::Type::getIntNPtrTy(LL_CONTEXT, key_component_width * 8);
1707  const auto composite_key_dict =
1708  hash_ptr->getType()->isPointerTy()
1709  ? LL_BUILDER.CreatePointerCast(hash_ptr, composite_dict_ptr_type)
1710  : LL_BUILDER.CreateIntToPtr(hash_ptr, composite_dict_ptr_type);
1711  const auto key_component_count = getKeyComponentCount();
1712  const auto key = executor_->cgen_state_->emitExternalCall(
1713  "get_composite_key_index_" + std::to_string(key_component_width * 8),
1714  get_int_type(64, LL_CONTEXT),
1715  {key_buff_lv,
1716  LL_INT(key_component_count),
1717  composite_key_dict,
1718  LL_INT(getEntryCount())});
1719  auto one_to_many_ptr = hash_ptr;
1720  if (one_to_many_ptr->getType()->isPointerTy()) {
1721  one_to_many_ptr =
1722  LL_BUILDER.CreatePtrToInt(hash_ptr, llvm::Type::getInt64Ty(LL_CONTEXT));
1723  } else {
1724  CHECK(one_to_many_ptr->getType()->isIntegerTy(64));
1725  }
1726  const auto composite_key_dict_size = offsetBufferOff();
1727  one_to_many_ptr =
1728  LL_BUILDER.CreateAdd(one_to_many_ptr, LL_INT(composite_key_dict_size));
1730  std::vector<llvm::Value*>{
1731  one_to_many_ptr, key, LL_INT(int64_t(0)), LL_INT(getEntryCount() - 1)},
1732  false,
1733  false,
1734  false,
1736  executor_);
1737  }
1738  UNREACHABLE();
1739  return HashJoinMatchingSet{};
1740 }
1741 
1743  const int device_id,
1744  bool raw) const {
1745  auto buffer = getJoinHashBuffer(device_type, device_id);
1746  CHECK_LT(static_cast<size_t>(device_id), hash_tables_for_device_.size());
1747  auto hash_table = hash_tables_for_device_[device_id];
1748  CHECK(hash_table);
1749  auto buffer_size = hash_table->getHashTableBufferSize(device_type);
1750 #ifdef HAVE_CUDA
1751  std::unique_ptr<int8_t[]> buffer_copy;
1752  if (device_type == ExecutorDeviceType::GPU) {
1753  buffer_copy = std::make_unique<int8_t[]>(buffer_size);
1754  CHECK(executor_);
1755  auto data_mgr = executor_->getDataMgr();
1756  auto device_allocator = std::make_unique<CudaAllocator>(
1757  data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id));
1758 
1759  device_allocator->copyFromDevice(buffer_copy.get(), buffer, buffer_size);
1760  }
1761  auto ptr1 = buffer_copy ? buffer_copy.get() : reinterpret_cast<const int8_t*>(buffer);
1762 #else
1763  auto ptr1 = reinterpret_cast<const int8_t*>(buffer);
1764 #endif // HAVE_CUDA
1765  auto ptr2 = ptr1 + offsetBufferOff();
1766  auto ptr3 = ptr1 + countBufferOff();
1767  auto ptr4 = ptr1 + payloadBufferOff();
1768  CHECK(hash_table);
1769  const auto layout = getHashType();
1770  return HashTable::toString(
1771  "geo",
1772  getHashTypeString(layout),
1773  getKeyComponentCount() + (layout == HashType::OneToOne ? 1 : 0),
1775  hash_table->getEntryCount(),
1776  ptr1,
1777  ptr2,
1778  ptr3,
1779  ptr4,
1780  buffer_size,
1781  raw);
1782 }
1783 
1784 std::set<DecodedJoinHashBufferEntry> OverlapsJoinHashTable::toSet(
1785  const ExecutorDeviceType device_type,
1786  const int device_id) const {
1787  auto buffer = getJoinHashBuffer(device_type, device_id);
1788  auto hash_table = getHashTableForDevice(device_id);
1789  CHECK(hash_table);
1790  auto buffer_size = hash_table->getHashTableBufferSize(device_type);
1791 #ifdef HAVE_CUDA
1792  std::unique_ptr<int8_t[]> buffer_copy;
1793  if (device_type == ExecutorDeviceType::GPU) {
1794  buffer_copy = std::make_unique<int8_t[]>(buffer_size);
1795  CHECK(executor_);
1796  auto data_mgr = executor_->getDataMgr();
1797  auto allocator = std::make_unique<CudaAllocator>(
1798  data_mgr, device_id, getQueryEngineCudaStreamForDevice(device_id));
1799 
1800  allocator->copyFromDevice(buffer_copy.get(), buffer, buffer_size);
1801  }
1802  auto ptr1 = buffer_copy ? buffer_copy.get() : reinterpret_cast<const int8_t*>(buffer);
1803 #else
1804  auto ptr1 = reinterpret_cast<const int8_t*>(buffer);
1805 #endif // HAVE_CUDA
1806  auto ptr2 = ptr1 + offsetBufferOff();
1807  auto ptr3 = ptr1 + countBufferOff();
1808  auto ptr4 = ptr1 + payloadBufferOff();
1809  const auto layout = getHashType();
1810  return HashTable::toSet(getKeyComponentCount() + (layout == HashType::OneToOne ? 1 : 0),
1812  hash_table->getEntryCount(),
1813  ptr1,
1814  ptr2,
1815  ptr3,
1816  ptr4,
1817  buffer_size);
1818 }
1819 
1821  const std::vector<InnerOuter>& inner_outer_pairs) const {
1824  this->executor_->getDataMgr()->gpusPresent() &&
1827  }
1828  // otherwise, try to build on CPU
1830 }
1831 
1833  try {
1835  } catch (...) {
1836  CHECK(false);
1837  }
1838  return 0;
1839 }
1840 
1842  QueryPlanHash key,
1843  CacheItemType item_type,
1844  DeviceIdentifier device_identifier) {
1845  auto timer = DEBUG_TIMER(__func__);
1846  VLOG(1) << "Checking CPU hash table cache.";
1848  HashtableCacheMetaInfo meta_info;
1850  auto cached_hashtable =
1851  hash_table_cache_->getItemFromCache(key, item_type, device_identifier, meta_info);
1852  if (cached_hashtable) {
1853  return cached_hashtable;
1854  }
1855  return nullptr;
1856 }
1857 
1858 std::optional<std::pair<size_t, size_t>>
1860  QueryPlanHash key,
1861  CacheItemType item_type,
1862  DeviceIdentifier device_identifier) {
1864  HashtableCacheMetaInfo metaInfo;
1866  auto cached_hashtable =
1867  hash_table_cache_->getItemFromCache(key, item_type, device_identifier, metaInfo);
1868  if (cached_hashtable) {
1869  return std::make_pair(cached_hashtable->getEntryCount() / 2,
1870  cached_hashtable->getEmittedKeysCount());
1871  }
1872  return std::nullopt;
1873 }
1874 
1876  QueryPlanHash key,
1877  CacheItemType item_type,
1878  std::shared_ptr<HashTable> hashtable_ptr,
1879  DeviceIdentifier device_identifier,
1880  size_t hashtable_building_time) {
1882  CHECK(hashtable_ptr && !hashtable_ptr->getGpuBuffer());
1883  HashtableCacheMetaInfo meta_info;
1885  meta_info.registered_query_hint = query_hints_;
1886  hash_table_cache_->putItemToCache(
1887  key,
1888  hashtable_ptr,
1889  item_type,
1890  device_identifier,
1891  hashtable_ptr->getHashTableBufferSize(ExecutorDeviceType::CPU),
1892  hashtable_building_time,
1893  meta_info);
1894 }
1895 
1897  return condition_->get_optype() == kBW_EQ;
1898 }
static std::vector< int > collectFragmentIds(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments)
Definition: HashJoin.cpp:451
llvm::Value * codegenKey(const CompilationOptions &)
#define CHECK_EQ(x, y)
Definition: Logger.h:297
int getInnerTableId() const noexceptoverride
size_t DeviceIdentifier
Definition: DataRecycler.h:129
virtual HashJoinMatchingSet codegenMatchingSet(const CompilationOptions &, const size_t)=0
virtual void reifyWithLayout(const HashType layout)
JoinType
Definition: sqldefs.h:164
Fragmenter_Namespace::TableInfo info
Definition: InputMetadata.h:35
std::string toString(const ExecutorDeviceType device_type, const int device_id=0, bool raw=false) const override
virtual std::pair< size_t, size_t > approximateTupleCount(const std::vector< double > &inverse_bucket_sizes_for_dimension, std::vector< ColumnsForDevice > &, const size_t chosen_max_hashtable_size, const double chosen_bucket_threshold)
static llvm::Value * codegenHashTableLoad(const size_t table_idx, Executor *executor)
Definition: HashJoin.cpp:257
std::shared_ptr< HashTable > initHashTableOnCpuFromCache(QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier)
static bool isInvalidHashTableCacheKey(const std::vector< QueryPlanHash > &cache_keys)
ExecutorDeviceType
std::vector< ChunkKey > cache_key_chunks
Definition: HashJoin.h:129
virtual void reifyImpl(std::vector< ColumnsForDevice > &columns_per_device, const Fragmenter_Namespace::TableInfo &query_info, const HashType layout, const size_t shard_count, const size_t entry_count, const size_t emitted_keys_count, const bool skip_hashtable_caching, const size_t chosen_max_hashtable_size, const double chosen_bucket_threshold)
bool overlaps_allow_gpu_build
Definition: QueryHint.h:318
T * transfer_flat_object_to_gpu(const T &object, DeviceAllocator &allocator)
#define LOG(tag)
Definition: Logger.h:283
std::ostream & operator<<(std::ostream &os, const SessionInfo &session_info)
Definition: SessionInfo.cpp:57
static std::pair< std::vector< InnerOuter >, std::vector< InnerOuterStringOpInfos > > normalizeColumnPairs(const Analyzer::BinOper *condition, const Catalog_Namespace::Catalog &cat, const TemporaryTables *temporary_tables)
Definition: HashJoin.cpp:996
void hll_unify(T1 *lhs, T2 *rhs, const size_t m)
Definition: HyperLogLog.h:107
JoinColumn fetchJoinColumn(const Analyzer::ColumnVar *hash_col, const std::vector< Fragmenter_Namespace::FragmentInfo > &fragment_info, const Data_Namespace::MemoryLevel effective_memory_level, const int device_id, std::vector< std::shared_ptr< Chunk_NS::Chunk >> &chunks_owner, DeviceAllocator *dev_buff_owner, std::vector< std::shared_ptr< void >> &malloc_owner, Executor *executor, ColumnCacheMap *column_cache)
Definition: HashJoin.cpp:58
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 JoinType join_type, const int device_count, ColumnCacheMap &column_cache, Executor *executor, const HashTableBuildDagMap &hashtable_build_dag_map, const RegisteredQueryHint &query_hint, const TableIdToNodeMap &table_id_to_node_map)
Make hash table from an in-flight SQL query&#39;s parse tree etc.
std::optional< OverlapsHashTableMetaInfo > overlaps_meta_info
#define LL_FP(v)
llvm::Value * posArg(const Analyzer::Expr *) const
Definition: ColumnIR.cpp:582
std::vector< std::shared_ptr< HashTable > > hash_tables_for_device_
Definition: HashJoin.h:361
llvm::Value * castArrayPointer(llvm::Value *ptr, const SQLTypeInfo &elem_ti)
#define UNREACHABLE()
Definition: Logger.h:333
std::optional< std::pair< size_t, size_t > > getApproximateTupleCountFromCache(QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier)
#define CHECK_GE(x, y)
Definition: Logger.h:302
int initHashTableOnGpu(KEY_HANDLER *key_handler, const std::vector< JoinColumn > &join_columns, const HashType layout, const JoinType join_type, const size_t key_component_width, const size_t key_component_count, const size_t keyspace_entry_count, const size_t emitted_keys_count, const int device_id, const Executor *executor, const RegisteredQueryHint &query_hint)
Definition: sqldefs.h:48
#define DEBUG_TIMER_NEW_THREAD(parent_thread_id)
Definition: Logger.h:412
double overlaps_keys_per_bin
Definition: QueryHint.h:320
BucketSizeTuner(const double bucket_threshold, const double step, const double min_threshold, const Data_Namespace::MemoryLevel effective_memory_level, const std::vector< ColumnsForDevice > &columns_per_device, const std::vector< InnerOuter > &inner_outer_pairs, const size_t table_tuple_count, const Executor *executor)
std::vector< FragmentInfo > fragments
Definition: Fragmenter.h:171
int initHashTableOnCpu(KEY_HANDLER *key_handler, const CompositeKeyInfo &composite_key_info, const std::vector< JoinColumn > &join_columns, const std::vector< JoinColumnTypeInfo > &join_column_types, const std::vector< JoinBucketInfo > &join_bucket_info, const StrProxyTranslationMapsPtrsAndOffsets &str_proxy_translation_maps_ptrs_and_offsets, const size_t keyspace_entry_count, const size_t keys_for_all_rows, const HashType layout, const JoinType join_type, const size_t key_component_width, const size_t key_component_count, const RegisteredQueryHint &query_hint)
static std::unique_ptr< OverlapsTuningParamRecycler > auto_tuner_cache_
void putHashTableOnCpuToCache(QueryPlanHash key, CacheItemType item_type, std::shared_ptr< HashTable > hashtable_ptr, DeviceIdentifier device_identifier, size_t hashtable_building_time)
std::shared_ptr< BaselineHashTable > 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, const bool skip_hashtable_caching)
llvm::Type * get_int_type(const int width, llvm::LLVMContext &context)
size_t hll_size(const T *M, const size_t bitmap_sz_bits)
Definition: HyperLogLog.h:88
#define CHECK_GT(x, y)
Definition: Logger.h:301
virtual std::pair< size_t, size_t > computeHashTableCounts(const size_t shard_count, const std::vector< double > &inverse_bucket_sizes_for_dimension, std::vector< ColumnsForDevice > &columns_per_device, const size_t chosen_max_hashtable_size, const double chosen_bucket_threshold)
HashType getHashType() const noexceptoverride
std::string to_string(char const *&&v)
size_t calculateHashTableSize(size_t number_of_dimensions, size_t emitted_keys_count, size_t entry_count) const
HashTableProps(const size_t entry_count, const size_t emitted_keys_count, const size_t hash_table_size, const std::vector< double > &bucket_sizes)
const std::shared_ptr< Analyzer::BinOper > condition_
const std::vector< JoinColumnTypeInfo > join_column_types
Definition: HashJoin.h:111
void compute_bucket_sizes_on_device(double *bucket_sizes_buffer, const JoinColumn *join_column, const JoinColumnTypeInfo *type_info, const double *bucket_size_thresholds)
future< Result > async(Fn &&fn, Args &&...args)
std::unordered_map< size_t, HashTableBuildDag > HashTableBuildDagMap
const ColumnDescriptor * get_column_descriptor_maybe(const int col_id, const int table_id, const Catalog_Namespace::Catalog &cat)
Definition: Execute.h:220
void reify(const HashType preferred_layout)
CacheItemType
Definition: DataRecycler.h:38
void reifyForDevice(const ColumnsForDevice &columns_for_device, const HashType layout, const size_t entry_count, const size_t emitted_keys_count, const bool skip_hashtable_caching, const int device_id, const logger::ThreadLocalIds parent_thread_local_ids)
ColumnCacheMap & column_cache_
RegisteredQueryHint query_hints_
QueryPlanHash getAlternativeCacheKey(AlternativeCacheKeyForOverlapsHashJoin &info)
void compute_bucket_sizes_on_cpu(std::vector< double > &bucket_sizes_for_dimension, const JoinColumn &join_column, const JoinColumnTypeInfo &type_info, const std::vector< double > &bucket_size_thresholds, const int thread_count)
const std::vector< InputTableInfo > & query_infos_
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)
size_t payloadBufferOff() const noexceptoverride
int8_t * getJoinHashBuffer(const ExecutorDeviceType device_type, const int device_id) const
Definition: HashJoin.h:298
DecodedJoinHashBufferSet toSet(const ExecutorDeviceType device_type, const int device_id) const override
DEVICE auto accumulate(ARGS &&...args)
Definition: gpu_enabled.h:42
TuningState(const size_t overlaps_max_table_size_bytes, const double overlaps_target_entries_per_bin)
double g_overlaps_target_entries_per_bin
Definition: Execute.cpp:106
HashTableBuildDagMap hashtable_build_dag_map_
#define LL_BUILDER
size_t g_overlaps_max_table_size_bytes
Definition: Execute.cpp:105
std::vector< llvm::Value * > codegenManyKey(const CompilationOptions &)
std::vector< QueryPlanHash > hashtable_cache_key_
void allocateDeviceMemory(const HashType layout, const size_t key_component_width, const size_t key_component_count, const size_t keyspace_entry_count, const size_t emitted_keys_count, const int device_id, const Executor *executor, const RegisteredQueryHint &query_hint)
virtual int getInnerTableId() const noexcept=0
#define AUTOMATIC_IR_METADATA(CGENSTATE)
void setOverlapsHashtableMetaInfo(size_t max_table_size_bytes, double bucket_threshold, std::vector< double > &bucket_sizes)
std::unordered_map< int, std::unordered_map< int, std::shared_ptr< const ColumnarResults >>> ColumnCacheMap
static std::shared_ptr< RangeJoinHashTable > getInstance(const std::shared_ptr< Analyzer::BinOper > condition, const Analyzer::RangeOper *range_expr, const std::vector< InputTableInfo > &query_infos, const Data_Namespace::MemoryLevel memory_level, const JoinType join_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)
HashTable * getHashTableForDevice(const size_t device_id) const
Definition: HashJoin.h:279
#define VLOGGING(n)
Definition: Logger.h:287
const InputTableInfo & get_inner_query_info(const int inner_table_id, const std::vector< InputTableInfo > &query_infos)
std::vector< llvm::Value * > codegen(const Analyzer::Expr *, const bool fetch_columns, const CompilationOptions &)
Definition: IRCodegen.cpp:30
std::vector< double > inverse_bucket_sizes_for_dimension_
#define CHECK_LT(x, y)
Definition: Logger.h:299
std::optional< HashType > layout_override_
std::pair< std::vector< const int32_t * >, std::vector< int32_t >> StrProxyTranslationMapsPtrsAndOffsets
size_t overlaps_max_size
Definition: QueryHint.h:317
void approximate_distinct_tuples_overlaps(uint8_t *hll_buffer_all_cpus, std::vector< int32_t > &row_counts, const uint32_t b, const size_t padded_size_bytes, const std::vector< JoinColumn > &join_column_per_key, const std::vector< JoinColumnTypeInfo > &type_info_per_key, const std::vector< JoinBucketInfo > &join_buckets_per_key, const int thread_count)
#define LL_INT(v)
#define CHECK_LE(x, y)
Definition: Logger.h:300
std::unique_ptr< BaselineHashTable > getHashTable()
static std::string getHashTypeString(HashType ht) noexcept
Definition: HashJoin.h:164
static std::unordered_set< size_t > getAlternativeTableKeys(const std::vector< ChunkKey > &chunk_keys, int db_id, int inner_table_id)
Definition: DataRecycler.h:154
static std::string toString(const std::string &type, const std::string &layout_type, size_t key_component_count, size_t key_component_width, size_t entry_count, const int8_t *ptr1, const int8_t *ptr2, const int8_t *ptr3, const int8_t *ptr4, size_t buffer_size, bool raw=false)
Decode hash table into a human-readable string.
Definition: HashTable.cpp:226
void setInverseBucketSizeInfo(const std::vector< double > &inverse_bucket_sizes, std::vector< ColumnsForDevice > &columns_per_device, const size_t device_count)
LocalIdsScopeGuard setNewThreadId() const
Definition: Logger.cpp:531
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)
bool isHintRegistered(const QueryHint hint) const
Definition: QueryHint.h:348
ColumnsForDevice fetchColumnsForDevice(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments, const int device_id, DeviceAllocator *dev_buff_owner)
HashJoinMatchingSet codegenMatchingSet(const CompilationOptions &, const size_t) override
size_t QueryPlanHash
bool tuneOneStep(const TuningState::TuningDirection tuning_direction)
CUstream getQueryEngineCudaStreamForDevice(int device_num)
Definition: QueryEngine.cpp:7
size_t offsetBufferOff() const noexceptoverride
size_t countBufferOff() const noexceptoverride
HashtableCacheMetaInfo hashtable_cache_meta_info_
bool operator()(const HashTableProps &new_props, const bool new_overlaps_threshold)
ColumnType get_join_column_type_kind(const SQLTypeInfo &ti)
std::vector< double > correct_uninitialized_bucket_sizes_to_thresholds(const std::vector< double > &bucket_sizes, const std::vector< double > &bucket_thresholds, const double initial_value)
#define CHECK(condition)
Definition: Logger.h:289
#define DEBUG_TIMER(name)
Definition: Logger.h:407
Definition: sqldefs.h:30
std::vector< double > compute_bucket_sizes(const std::vector< double > &bucket_thresholds, const Data_Namespace::MemoryLevel effective_memory_level, const JoinColumn &join_column, const JoinColumnTypeInfo &join_column_type, const std::vector< InnerOuter > &inner_outer_pairs, const Executor *executor)
const Data_Namespace::MemoryLevel memory_level_
void generateCacheKey(const size_t max_hashtable_size, const double bucket_threshold, const std::vector< double > &bucket_sizes, std::vector< std::vector< Fragmenter_Namespace::FragmentInfo >> &fragments_per_device, int device_count)
size_t getComponentBufferSize() const noexceptoverride
static std::unique_ptr< HashtableRecycler > hash_table_cache_
std::optional< OverlapsHashTableMetaInfo > getOverlapsHashTableMetaInfo()
std::vector< InnerOuter > inner_outer_pairs_
std::unordered_set< size_t > table_keys_
static DecodedJoinHashBufferSet toSet(size_t key_component_count, size_t key_component_width, size_t entry_count, const int8_t *ptr1, const int8_t *ptr2, const int8_t *ptr3, const int8_t *ptr4, size_t buffer_size)
Decode hash table into a std::set for easy inspection and validation.
Definition: HashTable.cpp:139
T * transfer_vector_of_flat_objects_to_gpu(const std::vector< T > &vec, DeviceAllocator &allocator)
ThreadId thread_id_
Definition: Logger.h:136
Data_Namespace::MemoryLevel getEffectiveMemoryLevel(const std::vector< InnerOuter > &inner_outer_pairs) const
std::vector< JoinBucketInfo > join_buckets
Definition: HashJoin.h:113
double overlaps_bucket_threshold
Definition: QueryHint.h:316
void copyFromDevice(void *host_dst, const void *device_src, const size_t num_bytes) const override
#define LL_CONTEXT
static constexpr DeviceIdentifier CPU_DEVICE_IDENTIFIER
Definition: DataRecycler.h:136
int cpu_threads()
Definition: thread_count.h:25
llvm::ArrayType * get_int_array_type(int const width, int count, llvm::LLVMContext &context)
static HashtableAccessPathInfo getHashtableAccessPathInfo(const std::vector< InnerOuter > &inner_outer_pairs, const std::vector< InnerOuterStringOpInfos > &inner_outer_string_op_infos_pairs, const SQLOps op_type, const JoinType join_type, const HashTableBuildDagMap &hashtable_build_dag_map, int device_count, int shard_count, const std::vector< std::vector< Fragmenter_Namespace::FragmentInfo >> &frags_for_device, Executor *executor)
CompositeKeyInfo composite_key_info_
bool tuneOneStep(const TuningState::TuningDirection tuning_direction, const double step_overide)
void approximate_distinct_tuples_on_device_overlaps(uint8_t *hll_buffer, const uint32_t b, int32_t *row_counts_buffer, const OverlapsKeyHandler *key_handler, const int64_t num_elems)
bool isBitwiseEq() const override
HashType
Definition: HashTable.h:19
ThreadLocalIds thread_local_ids()
Definition: Logger.cpp:873
const std::vector< JoinColumn > join_columns
Definition: HashJoin.h:110
#define VLOG(n)
Definition: Logger.h:383
static bool layoutRequiresAdditionalBuffers(HashType layout) noexcept
Definition: HashJoin.h:160
static CompositeKeyInfo getCompositeKeyInfo(const std::vector< InnerOuter > &inner_outer_pairs, const Executor *executor, const std::vector< InnerOuterStringOpInfos > &inner_outer_string_op_infos_pairs={})
Definition: HashJoin.cpp:460