OmniSciDB  a987f07e93
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
SegmentTree.h
Go to the documentation of this file.
1 /*
2  * Copyright 2022 HEAVY.AI, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <algorithm>
20 #include <cmath>
21 #include <numeric>
22 #include <vector>
23 
24 #ifndef __CUDACC__
25 #include <sstream>
26 #endif
27 
28 #include "SegmentTreeUtils.h"
29 #include "Shared/checked_alloc.h"
30 #include "Shared/sqldefs.h"
31 #include "Shared/sqltypes.h"
32 
33 // A generic segment tree class that builds a segment tree of a given input_col_buf
34 // with a fan_out
35 // depending on what aggregation operator we use, it constructs internal node differently
36 // i.e., for sum aggregation, a parent node becomes a sum of "all" child elements
37 template <typename INPUT_TYPE, typename AGG_TYPE>
38 class SegmentTree {
39  public:
40  SegmentTree(std::vector<const int8_t*> const& input_col_bufs,
41  SQLTypeInfo const& input_col_ti,
42  int32_t const* original_input_col_idx_buf,
43  int64_t const* ordered_input_col_idx_buf,
44  int64_t num_elems,
45  SqlWindowFunctionKind agg_type,
46  size_t fan_out)
47  : input_col_buf_(!input_col_bufs.empty()
48  ? reinterpret_cast<const INPUT_TYPE*>(input_col_bufs.front())
49  : nullptr)
50  , cond_col_buf_(input_col_bufs.size() == 2 ? input_col_bufs[1] : nullptr)
51  , input_col_ti_(input_col_ti)
52  , original_input_col_idx_buf_(original_input_col_idx_buf)
53  , ordered_input_col_idx_buf_(ordered_input_col_idx_buf)
54  , num_elems_(num_elems)
55  , fan_out_(fan_out)
56  , agg_type_(agg_type)
59  , null_val_(inline_null_value<AGG_TYPE>())
61  ? std::numeric_limits<INPUT_TYPE>::max()
63  ? std::numeric_limits<INPUT_TYPE>::min()
64  : 0) {
65  CHECK_GT(num_elems_, (int64_t)0);
66  auto max_tree_height_and_leaf_range = findMaxTreeHeight(num_elems_, fan_out_);
67  leaf_depth_ = max_tree_height_and_leaf_range.first;
68  leaf_range_ = max_tree_height_and_leaf_range.second;
69  // the index of the last elem of the leaf level is the same as the tree's size
70  tree_size_ = leaf_range_.second;
71  leaf_size_ = leaf_range_.second - leaf_range_.first;
72  // for derived aggregate, we maintain both "sum" aggregates and element counts
73  // to compute the value correctly
78  } else {
79  // we can use an array as a segment tree for the rest of aggregates
81  reinterpret_cast<AGG_TYPE*>(checked_malloc(tree_size_ * sizeof(AGG_TYPE)));
83  ? buildForCount(0, 0)
84  : is_conditional_agg_ ? buildForCondAgg(0, 0) : build(0, 0);
85  }
86  }
87 
89  if (num_elems_ > 0) {
91  free(derived_aggregated_);
92  } else {
93  free(aggregated_values_);
94  }
95  }
96  }
97 
98  // try to aggregate values of the given query range
99  AGG_TYPE query(const IndexPair& query_range) const {
100  if (query_range.first > query_range.second || query_range.first < 0 ||
101  query_range.second > leaf_size_) {
102  return null_val_;
103  }
104  // todo (yoonmin) : support more derived aggregate functions
106  SumAndCountPair<AGG_TYPE> sum_and_count_pair =
107  searchForDerivedAggregate(query_range, 0, 0, 0, leaf_size_);
108  if (sum_and_count_pair.sum == null_val_) {
109  return null_val_;
110  } else if (sum_and_count_pair.count == 0) {
111  return 0;
112  } else {
113  if (input_col_ti_.is_decimal()) {
114  return (static_cast<double>(sum_and_count_pair.sum) /
115  pow(10, input_col_ti_.get_scale())) /
116  sum_and_count_pair.count;
117  } else {
118  return sum_and_count_pair.sum / sum_and_count_pair.count;
119  }
120  }
121  } else {
122  const auto res = search(query_range, 0, 0, 0, leaf_size_);
123  if (res == null_val_) {
124  switch (agg_type_) {
127  return input_type_null_val_;
128  default:
129  return null_val_;
130  }
131  }
132  return res;
133  }
134  }
135 
136  AGG_TYPE* getAggregatedValues() const { return aggregated_values_; }
137 
139  return derived_aggregated_;
140  }
141 
142  size_t getLeafSize() const { return leaf_size_; }
143 
144  size_t getTreeSize() const { return tree_size_; }
145 
146  size_t getNumElems() const { return num_elems_; }
147 
148  size_t getLeafDepth() const { return leaf_depth_; }
149 
150  size_t getTreeFanout() const { return fan_out_; }
151 
152  IndexPair getLeafRange() const { return leaf_range_; }
153 
154  private:
155  // build a segment tree for a given aggregate function recursively
156  inline AGG_TYPE fetch_col_for_count(size_t const idx) {
158  }
159 
160  inline AGG_TYPE fetch_col_for_non_cond_agg(size_t const idx) {
161  auto const col_val = input_col_buf_[idx];
162  return col_val != input_type_null_val_ ? col_val : null_val_;
163  }
164 
165  inline AGG_TYPE fetch_col_for_cond_agg(size_t const idx) {
166  AGG_TYPE res{null_val_};
167  if (cond_col_buf_[idx] == 1) {
168  auto const col_val = input_col_buf_[idx];
169  res = col_val != input_type_null_val_ ? col_val : null_val_;
170  }
171  return res;
172  }
173 
174  AGG_TYPE build(int64_t cur_node_idx, size_t cur_node_depth) {
175  if (cur_node_idx >= leaf_range_.first && cur_node_idx < leaf_range_.second) {
176  // arrive at leaf level, so try to put a corresponding input column value
177  int64_t input_col_idx = cur_node_idx - leaf_range_.first;
178  if (input_col_idx >= num_elems_) {
179  // fill an invalid value
180  aggregated_values_[cur_node_idx] = invalid_val_;
181  return invalid_val_;
182  }
183  // try to get the current row's column value
184  const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
185  const auto refined_input_col_idx =
186  original_input_col_idx_buf_[input_col_idx_ordered];
187  aggregated_values_[cur_node_idx] =
188  fetch_col_for_non_cond_agg(refined_input_col_idx);
189  // return the current value to fill a parent node
190  return aggregated_values_[cur_node_idx];
191  }
192 
193  // when reaching here, we need to take care of a node having child nodes,
194  // and we compute an aggregated value from its child nodes
195  std::vector<AGG_TYPE> child_vals =
196  prepareChildValuesforAggregation(cur_node_idx, cur_node_depth);
197 
198  // compute the new aggregated value
199  aggregated_values_[cur_node_idx] = aggregateValue(child_vals);
200 
201  // return the value for the upper-level aggregation
202  return aggregated_values_[cur_node_idx];
203  }
204 
205  AGG_TYPE buildForCondAgg(int64_t cur_node_idx, size_t cur_node_depth) {
206  if (cur_node_idx >= leaf_range_.first && cur_node_idx < leaf_range_.second) {
207  // arrive at leaf level, so try to put a corresponding input column value
208  int64_t input_col_idx = cur_node_idx - leaf_range_.first;
209  if (input_col_idx >= num_elems_) {
210  // fill an invalid value
211  aggregated_values_[cur_node_idx] = invalid_val_;
212  return invalid_val_;
213  }
214  // try to get the current row's column value
215  const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
216  const auto refined_input_col_idx =
217  original_input_col_idx_buf_[input_col_idx_ordered];
218  aggregated_values_[cur_node_idx] = fetch_col_for_cond_agg(refined_input_col_idx);
219  // return the current value to fill a parent node
220  return aggregated_values_[cur_node_idx];
221  }
222 
223  // when reaching here, we need to take care of a node having child nodes,
224  // and we compute an aggregated value from its child nodes
225  std::vector<AGG_TYPE> child_vals =
226  prepareChildValuesforConditionalAggregation(cur_node_idx, cur_node_depth);
227 
228  // compute the new aggregated value
229  aggregated_values_[cur_node_idx] = aggregateValue(child_vals);
230 
231  // return the value for the upper-level aggregation
232  return aggregated_values_[cur_node_idx];
233  }
234 
235  AGG_TYPE buildForCount(int64_t cur_node_idx, size_t cur_node_depth) {
236  if (cur_node_idx >= leaf_range_.first && cur_node_idx <= leaf_range_.second) {
237  // arrive at leafs, so try to put a corresponding input column value
238  int64_t input_col_idx = cur_node_idx - leaf_range_.first;
239  if (input_col_idx >= num_elems_) {
240  // fill an invalid value
241  aggregated_values_[cur_node_idx] = invalid_val_;
242  return invalid_val_;
243  }
244  // try to get the current row's column value
245  const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
246  const auto refined_input_col_idx =
247  original_input_col_idx_buf_[input_col_idx_ordered];
248  aggregated_values_[cur_node_idx] = fetch_col_for_count(refined_input_col_idx);
249  // return the current value to fill a parent node
250  return aggregated_values_[cur_node_idx];
251  }
252 
253  // when reaching here, we need to take care of a node having child nodes,
254  // and we compute an aggregated value from its child nodes
255  std::vector<AGG_TYPE> child_vals =
256  prepareChildValuesforAggregationForCount(cur_node_idx, cur_node_depth);
257 
258  // compute the new aggregated value
259  aggregated_values_[cur_node_idx] = aggregateValue(child_vals);
260 
261  // return the value for the upper-level aggregation
262  return aggregated_values_[cur_node_idx];
263  }
264 
265  // the logic is exactly the same as normal aggregate case, but has a different
266  // node type: SumAndCountPair
268  size_t cur_node_depth) {
269  if (cur_node_idx >= leaf_range_.first && cur_node_idx <= leaf_range_.second) {
270  int64_t input_col_idx = cur_node_idx - leaf_range_.first;
271  if (input_col_idx >= num_elems_) {
272  derived_aggregated_[cur_node_idx] = {invalid_val_, 0};
273  } else {
274  const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
275  const auto refined_input_col_idx =
276  original_input_col_idx_buf_[input_col_idx_ordered];
277  auto col_val = input_col_buf_[refined_input_col_idx];
278  if (col_val != input_type_null_val_) {
279  derived_aggregated_[cur_node_idx] = {col_val, 1};
280  } else {
281  derived_aggregated_[cur_node_idx] = {null_val_, 0};
282  }
283  }
284  return derived_aggregated_[cur_node_idx];
285  }
286 
287  std::vector<SumAndCountPair<AGG_TYPE>> child_vals =
288  prepareChildValuesforDerivedAggregate(cur_node_idx, cur_node_depth);
289 
290  derived_aggregated_[cur_node_idx] = aggregateValueForDerivedAggregate(child_vals);
291  return derived_aggregated_[cur_node_idx];
292  }
293 
294  // gather aggregated values of each child node
295  std::vector<AGG_TYPE> prepareChildValuesforAggregation(int64_t parent_idx,
296  size_t cur_node_depth) {
297  std::vector<AGG_TYPE> child_vals(fan_out_);
298  size_t next_node_depth = cur_node_depth + 1;
299  if (cur_node_depth == 0) {
300  for (size_t i = 0; i < fan_out_; ++i) {
301  child_vals[i] = build(i + 1, next_node_depth);
302  }
303  } else {
304  int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
305  for (size_t i = 0; i < fan_out_; ++i) {
306  child_vals[i] = build(cur_depth_start_offset + i, next_node_depth);
307  }
308  }
309  return child_vals;
310  }
311 
312  // gather aggregated values of each child node
314  int64_t parent_idx,
315  size_t cur_node_depth) {
316  std::vector<AGG_TYPE> child_vals(fan_out_);
317  size_t next_node_depth = cur_node_depth + 1;
318  if (cur_node_depth == 0) {
319  for (size_t i = 0; i < fan_out_; ++i) {
320  child_vals[i] = buildForCondAgg(i + 1, next_node_depth);
321  }
322  } else {
323  int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
324  for (size_t i = 0; i < fan_out_; ++i) {
325  child_vals[i] = buildForCondAgg(cur_depth_start_offset + i, next_node_depth);
326  }
327  }
328  return child_vals;
329  }
330 
331  // gather aggregated values of each child node
332  std::vector<AGG_TYPE> prepareChildValuesforAggregationForCount(int64_t parent_idx,
333  size_t cur_node_depth) {
334  std::vector<AGG_TYPE> child_vals(fan_out_);
335  size_t next_node_depth = cur_node_depth + 1;
336  if (cur_node_depth == 0) {
337  for (size_t i = 0; i < fan_out_; ++i) {
338  child_vals[i] = buildForCount(i + 1, next_node_depth);
339  }
340  } else {
341  int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
342  for (size_t i = 0; i < fan_out_; ++i) {
343  child_vals[i] = buildForCount(cur_depth_start_offset + i, next_node_depth);
344  }
345  }
346  return child_vals;
347  }
348 
349  std::vector<SumAndCountPair<AGG_TYPE>> prepareChildValuesforDerivedAggregate(
350  int64_t parent_idx,
351  size_t cur_node_depth) {
352  std::vector<SumAndCountPair<AGG_TYPE>> child_vals(fan_out_);
353  size_t next_node_depth = cur_node_depth + 1;
354  if (cur_node_depth == 0) {
355  for (size_t i = 0; i < fan_out_; ++i) {
356  child_vals[i] = buildForDerivedAggregate(i + 1, next_node_depth);
357  }
358  } else {
359  int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
360  for (size_t i = 0; i < fan_out_; ++i) {
361  child_vals[i] =
362  buildForDerivedAggregate(cur_depth_start_offset + i, next_node_depth);
363  }
364  }
365  return child_vals;
366  }
367 
368  // compute aggregated value of the given values depending on the aggregate function
369  AGG_TYPE aggregateValue(const std::vector<AGG_TYPE>& vals) const {
370  // todo (yoonmin) : optimize logic for a non-null column
371  bool all_nulls = true;
373  AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
374  std::for_each(
375  vals.begin(), vals.end(), [&min_val, &all_nulls, this](const AGG_TYPE val) {
376  if (val != null_val_ && val != invalid_val_) {
377  all_nulls = false;
378  min_val = std::min(min_val, val);
379  }
380  });
381  if (all_nulls) {
382  min_val = null_val_;
383  }
384  return min_val;
385  } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
386  AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
387  std::for_each(
388  vals.begin(), vals.end(), [&max_val, &all_nulls, this](const AGG_TYPE val) {
389  if (val != null_val_ && val != invalid_val_) {
390  all_nulls = false;
391  max_val = std::max(max_val, val);
392  }
393  });
394  if (all_nulls) {
395  max_val = null_val_;
396  }
397  return max_val;
398  } else {
399  AGG_TYPE agg_val = 0;
400  std::for_each(
401  vals.begin(), vals.end(), [&agg_val, &all_nulls, this](const AGG_TYPE val) {
402  if (val != null_val_ && val != invalid_val_) {
403  agg_val += val;
404  all_nulls = false;
405  }
406  });
407  if (all_nulls) {
408  agg_val = null_val_;
409  }
410  return agg_val;
411  }
412  }
413 
414  AGG_TYPE aggregateValueViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const {
415  // todo (yoonmin) : optimize logic for a non-null column
416  bool all_nulls = true;
417  auto end_idx = cur_col_idx + num_visits;
419  AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
420  for (size_t i = cur_col_idx; i < end_idx; ++i) {
421  AGG_TYPE val = aggregated_values_[i];
422  if (val != null_val_ && val != invalid_val_) {
423  all_nulls = false;
424  min_val = std::min(min_val, val);
425  }
426  }
427  if (all_nulls) {
428  min_val = null_val_;
429  }
430  return min_val;
431  } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
432  AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
433  for (size_t i = cur_col_idx; i < end_idx; ++i) {
434  AGG_TYPE val = aggregated_values_[i];
435  if (val != null_val_ && val != invalid_val_) {
436  all_nulls = false;
437  max_val = std::max(max_val, val);
438  }
439  }
440  if (all_nulls) {
441  max_val = null_val_;
442  }
443  return max_val;
444  } else {
445  AGG_TYPE agg_val = 0;
446  for (size_t i = cur_col_idx; i < end_idx; ++i) {
447  AGG_TYPE val = aggregated_values_[i];
448  if (val != null_val_ && val != invalid_val_) {
449  agg_val += val;
450  all_nulls = false;
451  }
452  }
453  if (all_nulls) {
454  agg_val = null_val_;
455  }
456  return agg_val;
457  }
458  }
459 
461  const std::vector<SumAndCountPair<AGG_TYPE>>& vals) const {
463  bool all_nulls = true;
464  std::for_each(vals.begin(),
465  vals.end(),
466  [&res, &all_nulls, this](const SumAndCountPair<AGG_TYPE>& pair) {
467  if (pair.sum != null_val_ && pair.sum != invalid_val_) {
468  res.sum += pair.sum;
469  res.count += pair.count;
470  all_nulls = false;
471  }
472  });
473  if (all_nulls) {
474  return {null_val_, 0};
475  }
476  return res;
477  }
478 
480  int64_t cur_col_idx,
481  size_t num_visits) const {
483  bool all_nulls = true;
484  auto end_idx = cur_col_idx + num_visits;
485  for (size_t i = cur_col_idx; i < end_idx; ++i) {
486  const SumAndCountPair<AGG_TYPE> cur_pair_val = aggregated_values_[i];
487  if (cur_pair_val.sum != null_val_ && cur_pair_val.sum != invalid_val_) {
488  res.sum += cur_pair_val.sum;
489  res.count += cur_pair_val.count;
490  all_nulls = false;
491  }
492  }
493  if (all_nulls) {
494  return {null_val_, 0};
495  }
496  return res;
497  }
498 
499  // search an aggregated value of the given query range
500  // by visiting necessary nodes of the segment tree including leafs
501  AGG_TYPE search(const IndexPair& query_range,
502  int64_t cur_node_idx,
503  size_t cur_node_depth,
504  int64_t search_range_start_idx,
505  int64_t search_range_end_idx) const {
506  if (num_elems_ <= 0) {
507  return null_val_;
508  }
509  if (search_range_end_idx < query_range.first ||
510  query_range.second < search_range_start_idx) {
511  // completely out-of-bound
512  return invalid_val_;
513  } else if (query_range.first <= search_range_start_idx &&
514  search_range_end_idx <= query_range.second) {
515  // perfectly fitted in a range of the current node
516  return aggregated_values_[cur_node_idx];
517  } else {
518  // this node is partially within left and right indexes
519  if (cur_node_depth == leaf_depth_) {
520  // we already reach the leaf level, so do not need to proceed to the next level
521  // and so aggregate the value in the range by using a simple loop
522  size_t num_visits = query_range.second - search_range_start_idx + 1;
524  cur_node_idx, num_visits, null_val_, invalid_val_);
525  } else {
526  // find aggregated value from child nodes
527  int64_t pivot_idx = search_range_start_idx +
528  ((search_range_end_idx - search_range_start_idx) / fan_out_);
529  int64_t child_search_start_idx = search_range_start_idx;
530  int64_t child_search_end_idx = pivot_idx;
531  std::vector<size_t> child_indexes(fan_out_);
532  computeChildIndexes(child_indexes, cur_node_idx, cur_node_depth);
533  std::vector<AGG_TYPE> child_vals(fan_out_);
534  for (size_t i = 0; i < child_indexes.size(); ++i) {
535  child_vals[i] = search(query_range,
536  child_indexes[i],
537  cur_node_depth + 1,
538  child_search_start_idx,
539  child_search_end_idx);
540  child_search_start_idx = child_search_end_idx + 1;
541  child_search_end_idx = child_search_start_idx + pivot_idx;
542  if (child_search_end_idx > search_range_end_idx) {
543  child_search_end_idx = search_range_end_idx;
544  }
545  }
546  return aggregateValue(child_vals);
547  }
548  }
549  }
550 
552  const IndexPair& query_range,
553  int64_t cur_node_idx,
554  size_t cur_node_depth,
555  int64_t search_range_start_idx,
556  int64_t search_range_end_idx) const {
557  if (search_range_end_idx < query_range.first ||
558  query_range.second < search_range_start_idx) {
559  return {invalid_val_, 0};
560  } else if (query_range.first <= search_range_start_idx &&
561  search_range_end_idx <= query_range.second) {
562  return derived_aggregated_[cur_node_idx];
563  } else {
564  if (cur_node_depth == leaf_depth_) {
565  size_t num_visits = query_range.second - search_range_start_idx + 1;
567  cur_node_idx, num_visits, null_val_, invalid_val_);
568  } else {
569  // find aggregated value from child nodes
570  std::vector<int64_t> child_indexes(fan_out_);
571  computeChildIndexes(child_indexes, cur_node_idx, cur_node_depth);
572  std::vector<SumAndCountPair<AGG_TYPE>> child_vals(fan_out_, {invalid_val_, 0});
573  int64_t pivot_idx = search_range_start_idx +
574  ((search_range_end_idx - search_range_start_idx) / fan_out_);
575  int64_t child_search_start_idx = search_range_start_idx;
576  int64_t child_search_end_idx = pivot_idx;
577  for (size_t i = 0; i < child_indexes.size(); ++i) {
578  child_vals[i] = searchForDerivedAggregate(query_range,
579  child_indexes[i],
580  cur_node_depth + 1,
581  child_search_start_idx,
582  child_search_end_idx);
583  child_search_start_idx = child_search_end_idx + 1;
584  child_search_end_idx = child_search_start_idx + pivot_idx;
585  if (child_search_end_idx > search_range_end_idx) {
586  child_search_end_idx = search_range_end_idx;
587  }
588  }
589  return aggregateValueForDerivedAggregate(child_vals);
590  }
591  }
592  }
593 
594  // for prepareChildValuesForAggregate function includes the logic of the
595  // `computeChildIndexes` function internally to reduce # creation of the temporary
596  // vector while building a segment tree, but keep it to use it for `search` function
597  std::vector<int64_t> computeChildIndexes(std::vector<int64_t>& child_indexes,
598  int64_t parent_idx,
599  size_t parent_tree_depth) const {
600  if (parent_tree_depth == 0) {
601  for (size_t i = 0; i < fan_out_; ++i) {
602  child_indexes[i] = i + 1;
603  }
604  } else {
605  int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
606  for (size_t i = 0; i < fan_out_; ++i) {
607  child_indexes[i] = cur_depth_start_offset + i;
608  }
609  }
610  return child_indexes;
611  }
612 
613  // a utility function that computes a length and the start node index of a segment tree
614  // to contain 'num_elem' with a given 'fan_out'
615  std::pair<size_t, IndexPair> findMaxTreeHeight(int64_t num_elem, int fan_out) {
616  if (num_elem <= 0) {
617  return std::make_pair(0, std::make_pair(0, 0));
618  }
619  int64_t cur_level_start_offset = 0;
620  size_t depth = 0;
621  IndexPair index_pair = std::make_pair(0, 0);
622  while (true) {
623  size_t maximum_node_at_next_level = pow(fan_out, depth);
624  if (num_elem < maximum_node_at_next_level) {
625  index_pair = std::make_pair(cur_level_start_offset,
626  cur_level_start_offset + maximum_node_at_next_level);
627  return std::make_pair(depth, index_pair);
628  }
629  depth++;
630  cur_level_start_offset += maximum_node_at_next_level;
631  }
632  }
633 
634  // agg input column buffer and its type info
635  const INPUT_TYPE* const input_col_buf_;
636  // to deal with conditional aggregate function
637  const int8_t* const cond_col_buf_;
639  // the following two idx buffers are for accessing the sorted input column
640  // based on our current window function context (i.e., indirect column access)
641  // i-th row -> get indirect idx 'i_idx' from `ordered_input_col_idx_buf_`
642  // and use `i_idx` to get the true row index `t_idx` from `original_input_col_idx_buf_`
643  // and use `t_idx` to get i-th row of the sorted column
644  // otherwise, we can access the column when it keeps sorted values
645  // original index (i.e., row_id) to access input_col_buf
646  const int32_t* const original_input_col_idx_buf_;
647  // ordered index to access sorted input_col_buf
648  const int64_t* const ordered_input_col_idx_buf_;
649  // # input elements
650  int64_t const num_elems_;
651  // tree fanout
652  size_t const fan_out_;
653  // a type of aggregate function
656  INPUT_TYPE const input_type_null_val_;
657  AGG_TYPE const null_val_;
658  // invalid_val is required to fill an empty node for a correct aggregation
659  INPUT_TYPE const invalid_val_;
660  // # nodes in the leaf level
661  size_t leaf_size_;
662  // level of the leaf
663  size_t leaf_depth_;
664  // start ~ end indexes of the leaf level
666  // total number of nodes in the tree
667  size_t tree_size_;
668  // depending on aggregate function, we use different aggregation logic
669  // 1) a segment tree for computing derived aggregates, i.e., avg and stddev
671  // 2) rest of aggregate functions can use a vector of elements
673 };
const int64_t *const ordered_input_col_idx_buf_
Definition: SegmentTree.h:648
AGG_TYPE aggregateValueViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const
Definition: SegmentTree.h:414
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:670
IndexPair getLeafRange() const
Definition: SegmentTree.h:152
SQLTypeInfo const input_col_ti_
Definition: SegmentTree.h:638
size_t const fan_out_
Definition: SegmentTree.h:652
size_t getLeafDepth() const
Definition: SegmentTree.h:148
const INPUT_TYPE *const input_col_buf_
Definition: SegmentTree.h:635
HOST DEVICE int get_scale() const
Definition: sqltypes.h:385
std::vector< AGG_TYPE > prepareChildValuesforConditionalAggregation(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:313
size_t getTreeSize() const
Definition: SegmentTree.h:144
size_t getLeafSize() const
Definition: SegmentTree.h:142
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
Definition: SegmentTree.h:501
Constants for Builtin SQL Types supported by HEAVY.AI.
SumAndCountPair< AGG_TYPE > buildForDerivedAggregate(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:267
size_t leaf_size_
Definition: SegmentTree.h:661
#define CHECK_GT(x, y)
Definition: Logger.h:301
AGG_TYPE buildForCount(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:235
size_t getTreeFanout() const
Definition: SegmentTree.h:150
bool const is_conditional_agg_
Definition: SegmentTree.h:655
AGG_TYPE fetch_col_for_non_cond_agg(size_t const idx)
Definition: SegmentTree.h:160
std::vector< int64_t > computeChildIndexes(std::vector< int64_t > &child_indexes, int64_t parent_idx, size_t parent_tree_depth) const
Definition: SegmentTree.h:597
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
Definition: SegmentTree.h:551
SegmentTree(std::vector< const int8_t * > const &input_col_bufs, SQLTypeInfo const &input_col_ti, int32_t const *original_input_col_idx_buf, int64_t const *ordered_input_col_idx_buf, int64_t num_elems, SqlWindowFunctionKind agg_type, size_t fan_out)
Definition: SegmentTree.h:40
DEVICE TextEncodingDict inline_null_value()
Definition: heavydbTypes.h:187
size_t getNumElems() const
Definition: SegmentTree.h:146
void * checked_malloc(const size_t size)
Definition: checked_alloc.h:45
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregateViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const
Definition: SegmentTree.h:479
AGG_TYPE buildForCondAgg(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:205
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregate(const std::vector< SumAndCountPair< AGG_TYPE >> &vals) const
Definition: SegmentTree.h:460
AGG_TYPE query(const IndexPair &query_range) const
Definition: SegmentTree.h:99
std::pair< int64_t, int64_t > IndexPair
AGG_TYPE * getAggregatedValues() const
Definition: SegmentTree.h:136
INPUT_TYPE const input_type_null_val_
Definition: SegmentTree.h:656
std::vector< SumAndCountPair< AGG_TYPE > > prepareChildValuesforDerivedAggregate(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:349
size_t tree_size_
Definition: SegmentTree.h:667
const int32_t *const original_input_col_idx_buf_
Definition: SegmentTree.h:646
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
std::vector< AGG_TYPE > prepareChildValuesforAggregation(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:295
SqlWindowFunctionKind
Definition: sqldefs.h:120
AGG_TYPE fetch_col_for_cond_agg(size_t const idx)
Definition: SegmentTree.h:165
SqlWindowFunctionKind const agg_type_
Definition: SegmentTree.h:654
AGG_TYPE fetch_col_for_count(size_t const idx)
Definition: SegmentTree.h:156
AGG_TYPE build(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:174
Common Enum definitions for SQL processing.
std::pair< size_t, IndexPair > findMaxTreeHeight(int64_t num_elem, int fan_out)
Definition: SegmentTree.h:615
SumAndCountPair< AGG_TYPE > * getDerivedAggregatedValues() const
Definition: SegmentTree.h:138
IndexPair leaf_range_
Definition: SegmentTree.h:665
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
Definition: SegmentTree.h:369
const int8_t *const cond_col_buf_
Definition: SegmentTree.h:637
bool is_decimal() const
Definition: sqltypes.h:579
std::vector< AGG_TYPE > prepareChildValuesforAggregationForCount(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:332
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:672
size_t leaf_depth_
Definition: SegmentTree.h:663
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659
int64_t const num_elems_
Definition: SegmentTree.h:650