OmniSciDB  cde582ebc3
 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 refined_input_col_idx =
181  const auto col_val = input_col_buf_[refined_input_col_idx];
182  if (col_val != input_type_null_val_) {
184  // for count aggregation, we fill '1` instead of the col_val
185  aggregated_values_[cur_node_idx] = 1;
186  } else {
187  // otherwise, we fill the `col_val` to leaf nodes
188  aggregated_values_[cur_node_idx] = col_val;
189  }
190  } else {
191  // fill null val
192  aggregated_values_[cur_node_idx] = null_val_;
193  }
194  // return the current value to fill a parent node
195  return aggregated_values_[cur_node_idx];
196  }
197 
198  // when reaching here, we need to take care of a node having child nodes,
199  // and we compute an aggregated value from its child nodes
200  std::vector<AGG_TYPE> child_vals =
201  prepareChildValuesforAggregation(cur_node_idx, cur_node_depth);
202 
203  // compute the new aggregated value
204  aggregated_values_[cur_node_idx] = aggregateValue(child_vals);
205 
206  // return the value for the upper-level aggregation
207  return aggregated_values_[cur_node_idx];
208  }
209 
210  // the logic is exactly the same as normal aggregate case, but has a different
211  // node type: SumAndCountPair
213  size_t cur_node_depth) {
214  if (cur_node_idx >= leaf_range_.first && cur_node_idx <= leaf_range_.second) {
215  int64_t input_col_idx = cur_node_idx - leaf_range_.first;
216  const auto modified_input_col_idx =
218  if (input_col_idx >= num_elems_) {
219  derived_aggregated_[cur_node_idx] = {invalid_val_, 0};
220  } else {
221  auto col_val = input_col_buf_[modified_input_col_idx];
222  if (col_val != input_type_null_val_) {
223  derived_aggregated_[cur_node_idx] = {col_val, 1};
224  } else {
225  derived_aggregated_[cur_node_idx] = {null_val_, 0};
226  }
227  }
228  return derived_aggregated_[cur_node_idx];
229  }
230 
231  std::vector<SumAndCountPair<AGG_TYPE>> child_vals =
232  prepareChildValuesforDerivedAggregate(cur_node_idx, cur_node_depth);
233 
234  derived_aggregated_[cur_node_idx] = aggregateValueForDerivedAggregate(child_vals);
235  return derived_aggregated_[cur_node_idx];
236  }
237 
238  // gather aggregated values of each child node
239  std::vector<AGG_TYPE> prepareChildValuesforAggregation(int64_t parent_idx,
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);
246  }
247  } else {
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);
251  }
252  }
253  return child_vals;
254  }
255 
256  std::vector<SumAndCountPair<AGG_TYPE>> prepareChildValuesforDerivedAggregate(
257  int64_t parent_idx,
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) {
263  child_vals[i] = buildForDerivedAggregate(i + 1, next_node_depth);
264  }
265  } else {
266  int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
267  for (size_t i = 0; i < fan_out_; ++i) {
268  child_vals[i] =
269  buildForDerivedAggregate(cur_depth_start_offset + i, next_node_depth);
270  }
271  }
272  return child_vals;
273  }
274 
275  // compute aggregated value of the given values depending on the aggregate function
276  AGG_TYPE aggregateValue(const std::vector<AGG_TYPE>& vals) const {
277  // todo (yoonmin) : optimize logic for a non-null column
278  bool all_nulls = true;
280  AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
281  std::for_each(
282  vals.begin(), vals.end(), [&min_val, &all_nulls, this](const AGG_TYPE val) {
283  if (val != null_val_ && val != invalid_val_) {
284  all_nulls = false;
285  min_val = std::min(min_val, val);
286  }
287  });
288  if (all_nulls) {
289  min_val = null_val_;
290  }
291  return min_val;
292  } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
293  AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
294  std::for_each(
295  vals.begin(), vals.end(), [&max_val, &all_nulls, this](const AGG_TYPE val) {
296  if (val != null_val_ && val != invalid_val_) {
297  all_nulls = false;
298  max_val = std::max(max_val, val);
299  }
300  });
301  if (all_nulls) {
302  max_val = null_val_;
303  }
304  return max_val;
305  } else {
306  AGG_TYPE agg_val = 0;
307  std::for_each(
308  vals.begin(), vals.end(), [&agg_val, &all_nulls, this](const AGG_TYPE val) {
309  if (val != null_val_ && val != invalid_val_) {
310  agg_val += val;
311  all_nulls = false;
312  }
313  });
314  if (all_nulls) {
315  agg_val = null_val_;
316  }
317  return agg_val;
318  }
319  }
320 
321  AGG_TYPE aggregateValueViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const {
322  // todo (yoonmin) : optimize logic for a non-null column
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) {
328  AGG_TYPE val = aggregated_values_[i];
329  if (val != null_val_ && val != invalid_val_) {
330  all_nulls = false;
331  min_val = std::min(min_val, val);
332  }
333  }
334  if (all_nulls) {
335  min_val = null_val_;
336  }
337  return min_val;
338  } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
339  AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
340  for (size_t i = cur_col_idx; i < end_idx; ++i) {
341  AGG_TYPE val = aggregated_values_[i];
342  if (val != null_val_ && val != invalid_val_) {
343  all_nulls = false;
344  max_val = std::max(max_val, val);
345  }
346  }
347  if (all_nulls) {
348  max_val = null_val_;
349  }
350  return max_val;
351  } else {
352  AGG_TYPE agg_val = 0;
353  for (size_t i = cur_col_idx; i < end_idx; ++i) {
354  AGG_TYPE val = aggregated_values_[i];
355  if (val != null_val_ && val != invalid_val_) {
356  agg_val += val;
357  all_nulls = false;
358  }
359  }
360  if (all_nulls) {
361  agg_val = null_val_;
362  }
363  return agg_val;
364  }
365  }
366 
368  const std::vector<SumAndCountPair<AGG_TYPE>>& vals) const {
370  bool all_nulls = true;
371  std::for_each(vals.begin(),
372  vals.end(),
373  [&res, &all_nulls, this](const SumAndCountPair<AGG_TYPE>& pair) {
374  if (pair.sum != null_val_ && pair.sum != invalid_val_) {
375  res.sum += pair.sum;
376  res.count += pair.count;
377  all_nulls = false;
378  }
379  });
380  if (all_nulls) {
381  return {null_val_, 0};
382  }
383  return res;
384  }
385 
387  int64_t cur_col_idx,
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) {
393  const SumAndCountPair<AGG_TYPE> cur_pair_val = aggregated_values_[i];
394  if (cur_pair_val.sum != null_val_ && cur_pair_val.sum != invalid_val_) {
395  res.sum += cur_pair_val.sum;
396  res.count += cur_pair_val.count;
397  all_nulls = false;
398  }
399  }
400  if (all_nulls) {
401  return {null_val_, 0};
402  }
403  return res;
404  }
405 
406  // search an aggregated value of the given query range
407  // by visiting necessary nodes of the segment tree including leafs
408  AGG_TYPE search(const IndexPair& query_range,
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 {
413  if (num_elems_ <= 0) {
414  return null_val_;
415  }
416  if (search_range_end_idx < query_range.first ||
417  query_range.second < search_range_start_idx) {
418  // completely out-of-bound
419  return invalid_val_;
420  } else if (query_range.first <= search_range_start_idx &&
421  search_range_end_idx <= query_range.second) {
422  // perfectly fitted in a range of the current node
423  return aggregated_values_[cur_node_idx];
424  } else {
425  // this node is partially within left and right indexes
426  if (cur_node_depth == leaf_depth_) {
427  // we already reach the leaf level, so do not need to proceed to the next level
428  // and so aggregate the value in the range by using a simple loop
429  size_t num_visits = query_range.second - search_range_start_idx + 1;
431  cur_node_idx, num_visits, null_val_, invalid_val_);
432  } else {
433  // find aggregated value from child nodes
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_);
439  computeChildIndexes(child_indexes, cur_node_idx, cur_node_depth);
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,
443  child_indexes[i],
444  cur_node_depth + 1,
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;
451  }
452  }
453  return aggregateValue(child_vals);
454  }
455  }
456  }
457 
459  const IndexPair& query_range,
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) {
466  return {invalid_val_, 0};
467  } else if (query_range.first <= search_range_start_idx &&
468  search_range_end_idx <= query_range.second) {
469  return derived_aggregated_[cur_node_idx];
470  } else {
471  if (cur_node_depth == leaf_depth_) {
472  size_t num_visits = query_range.second - search_range_start_idx + 1;
474  cur_node_idx, num_visits, null_val_, invalid_val_);
475  } else {
476  // find aggregated value from child nodes
477  std::vector<int64_t> child_indexes(fan_out_);
478  computeChildIndexes(child_indexes, cur_node_idx, cur_node_depth);
479  std::vector<SumAndCountPair<AGG_TYPE>> child_vals(fan_out_, {invalid_val_, 0});
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) {
485  child_vals[i] = searchForDerivedAggregate(query_range,
486  child_indexes[i],
487  cur_node_depth + 1,
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;
494  }
495  }
496  return aggregateValueForDerivedAggregate(child_vals);
497  }
498  }
499  }
500 
501  // for prepareChildValuesForAggregate function includes the logic of the
502  // `computeChildIndexes` function internally to reduce # creation of the temporary
503  // vector while building a segment tree, but keep it to use it for `search` function
504  std::vector<int64_t> computeChildIndexes(std::vector<int64_t>& child_indexes,
505  int64_t parent_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;
510  }
511  } else {
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;
515  }
516  }
517  return child_indexes;
518  }
519 
520  // a utility function that computes a length and the start node index of a segment tree
521  // to contain 'num_elem' with a given 'fan_out'
522  std::pair<size_t, IndexPair> findMaxTreeHeight(int64_t num_elem, int fan_out) {
523  if (num_elem <= 0) {
524  return std::make_pair(0, std::make_pair(0, 0));
525  }
526  int64_t cur_level_start_offset = 1;
527  size_t depth = 0;
528  IndexPair index_pair = std::make_pair(0, 0);
529  while (true) {
530  if (num_elem < cur_level_start_offset) {
531  return std::make_pair(depth, index_pair);
532  }
533  depth++;
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;
538  }
539  }
540 
541  // agg input column buffer and its type info
542  const INPUT_TYPE* input_col_buf_;
544  // the following two idx buffers are for accessing the sorted input column
545  // based on our current window function context (i.e., indirect column access)
546  // i-th row -> get indirect idx 'i_idx' from `ordered_input_col_idx_buf_`
547  // and use `i_idx` to get the true row index `t_idx` from `original_input_col_idx_buf_`
548  // and use `t_idx` to get i-th row of the sorted column
549  // otherwise, we can access the column when it keeps sorted values
550  // original index (i.e., row_id) to access input_col_buf
552  // ordered index to access sorted input_col_buf
554  // # input elements
555  int64_t num_elems_;
556  // tree fanout
557  size_t fan_out_;
558  // # nodes in the leaf level
559  size_t leaf_size_;
560  // a type of aggregate function
562  // level of the leaf
563  size_t leaf_depth_;
564  // start ~ end indexes of the leaf level
566  // index range of null value if exists
568  // total number of nodes in the tree
569  size_t tree_size_;
570  // depending on aggregate function, we use different aggregation logic
571  // 1) a segment tree for computing derived aggregates, i.e., avg and stddev
573  // 2) rest of aggregate functions can use a vector of elements
575  // invalid value is different depending on 1) a type of window expression (i.e., sum,
576  // avg, count, ...) and 2) a type of the expression, i.e., tinyint, double, float, ...
577  INPUT_TYPE invalid_val_;
579  AGG_TYPE null_val_;
580 };
AGG_TYPE aggregateValueViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const
Definition: SegmentTree.h:321
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:572
const int32_t * original_input_col_idx_buf_
Definition: SegmentTree.h:551
int64_t num_elems_
Definition: SegmentTree.h:555
IndexPair getLeafRange() const
Definition: SegmentTree.h:165
size_t getLeafDepth() const
Definition: SegmentTree.h:161
SqlWindowFunctionKind agg_type_
Definition: SegmentTree.h:561
HOST DEVICE int get_scale() const
Definition: sqltypes.h:334
const int64_t * ordered_input_col_idx_buf_
Definition: SegmentTree.h:553
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:408
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:212
size_t leaf_size_
Definition: SegmentTree.h:559
#define CHECK_GT(x, y)
Definition: Logger.h:234
AGG_TYPE null_val_
Definition: SegmentTree.h:579
size_t getTreeFanout() const
Definition: SegmentTree.h:163
const SQLTypeInfo input_col_ti_
Definition: SegmentTree.h:543
std::vector< int64_t > computeChildIndexes(std::vector< int64_t > &child_indexes, int64_t parent_idx, size_t parent_tree_depth) const
Definition: SegmentTree.h:504
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:458
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:577
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:386
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregate(const std::vector< SumAndCountPair< AGG_TYPE >> &vals) const
Definition: SegmentTree.h:367
const INPUT_TYPE * input_col_buf_
Definition: SegmentTree.h:542
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:256
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:569
std::vector< AGG_TYPE > prepareChildValuesforAggregation(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:239
SqlWindowFunctionKind
Definition: sqldefs.h:110
size_t fan_out_
Definition: SegmentTree.h:557
INPUT_TYPE input_type_null_val_
Definition: SegmentTree.h:578
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:522
SumAndCountPair< AGG_TYPE > * getDerivedAggregatedValues() const
Definition: SegmentTree.h:151
IndexPair null_range_
Definition: SegmentTree.h:567
IndexPair leaf_range_
Definition: SegmentTree.h:565
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
Definition: SegmentTree.h:276
bool is_decimal() const
Definition: sqltypes.h:513
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:574
size_t leaf_depth_
Definition: SegmentTree.h:563
#define VLOG(n)
Definition: Logger.h:316