34 std::make_unique<OverlapsTuningParamRecycler>();
38 const std::shared_ptr<Analyzer::BinOper> condition,
39 const std::vector<InputTableInfo>& query_infos,
42 const int device_count,
48 decltype(std::chrono::steady_clock::now()) ts1, ts2;
50 std::vector<InnerOuter> inner_outer_pairs;
52 if (
const auto range_expr =
53 dynamic_cast<const Analyzer::RangeOper*>(condition->get_right_operand())) {
62 hashtable_build_dag_map,
64 table_id_to_node_map);
68 condition.get(), *executor->getCatalog(), executor->getTemporaryTables())
71 CHECK(!inner_outer_pairs.empty());
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() &&
82 inner_outer_pairs[0].second->get_type_info().get_size() == 32) {
89 const auto layout = getHashTableType(condition, inner_outer_pairs);
93 <<
" for qual: " << condition->toString();
94 ts1 = std::chrono::steady_clock::now();
97 const auto qi_0 = query_infos[0].info.getNumTuplesUpperBound();
98 const auto qi_1 = query_infos[1].info.getNumTuplesUpperBound();
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.";
103 const auto& query_info =
107 if (total_entries > static_cast<size_t>(std::numeric_limits<int32_t>::max())) {
111 auto join_hash_table = std::make_shared<OverlapsJoinHashTable>(condition,
119 hashtable_build_dag_map,
120 table_id_to_node_map);
122 join_hash_table->registerQueryHint(query_hint);
125 join_hash_table->reify(layout);
127 throw HashJoinFail(std::string(
"Could not build a 1-to-1 correspondence for columns "
128 "involved in overlaps join | ") +
131 throw HashJoinFail(std::string(
"Could not build hash tables for overlaps join | "
132 "Inner table too big. Attempt manual table reordering "
133 "or create a single fragment inner table. | ") +
135 }
catch (
const std::exception& e) {
136 throw HashJoinFail(std::string(
"Failed to build hash tables for overlaps join | ") +
140 ts2 = std::chrono::steady_clock::now();
142 << std::chrono::duration_cast<std::chrono::milliseconds>(ts2 - ts1).count()
145 return join_hash_table;
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];
160 return corrected_bucket_sizes;
164 const std::vector<double>& bucket_thresholds,
168 const std::vector<InnerOuter>& inner_outer_pairs,
169 const Executor* executor) {
171 CHECK_EQ(inner_outer_pairs.size(), 1u);
173 const auto col = inner_outer_pairs[0].first;
175 const auto col_ti = col->get_type_info();
176 CHECK(col_ti.is_array());
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);
185 <<
"Computing x and y bucket sizes for overlaps hash join with maximum bucket size "
192 bucket_sizes, join_column, join_column_type, bucket_thresholds, thread_count);
197 const int device_id = 0;
198 auto data_mgr = executor->getDataMgr();
201 auto device_bucket_sizes_gpu =
205 auto device_bucket_thresholds_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));
218 bucket_sizes, bucket_thresholds, initial_bin_value);
220 VLOG(1) <<
"Computed x and y bucket sizes for overlaps hash join: ("
221 << corrected_bucket_sizes[0] <<
", " << corrected_bucket_sizes[1] <<
")";
223 return corrected_bucket_sizes;
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) {}
248 os <<
" entry_count: " << props.
entry_count <<
", emitted_keys "
256 const double overlaps_target_entries_per_bin)
259 , chosen_overlaps_threshold(-1)
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) {}
272 TuningDirection tuning_direction{TuningDirection::SMALLER};
279 const size_t max_reverse_search_iterations{8};
286 prev_props = crt_props;
287 crt_props = new_props;
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());
300 if (previousIterationValid()) {
301 VLOG(1) <<
"Using previous threshold value " << chosen_overlaps_threshold;
302 crt_props = prev_props;
305 CHECK(hashTableTooBig());
306 crt_reverse_search_iteration++;
307 chosen_overlaps_threshold = new_overlaps_threshold;
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";
316 if (crt_reverse_search_iteration > 1 &&
317 crt_props.hash_table_size == prev_props.hash_table_size) {
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";
327 if (crt_step == 1 && crt_reverse_search_iteration == 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 <<
")";
333 tuning_direction = TuningDirection::LARGER;
340 chosen_overlaps_threshold = new_overlaps_threshold;
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.";
349 if (crt_reverse_search_iteration > 0) {
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.";
364 return crt_props.hash_table_size > overlaps_max_table_size_bytes;
368 return crt_props.keys_per_bin > prev_props.keys_per_bin;
372 return tuning_direction == TuningDirection::SMALLER && crt_step > 1;
376 return crt_props.keys_per_bin < overlaps_target_entries_per_bin;
384 const double min_threshold,
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)
391 , bucket_thresholds_(num_dims_, bucket_threshold)
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());
405 return tuneOneStep(tuning_direction, step_);
409 const double step_overide) {
410 if (table_tuple_count_ == 0) {
413 if (tuning_direction == TuningState::TuningDirection::SMALLER) {
414 return tuneSmallerOneStep(step_overide);
416 return tuneLargerOneStep(step_overide);
420 return *std::min_element(bucket_thresholds_.begin(), bucket_thresholds_.end());
430 if (num_steps_ == 0) {
431 CHECK_EQ(current_bucket_sizes_.size(),
static_cast<size_t>(0));
432 current_bucket_sizes_ = computeBucketSizes();
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);
439 return inverse_bucket_sizes;
444 for (
const auto& t : bucket_thresholds_) {
445 if (t < min_threshold_) {
453 if (table_tuple_count_ == 0) {
454 return std::vector<double>(num_dims_, 0);
457 effective_memory_level_,
458 columns_per_device_.front().join_columns[0],
459 columns_per_device_.front().join_column_types[0],
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_) {
472 if (bucketThresholdsBelowMinThreshold()) {
473 VLOG(1) <<
"Aborting overlaps tuning as at least one bucket size is below min "
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.";
483 current_bucket_sizes_ = next_bucket_sizes;
489 if (!current_bucket_sizes_.empty()) {
490 CHECK_EQ(current_bucket_sizes_.size(), bucket_thresholds_.size());
491 bucket_thresholds_ = current_bucket_sizes_;
494 for (
auto& t : bucket_thresholds_) {
504 current_bucket_sizes_ = bucket_thresholds_;
511 size_t num_steps_{0};
526 os <<
"Step Num: " << tuner.
num_steps_ <<
", Threshold: " << std::fixed <<
"("
528 <<
", Step Size: " << std::fixed << tuner.
step_ <<
", Min: " << std::fixed
538 const auto& query_info =
543 if (query_info.fragments.empty()) {
548 std::optional<double> overlaps_threshold_override;
551 auto skip_hashtable_caching =
false;
553 VLOG(1) <<
"Setting overlaps bucket threshold "
554 "\'overlaps_hashjoin_bucket_threshold\' via "
556 << query_hint.overlaps_bucket_threshold;
557 overlaps_threshold_override = query_hint.overlaps_bucket_threshold;
560 std::ostringstream oss;
561 oss <<
"User requests to change a threshold \'overlaps_max_table_size_bytes\' via "
563 if (!overlaps_threshold_override.has_value()) {
564 oss <<
": " << overlaps_max_table_size_bytes <<
" -> "
565 << query_hint.overlaps_max_size;
566 overlaps_max_table_size_bytes = query_hint.overlaps_max_size;
568 oss <<
", but is skipped since the query hint also changes the threshold "
569 "\'overlaps_hashjoin_bucket_threshold\'";
571 VLOG(1) << oss.str();
574 VLOG(1) <<
"User requests to skip caching overlaps join hashtable and its tuned "
575 "parameters for this query";
576 skip_hashtable_caching =
true;
579 VLOG(1) <<
"User requests to change a threshold \'overlaps_keys_per_bin\' via query "
581 << overlaps_target_entries_per_bin <<
" -> "
582 << query_hint.overlaps_keys_per_bin;
583 overlaps_target_entries_per_bin = query_hint.overlaps_keys_per_bin;
591 auto allow_gpu_hashtable_build =
594 if (allow_gpu_hashtable_build) {
595 if (data_mgr->gpusPresent() &&
597 VLOG(1) <<
"A user forces to build GPU hash table for this overlaps join operator";
599 allow_gpu_hashtable_build =
false;
600 VLOG(1) <<
"A user forces to build GPU hash table for this overlaps join operator "
602 "skip it since either GPU is not presented or CPU execution mode is set";
606 std::vector<ColumnsForDevice> columns_per_device;
607 std::vector<std::unique_ptr<CudaAllocator>> dev_buff_owners;
609 allow_gpu_hashtable_build) {
610 for (
int device_id = 0; device_id <
device_count_; ++device_id) {
611 dev_buff_owners.emplace_back(std::make_unique<CudaAllocator>(
616 std::vector<std::vector<Fragmenter_Namespace::FragmentInfo>> fragments_per_device;
618 size_t total_num_tuples = 0;
619 for (
int device_id = 0; device_id <
device_count_; ++device_id) {
620 fragments_per_device.emplace_back(
623 : query_info.fragments);
624 const size_t crt_num_tuples =
626 fragments_per_device.back().end(),
628 [](
const auto& sum,
const auto& fragment) {
629 return sum + fragment.getNumTuples();
631 total_num_tuples += crt_num_tuples;
632 const auto columns_for_device =
636 allow_gpu_hashtable_build
637 ? dev_buff_owners[device_id].get()
639 columns_per_device.push_back(columns_for_device);
643 auto hashtable_access_path_info =
651 fragments_per_device,
655 table_keys_ = hashtable_access_path_info.table_keys;
657 if (overlaps_threshold_override) {
659 BucketSizeTuner tuner(*overlaps_threshold_override,
667 const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
669 auto [entry_count, emitted_keys_count] =
671 inverse_bucket_sizes,
673 overlaps_max_table_size_bytes,
674 *overlaps_threshold_override);
680 *overlaps_threshold_override,
681 inverse_bucket_sizes,
682 fragments_per_device,
690 skip_hashtable_caching,
691 overlaps_max_table_size_bytes,
692 *overlaps_threshold_override);
694 double overlaps_bucket_threshold = std::numeric_limits<double>::max();
696 overlaps_bucket_threshold,
698 fragments_per_device,
700 std::vector<size_t> per_device_chunk_key(device_count_);
703 std::vector<int> alternative_table_key{
706 const auto table_keys =
707 std::unordered_set<size_t>{boost::hash_value(alternative_table_key)};
709 for (
int device_id = 0; device_id <
device_count_; ++device_id) {
714 per_device_chunk_key.push_back(chunk_key_hash);
717 columns_per_device.front().join_columns.front().num_elems,
720 overlaps_max_table_size_bytes,
721 overlaps_bucket_threshold,
729 auto cached_bucket_threshold =
733 if (cached_bucket_threshold) {
734 overlaps_bucket_threshold = cached_bucket_threshold->bucket_threshold;
735 auto inverse_bucket_sizes = cached_bucket_threshold->bucket_sizes;
737 overlaps_max_table_size_bytes, overlaps_bucket_threshold, inverse_bucket_sizes);
739 overlaps_bucket_threshold,
740 inverse_bucket_sizes,
741 fragments_per_device,
744 if (
auto hash_table =
755 VLOG(1) <<
"Using cached hash table bucket size";
761 hash_table->getEntryCount(),
762 hash_table->getEmittedKeysCount(),
763 skip_hashtable_caching,
764 overlaps_max_table_size_bytes,
765 overlaps_bucket_threshold);
767 VLOG(1) <<
"Computing bucket size for cached bucket threshold";
769 BucketSizeTuner tuner(overlaps_bucket_threshold,
778 const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
780 auto [entry_count, emitted_keys_count] =
782 inverse_bucket_sizes,
784 overlaps_max_table_size_bytes,
785 overlaps_bucket_threshold);
789 overlaps_bucket_threshold,
790 inverse_bucket_sizes,
791 fragments_per_device,
800 skip_hashtable_caching,
801 overlaps_max_table_size_bytes,
802 overlaps_bucket_threshold);
806 BucketSizeTuner tuner(
807 overlaps_bucket_threshold,
816 VLOG(1) <<
"Running overlaps join size auto tune with parameters: " << tuner;
819 TuningState tuning_state(overlaps_max_table_size_bytes,
820 overlaps_target_entries_per_bin);
821 while (tuner.tuneOneStep(tuning_state.tuning_direction)) {
822 const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
824 const auto [crt_entry_count, crt_emitted_keys_count] =
826 inverse_bucket_sizes,
828 tuning_state.overlaps_max_table_size_bytes,
829 tuning_state.chosen_overlaps_threshold);
831 inverse_bucket_sizes.size(), crt_emitted_keys_count, crt_entry_count);
832 HashTableProps crt_props(crt_entry_count,
833 crt_emitted_keys_count,
835 inverse_bucket_sizes);
836 VLOG(1) <<
"Tuner output: " << tuner <<
" with properties " << crt_props;
838 const auto should_continue = tuning_state(crt_props, tuner.getMinBucketSize());
840 tuning_state.crt_props.bucket_sizes, columns_per_device, device_count_);
841 if (!should_continue) {
846 const auto& crt_props = tuning_state.crt_props;
849 const size_t hash_table_size =
851 crt_props.emitted_keys_count,
852 crt_props.entry_count);
853 CHECK_EQ(crt_props.hash_table_size, hash_table_size);
856 hash_table_size > overlaps_max_table_size_bytes) {
857 VLOG(1) <<
"Could not find suitable overlaps join parameters to create hash "
858 "table under max allowed size ("
859 << overlaps_max_table_size_bytes <<
") bytes.";
863 VLOG(1) <<
"Final tuner output: " << tuner <<
" with properties " << crt_props;
865 VLOG(1) <<
"Final bucket sizes: ";
867 VLOG(1) <<
"dim[" << dim
870 CHECK_GE(tuning_state.chosen_overlaps_threshold,
double(0));
872 tuning_state.chosen_overlaps_threshold,
874 fragments_per_device,
876 const auto candidate_auto_tuner_cache_key = hashtable_cache_key_.front();
877 if (skip_hashtable_caching) {
878 VLOG(1) <<
"Skip to add tuned parameters to auto tuner";
881 tuning_state.chosen_overlaps_threshold,
890 overlaps_bucket_threshold = tuning_state.chosen_overlaps_threshold;
895 crt_props.entry_count,
896 crt_props.emitted_keys_count,
897 skip_hashtable_caching,
898 overlaps_max_table_size_bytes,
899 overlaps_bucket_threshold);
905 size_t emitted_keys_count,
906 size_t entry_count)
const {
908 const auto key_component_count = number_of_dimensions;
909 const auto entry_size = key_component_count * key_component_width;
910 const auto keys_for_all_rows = emitted_keys_count;
911 const size_t one_to_many_hash_entries = 2 * entry_count + keys_for_all_rows;
912 const size_t hash_table_size =
913 entry_size * entry_count + one_to_many_hash_entries *
sizeof(int32_t);
914 return hash_table_size;
918 const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
921 const auto& catalog = *
executor_->getCatalog();
924 std::vector<JoinColumn> join_columns;
925 std::vector<std::shared_ptr<Chunk_NS::Chunk>> chunks_owner;
926 std::vector<JoinColumnTypeInfo> join_column_types;
927 std::vector<std::shared_ptr<void>> malloc_owner;
929 const auto inner_col = inner_outer_pair.first;
931 inner_col->get_column_id(), inner_col->get_table_id(), catalog);
932 if (inner_cd && inner_cd->isVirtualCol) {
937 effective_memory_level,
944 const auto& ti = inner_col->get_type_info();
948 inline_int_null_value<int64_t>(),
952 CHECK(ti.is_array()) <<
"Overlaps join currently only supported for arrays.";
954 return {join_columns, join_column_types, chunks_owner, {}, malloc_owner};
958 const size_t shard_count,
959 const std::vector<double>& inverse_bucket_sizes_for_dimension,
960 std::vector<ColumnsForDevice>& columns_per_device,
961 const size_t chosen_max_hashtable_size,
962 const double chosen_bucket_threshold) {
963 CHECK(!inverse_bucket_sizes_for_dimension.empty());
964 const auto [tuple_count, emitted_keys_count] =
967 chosen_max_hashtable_size,
968 chosen_bucket_threshold);
969 const auto entry_count = 2 * std::max(tuple_count,
size_t(1));
971 return std::make_pair(
977 const std::vector<double>& inverse_bucket_sizes_for_dimension,
978 std::vector<ColumnsForDevice>& columns_per_device,
979 const size_t chosen_max_hashtable_size,
980 const double chosen_bucket_threshold) {
991 const auto padded_size_bytes = count_distinct_desc.bitmapPaddedSizeBytes();
993 CHECK(!columns_per_device.empty() && !columns_per_device.front().join_columns.empty());
994 if (columns_per_device.front().join_columns.front().num_elems == 0) {
995 return std::make_pair(0, 0);
1001 for (
size_t device_id = 0; device_id < columns_per_device.size(); ++device_id) {
1002 auto& columns_for_device = columns_per_device[device_id];
1003 columns_for_device.setBucketInfo(inverse_bucket_sizes_for_dimension,
1008 CHECK_EQ(columns_per_device.front().join_columns.size(),
1009 columns_per_device.front().join_buckets.size());
1013 const auto cached_count_info =
1017 if (cached_count_info) {
1018 VLOG(1) <<
"Using a cached tuple count: " << cached_count_info->first
1019 <<
", emitted keys count: " << cached_count_info->second;
1020 return *cached_count_info;
1023 std::vector<uint8_t> hll_buffer_all_cpus(thread_count * padded_size_bytes);
1024 auto hll_result = &hll_buffer_all_cpus[0];
1026 std::vector<int32_t> num_keys_for_row;
1028 num_keys_for_row.resize(columns_per_device.front().join_columns[0].num_elems);
1032 count_distinct_desc.bitmap_sz_bits,
1034 columns_per_device.front().join_columns,
1035 columns_per_device.front().join_column_types,
1036 columns_per_device.front().join_buckets,
1038 for (
int i = 1; i < thread_count; ++i) {
1040 hll_result + i * padded_size_bytes,
1041 1 << count_distinct_desc.bitmap_sz_bits);
1043 return std::make_pair(
1044 hll_size(hll_result, count_distinct_desc.bitmap_sz_bits),
1045 static_cast<size_t>(num_keys_for_row.size() > 0 ? num_keys_for_row.back() : 0));
1048 auto data_mgr =
executor_->getDataMgr();
1049 std::vector<std::vector<uint8_t>> host_hll_buffers(
device_count_);
1050 for (
auto& host_hll_buffer : host_hll_buffers) {
1051 host_hll_buffer.resize(count_distinct_desc.bitmapPaddedSizeBytes());
1053 std::vector<size_t> emitted_keys_count_device_threads(
device_count_, 0);
1054 std::vector<std::future<void>> approximate_distinct_device_threads;
1055 for (
int device_id = 0; device_id <
device_count_; ++device_id) {
1056 approximate_distinct_device_threads.emplace_back(
std::async(
1059 &columns_per_device,
1060 &count_distinct_desc,
1063 &emitted_keys_count_device_threads] {
1064 auto allocator = std::make_unique<CudaAllocator>(
1066 auto device_hll_buffer =
1067 allocator->alloc(count_distinct_desc.bitmapPaddedSizeBytes());
1068 data_mgr->getCudaMgr()->zeroDeviceMem(
1070 count_distinct_desc.bitmapPaddedSizeBytes(),
1073 const auto& columns_for_device = columns_per_device[device_id];
1075 columns_for_device.join_columns, *allocator);
1077 CHECK_GT(columns_for_device.join_buckets.size(), 0u);
1078 const auto& inverse_bucket_sizes_for_dimension =
1079 columns_for_device.join_buckets[0].inverse_bucket_sizes_for_dimension;
1080 auto inverse_bucket_sizes_gpu = allocator->alloc(
1081 inverse_bucket_sizes_for_dimension.size() *
sizeof(double));
1082 allocator->copyToDevice(
1083 inverse_bucket_sizes_gpu,
1084 inverse_bucket_sizes_for_dimension.data(),
1085 inverse_bucket_sizes_for_dimension.size() *
sizeof(double));
1086 const size_t row_counts_buffer_sz =
1087 columns_per_device.front().join_columns[0].num_elems *
sizeof(int32_t);
1088 auto row_counts_buffer = allocator->alloc(row_counts_buffer_sz);
1089 data_mgr->getCudaMgr()->zeroDeviceMem(
1091 row_counts_buffer_sz,
1094 const auto key_handler =
1097 reinterpret_cast<double*
>(inverse_bucket_sizes_gpu));
1098 const auto key_handler_gpu =
1101 reinterpret_cast<uint8_t*>(device_hll_buffer),
1102 count_distinct_desc.bitmap_sz_bits,
1103 reinterpret_cast<int32_t*>(row_counts_buffer),
1105 columns_for_device.join_columns[0].num_elems);
1107 auto& host_emitted_keys_count = emitted_keys_count_device_threads[device_id];
1108 allocator->copyFromDevice(
1109 &host_emitted_keys_count,
1111 (columns_per_device.front().join_columns[0].num_elems - 1) *
1115 auto& host_hll_buffer = host_hll_buffers[device_id];
1116 allocator->copyFromDevice(&host_hll_buffer[0],
1118 count_distinct_desc.bitmapPaddedSizeBytes());
1121 for (
auto& child : approximate_distinct_device_threads) {
1125 auto& result_hll_buffer = host_hll_buffers.front();
1126 auto hll_result =
reinterpret_cast<int32_t*
>(&result_hll_buffer[0]);
1127 for (
int device_id = 1; device_id <
device_count_; ++device_id) {
1128 auto& host_hll_buffer = host_hll_buffers[device_id];
1130 reinterpret_cast<int32_t*>(&host_hll_buffer[0]),
1131 1 << count_distinct_desc.bitmap_sz_bits);
1133 const size_t emitted_keys_count =
1135 emitted_keys_count_device_threads.end(),
1137 return std::make_pair(
hll_size(hll_result, count_distinct_desc.bitmap_sz_bits),
1138 emitted_keys_count);
1146 const std::vector<double>& inverse_bucket_sizes,
1147 std::vector<ColumnsForDevice>& columns_per_device,
1148 const size_t device_count) {
1153 CHECK_EQ(columns_per_device.size(),
static_cast<size_t>(device_count));
1154 for (
size_t device_id = 0; device_id < device_count; ++device_id) {
1155 auto& columns_for_device = columns_per_device[device_id];
1188 }
catch (
const std::exception& e) {
1189 VLOG(1) <<
"Caught exception while building overlaps baseline hash table: "
1198 const size_t shard_count,
1199 const size_t entry_count,
1200 const size_t emitted_keys_count,
1201 const bool skip_hashtable_caching,
1202 const size_t chosen_max_hashtable_size,
1203 const double chosen_bucket_threshold) {
1204 std::vector<std::future<void>> init_threads;
1211 for (
int device_id = 0; device_id <
device_count_; ++device_id) {
1212 const auto fragments =
1219 columns_per_device[device_id],
1223 skip_hashtable_caching,
1227 for (
auto& init_thread : init_threads) {
1230 for (
auto& init_thread : init_threads) {
1237 const size_t entry_count,
1238 const size_t emitted_keys_count,
1239 const bool skip_hashtable_caching,
1240 const int device_id,
1248 VLOG(1) <<
"Building overlaps join hash table on CPU.";
1255 skip_hashtable_caching);
1260 auto gpu_hash_table = copyCpuHashTableToGpu(
1261 hash_table, layout, entry_count, emitted_keys_count, device_id);
1275 auto hash_table = initHashTableOnGpu(columns_for_device.
join_columns,
1291 const std::vector<JoinColumn>& join_columns,
1292 const std::vector<JoinColumnTypeInfo>& join_column_types,
1293 const std::vector<JoinBucketInfo>& join_bucket_info,
1295 const size_t entry_count,
1296 const size_t emitted_keys_count,
1297 const bool skip_hashtable_caching) {
1299 decltype(std::chrono::steady_clock::now()) ts1, ts2;
1300 ts1 = std::chrono::steady_clock::now();
1301 CHECK(!join_columns.empty());
1302 CHECK(!join_bucket_info.empty());
1304 if (
auto generic_hash_table =
1308 if (
auto hash_table =
1309 std::dynamic_pointer_cast<BaselineHashTable>(generic_hash_table)) {
1310 VLOG(1) <<
"Using cached CPU hash table for initialization.";
1319 if (layout == hash_table->getLayout()) {
1325 const auto key_component_count =
1326 join_bucket_info[0].inverse_bucket_sizes_for_dimension.size();
1328 const auto key_handler =
1331 join_bucket_info[0].inverse_bucket_sizes_for_dimension.data());
1334 dummy_str_proxy_translation_maps_ptrs_and_offsets;
1341 dummy_str_proxy_translation_maps_ptrs_and_offsets,
1348 ts2 = std::chrono::steady_clock::now();
1351 std::string(
"Unrecognized error when initializing CPU overlaps hash table (") +
1354 std::shared_ptr<BaselineHashTable> hash_table = builder.getHashTable();
1355 if (skip_hashtable_caching) {
1356 VLOG(1) <<
"Skip to cache overlaps join hashtable";
1358 auto hashtable_build_time =
1359 std::chrono::duration_cast<std::chrono::milliseconds>(ts2 - ts1).count();
1364 hashtable_build_time);
1371 std::shared_ptr<BaselineHashTable> OverlapsJoinHashTable::initHashTableOnGpu(
1372 const std::vector<JoinColumn>& join_columns,
1373 const std::vector<JoinColumnTypeInfo>& join_column_types,
1374 const std::vector<JoinBucketInfo>& join_bucket_info,
1376 const size_t entry_count,
1377 const size_t emitted_keys_count,
1378 const size_t device_id) {
1381 VLOG(1) <<
"Building overlaps join hash table on GPU.";
1384 auto data_mgr =
executor_->getDataMgr();
1389 CHECK(!join_bucket_info.empty());
1390 auto& inverse_bucket_sizes_for_dimension =
1391 join_bucket_info[0].inverse_bucket_sizes_for_dimension;
1393 inverse_bucket_sizes_for_dimension, allocator);
1394 const auto key_handler =
OverlapsKeyHandler(inverse_bucket_sizes_for_dimension.size(),
1396 inverse_bucket_sizes_gpu);
1410 std::string(
"Unrecognized error when initializing GPU overlaps hash table (") +
1416 std::shared_ptr<BaselineHashTable> OverlapsJoinHashTable::copyCpuHashTableToGpu(
1417 std::shared_ptr<BaselineHashTable>& cpu_hash_table,
1419 const size_t entry_count,
1420 const size_t emitted_keys_count,
1421 const size_t device_id) {
1424 auto data_mgr =
executor_->getDataMgr();
1435 std::shared_ptr<BaselineHashTable> gpu_hash_table = gpu_builder.
getHashTable();
1436 CHECK(gpu_hash_table);
1437 auto gpu_buffer_ptr = gpu_hash_table->getGpuBuffer();
1438 CHECK(gpu_buffer_ptr);
1442 auto device_allocator = std::make_unique<CudaAllocator>(
1444 device_allocator->copyToDevice(
1446 cpu_hash_table->getCpuBuffer(),
1448 return gpu_hash_table;
1453 #define LL_CONTEXT executor_->cgen_state_->context_
1454 #define LL_BUILDER executor_->cgen_state_->ir_builder_
1455 #define LL_INT(v) executor_->cgen_state_->llInt(v)
1456 #define LL_FP(v) executor_->cgen_state_->llFp(v)
1457 #define ROW_FUNC executor_->cgen_state_->row_func_
1462 CHECK(key_component_width == 4 || key_component_width == 8);
1464 llvm::Value* key_buff_lv{
nullptr};
1465 switch (key_component_width) {
1479 const auto outer_geo = inner_outer_pair.second;
1480 const auto outer_geo_ti = outer_geo->get_type_info();
1482 llvm::Value* arr_ptr =
nullptr;
1486 if (outer_geo_ti.is_geometry()) {
1491 if (
const auto outer_geo_col = dynamic_cast<const Analyzer::ColumnVar*>(outer_geo)) {
1492 const auto outer_geo_col_lvs = code_generator.
codegen(outer_geo_col,
true, co);
1493 CHECK_EQ(outer_geo_col_lvs.size(), size_t(1));
1494 const auto coords_cd =
executor_->getCatalog()->getMetadataForColumn(
1495 outer_geo_col->get_table_id(), outer_geo_col->get_column_id() + 1);
1498 const auto array_ptr =
executor_->cgen_state_->emitExternalCall(
1500 llvm::Type::getInt8PtrTy(
executor_->cgen_state_->context_),
1501 {outer_geo_col_lvs.front(), code_generator.
posArg(outer_geo_col)});
1502 CHECK(coords_cd->columnType.get_elem_type().get_type() ==
kTINYINT)
1503 <<
"Only TINYINT coordinates columns are supported in geo overlaps hash "
1506 coords_cd->columnType.get_elem_type());
1507 }
else if (
const auto outer_geo_function_operator =
1508 dynamic_cast<const Analyzer::GeoOperator*>(outer_geo)) {
1510 const auto outer_geo_function_operator_lvs =
1511 code_generator.
codegen(outer_geo_function_operator,
true, co);
1512 CHECK_EQ(outer_geo_function_operator_lvs.size(), size_t(2));
1513 arr_ptr = outer_geo_function_operator_lvs.front();
1514 }
else if (
const auto outer_geo_expr =
1515 dynamic_cast<const Analyzer::GeoExpr*>(outer_geo)) {
1518 }
else if (outer_geo_ti.is_fixlen_array()) {
1520 const auto outer_geo_cast_coord_array =
1524 outer_geo_cast_coord_array->get_operand());
1525 CHECK(outer_geo_coord_array);
1526 CHECK(outer_geo_coord_array->isLocalAlloc());
1527 CHECK_EQ(outer_geo_coord_array->getElementCount(), 2);
1531 CHECK_EQ(outer_geo_ti.get_size(), int(2 * elem_size));
1532 const auto outer_geo_constructed_lvs = code_generator.codegen(outer_geo,
true, co);
1534 const auto array_ptr = outer_geo_constructed_lvs.front();
1536 array_ptr->getType()->getScalarType()->getPointerElementType(),
1542 LOG(
FATAL) <<
"Overlaps key currently only supported for geospatial columns and "
1543 "constructed points.";
1546 for (
size_t i = 0; i < 2; i++) {
1547 const auto key_comp_dest_lv =
LL_BUILDER.CreateGEP(
1548 key_buff_lv->getType()->getScalarType()->getPointerElementType(),
1556 ? executor_->cgen_state_->emitExternalCall(
1557 "get_bucket_key_for_range_compressed",
1559 {arr_ptr,
LL_INT(i),
LL_FP(inverse_bucket_sizes_for_dimension_[i])})
1560 : executor_->cgen_state_->emitExternalCall(
1561 "get_bucket_key_for_range_double",
1563 {arr_ptr,
LL_INT(i),
LL_FP(inverse_bucket_sizes_for_dimension_[i])});
1566 LL_BUILDER.CreateStore(col_lv, key_comp_dest_lv);
1575 CHECK(key_component_width == 4 || key_component_width == 8);
1580 VLOG(1) <<
"Performing codgen for ManyToMany";
1582 const auto outer_col = inner_outer_pair.second;
1585 const auto col_lvs = code_generator.
codegen(outer_col,
true, co);
1586 CHECK_EQ(col_lvs.size(), size_t(1));
1589 CHECK(outer_col_var);
1590 const auto coords_cd =
executor_->getCatalog()->getMetadataForColumn(
1591 outer_col_var->get_table_id(), outer_col_var->get_column_id());
1594 const auto array_ptr =
executor_->cgen_state_->emitExternalCall(
1596 llvm::Type::getInt8PtrTy(
executor_->cgen_state_->context_),
1597 {col_lvs.front(), code_generator.
posArg(outer_col)});
1603 array_ptr->setName(
"array_ptr");
1605 auto num_keys_lv = executor_->cgen_state_->emitExternalCall(
1606 "get_num_buckets_for_bounds",
1610 LL_FP(inverse_bucket_sizes_for_dimension_[0]),
1611 LL_FP(inverse_bucket_sizes_for_dimension_[1])});
1612 num_keys_lv->setName(
"num_keys_lv");
1614 return {num_keys_lv, array_ptr};
1619 const size_t index) {
1622 VLOG(1) <<
"Building codegenMatchingSet for ManyToMany";
1624 CHECK(key_component_width == 4 || key_component_width == 8);
1627 const auto composite_dict_ptr_type =
1628 llvm::Type::getIntNPtrTy(
LL_CONTEXT, key_component_width * 8);
1629 const auto composite_key_dict =
1630 hash_ptr->getType()->isPointerTy()
1631 ?
LL_BUILDER.CreatePointerCast(hash_ptr, composite_dict_ptr_type)
1632 :
LL_BUILDER.CreateIntToPtr(hash_ptr, composite_dict_ptr_type);
1635 auto one_to_many_ptr = hash_ptr;
1637 if (one_to_many_ptr->getType()->isPointerTy()) {
1641 CHECK(one_to_many_ptr->getType()->isIntegerTy(64));
1651 const int max_array_size = 200;
1653 const auto out_arr_lv =
LL_BUILDER.CreateAlloca(arr_type);
1654 out_arr_lv->setName(
"out_arr");
1656 const auto casted_out_arr_lv =
1657 LL_BUILDER.CreatePointerCast(out_arr_lv, arr_type->getPointerTo());
1659 const auto element_ptr =
LL_BUILDER.CreateGEP(arr_type, casted_out_arr_lv,
LL_INT(0));
1661 auto rowid_ptr_i32 =
1664 const auto candidate_count_lv =
executor_->cgen_state_->emitExternalCall(
1665 "get_candidate_rows",
1670 many_to_many_args[1],
1674 many_to_many_args[0],
1675 LL_INT(key_component_count),
1678 LL_INT(composite_key_dict_size),
1682 const auto slot_lv =
LL_INT(int64_t(0));
1684 return {rowid_ptr_i32, candidate_count_lv, slot_lv};
1686 VLOG(1) <<
"Building codegenMatchingSet for Baseline";
1689 CHECK(key_component_width == 4 || key_component_width == 8);
1693 const auto composite_dict_ptr_type =
1694 llvm::Type::getIntNPtrTy(
LL_CONTEXT, key_component_width * 8);
1695 const auto composite_key_dict =
1696 hash_ptr->getType()->isPointerTy()
1697 ?
LL_BUILDER.CreatePointerCast(hash_ptr, composite_dict_ptr_type)
1698 :
LL_BUILDER.CreateIntToPtr(hash_ptr, composite_dict_ptr_type);
1700 const auto key =
executor_->cgen_state_->emitExternalCall(
1701 "get_composite_key_index_" +
std::to_string(key_component_width * 8),
1704 LL_INT(key_component_count),
1707 auto one_to_many_ptr = hash_ptr;
1708 if (one_to_many_ptr->getType()->isPointerTy()) {
1712 CHECK(one_to_many_ptr->getType()->isIntegerTy(64));
1718 std::vector<llvm::Value*>{
1731 const int device_id,
1737 auto buffer_size = hash_table->getHashTableBufferSize(device_type);
1739 std::unique_ptr<int8_t[]> buffer_copy;
1741 buffer_copy = std::make_unique<int8_t[]>(buffer_size);
1743 auto data_mgr =
executor_->getDataMgr();
1744 auto device_allocator = std::make_unique<CudaAllocator>(
1747 device_allocator->copyFromDevice(buffer_copy.get(), buffer, buffer_size);
1749 auto ptr1 = buffer_copy ? buffer_copy.get() :
reinterpret_cast<const int8_t*
>(buffer);
1751 auto ptr1 =
reinterpret_cast<const int8_t*
>(buffer);
1763 hash_table->getEntryCount(),
1774 const int device_id)
const {
1778 auto buffer_size = hash_table->getHashTableBufferSize(device_type);
1780 std::unique_ptr<int8_t[]> buffer_copy;
1782 buffer_copy = std::make_unique<int8_t[]>(buffer_size);
1784 auto data_mgr =
executor_->getDataMgr();
1785 auto allocator = std::make_unique<CudaAllocator>(
1788 allocator->copyFromDevice(buffer_copy.get(), buffer, buffer_size);
1790 auto ptr1 = buffer_copy ? buffer_copy.get() :
reinterpret_cast<const int8_t*
>(buffer);
1792 auto ptr1 =
reinterpret_cast<const int8_t*
>(buffer);
1800 hash_table->getEntryCount(),
1809 const std::vector<InnerOuter>& inner_outer_pairs)
const {
1812 this->
executor_->getDataMgr()->gpusPresent() &&
1834 VLOG(1) <<
"Checking CPU hash table cache.";
1838 auto cached_hashtable =
1839 hash_table_cache_->getItemFromCache(key, item_type, device_identifier, meta_info);
1840 if (cached_hashtable) {
1841 return cached_hashtable;
1846 std::optional<std::pair<size_t, size_t>>
1854 auto cached_hashtable =
1855 hash_table_cache_->getItemFromCache(key, item_type, device_identifier, metaInfo);
1856 if (cached_hashtable) {
1857 return std::make_pair(cached_hashtable->getEntryCount() / 2,
1858 cached_hashtable->getEmittedKeysCount());
1860 return std::nullopt;
1866 std::shared_ptr<HashTable> hashtable_ptr,
1868 size_t hashtable_building_time) {
1870 CHECK(hashtable_ptr && !hashtable_ptr->getGpuBuffer());
1880 hashtable_building_time,
static std::vector< int > collectFragmentIds(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments)
llvm::Value * codegenKey(const CompilationOptions &)
const JoinType join_type_
int getInnerTableId() const noexceptoverride
virtual HashJoinMatchingSet codegenMatchingSet(const CompilationOptions &, const size_t)=0
virtual void reifyWithLayout(const HashType layout)
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)
std::shared_ptr< HashTable > initHashTableOnCpuFromCache(QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier)
static bool isInvalidHashTableCacheKey(const std::vector< QueryPlanHash > &cache_keys)
std::vector< ChunkKey > cache_key_chunks
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)
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)
bool overlaps_allow_gpu_build
HashTableProps prev_props
T * transfer_flat_object_to_gpu(const T &object, DeviceAllocator &allocator)
size_t getEntryCount() const
const size_t table_tuple_count_
std::ostream & operator<<(std::ostream &os, const SessionInfo &session_info)
static std::pair< std::vector< InnerOuter >, std::vector< InnerOuterStringOpInfos > > normalizeColumnPairs(const Analyzer::BinOper *condition, const Catalog_Namespace::Catalog &cat, const TemporaryTables *temporary_tables)
void hll_unify(T1 *lhs, T2 *rhs, const size_t m)
bool previousIterationValid() const
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)
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's parse tree etc.
const RegisteredQueryHint & getRegisteredQueryHint()
llvm::Value * posArg(const Analyzer::Expr *) const
std::vector< std::shared_ptr< HashTable > > hash_tables_for_device_
llvm::Value * castArrayPointer(llvm::Value *ptr, const SQLTypeInfo &elem_ti)
std::optional< std::pair< size_t, size_t > > getApproximateTupleCountFromCache(QueryPlanHash key, CacheItemType item_type, DeviceIdentifier device_identifier)
RegisteredQueryHint query_hint_
#define DEBUG_TIMER_NEW_THREAD(parent_thread_id)
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
static std::unique_ptr< OverlapsTuningParamRecycler > auto_tuner_cache_
const Data_Namespace::MemoryLevel effective_memory_level_
auto getMinBucketSize() const
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)
size_t crt_reverse_search_iteration
std::vector< double > computeBucketSizes() const
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)
size_t emitted_keys_count
HashType getHashType() const noexceptoverride
bool keysPerBinUnderThreshold() const
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< ColumnsForDevice > & columns_per_device_
const std::vector< InnerOuter > & inner_outer_pairs_
const std::vector< JoinColumnTypeInfo > join_column_types
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
bool keysPerBinIncreasing() const
const ColumnDescriptor * get_column_descriptor_maybe(const int col_id, const int table_id, const Catalog_Namespace::Catalog &cat)
void reify(const HashType preferred_layout)
double chosen_overlaps_threshold
ColumnCacheMap & column_cache_
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
bool tuneLargerOneStep(const double step_overide)
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_hint, const TableIdToNodeMap &table_id_to_node_map)
int8_t * getJoinHashBuffer(const ExecutorDeviceType device_type, const int device_id) const
DecodedJoinHashBufferSet toSet(const ExecutorDeviceType device_type, const int device_id) const override
DEVICE auto accumulate(ARGS &&...args)
TuningState(const size_t overlaps_max_table_size_bytes, const double overlaps_target_entries_per_bin)
double g_overlaps_target_entries_per_bin
HashTableBuildDagMap hashtable_build_dag_map_
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)
size_t g_overlaps_max_table_size_bytes
std::vector< llvm::Value * > codegenManyKey(const CompilationOptions &)
std::vector< QueryPlanHash > hashtable_cache_key_
virtual int getInnerTableId() const noexcept=0
bool hashTableTooBig() const
std::vector< double > getInverseBucketSizes()
const double min_threshold_
void setOverlapsHashtableMetaInfo(size_t max_table_size_bytes, double bucket_threshold, std::vector< double > &bucket_sizes)
size_t overlaps_max_table_size_bytes
std::unordered_map< int, std::unordered_map< int, std::shared_ptr< const ColumnarResults >>> ColumnCacheMap
HashTable * getHashTableForDevice(const size_t device_id) const
const InputTableInfo & get_inner_query_info(const int inner_table_id, const std::vector< InputTableInfo > &query_infos)
double chosen_overlaps_bucket_threshold_
std::vector< llvm::Value * > codegen(const Analyzer::Expr *, const bool fetch_columns, const CompilationOptions &)
std::vector< double > inverse_bucket_sizes_for_dimension_
std::optional< HashType > layout_override_
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::ThreadId parent_thread_id)
std::pair< std::vector< const int32_t * >, std::vector< int32_t >> StrProxyTranslationMapsPtrsAndOffsets
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)
bool bucketThresholdsBelowMinThreshold() const
std::unique_ptr< BaselineHashTable > getHashTable()
static std::string getHashTypeString(HashType ht) noexcept
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.
void setInverseBucketSizeInfo(const std::vector< double > &inverse_bucket_sizes, std::vector< ColumnsForDevice > &columns_per_device, const size_t device_count)
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
ColumnsForDevice fetchColumnsForDevice(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments, const int device_id, DeviceAllocator *dev_buff_owner)
double overlaps_target_entries_per_bin
size_t getKeyComponentCount() const
HashJoinMatchingSet codegenMatchingSet(const CompilationOptions &, const size_t) override
bool tuneOneStep(const TuningState::TuningDirection tuning_direction)
CUstream getQueryEngineCudaStreamForDevice(int device_num)
size_t offsetBufferOff() const noexceptoverride
size_t countBufferOff() const noexceptoverride
size_t shardCount() const
HashtableCacheMetaInfo hashtable_cache_meta_info_
bool operator()(const HashTableProps &new_props, const bool new_overlaps_threshold)
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)
static HashTableProps invalid()
size_t getNumTuplesUpperBound() const
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 DEBUG_TIMER(name)
std::vector< double > bucket_thresholds_
std::mutex cpu_hash_table_buff_mutex_
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 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.
T * transfer_vector_of_flat_objects_to_gpu(const std::vector< T > &vec, DeviceAllocator &allocator)
Data_Namespace::MemoryLevel getEffectiveMemoryLevel(const std::vector< InnerOuter > &inner_outer_pairs) const
std::vector< JoinBucketInfo > join_buckets
void copyFromDevice(void *host_dst, const void *device_src, const size_t num_bytes) const override
static constexpr DeviceIdentifier CPU_DEVICE_IDENTIFIER
bool tuneSmallerOneStep(const double step_overide)
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_
size_t getKeyComponentWidth() const
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
std::vector< double > current_bucket_sizes_
const std::vector< JoinColumn > join_columns
bool isAnyQueryHintDelivered() const
static bool layoutRequiresAdditionalBuffers(HashType layout) noexcept
std::vector< double > bucket_sizes
static CompositeKeyInfo getCompositeKeyInfo(const std::vector< InnerOuter > &inner_outer_pairs, const Executor *executor, const std::vector< InnerOuterStringOpInfos > &inner_outer_string_op_infos_pairs={})
size_t chosen_overlaps_max_table_size_bytes_