37 template <
typename INPUT_TYPE,
typename AGG_TYPE>
42 const int32_t* original_input_col_idx_buf,
43 const int64_t* ordered_input_col_idx_buf,
48 :
input_col_buf_(reinterpret_cast<const INPUT_TYPE*>(input_col_buf))
59 leaf_range_ = max_tree_height_and_leaf_range.second;
63 null_range_.first = std::numeric_limits<int64_t>::max();
64 null_range_.second = std::numeric_limits<int64_t>::min();
77 null_val_ = inline_null_value<AGG_TYPE>();
113 if (query_range.first > query_range.second || query_range.first < 0 ||
123 }
else if (sum_and_count_pair.
count == 0) {
127 return (static_cast<double>(sum_and_count_pair.
sum) /
129 sum_and_count_pair.
count;
131 return sum_and_count_pair.
sum / sum_and_count_pair.
count;
169 AGG_TYPE
build(int64_t cur_node_idx,
size_t cur_node_depth) {
172 int64_t input_col_idx = cur_node_idx -
leaf_range_.first;
180 const auto refined_input_col_idx =
201 std::vector<AGG_TYPE> child_vals =
214 size_t cur_node_depth) {
216 int64_t input_col_idx = cur_node_idx -
leaf_range_.first;
221 const auto refined_input_col_idx =
233 std::vector<SumAndCountPair<AGG_TYPE>> child_vals =
242 size_t cur_node_depth) {
243 std::vector<AGG_TYPE> child_vals(
fan_out_);
244 size_t next_node_depth = cur_node_depth + 1;
245 if (cur_node_depth == 0) {
246 for (
size_t i = 0; i <
fan_out_; ++i) {
247 child_vals[i] =
build(i + 1, next_node_depth);
250 int64_t cur_depth_start_offset = parent_idx *
fan_out_ + 1;
251 for (
size_t i = 0; i <
fan_out_; ++i) {
252 child_vals[i] =
build(cur_depth_start_offset + i, next_node_depth);
260 size_t cur_node_depth) {
261 std::vector<SumAndCountPair<AGG_TYPE>> child_vals(
fan_out_);
262 size_t next_node_depth = cur_node_depth + 1;
263 if (cur_node_depth == 0) {
264 for (
size_t i = 0; i <
fan_out_; ++i) {
268 int64_t cur_depth_start_offset = parent_idx *
fan_out_ + 1;
269 for (
size_t i = 0; i <
fan_out_; ++i) {
280 bool all_nulls =
true;
282 AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
284 vals.begin(), vals.end(), [&min_val, &all_nulls,
this](
const AGG_TYPE val) {
287 min_val = std::min(min_val, val);
295 AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
297 vals.begin(), vals.end(), [&max_val, &all_nulls,
this](
const AGG_TYPE val) {
300 max_val = std::max(max_val, val);
308 AGG_TYPE agg_val = 0;
310 vals.begin(), vals.end(), [&agg_val, &all_nulls,
this](
const AGG_TYPE val) {
325 bool all_nulls =
true;
326 auto end_idx = cur_col_idx + num_visits;
328 AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
329 for (
size_t i = cur_col_idx; i < end_idx; ++i) {
333 min_val = std::min(min_val, val);
341 AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
342 for (
size_t i = cur_col_idx; i < end_idx; ++i) {
346 max_val = std::max(max_val, val);
354 AGG_TYPE agg_val = 0;
355 for (
size_t i = cur_col_idx; i < end_idx; ++i) {
372 bool all_nulls =
true;
373 std::for_each(vals.begin(),
378 res.count += pair.count;
390 size_t num_visits)
const {
392 bool all_nulls =
true;
393 auto end_idx = cur_col_idx + num_visits;
394 for (
size_t i = cur_col_idx; i < end_idx; ++i) {
397 res.sum += cur_pair_val.
sum;
411 int64_t cur_node_idx,
412 size_t cur_node_depth,
413 int64_t search_range_start_idx,
414 int64_t search_range_end_idx)
const {
418 if (search_range_end_idx < query_range.first ||
419 query_range.second < search_range_start_idx) {
422 }
else if (query_range.first <= search_range_start_idx &&
423 search_range_end_idx <= query_range.second) {
431 size_t num_visits = query_range.second - search_range_start_idx + 1;
436 int64_t pivot_idx = search_range_start_idx +
437 ((search_range_end_idx - search_range_start_idx) /
fan_out_);
438 int64_t child_search_start_idx = search_range_start_idx;
439 int64_t child_search_end_idx = pivot_idx;
440 std::vector<size_t> child_indexes(
fan_out_);
442 std::vector<AGG_TYPE> child_vals(
fan_out_);
443 for (
size_t i = 0; i < child_indexes.size(); ++i) {
444 child_vals[i] =
search(query_range,
447 child_search_start_idx,
448 child_search_end_idx);
449 child_search_start_idx = child_search_end_idx + 1;
450 child_search_end_idx = child_search_start_idx + pivot_idx;
451 if (child_search_end_idx > search_range_end_idx) {
452 child_search_end_idx = search_range_end_idx;
462 int64_t cur_node_idx,
463 size_t cur_node_depth,
464 int64_t search_range_start_idx,
465 int64_t search_range_end_idx)
const {
466 if (search_range_end_idx < query_range.first ||
467 query_range.second < search_range_start_idx) {
469 }
else if (query_range.first <= search_range_start_idx &&
470 search_range_end_idx <= query_range.second) {
474 size_t num_visits = query_range.second - search_range_start_idx + 1;
479 std::vector<int64_t> child_indexes(
fan_out_);
482 int64_t pivot_idx = search_range_start_idx +
483 ((search_range_end_idx - search_range_start_idx) /
fan_out_);
484 int64_t child_search_start_idx = search_range_start_idx;
485 int64_t child_search_end_idx = pivot_idx;
486 for (
size_t i = 0; i < child_indexes.size(); ++i) {
490 child_search_start_idx,
491 child_search_end_idx);
492 child_search_start_idx = child_search_end_idx + 1;
493 child_search_end_idx = child_search_start_idx + pivot_idx;
494 if (child_search_end_idx > search_range_end_idx) {
495 child_search_end_idx = search_range_end_idx;
508 size_t parent_tree_depth)
const {
509 if (parent_tree_depth == 0) {
510 for (
size_t i = 0; i <
fan_out_; ++i) {
511 child_indexes[i] = i + 1;
514 int64_t cur_depth_start_offset = parent_idx *
fan_out_ + 1;
515 for (
size_t i = 0; i <
fan_out_; ++i) {
516 child_indexes[i] = cur_depth_start_offset + i;
519 return child_indexes;
526 return std::make_pair(0, std::make_pair(0, 0));
528 int64_t cur_level_start_offset = 0;
530 IndexPair index_pair = std::make_pair(0, 0);
532 size_t maximum_node_at_next_level = pow(fan_out, depth);
533 if (num_elem < maximum_node_at_next_level) {
534 index_pair = std::make_pair(cur_level_start_offset,
535 cur_level_start_offset + maximum_node_at_next_level);
536 return std::make_pair(depth, index_pair);
539 cur_level_start_offset += maximum_node_at_next_level;
AGG_TYPE aggregateValueViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const
SumAndCountPair< AGG_TYPE > * derived_aggregated_
const int32_t * original_input_col_idx_buf_
IndexPair getLeafRange() const
size_t getLeafDepth() const
SqlWindowFunctionKind agg_type_
HOST DEVICE int get_scale() const
const int64_t * ordered_input_col_idx_buf_
size_t getTreeSize() const
size_t getLeafSize() const
AGG_TYPE search(const IndexPair &query_range, int64_t cur_node_idx, size_t cur_node_depth, int64_t search_range_start_idx, int64_t search_range_end_idx) const
Constants for Builtin SQL Types supported by HEAVY.AI.
SumAndCountPair< AGG_TYPE > buildForDerivedAggregate(int64_t cur_node_idx, size_t cur_node_depth)
size_t getTreeFanout() const
const SQLTypeInfo input_col_ti_
std::vector< int64_t > computeChildIndexes(std::vector< int64_t > &child_indexes, int64_t parent_idx, size_t parent_tree_depth) const
SumAndCountPair< AGG_TYPE > searchForDerivedAggregate(const IndexPair &query_range, int64_t cur_node_idx, size_t cur_node_depth, int64_t search_range_start_idx, int64_t search_range_end_idx) const
size_t getNumElems() const
void * checked_malloc(const size_t size)
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregateViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregate(const std::vector< SumAndCountPair< AGG_TYPE >> &vals) const
const INPUT_TYPE * input_col_buf_
AGG_TYPE query(const IndexPair &query_range) const
std::pair< int64_t, int64_t > IndexPair
AGG_TYPE * getAggregatedValues() const
std::vector< SumAndCountPair< AGG_TYPE > > prepareChildValuesforDerivedAggregate(int64_t parent_idx, size_t cur_node_depth)
SegmentTree(const int8_t *input_col_buf, const SQLTypeInfo &input_col_ti, const int32_t *original_input_col_idx_buf, const int64_t *ordered_input_col_idx_buf, IndexPair order_col_null_range, int64_t num_elems, SqlWindowFunctionKind agg_type, size_t fan_out)
std::vector< AGG_TYPE > prepareChildValuesforAggregation(int64_t parent_idx, size_t cur_node_depth)
INPUT_TYPE input_type_null_val_
AGG_TYPE build(int64_t cur_node_idx, size_t cur_node_depth)
Common Enum definitions for SQL processing.
std::pair< size_t, IndexPair > findMaxTreeHeight(int64_t num_elem, int fan_out)
SumAndCountPair< AGG_TYPE > * getDerivedAggregatedValues() const
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
AGG_TYPE * aggregated_values_