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;
179 const auto refined_input_col_idx =
200 std::vector<AGG_TYPE> child_vals =
213 size_t cur_node_depth) {
215 int64_t input_col_idx = cur_node_idx -
leaf_range_.first;
216 const auto modified_input_col_idx =
231 std::vector<SumAndCountPair<AGG_TYPE>> child_vals =
240 size_t cur_node_depth) {
241 std::vector<AGG_TYPE> child_vals(
fan_out_);
242 size_t next_node_depth = cur_node_depth + 1;
243 if (cur_node_depth == 0) {
244 for (
size_t i = 0; i <
fan_out_; ++i) {
245 child_vals[i] =
build(i + 1, next_node_depth);
248 int64_t cur_depth_start_offset = parent_idx *
fan_out_ + 1;
249 for (
size_t i = 0; i <
fan_out_; ++i) {
250 child_vals[i] =
build(cur_depth_start_offset + i, next_node_depth);
258 size_t cur_node_depth) {
259 std::vector<SumAndCountPair<AGG_TYPE>> child_vals(
fan_out_);
260 size_t next_node_depth = cur_node_depth + 1;
261 if (cur_node_depth == 0) {
262 for (
size_t i = 0; i <
fan_out_; ++i) {
266 int64_t cur_depth_start_offset = parent_idx *
fan_out_ + 1;
267 for (
size_t i = 0; i <
fan_out_; ++i) {
278 bool all_nulls =
true;
280 AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
282 vals.begin(), vals.end(), [&min_val, &all_nulls,
this](
const AGG_TYPE val) {
285 min_val = std::min(min_val, val);
293 AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
295 vals.begin(), vals.end(), [&max_val, &all_nulls,
this](
const AGG_TYPE val) {
298 max_val = std::max(max_val, val);
306 AGG_TYPE agg_val = 0;
308 vals.begin(), vals.end(), [&agg_val, &all_nulls,
this](
const AGG_TYPE val) {
323 bool all_nulls =
true;
324 auto end_idx = cur_col_idx + num_visits;
326 AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
327 for (
size_t i = cur_col_idx; i < end_idx; ++i) {
331 min_val = std::min(min_val, val);
339 AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
340 for (
size_t i = cur_col_idx; i < end_idx; ++i) {
344 max_val = std::max(max_val, val);
352 AGG_TYPE agg_val = 0;
353 for (
size_t i = cur_col_idx; i < end_idx; ++i) {
370 bool all_nulls =
true;
371 std::for_each(vals.begin(),
376 res.count += pair.count;
388 size_t num_visits)
const {
390 bool all_nulls =
true;
391 auto end_idx = cur_col_idx + num_visits;
392 for (
size_t i = cur_col_idx; i < end_idx; ++i) {
395 res.sum += cur_pair_val.
sum;
409 int64_t cur_node_idx,
410 size_t cur_node_depth,
411 int64_t search_range_start_idx,
412 int64_t search_range_end_idx)
const {
416 if (search_range_end_idx < query_range.first ||
417 query_range.second < search_range_start_idx) {
420 }
else if (query_range.first <= search_range_start_idx &&
421 search_range_end_idx <= query_range.second) {
429 size_t num_visits = query_range.second - search_range_start_idx + 1;
434 int64_t pivot_idx = search_range_start_idx +
435 ((search_range_end_idx - search_range_start_idx) /
fan_out_);
436 int64_t child_search_start_idx = search_range_start_idx;
437 int64_t child_search_end_idx = pivot_idx;
438 std::vector<size_t> child_indexes(
fan_out_);
440 std::vector<AGG_TYPE> child_vals(
fan_out_);
441 for (
size_t i = 0; i < child_indexes.size(); ++i) {
442 child_vals[i] =
search(query_range,
445 child_search_start_idx,
446 child_search_end_idx);
447 child_search_start_idx = child_search_end_idx + 1;
448 child_search_end_idx = child_search_start_idx + pivot_idx;
449 if (child_search_end_idx > search_range_end_idx) {
450 child_search_end_idx = search_range_end_idx;
460 int64_t cur_node_idx,
461 size_t cur_node_depth,
462 int64_t search_range_start_idx,
463 int64_t search_range_end_idx)
const {
464 if (search_range_end_idx < query_range.first ||
465 query_range.second < search_range_start_idx) {
467 }
else if (query_range.first <= search_range_start_idx &&
468 search_range_end_idx <= query_range.second) {
472 size_t num_visits = query_range.second - search_range_start_idx + 1;
477 std::vector<int64_t> child_indexes(
fan_out_);
480 int64_t pivot_idx = search_range_start_idx +
481 ((search_range_end_idx - search_range_start_idx) /
fan_out_);
482 int64_t child_search_start_idx = search_range_start_idx;
483 int64_t child_search_end_idx = pivot_idx;
484 for (
size_t i = 0; i < child_indexes.size(); ++i) {
488 child_search_start_idx,
489 child_search_end_idx);
490 child_search_start_idx = child_search_end_idx + 1;
491 child_search_end_idx = child_search_start_idx + pivot_idx;
492 if (child_search_end_idx > search_range_end_idx) {
493 child_search_end_idx = search_range_end_idx;
506 size_t parent_tree_depth)
const {
507 if (parent_tree_depth == 0) {
508 for (
size_t i = 0; i <
fan_out_; ++i) {
509 child_indexes[i] = i + 1;
512 int64_t cur_depth_start_offset = parent_idx *
fan_out_ + 1;
513 for (
size_t i = 0; i <
fan_out_; ++i) {
514 child_indexes[i] = cur_depth_start_offset + i;
517 return child_indexes;
524 return std::make_pair(0, std::make_pair(0, 0));
526 int64_t cur_level_start_offset = 1;
528 IndexPair index_pair = std::make_pair(0, 0);
530 if (num_elem < cur_level_start_offset) {
531 return std::make_pair(depth, index_pair);
534 size_t maximum_node_at_next_level = pow(fan_out, depth);
535 index_pair = std::make_pair(cur_level_start_offset,
536 cur_level_start_offset + maximum_node_at_next_level);
537 cur_level_start_offset = index_pair.second;
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_