OmniSciDB  c0231cc57d
 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(const int8_t* input_col_buf,
41  const SQLTypeInfo& input_col_ti,
42  const int32_t* original_input_col_idx_buf,
43  const int64_t* ordered_input_col_idx_buf,
44  IndexPair order_col_null_range,
45  int64_t num_elems,
46  SqlWindowFunctionKind agg_type,
47  size_t fan_out)
48  : input_col_buf_(reinterpret_cast<const INPUT_TYPE*>(input_col_buf))
49  , input_col_ti_(input_col_ti)
50  , original_input_col_idx_buf_(original_input_col_idx_buf)
51  , ordered_input_col_idx_buf_(ordered_input_col_idx_buf)
52  , num_elems_(num_elems)
53  , fan_out_(fan_out)
54  , agg_type_(agg_type)
55  , null_range_(order_col_null_range) {
56  CHECK_GT(num_elems_, (int64_t)0);
57  auto max_tree_height_and_leaf_range = findMaxTreeHeight(num_elems_, fan_out_);
58  leaf_depth_ = max_tree_height_and_leaf_range.first;
59  leaf_range_ = max_tree_height_and_leaf_range.second;
60  // since the input column is ordered we can know the exact range of null values
61  // and can use this information to elaborate a query range to do better finding
62  // of lower and upper bounds while computing the aggregate operation
63  null_range_.first = std::numeric_limits<int64_t>::max();
64  null_range_.second = std::numeric_limits<int64_t>::min();
65  // the index of the last elem of the leaf level is the same as the tree's size
66  tree_size_ = leaf_range_.second;
67  leaf_size_ = leaf_range_.second - leaf_range_.first;
68  // invalid_val is required to fill an empty node for a correct aggregation
70  invalid_val_ = std::numeric_limits<INPUT_TYPE>::max();
71  } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
72  invalid_val_ = std::numeric_limits<INPUT_TYPE>::min();
73  } else {
74  invalid_val_ = 0;
75  }
76  // sometimes, we need to fill the null value to internal nodes
77  null_val_ = inline_null_value<AGG_TYPE>();
78  // and we also need to know the null value of the input column type
79  // to recognize it while building a segment tree
80  input_type_null_val_ = inline_null_value<INPUT_TYPE>();
81  // for derived aggregate, we maintain both "sum" aggregates and element counts
82  // to compute the value correctly
87  } else {
88  // we can use an array as a segment tree for the rest of aggregates
90  reinterpret_cast<AGG_TYPE*>(checked_malloc(tree_size_ * sizeof(AGG_TYPE)));
91  build(0, 0);
92  }
93 #ifndef __CUDACC__
94  VLOG(1) << "tree size: " << getTreeSize() << ", tree fanout: " << getTreeFanout()
95  << ", leaf depth: " << getLeafDepth()
96  << ", leaf range: " << getLeafRange().first << " ~ " << getLeafRange().second
97  << ", leaf size: " << getLeafSize();
98 #endif
99  }
100 
102  if (num_elems_ > 0) {
104  free(derived_aggregated_);
105  } else {
106  free(aggregated_values_);
107  }
108  }
109  }
110 
111  // try to aggregate values of the given query range
112  AGG_TYPE query(const IndexPair& query_range) const {
113  if (query_range.first > query_range.second || query_range.first < 0 ||
114  query_range.second > leaf_size_) {
115  return null_val_;
116  }
117  // todo (yoonmin) : support more derived aggregate functions
119  SumAndCountPair<AGG_TYPE> sum_and_count_pair =
120  searchForDerivedAggregate(query_range, 0, 0, 0, leaf_size_);
121  if (sum_and_count_pair.sum == null_val_) {
122  return null_val_;
123  } else if (sum_and_count_pair.count == 0) {
124  return 0;
125  } else {
126  if (input_col_ti_.is_decimal()) {
127  return (static_cast<double>(sum_and_count_pair.sum) /
128  pow(10, input_col_ti_.get_scale())) /
129  sum_and_count_pair.count;
130  } else {
131  return sum_and_count_pair.sum / sum_and_count_pair.count;
132  }
133  }
134  } else {
135  const auto res = search(query_range, 0, 0, 0, leaf_size_);
136  if (res == null_val_) {
137  switch (agg_type_) {
140  return input_type_null_val_;
141  default:
142  return null_val_;
143  }
144  }
145  return res;
146  }
147  }
148 
149  AGG_TYPE* getAggregatedValues() const { return aggregated_values_; }
150 
152  return derived_aggregated_;
153  }
154 
155  size_t getLeafSize() const { return leaf_size_; }
156 
157  size_t getTreeSize() const { return tree_size_; }
158 
159  size_t getNumElems() const { return num_elems_; }
160 
161  size_t getLeafDepth() const { return leaf_depth_; }
162 
163  size_t getTreeFanout() const { return fan_out_; }
164 
165  IndexPair getLeafRange() const { return leaf_range_; }
166 
167  private:
168  // build a segment tree for a given aggregate function recursively
169  AGG_TYPE build(int64_t cur_node_idx, size_t cur_node_depth) {
170  if (cur_node_idx >= leaf_range_.first && cur_node_idx <= leaf_range_.second) {
171  // arrive at leafs, so try to put a corresponding input column value
172  int64_t input_col_idx = cur_node_idx - leaf_range_.first;
173  if (input_col_idx >= num_elems_) {
174  // fill an invalid value
175  aggregated_values_[cur_node_idx] = invalid_val_;
176  return invalid_val_;
177  }
178  // try to get the current row's column value
179  const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
180  const auto refined_input_col_idx =
181  original_input_col_idx_buf_[input_col_idx_ordered];
182  const auto col_val = input_col_buf_[refined_input_col_idx];
183  if (col_val != input_type_null_val_) {
185  // for count aggregation, we fill '1` instead of the col_val
186  aggregated_values_[cur_node_idx] = 1;
187  } else {
188  // otherwise, we fill the `col_val` to leaf nodes
189  aggregated_values_[cur_node_idx] = col_val;
190  }
191  } else {
192  // fill null val
193  aggregated_values_[cur_node_idx] = null_val_;
194  }
195  // return the current value to fill a parent node
196  return aggregated_values_[cur_node_idx];
197  }
198 
199  // when reaching here, we need to take care of a node having child nodes,
200  // and we compute an aggregated value from its child nodes
201  std::vector<AGG_TYPE> child_vals =
202  prepareChildValuesforAggregation(cur_node_idx, cur_node_depth);
203 
204  // compute the new aggregated value
205  aggregated_values_[cur_node_idx] = aggregateValue(child_vals);
206 
207  // return the value for the upper-level aggregation
208  return aggregated_values_[cur_node_idx];
209  }
210 
211  // the logic is exactly the same as normal aggregate case, but has a different
212  // node type: SumAndCountPair
214  size_t cur_node_depth) {
215  if (cur_node_idx >= leaf_range_.first && cur_node_idx <= leaf_range_.second) {
216  int64_t input_col_idx = cur_node_idx - leaf_range_.first;
217  if (input_col_idx >= num_elems_) {
218  derived_aggregated_[cur_node_idx] = {invalid_val_, 0};
219  } else {
220  const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
221  const auto refined_input_col_idx =
222  original_input_col_idx_buf_[input_col_idx_ordered];
223  auto col_val = input_col_buf_[refined_input_col_idx];
224  if (col_val != input_type_null_val_) {
225  derived_aggregated_[cur_node_idx] = {col_val, 1};
226  } else {
227  derived_aggregated_[cur_node_idx] = {null_val_, 0};
228  }
229  }
230  return derived_aggregated_[cur_node_idx];
231  }
232 
233  std::vector<SumAndCountPair<AGG_TYPE>> child_vals =
234  prepareChildValuesforDerivedAggregate(cur_node_idx, cur_node_depth);
235 
236  derived_aggregated_[cur_node_idx] = aggregateValueForDerivedAggregate(child_vals);
237  return derived_aggregated_[cur_node_idx];
238  }
239 
240  // gather aggregated values of each child node
241  std::vector<AGG_TYPE> prepareChildValuesforAggregation(int64_t parent_idx,
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);
248  }
249  } else {
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);
253  }
254  }
255  return child_vals;
256  }
257 
258  std::vector<SumAndCountPair<AGG_TYPE>> prepareChildValuesforDerivedAggregate(
259  int64_t parent_idx,
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) {
265  child_vals[i] = buildForDerivedAggregate(i + 1, next_node_depth);
266  }
267  } else {
268  int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
269  for (size_t i = 0; i < fan_out_; ++i) {
270  child_vals[i] =
271  buildForDerivedAggregate(cur_depth_start_offset + i, next_node_depth);
272  }
273  }
274  return child_vals;
275  }
276 
277  // compute aggregated value of the given values depending on the aggregate function
278  AGG_TYPE aggregateValue(const std::vector<AGG_TYPE>& vals) const {
279  // todo (yoonmin) : optimize logic for a non-null column
280  bool all_nulls = true;
282  AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
283  std::for_each(
284  vals.begin(), vals.end(), [&min_val, &all_nulls, this](const AGG_TYPE val) {
285  if (val != null_val_ && val != invalid_val_) {
286  all_nulls = false;
287  min_val = std::min(min_val, val);
288  }
289  });
290  if (all_nulls) {
291  min_val = null_val_;
292  }
293  return min_val;
294  } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
295  AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
296  std::for_each(
297  vals.begin(), vals.end(), [&max_val, &all_nulls, this](const AGG_TYPE val) {
298  if (val != null_val_ && val != invalid_val_) {
299  all_nulls = false;
300  max_val = std::max(max_val, val);
301  }
302  });
303  if (all_nulls) {
304  max_val = null_val_;
305  }
306  return max_val;
307  } else {
308  AGG_TYPE agg_val = 0;
309  std::for_each(
310  vals.begin(), vals.end(), [&agg_val, &all_nulls, this](const AGG_TYPE val) {
311  if (val != null_val_ && val != invalid_val_) {
312  agg_val += val;
313  all_nulls = false;
314  }
315  });
316  if (all_nulls) {
317  agg_val = null_val_;
318  }
319  return agg_val;
320  }
321  }
322 
323  AGG_TYPE aggregateValueViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const {
324  // todo (yoonmin) : optimize logic for a non-null column
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) {
330  AGG_TYPE val = aggregated_values_[i];
331  if (val != null_val_ && val != invalid_val_) {
332  all_nulls = false;
333  min_val = std::min(min_val, val);
334  }
335  }
336  if (all_nulls) {
337  min_val = null_val_;
338  }
339  return min_val;
340  } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
341  AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
342  for (size_t i = cur_col_idx; i < end_idx; ++i) {
343  AGG_TYPE val = aggregated_values_[i];
344  if (val != null_val_ && val != invalid_val_) {
345  all_nulls = false;
346  max_val = std::max(max_val, val);
347  }
348  }
349  if (all_nulls) {
350  max_val = null_val_;
351  }
352  return max_val;
353  } else {
354  AGG_TYPE agg_val = 0;
355  for (size_t i = cur_col_idx; i < end_idx; ++i) {
356  AGG_TYPE val = aggregated_values_[i];
357  if (val != null_val_ && val != invalid_val_) {
358  agg_val += val;
359  all_nulls = false;
360  }
361  }
362  if (all_nulls) {
363  agg_val = null_val_;
364  }
365  return agg_val;
366  }
367  }
368 
370  const std::vector<SumAndCountPair<AGG_TYPE>>& vals) const {
372  bool all_nulls = true;
373  std::for_each(vals.begin(),
374  vals.end(),
375  [&res, &all_nulls, this](const SumAndCountPair<AGG_TYPE>& pair) {
376  if (pair.sum != null_val_ && pair.sum != invalid_val_) {
377  res.sum += pair.sum;
378  res.count += pair.count;
379  all_nulls = false;
380  }
381  });
382  if (all_nulls) {
383  return {null_val_, 0};
384  }
385  return res;
386  }
387 
389  int64_t cur_col_idx,
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) {
395  const SumAndCountPair<AGG_TYPE> cur_pair_val = aggregated_values_[i];
396  if (cur_pair_val.sum != null_val_ && cur_pair_val.sum != invalid_val_) {
397  res.sum += cur_pair_val.sum;
398  res.count += cur_pair_val.count;
399  all_nulls = false;
400  }
401  }
402  if (all_nulls) {
403  return {null_val_, 0};
404  }
405  return res;
406  }
407 
408  // search an aggregated value of the given query range
409  // by visiting necessary nodes of the segment tree including leafs
410  AGG_TYPE search(const IndexPair& query_range,
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 {
415  if (num_elems_ <= 0) {
416  return null_val_;
417  }
418  if (search_range_end_idx < query_range.first ||
419  query_range.second < search_range_start_idx) {
420  // completely out-of-bound
421  return invalid_val_;
422  } else if (query_range.first <= search_range_start_idx &&
423  search_range_end_idx <= query_range.second) {
424  // perfectly fitted in a range of the current node
425  return aggregated_values_[cur_node_idx];
426  } else {
427  // this node is partially within left and right indexes
428  if (cur_node_depth == leaf_depth_) {
429  // we already reach the leaf level, so do not need to proceed to the next level
430  // and so aggregate the value in the range by using a simple loop
431  size_t num_visits = query_range.second - search_range_start_idx + 1;
433  cur_node_idx, num_visits, null_val_, invalid_val_);
434  } else {
435  // find aggregated value from child nodes
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_);
441  computeChildIndexes(child_indexes, cur_node_idx, cur_node_depth);
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,
445  child_indexes[i],
446  cur_node_depth + 1,
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;
453  }
454  }
455  return aggregateValue(child_vals);
456  }
457  }
458  }
459 
461  const IndexPair& query_range,
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) {
468  return {invalid_val_, 0};
469  } else if (query_range.first <= search_range_start_idx &&
470  search_range_end_idx <= query_range.second) {
471  return derived_aggregated_[cur_node_idx];
472  } else {
473  if (cur_node_depth == leaf_depth_) {
474  size_t num_visits = query_range.second - search_range_start_idx + 1;
476  cur_node_idx, num_visits, null_val_, invalid_val_);
477  } else {
478  // find aggregated value from child nodes
479  std::vector<int64_t> child_indexes(fan_out_);
480  computeChildIndexes(child_indexes, cur_node_idx, cur_node_depth);
481  std::vector<SumAndCountPair<AGG_TYPE>> child_vals(fan_out_, {invalid_val_, 0});
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) {
487  child_vals[i] = searchForDerivedAggregate(query_range,
488  child_indexes[i],
489  cur_node_depth + 1,
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;
496  }
497  }
498  return aggregateValueForDerivedAggregate(child_vals);
499  }
500  }
501  }
502 
503  // for prepareChildValuesForAggregate function includes the logic of the
504  // `computeChildIndexes` function internally to reduce # creation of the temporary
505  // vector while building a segment tree, but keep it to use it for `search` function
506  std::vector<int64_t> computeChildIndexes(std::vector<int64_t>& child_indexes,
507  int64_t parent_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;
512  }
513  } else {
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;
517  }
518  }
519  return child_indexes;
520  }
521 
522  // a utility function that computes a length and the start node index of a segment tree
523  // to contain 'num_elem' with a given 'fan_out'
524  std::pair<size_t, IndexPair> findMaxTreeHeight(int64_t num_elem, int fan_out) {
525  if (num_elem <= 0) {
526  return std::make_pair(0, std::make_pair(0, 0));
527  }
528  int64_t cur_level_start_offset = 0;
529  size_t depth = 0;
530  IndexPair index_pair = std::make_pair(0, 0);
531  while (true) {
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);
537  }
538  depth++;
539  cur_level_start_offset += maximum_node_at_next_level;
540  }
541  }
542 
543  // agg input column buffer and its type info
544  const INPUT_TYPE* input_col_buf_;
546  // the following two idx buffers are for accessing the sorted input column
547  // based on our current window function context (i.e., indirect column access)
548  // i-th row -> get indirect idx 'i_idx' from `ordered_input_col_idx_buf_`
549  // and use `i_idx` to get the true row index `t_idx` from `original_input_col_idx_buf_`
550  // and use `t_idx` to get i-th row of the sorted column
551  // otherwise, we can access the column when it keeps sorted values
552  // original index (i.e., row_id) to access input_col_buf
554  // ordered index to access sorted input_col_buf
556  // # input elements
557  int64_t num_elems_;
558  // tree fanout
559  size_t fan_out_;
560  // # nodes in the leaf level
561  size_t leaf_size_;
562  // a type of aggregate function
564  // level of the leaf
565  size_t leaf_depth_;
566  // start ~ end indexes of the leaf level
568  // index range of null value if exists
570  // total number of nodes in the tree
571  size_t tree_size_;
572  // depending on aggregate function, we use different aggregation logic
573  // 1) a segment tree for computing derived aggregates, i.e., avg and stddev
575  // 2) rest of aggregate functions can use a vector of elements
577  // invalid value is different depending on 1) a type of window expression (i.e., sum,
578  // avg, count, ...) and 2) a type of the expression, i.e., tinyint, double, float, ...
579  INPUT_TYPE invalid_val_;
581  AGG_TYPE null_val_;
582 };
AGG_TYPE aggregateValueViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const
Definition: SegmentTree.h:323
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:574
const int32_t * original_input_col_idx_buf_
Definition: SegmentTree.h:553
int64_t num_elems_
Definition: SegmentTree.h:557
IndexPair getLeafRange() const
Definition: SegmentTree.h:165
size_t getLeafDepth() const
Definition: SegmentTree.h:161
SqlWindowFunctionKind agg_type_
Definition: SegmentTree.h:563
HOST DEVICE int get_scale() const
Definition: sqltypes.h:409
const int64_t * ordered_input_col_idx_buf_
Definition: SegmentTree.h:555
size_t getTreeSize() const
Definition: SegmentTree.h:157
size_t getLeafSize() const
Definition: SegmentTree.h:155
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:410
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:213
size_t leaf_size_
Definition: SegmentTree.h:561
#define CHECK_GT(x, y)
Definition: Logger.h:234
AGG_TYPE null_val_
Definition: SegmentTree.h:581
size_t getTreeFanout() const
Definition: SegmentTree.h:163
const SQLTypeInfo input_col_ti_
Definition: SegmentTree.h:545
std::vector< int64_t > computeChildIndexes(std::vector< int64_t > &child_indexes, int64_t parent_idx, size_t parent_tree_depth) const
Definition: SegmentTree.h:506
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:460
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:579
size_t getNumElems() const
Definition: SegmentTree.h:159
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:388
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregate(const std::vector< SumAndCountPair< AGG_TYPE >> &vals) const
Definition: SegmentTree.h:369
const INPUT_TYPE * input_col_buf_
Definition: SegmentTree.h:544
AGG_TYPE query(const IndexPair &query_range) const
Definition: SegmentTree.h:112
std::pair< int64_t, int64_t > IndexPair
AGG_TYPE * getAggregatedValues() const
Definition: SegmentTree.h:149
std::vector< SumAndCountPair< AGG_TYPE > > prepareChildValuesforDerivedAggregate(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:258
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)
Definition: SegmentTree.h:40
size_t tree_size_
Definition: SegmentTree.h:571
std::vector< AGG_TYPE > prepareChildValuesforAggregation(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:241
SqlWindowFunctionKind
Definition: sqldefs.h:113
size_t fan_out_
Definition: SegmentTree.h:559
INPUT_TYPE input_type_null_val_
Definition: SegmentTree.h:580
AGG_TYPE build(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:169
Common Enum definitions for SQL processing.
std::pair< size_t, IndexPair > findMaxTreeHeight(int64_t num_elem, int fan_out)
Definition: SegmentTree.h:524
SumAndCountPair< AGG_TYPE > * getDerivedAggregatedValues() const
Definition: SegmentTree.h:151
IndexPair null_range_
Definition: SegmentTree.h:569
IndexPair leaf_range_
Definition: SegmentTree.h:567
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
Definition: SegmentTree.h:278
bool is_decimal() const
Definition: sqltypes.h:603
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:576
size_t leaf_depth_
Definition: SegmentTree.h:565
#define VLOG(n)
Definition: Logger.h:316