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);
70 CHECK(!inner_outer_pairs.empty());
72 const auto getHashTableType =
73 [](
const std::shared_ptr<Analyzer::BinOper> condition,
74 const std::vector<InnerOuter>& inner_outer_pairs) ->
HashType {
76 if (condition->is_overlaps_oper()) {
77 CHECK_EQ(inner_outer_pairs.size(), size_t(1));
78 if (inner_outer_pairs[0].first->get_type_info().is_array() &&
79 inner_outer_pairs[0].second->get_type_info().is_array() &&
81 inner_outer_pairs[0].second->get_type_info().get_size() == 32) {
88 const auto layout = getHashTableType(condition, inner_outer_pairs);
92 <<
" for qual: " << condition->toString();
93 ts1 = std::chrono::steady_clock::now();
96 const auto qi_0 = query_infos[0].info.getNumTuplesUpperBound();
97 const auto qi_1 = query_infos[1].info.getNumTuplesUpperBound();
99 VLOG(1) <<
"table_key = " << query_infos[0].table_key <<
" has " << qi_0 <<
" tuples.";
100 VLOG(1) <<
"table_key = " << query_infos[1].table_key <<
" has " << qi_1 <<
" tuples.";
102 const auto& query_info =
106 if (total_entries > static_cast<size_t>(std::numeric_limits<int32_t>::max())) {
110 auto join_hash_table = std::make_shared<OverlapsJoinHashTable>(condition,
119 hashtable_build_dag_map,
120 table_id_to_node_map);
122 join_hash_table->reify(layout);
124 throw HashJoinFail(std::string(
"Could not build a 1-to-1 correspondence for columns "
125 "involved in overlaps join | ") +
128 throw HashJoinFail(std::string(
"Could not build hash tables for overlaps join | "
129 "Inner table too big. Attempt manual table reordering "
130 "or create a single fragment inner table. | ") +
134 }
catch (
const std::exception& e) {
135 throw HashJoinFail(std::string(
"Failed to build hash tables for overlaps join | ") +
139 ts2 = std::chrono::steady_clock::now();
141 << std::chrono::duration_cast<std::chrono::milliseconds>(ts2 - ts1).count()
144 return join_hash_table;
150 const std::vector<double>& bucket_sizes,
151 const std::vector<double>& bucket_thresholds,
152 const double initial_value) {
153 std::vector<double> corrected_bucket_sizes(bucket_sizes);
154 for (
size_t i = 0; i != bucket_sizes.size(); ++i) {
155 if (bucket_sizes[i] == initial_value) {
156 corrected_bucket_sizes[i] = bucket_thresholds[i];
159 return corrected_bucket_sizes;
163 const std::vector<double>& bucket_thresholds,
167 const std::vector<InnerOuter>& inner_outer_pairs,
168 const Executor* executor) {
170 CHECK_EQ(inner_outer_pairs.size(), 1u);
172 const auto col = inner_outer_pairs[0].first;
174 const auto col_ti = col->get_type_info();
175 CHECK(col_ti.is_array());
178 const size_t num_dims{2};
179 const double initial_bin_value{0.0};
180 std::vector<double> bucket_sizes(num_dims, initial_bin_value);
181 CHECK_EQ(bucket_thresholds.size(), num_dims);
184 <<
"Computing x and y bucket sizes for overlaps hash join with maximum bucket size "
191 bucket_sizes, join_column, join_column_type, bucket_thresholds, thread_count);
196 const int device_id = 0;
197 auto data_mgr = executor->getDataMgr();
200 auto device_bucket_sizes_gpu =
204 auto device_bucket_thresholds_gpu =
209 join_column_type_gpu,
210 device_bucket_thresholds_gpu);
211 allocator.
copyFromDevice(reinterpret_cast<int8_t*>(bucket_sizes.data()),
212 reinterpret_cast<int8_t*>(device_bucket_sizes_gpu),
213 bucket_sizes.size() *
sizeof(double));
217 bucket_sizes, bucket_thresholds, initial_bin_value);
219 VLOG(1) <<
"Computed x and y bucket sizes for overlaps hash join: ("
220 << corrected_bucket_sizes[0] <<
", " << corrected_bucket_sizes[1] <<
")";
222 return corrected_bucket_sizes;
227 const size_t emitted_keys_count,
228 const size_t hash_table_size,
229 const std::vector<double>& bucket_sizes)
230 : entry_count(entry_count)
231 , emitted_keys_count(emitted_keys_count)
232 , keys_per_bin(entry_count == 0 ? std::numeric_limits<double>::max()
233 : emitted_keys_count / (entry_count / 2.0))
234 , hash_table_size(hash_table_size)
235 , bucket_sizes(bucket_sizes) {}
247 os <<
" entry_count: " << props.
entry_count <<
", emitted_keys "
255 const double overlaps_target_entries_per_bin)
258 , chosen_overlaps_threshold(-1)
260 , crt_reverse_search_iteration(0)
261 , overlaps_max_table_size_bytes(overlaps_max_table_size_bytes)
262 , overlaps_target_entries_per_bin(overlaps_target_entries_per_bin) {}
278 const size_t max_reverse_search_iterations{8};
285 prev_props = crt_props;
286 crt_props = new_props;
289 if (hashTableTooBig() || keysPerBinIncreasing()) {
290 if (hashTableTooBig()) {
291 VLOG(1) <<
"Reached hash table size limit: " << overlaps_max_table_size_bytes
292 <<
" with " << crt_props.hash_table_size <<
" byte hash table, "
293 << crt_props.keys_per_bin <<
" keys per bin.";
294 }
else if (keysPerBinIncreasing()) {
295 VLOG(1) <<
"Keys per bin increasing from " << prev_props.keys_per_bin <<
" to "
296 << crt_props.keys_per_bin;
297 CHECK(previousIterationValid());
299 if (previousIterationValid()) {
300 VLOG(1) <<
"Using previous threshold value " << chosen_overlaps_threshold;
301 crt_props = prev_props;
304 CHECK(hashTableTooBig());
305 crt_reverse_search_iteration++;
306 chosen_overlaps_threshold = new_overlaps_threshold;
308 if (crt_reverse_search_iteration == max_reverse_search_iterations) {
309 VLOG(1) <<
"Hit maximum number (" << max_reverse_search_iterations
310 <<
") of reverse tuning iterations. Aborting tuning";
315 if (crt_reverse_search_iteration > 1 &&
316 crt_props.hash_table_size == prev_props.hash_table_size) {
318 VLOG(1) <<
"Hash table size not decreasing (" << crt_props.hash_table_size
319 <<
" bytes) and still above maximum allowed size ("
320 << overlaps_max_table_size_bytes <<
" bytes). Aborting tuning";
326 if (crt_step == 1 && crt_reverse_search_iteration == 1) {
328 <<
"First iteration of overlaps tuning led to hash table size over "
329 "limit. Reversing search to try larger bin sizes (previous threshold: "
330 << chosen_overlaps_threshold <<
")";
332 tuning_direction = TuningDirection::LARGER;
339 chosen_overlaps_threshold = new_overlaps_threshold;
341 if (keysPerBinUnderThreshold()) {
342 VLOG(1) <<
"Hash table reached size " << crt_props.hash_table_size
343 <<
" with keys per bin " << crt_props.keys_per_bin <<
" under threshold "
344 << overlaps_target_entries_per_bin <<
". Terminating bucket size loop.";
348 if (crt_reverse_search_iteration > 0) {
352 VLOG(1) <<
"On reverse (larger tuning direction) search found workable "
353 <<
" hash table size of " << crt_props.hash_table_size
354 <<
" with keys per bin " << crt_props.keys_per_bin
355 <<
". Terminating bucket size loop.";
363 return crt_props.hash_table_size > overlaps_max_table_size_bytes;
367 return crt_props.keys_per_bin > prev_props.keys_per_bin;
371 return tuning_direction == TuningDirection::SMALLER && crt_step > 1;
375 return crt_props.keys_per_bin < overlaps_target_entries_per_bin;
383 const double min_threshold,
385 const std::vector<ColumnsForDevice>& columns_per_device,
386 const std::vector<InnerOuter>& inner_outer_pairs,
387 const size_t table_tuple_count,
388 const Executor* executor)
390 , bucket_thresholds_(num_dims_, bucket_threshold)
392 , min_threshold_(min_threshold)
393 , effective_memory_level_(effective_memory_level)
394 , columns_per_device_(columns_per_device)
395 , inner_outer_pairs_(inner_outer_pairs)
396 , table_tuple_count_(table_tuple_count)
398 CHECK(!columns_per_device_.empty());
404 return tuneOneStep(tuning_direction, step_);
408 const double step_overide) {
409 if (table_tuple_count_ == 0) {
412 if (tuning_direction == TuningState::TuningDirection::SMALLER) {
413 return tuneSmallerOneStep(step_overide);
415 return tuneLargerOneStep(step_overide);
419 return *std::min_element(bucket_thresholds_.begin(), bucket_thresholds_.end());
429 if (num_steps_ == 0) {
430 CHECK_EQ(current_bucket_sizes_.size(),
static_cast<size_t>(0));
431 current_bucket_sizes_ = computeBucketSizes();
433 CHECK_EQ(current_bucket_sizes_.size(), num_dims_);
434 std::vector<double> inverse_bucket_sizes;
435 for (
const auto s : current_bucket_sizes_) {
436 inverse_bucket_sizes.emplace_back(1.0 / s);
438 return inverse_bucket_sizes;
443 for (
const auto& t : bucket_thresholds_) {
444 if (t < min_threshold_) {
452 if (table_tuple_count_ == 0) {
453 return std::vector<double>(num_dims_, 0);
456 effective_memory_level_,
457 columns_per_device_.front().join_columns[0],
458 columns_per_device_.front().join_column_types[0],
464 if (!current_bucket_sizes_.empty()) {
465 CHECK_EQ(current_bucket_sizes_.size(), bucket_thresholds_.size());
466 bucket_thresholds_ = current_bucket_sizes_;
467 for (
auto& t : bucket_thresholds_) {
471 if (bucketThresholdsBelowMinThreshold()) {
472 VLOG(1) <<
"Aborting overlaps tuning as at least one bucket size is below min "
476 const auto next_bucket_sizes = computeBucketSizes();
477 if (next_bucket_sizes == current_bucket_sizes_) {
478 VLOG(1) <<
"Aborting overlaps tuning as bucket size is no longer changing.";
482 current_bucket_sizes_ = next_bucket_sizes;
488 if (!current_bucket_sizes_.empty()) {
489 CHECK_EQ(current_bucket_sizes_.size(), bucket_thresholds_.size());
490 bucket_thresholds_ = current_bucket_sizes_;
493 for (
auto& t : bucket_thresholds_) {
503 current_bucket_sizes_ = bucket_thresholds_;
510 size_t num_steps_{0};
525 os <<
"Step Num: " << tuner.
num_steps_ <<
", Threshold: " << std::fixed <<
"("
527 <<
", Step Size: " << std::fixed << tuner.
step_ <<
", Min: " << std::fixed
537 const auto& query_info =
542 <<
", table_id: " << table_id;
543 if (query_info.fragments.empty()) {
548 std::optional<double> overlaps_threshold_override;
550 auto skip_hashtable_caching =
false;
552 VLOG(1) <<
"Setting overlaps bucket threshold "
553 "\'overlaps_hashjoin_bucket_threshold\' via "
559 std::ostringstream oss;
560 oss <<
"User requests to change a threshold \'overlaps_max_table_size_bytes\' via "
562 if (!overlaps_threshold_override.has_value()) {
563 oss <<
": " << overlaps_max_table_size_bytes <<
" -> "
567 oss <<
", but is skipped since the query hint also changes the threshold "
568 "\'overlaps_hashjoin_bucket_threshold\'";
570 VLOG(1) << oss.str();
573 VLOG(1) <<
"User requests to skip caching overlaps join hashtable and its tuned "
574 "parameters for this query";
575 skip_hashtable_caching =
true;
578 VLOG(1) <<
"User requests to change a threshold \'overlaps_keys_per_bin\' via query "
580 << overlaps_target_entries_per_bin <<
" -> "
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";
598 allow_gpu_hashtable_build =
false;
599 VLOG(1) <<
"A user forces to build GPU hash table for this overlaps join operator "
601 "skip it since either GPU is not presented or CPU execution mode is set";
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>(
615 std::vector<std::vector<Fragmenter_Namespace::FragmentInfo>> fragments_per_device;
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(
622 : query_info.fragments);
623 const size_t crt_num_tuples =
625 fragments_per_device.back().end(),
627 [](
const auto& sum,
const auto& fragment) {
628 return sum + fragment.getNumTuples();
630 total_num_tuples += crt_num_tuples;
631 const auto columns_for_device =
635 allow_gpu_hashtable_build
636 ? dev_buff_owners[device_id].get()
638 columns_per_device.push_back(columns_for_device);
642 auto hashtable_access_path_info =
650 fragments_per_device,
654 table_keys_ = hashtable_access_path_info.table_keys;
656 auto get_inner_table_key = [
this]() {
658 return col_var->getTableKey();
662 const auto& table_key = get_inner_table_key();
668 if (overlaps_threshold_override) {
670 BucketSizeTuner tuner(*overlaps_threshold_override,
678 const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
680 auto [entry_count, emitted_keys_count] =
682 inverse_bucket_sizes,
684 overlaps_max_table_size_bytes,
685 *overlaps_threshold_override);
691 *overlaps_threshold_override,
692 inverse_bucket_sizes,
693 fragments_per_device,
701 skip_hashtable_caching,
702 overlaps_max_table_size_bytes,
703 *overlaps_threshold_override);
705 double overlaps_bucket_threshold = std::numeric_limits<double>::max();
707 overlaps_bucket_threshold,
709 fragments_per_device,
711 std::vector<size_t> per_device_chunk_key;
713 get_inner_table_key().table_id > 0) {
714 for (
int device_id = 0; device_id <
device_count_; ++device_id) {
719 per_device_chunk_key.push_back(chunk_key_hash);
722 columns_per_device.front().join_columns.front().num_elems,
725 overlaps_max_table_size_bytes,
726 overlaps_bucket_threshold,
734 auto cached_bucket_threshold =
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);
744 overlaps_bucket_threshold,
745 inverse_bucket_sizes,
746 fragments_per_device,
749 if (
auto hash_table =
760 VLOG(1) <<
"Using cached hash table bucket size";
766 hash_table->getEntryCount(),
767 hash_table->getEmittedKeysCount(),
768 skip_hashtable_caching,
769 overlaps_max_table_size_bytes,
770 overlaps_bucket_threshold);
772 VLOG(1) <<
"Computing bucket size for cached bucket threshold";
774 BucketSizeTuner tuner(overlaps_bucket_threshold,
783 const auto inverse_bucket_sizes = tuner.getInverseBucketSizes();
785 auto [entry_count, emitted_keys_count] =
787 inverse_bucket_sizes,
789 overlaps_max_table_size_bytes,
790 overlaps_bucket_threshold);
794 overlaps_bucket_threshold,
795 inverse_bucket_sizes,
796 fragments_per_device,
805 skip_hashtable_caching,
806 overlaps_max_table_size_bytes,
807 overlaps_bucket_threshold);
811 BucketSizeTuner tuner(
812 overlaps_bucket_threshold,
821 VLOG(1) <<
"Running overlaps join size auto tune with parameters: " << tuner;
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();
829 const auto [crt_entry_count, crt_emitted_keys_count] =
831 inverse_bucket_sizes,
833 tuning_state.overlaps_max_table_size_bytes,
834 tuning_state.chosen_overlaps_threshold);
836 inverse_bucket_sizes.size(), crt_emitted_keys_count, crt_entry_count);
837 HashTableProps crt_props(crt_entry_count,
838 crt_emitted_keys_count,
840 inverse_bucket_sizes);
841 VLOG(1) <<
"Tuner output: " << tuner <<
" with properties " << crt_props;
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) {
851 const auto& crt_props = tuning_state.crt_props;
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);
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.";
868 VLOG(1) <<
"Final tuner output: " << tuner <<
" with properties " << crt_props;
870 VLOG(1) <<
"Final bucket sizes: ";
872 VLOG(1) <<
"dim[" << dim
875 CHECK_GE(tuning_state.chosen_overlaps_threshold,
double(0));
877 tuning_state.chosen_overlaps_threshold,
879 fragments_per_device,
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";
886 tuning_state.chosen_overlaps_threshold,
895 overlaps_bucket_threshold = tuning_state.chosen_overlaps_threshold;
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);
910 size_t emitted_keys_count,
911 size_t entry_count)
const {
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;
923 const std::vector<Fragmenter_Namespace::FragmentInfo>& fragments,
928 std::vector<JoinColumn> join_columns;
929 std::vector<std::shared_ptr<Chunk_NS::Chunk>> chunks_owner;
930 std::vector<JoinColumnTypeInfo> join_column_types;
931 std::vector<std::shared_ptr<void>> malloc_owner;
933 const auto inner_col = inner_outer_pair.first;
935 if (inner_cd && inner_cd->isVirtualCol) {
940 effective_memory_level,
947 const auto& ti = inner_col->get_type_info();
951 inline_int_null_value<int64_t>(),
955 CHECK(ti.is_array()) <<
"Overlaps join currently only supported for arrays.";
957 return {join_columns, join_column_types, chunks_owner, {}, malloc_owner};
961 const size_t shard_count,
962 const std::vector<double>& inverse_bucket_sizes_for_dimension,
963 std::vector<ColumnsForDevice>& columns_per_device,
964 const size_t chosen_max_hashtable_size,
965 const double chosen_bucket_threshold) {
966 CHECK(!inverse_bucket_sizes_for_dimension.empty());
967 const auto [tuple_count, emitted_keys_count] =
970 chosen_max_hashtable_size,
971 chosen_bucket_threshold);
972 const auto entry_count = 2 * std::max(tuple_count,
size_t(1));
974 return std::make_pair(
980 const std::vector<double>& inverse_bucket_sizes_for_dimension,
981 std::vector<ColumnsForDevice>& columns_per_device,
982 const size_t chosen_max_hashtable_size,
983 const double chosen_bucket_threshold) {
994 const auto padded_size_bytes = count_distinct_desc.bitmapPaddedSizeBytes();
996 CHECK(!columns_per_device.empty() && !columns_per_device.front().join_columns.empty());
997 if (columns_per_device.front().join_columns.front().num_elems == 0) {
998 return std::make_pair(0, 0);
1004 for (
size_t device_id = 0; device_id < columns_per_device.size(); ++device_id) {
1005 auto& columns_for_device = columns_per_device[device_id];
1006 columns_for_device.setBucketInfo(inverse_bucket_sizes_for_dimension,
1011 CHECK_EQ(columns_per_device.front().join_columns.size(),
1012 columns_per_device.front().join_buckets.size());
1016 const auto cached_count_info =
1020 if (cached_count_info) {
1021 VLOG(1) <<
"Using a cached tuple count: " << cached_count_info->first
1022 <<
", emitted keys count: " << cached_count_info->second;
1023 return *cached_count_info;
1026 std::vector<uint8_t> hll_buffer_all_cpus(thread_count * padded_size_bytes);
1027 auto hll_result = &hll_buffer_all_cpus[0];
1029 std::vector<int32_t> num_keys_for_row;
1031 num_keys_for_row.resize(columns_per_device.front().join_columns[0].num_elems);
1035 count_distinct_desc.bitmap_sz_bits,
1037 columns_per_device.front().join_columns,
1038 columns_per_device.front().join_column_types,
1039 columns_per_device.front().join_buckets,
1041 for (
int i = 1; i < thread_count; ++i) {
1043 hll_result + i * padded_size_bytes,
1044 1 << count_distinct_desc.bitmap_sz_bits);
1046 return std::make_pair(
1047 hll_size(hll_result, count_distinct_desc.bitmap_sz_bits),
1048 static_cast<size_t>(num_keys_for_row.size() > 0 ? num_keys_for_row.back() : 0));
1051 auto data_mgr =
executor_->getDataMgr();
1052 std::vector<std::vector<uint8_t>> host_hll_buffers(
device_count_);
1053 for (
auto& host_hll_buffer : host_hll_buffers) {
1054 host_hll_buffer.resize(count_distinct_desc.bitmapPaddedSizeBytes());
1056 std::vector<size_t> emitted_keys_count_device_threads(
device_count_, 0);
1057 std::vector<std::future<void>> approximate_distinct_device_threads;
1058 for (
int device_id = 0; device_id <
device_count_; ++device_id) {
1059 approximate_distinct_device_threads.emplace_back(
std::async(
1062 &columns_per_device,
1063 &count_distinct_desc,
1066 &emitted_keys_count_device_threads] {
1067 auto allocator = std::make_unique<CudaAllocator>(
1069 auto device_hll_buffer =
1070 allocator->alloc(count_distinct_desc.bitmapPaddedSizeBytes());
1071 data_mgr->getCudaMgr()->zeroDeviceMem(
1073 count_distinct_desc.bitmapPaddedSizeBytes(),
1076 const auto& columns_for_device = columns_per_device[device_id];
1078 columns_for_device.join_columns, *allocator);
1080 CHECK_GT(columns_for_device.join_buckets.size(), 0u);
1081 const auto& inverse_bucket_sizes_for_dimension =
1082 columns_for_device.join_buckets[0].inverse_bucket_sizes_for_dimension;
1083 auto inverse_bucket_sizes_gpu = allocator->alloc(
1084 inverse_bucket_sizes_for_dimension.size() *
sizeof(double));
1085 allocator->copyToDevice(
1086 inverse_bucket_sizes_gpu,
1087 inverse_bucket_sizes_for_dimension.data(),
1088 inverse_bucket_sizes_for_dimension.size() *
sizeof(double));
1089 const size_t row_counts_buffer_sz =
1090 columns_per_device.front().join_columns[0].num_elems *
sizeof(int32_t);
1091 auto row_counts_buffer = allocator->alloc(row_counts_buffer_sz);
1092 data_mgr->getCudaMgr()->zeroDeviceMem(
1094 row_counts_buffer_sz,
1097 const auto key_handler =
1100 reinterpret_cast<double*
>(inverse_bucket_sizes_gpu));
1101 const auto key_handler_gpu =
1104 reinterpret_cast<uint8_t*>(device_hll_buffer),
1105 count_distinct_desc.bitmap_sz_bits,
1106 reinterpret_cast<int32_t*>(row_counts_buffer),
1108 columns_for_device.join_columns[0].num_elems);
1110 auto& host_emitted_keys_count = emitted_keys_count_device_threads[device_id];
1111 allocator->copyFromDevice(
1112 &host_emitted_keys_count,
1114 (columns_per_device.front().join_columns[0].num_elems - 1) *
1118 auto& host_hll_buffer = host_hll_buffers[device_id];
1119 allocator->copyFromDevice(&host_hll_buffer[0],
1121 count_distinct_desc.bitmapPaddedSizeBytes());
1124 for (
auto& child : approximate_distinct_device_threads) {
1128 auto& result_hll_buffer = host_hll_buffers.front();
1129 auto hll_result =
reinterpret_cast<int32_t*
>(&result_hll_buffer[0]);
1130 for (
int device_id = 1; device_id <
device_count_; ++device_id) {
1131 auto& host_hll_buffer = host_hll_buffers[device_id];
1133 reinterpret_cast<int32_t*>(&host_hll_buffer[0]),
1134 1 << count_distinct_desc.bitmap_sz_bits);
1136 const size_t emitted_keys_count =
1138 emitted_keys_count_device_threads.end(),
1140 return std::make_pair(
hll_size(hll_result, count_distinct_desc.bitmap_sz_bits),
1141 emitted_keys_count);
1149 const std::vector<double>& inverse_bucket_sizes,
1150 std::vector<ColumnsForDevice>& columns_per_device,
1151 const size_t device_count) {
1156 CHECK_EQ(columns_per_device.size(),
static_cast<size_t>(device_count));
1157 for (
size_t device_id = 0; device_id < device_count; ++device_id) {
1158 auto& columns_for_device = columns_per_device[device_id];
1193 }
catch (
const std::exception& e) {
1194 VLOG(1) <<
"Caught exception while building overlaps baseline hash table: "
1203 const size_t shard_count,
1204 const size_t entry_count,
1205 const size_t emitted_keys_count,
1206 const bool skip_hashtable_caching,
1207 const size_t chosen_max_hashtable_size,
1208 const double chosen_bucket_threshold) {
1209 std::vector<std::future<void>> init_threads;
1216 for (
int device_id = 0; device_id <
device_count_; ++device_id) {
1217 const auto fragments =
1224 columns_per_device[device_id],
1228 skip_hashtable_caching,
1232 for (
auto& init_thread : init_threads) {
1235 for (
auto& init_thread : init_threads) {
1243 const size_t entry_count,
1244 const size_t emitted_keys_count,
1245 const bool skip_hashtable_caching,
1246 const int device_id,
1255 VLOG(1) <<
"Building overlaps join hash table on CPU.";
1262 skip_hashtable_caching);
1267 auto gpu_hash_table = copyCpuHashTableToGpu(
1268 hash_table, layout, entry_count, emitted_keys_count, device_id);
1282 auto hash_table = initHashTableOnGpu(columns_for_device.
join_columns,
1298 const std::vector<JoinColumn>& join_columns,
1299 const std::vector<JoinColumnTypeInfo>& join_column_types,
1300 const std::vector<JoinBucketInfo>& join_bucket_info,
1302 const size_t entry_count,
1303 const size_t emitted_keys_count,
1304 const bool skip_hashtable_caching) {
1306 decltype(std::chrono::steady_clock::now()) ts1, ts2;
1307 ts1 = std::chrono::steady_clock::now();
1308 CHECK(!join_columns.empty());
1309 CHECK(!join_bucket_info.empty());
1311 if (
auto generic_hash_table =
1315 if (
auto hash_table =
1316 std::dynamic_pointer_cast<BaselineHashTable>(generic_hash_table)) {
1317 VLOG(1) <<
"Using cached CPU hash table for initialization.";
1326 if (layout == hash_table->getLayout()) {
1332 const auto key_component_count =
1333 join_bucket_info[0].inverse_bucket_sizes_for_dimension.size();
1335 const auto key_handler =
1338 join_bucket_info[0].inverse_bucket_sizes_for_dimension.data());
1341 dummy_str_proxy_translation_maps_ptrs_and_offsets;
1348 dummy_str_proxy_translation_maps_ptrs_and_offsets,
1356 ts2 = std::chrono::steady_clock::now();
1359 std::string(
"Unrecognized error when initializing CPU overlaps hash table (") +
1362 std::shared_ptr<BaselineHashTable> hash_table = builder.getHashTable();
1363 if (skip_hashtable_caching) {
1364 VLOG(1) <<
"Skip to cache overlaps join hashtable";
1366 auto hashtable_build_time =
1367 std::chrono::duration_cast<std::chrono::milliseconds>(ts2 - ts1).count();
1372 hashtable_build_time);
1379 std::shared_ptr<BaselineHashTable> OverlapsJoinHashTable::initHashTableOnGpu(
1380 const std::vector<JoinColumn>& join_columns,
1381 const std::vector<JoinColumnTypeInfo>& join_column_types,
1382 const std::vector<JoinBucketInfo>& join_bucket_info,
1384 const size_t entry_count,
1385 const size_t emitted_keys_count,
1386 const size_t device_id) {
1389 VLOG(1) <<
"Building overlaps join hash table on GPU.";
1392 auto data_mgr =
executor_->getDataMgr();
1397 CHECK(!join_bucket_info.empty());
1398 auto& inverse_bucket_sizes_for_dimension =
1399 join_bucket_info[0].inverse_bucket_sizes_for_dimension;
1401 inverse_bucket_sizes_for_dimension, allocator);
1402 const auto key_handler =
OverlapsKeyHandler(inverse_bucket_sizes_for_dimension.size(),
1404 inverse_bucket_sizes_gpu);
1419 std::string(
"Unrecognized error when initializing GPU overlaps hash table (") +
1425 std::shared_ptr<BaselineHashTable> OverlapsJoinHashTable::copyCpuHashTableToGpu(
1426 std::shared_ptr<BaselineHashTable>& cpu_hash_table,
1428 const size_t entry_count,
1429 const size_t emitted_keys_count,
1430 const size_t device_id) {
1433 auto data_mgr =
executor_->getDataMgr();
1445 std::shared_ptr<BaselineHashTable> gpu_hash_table = gpu_builder.
getHashTable();
1446 CHECK(gpu_hash_table);
1447 auto gpu_buffer_ptr = gpu_hash_table->getGpuBuffer();
1448 CHECK(gpu_buffer_ptr);
1452 auto device_allocator = std::make_unique<CudaAllocator>(
1454 device_allocator->copyToDevice(
1456 cpu_hash_table->getCpuBuffer(),
1458 return gpu_hash_table;
1463 #define LL_CONTEXT executor_->cgen_state_->context_
1464 #define LL_BUILDER executor_->cgen_state_->ir_builder_
1465 #define LL_INT(v) executor_->cgen_state_->llInt(v)
1466 #define LL_FP(v) executor_->cgen_state_->llFp(v)
1467 #define ROW_FUNC executor_->cgen_state_->row_func_
1472 CHECK(key_component_width == 4 || key_component_width == 8);
1474 llvm::Value* key_buff_lv{
nullptr};
1475 switch (key_component_width) {
1489 const auto outer_geo = inner_outer_pair.second;
1490 const auto outer_geo_ti = outer_geo->get_type_info();
1492 llvm::Value* arr_ptr =
nullptr;
1496 if (outer_geo_ti.is_geometry()) {
1501 if (
const auto outer_geo_col = dynamic_cast<const Analyzer::ColumnVar*>(outer_geo)) {
1502 const auto outer_geo_col_lvs = code_generator.
codegen(outer_geo_col,
true, co);
1503 CHECK_EQ(outer_geo_col_lvs.size(), size_t(1));
1504 auto column_key = outer_geo_col->getColumnKey();
1505 column_key.column_id = column_key.column_id + 1;
1509 const auto array_ptr =
executor_->cgen_state_->emitExternalCall(
1511 llvm::Type::getInt8PtrTy(
executor_->cgen_state_->context_),
1512 {outer_geo_col_lvs.front(), code_generator.
posArg(outer_geo_col)});
1513 CHECK(coords_cd->columnType.get_elem_type().get_type() ==
kTINYINT)
1514 <<
"Only TINYINT coordinates columns are supported in geo overlaps hash "
1517 coords_cd->columnType.get_elem_type());
1518 }
else if (
const auto outer_geo_function_operator =
1519 dynamic_cast<const Analyzer::GeoOperator*>(outer_geo)) {
1521 const auto outer_geo_function_operator_lvs =
1522 code_generator.
codegen(outer_geo_function_operator,
true, co);
1523 CHECK_EQ(outer_geo_function_operator_lvs.size(), size_t(2));
1524 arr_ptr = outer_geo_function_operator_lvs.front();
1525 }
else if (
const auto outer_geo_expr =
1526 dynamic_cast<const Analyzer::GeoExpr*>(outer_geo)) {
1529 }
else if (outer_geo_ti.is_fixlen_array()) {
1531 const auto outer_geo_cast_coord_array =
1535 outer_geo_cast_coord_array->get_operand());
1536 CHECK(outer_geo_coord_array);
1537 CHECK(outer_geo_coord_array->isLocalAlloc());
1538 CHECK_EQ(outer_geo_coord_array->getElementCount(), 2);
1542 CHECK_EQ(outer_geo_ti.get_size(), int(2 * elem_size));
1543 const auto outer_geo_constructed_lvs = code_generator.codegen(outer_geo,
true, co);
1545 const auto array_ptr = outer_geo_constructed_lvs.front();
1547 array_ptr->getType()->getScalarType()->getPointerElementType(),
1553 LOG(
FATAL) <<
"Overlaps key currently only supported for geospatial columns and "
1554 "constructed points.";
1557 for (
size_t i = 0; i < 2; i++) {
1558 const auto key_comp_dest_lv =
LL_BUILDER.CreateGEP(
1559 key_buff_lv->getType()->getScalarType()->getPointerElementType(),
1567 ?
executor_->cgen_state_->emitExternalCall(
1568 "get_bucket_key_for_range_compressed",
1570 {arr_ptr,
LL_INT(i),
LL_FP(inverse_bucket_sizes_for_dimension_[i])})
1571 :
executor_->cgen_state_->emitExternalCall(
1572 "get_bucket_key_for_range_double",
1574 {arr_ptr,
LL_INT(i),
LL_FP(inverse_bucket_sizes_for_dimension_[i])});
1577 LL_BUILDER.CreateStore(col_lv, key_comp_dest_lv);
1586 CHECK(key_component_width == 4 || key_component_width == 8);
1591 VLOG(1) <<
"Performing codgen for ManyToMany";
1593 const auto outer_col = inner_outer_pair.second;
1596 const auto col_lvs = code_generator.
codegen(outer_col,
true, co);
1597 CHECK_EQ(col_lvs.size(), size_t(1));
1600 CHECK(outer_col_var);
1601 const auto coords_cd =
1605 const auto array_ptr =
executor_->cgen_state_->emitExternalCall(
1607 llvm::Type::getInt8PtrTy(
executor_->cgen_state_->context_),
1608 {col_lvs.front(), code_generator.
posArg(outer_col)});
1614 array_ptr->setName(
"array_ptr");
1616 auto num_keys_lv =
executor_->cgen_state_->emitExternalCall(
1617 "get_num_buckets_for_bounds",
1621 LL_FP(inverse_bucket_sizes_for_dimension_[0]),
1622 LL_FP(inverse_bucket_sizes_for_dimension_[1])});
1623 num_keys_lv->setName(
"num_keys_lv");
1625 return {num_keys_lv, array_ptr};
1630 const size_t index) {
1633 VLOG(1) <<
"Building codegenMatchingSet for ManyToMany";
1635 CHECK(key_component_width == 4 || key_component_width == 8);
1638 const auto composite_dict_ptr_type =
1639 llvm::Type::getIntNPtrTy(
LL_CONTEXT, key_component_width * 8);
1640 const auto composite_key_dict =
1641 hash_ptr->getType()->isPointerTy()
1642 ?
LL_BUILDER.CreatePointerCast(hash_ptr, composite_dict_ptr_type)
1643 :
LL_BUILDER.CreateIntToPtr(hash_ptr, composite_dict_ptr_type);
1646 auto one_to_many_ptr = hash_ptr;
1648 if (one_to_many_ptr->getType()->isPointerTy()) {
1652 CHECK(one_to_many_ptr->getType()->isIntegerTy(64));
1662 const int max_array_size = 200;
1664 const auto out_arr_lv =
LL_BUILDER.CreateAlloca(arr_type);
1665 out_arr_lv->setName(
"out_arr");
1667 const auto casted_out_arr_lv =
1668 LL_BUILDER.CreatePointerCast(out_arr_lv, arr_type->getPointerTo());
1670 const auto element_ptr =
LL_BUILDER.CreateGEP(arr_type, casted_out_arr_lv,
LL_INT(0));
1672 auto rowid_ptr_i32 =
1675 const auto candidate_count_lv =
executor_->cgen_state_->emitExternalCall(
1676 "get_candidate_rows",
1681 many_to_many_args[1],
1685 many_to_many_args[0],
1686 LL_INT(key_component_count),
1689 LL_INT(composite_key_dict_size),
1693 const auto slot_lv =
LL_INT(int64_t(0));
1695 return {rowid_ptr_i32, candidate_count_lv, slot_lv};
1697 VLOG(1) <<
"Building codegenMatchingSet for Baseline";
1700 CHECK(key_component_width == 4 || key_component_width == 8);
1704 const auto composite_dict_ptr_type =
1705 llvm::Type::getIntNPtrTy(
LL_CONTEXT, key_component_width * 8);
1706 const auto composite_key_dict =
1707 hash_ptr->getType()->isPointerTy()
1708 ?
LL_BUILDER.CreatePointerCast(hash_ptr, composite_dict_ptr_type)
1709 :
LL_BUILDER.CreateIntToPtr(hash_ptr, composite_dict_ptr_type);
1711 const auto key =
executor_->cgen_state_->emitExternalCall(
1712 "get_composite_key_index_" +
std::to_string(key_component_width * 8),
1715 LL_INT(key_component_count),
1718 auto one_to_many_ptr = hash_ptr;
1719 if (one_to_many_ptr->getType()->isPointerTy()) {
1723 CHECK(one_to_many_ptr->getType()->isIntegerTy(64));
1729 std::vector<llvm::Value*>{
1742 const int device_id,
1748 auto buffer_size = hash_table->getHashTableBufferSize(device_type);
1750 std::unique_ptr<int8_t[]> buffer_copy;
1752 buffer_copy = std::make_unique<int8_t[]>(buffer_size);
1754 auto data_mgr =
executor_->getDataMgr();
1755 auto device_allocator = std::make_unique<CudaAllocator>(
1758 device_allocator->copyFromDevice(buffer_copy.get(), buffer, buffer_size);
1760 auto ptr1 = buffer_copy ? buffer_copy.get() :
reinterpret_cast<const int8_t*
>(buffer);
1762 auto ptr1 =
reinterpret_cast<const int8_t*
>(buffer);
1774 hash_table->getEntryCount(),
1785 const int device_id)
const {
1789 auto buffer_size = hash_table->getHashTableBufferSize(device_type);
1791 std::unique_ptr<int8_t[]> buffer_copy;
1793 buffer_copy = std::make_unique<int8_t[]>(buffer_size);
1795 auto data_mgr =
executor_->getDataMgr();
1796 auto allocator = std::make_unique<CudaAllocator>(
1799 allocator->copyFromDevice(buffer_copy.get(), buffer, buffer_size);
1801 auto ptr1 = buffer_copy ? buffer_copy.get() :
reinterpret_cast<const int8_t*
>(buffer);
1803 auto ptr1 =
reinterpret_cast<const int8_t*
>(buffer);
1811 hash_table->getEntryCount(),
1820 const std::vector<InnerOuter>& inner_outer_pairs)
const {
1823 this->
executor_->getDataMgr()->gpusPresent() &&
1845 VLOG(1) <<
"Checking CPU hash table cache.";
1849 auto cached_hashtable =
1850 hash_table_cache_->getItemFromCache(key, item_type, device_identifier, meta_info);
1851 if (cached_hashtable) {
1852 return cached_hashtable;
1857 std::optional<std::pair<size_t, size_t>>
1865 auto cached_hashtable =
1866 hash_table_cache_->getItemFromCache(key, item_type, device_identifier, metaInfo);
1867 if (cached_hashtable) {
1868 return std::make_pair(cached_hashtable->getEntryCount() / 2,
1869 cached_hashtable->getEmittedKeysCount());
1871 return std::nullopt;
1877 std::shared_ptr<HashTable> hashtable_ptr,
1879 size_t hashtable_building_time) {
1881 CHECK(hashtable_ptr && !hashtable_ptr->getGpuBuffer());
1891 hashtable_building_time,
static std::vector< int > collectFragmentIds(const std::vector< Fragmenter_Namespace::FragmentInfo > &fragments)
llvm::Value * codegenKey(const CompilationOptions &)
const JoinType join_type_
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)
shared::TableKey getInnerTableId() const noexceptoverride
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)
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)
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.
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)
const ColumnDescriptor * get_metadata_for_column(const ::shared::ColumnKey &column_key)
const InputTableInfo & get_inner_query_info(const shared::TableKey &inner_table_key, const std::vector< InputTableInfo > &query_infos)
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)
#define DEBUG_TIMER_NEW_THREAD(parent_thread_id)
double overlaps_keys_per_bin
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
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_
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
void reify(const HashType preferred_layout)
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)
const ColumnDescriptor * get_column_descriptor_maybe(const shared::ColumnKey &column_key)
double chosen_overlaps_threshold
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::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)
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_
static std::unordered_set< size_t > getAlternativeTableKeys(const std::vector< ChunkKey > &chunk_keys, const shared::TableKey &inner_table_key)
size_t g_overlaps_max_table_size_bytes
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)
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
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
virtual shared::TableKey getInnerTableId() const noexcept=0
std::unordered_map< shared::TableKey, const RelAlgNode * > TableIdToNodeMap
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_
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)
LocalIdsScopeGuard setNewThreadId() const
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
std::unordered_map< shared::TableKey, std::unordered_map< int, std::shared_ptr< const ColumnarResults >>> ColumnCacheMap
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)
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_
static std::pair< std::vector< InnerOuter >, std::vector< InnerOuterStringOpInfos > > normalizeColumnPairs(const Analyzer::BinOper *condition, const TemporaryTables *temporary_tables)
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
double overlaps_bucket_threshold
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_
ThreadLocalIds thread_local_ids()
const std::vector< JoinColumn > join_columns
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_