OmniSciDB  c0231cc57d
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
SegmentTree< INPUT_TYPE, AGG_TYPE > Class Template Reference

#include <SegmentTree.h>

+ Collaboration diagram for SegmentTree< INPUT_TYPE, AGG_TYPE >:

Public Member Functions

 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)
 
 ~SegmentTree ()
 
AGG_TYPE query (const IndexPair &query_range) const
 
AGG_TYPE * getAggregatedValues () const
 
SumAndCountPair< AGG_TYPE > * getDerivedAggregatedValues () const
 
size_t getLeafSize () const
 
size_t getTreeSize () const
 
size_t getNumElems () const
 
size_t getLeafDepth () const
 
size_t getTreeFanout () const
 
IndexPair getLeafRange () const
 

Private Member Functions

AGG_TYPE build (int64_t cur_node_idx, size_t cur_node_depth)
 
SumAndCountPair< AGG_TYPE > buildForDerivedAggregate (int64_t cur_node_idx, size_t cur_node_depth)
 
std::vector< AGG_TYPE > prepareChildValuesforAggregation (int64_t parent_idx, size_t cur_node_depth)
 
std::vector< SumAndCountPair
< AGG_TYPE > > 
prepareChildValuesforDerivedAggregate (int64_t parent_idx, size_t cur_node_depth)
 
AGG_TYPE aggregateValue (const std::vector< AGG_TYPE > &vals) const
 
AGG_TYPE aggregateValueViaColumnAccess (int64_t cur_col_idx, size_t num_visits) const
 
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregate (const std::vector< SumAndCountPair< AGG_TYPE >> &vals) const
 
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregateViaColumnAccess (int64_t cur_col_idx, size_t num_visits) 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
 
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
 
std::vector< int64_t > computeChildIndexes (std::vector< int64_t > &child_indexes, int64_t parent_idx, size_t parent_tree_depth) const
 
std::pair< size_t, IndexPairfindMaxTreeHeight (int64_t num_elem, int fan_out)
 

Private Attributes

const INPUT_TYPE * input_col_buf_
 
const SQLTypeInfo input_col_ti_
 
const int32_t * original_input_col_idx_buf_
 
const int64_t * ordered_input_col_idx_buf_
 
int64_t num_elems_
 
size_t fan_out_
 
size_t leaf_size_
 
SqlWindowFunctionKind agg_type_
 
size_t leaf_depth_
 
IndexPair leaf_range_
 
IndexPair null_range_
 
size_t tree_size_
 
SumAndCountPair< AGG_TYPE > * derived_aggregated_
 
AGG_TYPE * aggregated_values_
 
INPUT_TYPE invalid_val_
 
INPUT_TYPE input_type_null_val_
 
AGG_TYPE null_val_
 

Detailed Description

template<typename INPUT_TYPE, typename AGG_TYPE>
class SegmentTree< INPUT_TYPE, AGG_TYPE >

Definition at line 38 of file SegmentTree.h.

Constructor & Destructor Documentation

template<typename INPUT_TYPE , typename AGG_TYPE >
SegmentTree< INPUT_TYPE, AGG_TYPE >::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 
)
inline

Definition at line 40 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::agg_type_, SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_, AVG, SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), CHECK_GT, checked_malloc(), SegmentTree< INPUT_TYPE, AGG_TYPE >::derived_aggregated_, SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_, SegmentTree< INPUT_TYPE, AGG_TYPE >::findMaxTreeHeight(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafDepth(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafRange(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafSize(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getTreeFanout(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getTreeSize(), SegmentTree< INPUT_TYPE, AGG_TYPE >::input_type_null_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_depth_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_size_, MAX, MIN, SegmentTree< INPUT_TYPE, AGG_TYPE >::null_range_, SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_, SegmentTree< INPUT_TYPE, AGG_TYPE >::tree_size_, and VLOG.

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  }
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
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
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
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:579
void * checked_malloc(const size_t size)
Definition: checked_alloc.h:45
const INPUT_TYPE * input_col_buf_
Definition: SegmentTree.h:544
size_t tree_size_
Definition: SegmentTree.h:571
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
std::pair< size_t, IndexPair > findMaxTreeHeight(int64_t num_elem, int fan_out)
Definition: SegmentTree.h:524
IndexPair null_range_
Definition: SegmentTree.h:569
IndexPair leaf_range_
Definition: SegmentTree.h:567
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:576
size_t leaf_depth_
Definition: SegmentTree.h:565
#define VLOG(n)
Definition: Logger.h:316

+ Here is the call graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
SegmentTree< INPUT_TYPE, AGG_TYPE >::~SegmentTree ( )
inline

Definition at line 101 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::agg_type_, SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_, AVG, SegmentTree< INPUT_TYPE, AGG_TYPE >::derived_aggregated_, and SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_.

101  {
102  if (num_elems_ > 0) {
104  free(derived_aggregated_);
105  } else {
106  free(aggregated_values_);
107  }
108  }
109  }
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:574
int64_t num_elems_
Definition: SegmentTree.h:557
SqlWindowFunctionKind agg_type_
Definition: SegmentTree.h:563
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:576

Member Function Documentation

template<typename INPUT_TYPE , typename AGG_TYPE >
AGG_TYPE SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue ( const std::vector< AGG_TYPE > &  vals) const
inlineprivate

Definition at line 278 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::agg_type_, SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, MAX, MIN, and SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::search().

278  {
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  }
SqlWindowFunctionKind agg_type_
Definition: SegmentTree.h:563
AGG_TYPE null_val_
Definition: SegmentTree.h:581
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:579

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
SumAndCountPair<AGG_TYPE> SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregate ( const std::vector< SumAndCountPair< AGG_TYPE >> &  vals) const
inlineprivate

Definition at line 369 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_, and run_benchmark_import::res.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::searchForDerivedAggregate().

370  {
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  }
AGG_TYPE null_val_
Definition: SegmentTree.h:581
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:579

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
SumAndCountPair<AGG_TYPE> SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregateViaColumnAccess ( int64_t  cur_col_idx,
size_t  num_visits 
) const
inlineprivate

Definition at line 388 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_, SumAndCountPair< T >::count, SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_, run_benchmark_import::res, and SumAndCountPair< T >::sum.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::searchForDerivedAggregate().

390  {
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  }
AGG_TYPE null_val_
Definition: SegmentTree.h:581
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:579
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:576

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
AGG_TYPE SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueViaColumnAccess ( int64_t  cur_col_idx,
size_t  num_visits 
) const
inlineprivate

Definition at line 323 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::agg_type_, SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_, SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, MAX, MIN, and SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::search().

323  {
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  }
SqlWindowFunctionKind agg_type_
Definition: SegmentTree.h:563
AGG_TYPE null_val_
Definition: SegmentTree.h:581
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:579
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:576

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
AGG_TYPE SegmentTree< INPUT_TYPE, AGG_TYPE >::build ( int64_t  cur_node_idx,
size_t  cur_node_depth 
)
inlineprivate

Definition at line 169 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::agg_type_, SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_, SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue(), COUNT, SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_buf_, SegmentTree< INPUT_TYPE, AGG_TYPE >::input_type_null_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_, SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_, SegmentTree< INPUT_TYPE, AGG_TYPE >::ordered_input_col_idx_buf_, SegmentTree< INPUT_TYPE, AGG_TYPE >::original_input_col_idx_buf_, and SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforAggregation().

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforAggregation(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

169  {
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  }
const int32_t * original_input_col_idx_buf_
Definition: SegmentTree.h:553
int64_t num_elems_
Definition: SegmentTree.h:557
SqlWindowFunctionKind agg_type_
Definition: SegmentTree.h:563
const int64_t * ordered_input_col_idx_buf_
Definition: SegmentTree.h:555
AGG_TYPE null_val_
Definition: SegmentTree.h:581
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:579
const INPUT_TYPE * input_col_buf_
Definition: SegmentTree.h:544
std::vector< AGG_TYPE > prepareChildValuesforAggregation(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:241
INPUT_TYPE input_type_null_val_
Definition: SegmentTree.h:580
IndexPair leaf_range_
Definition: SegmentTree.h:567
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
Definition: SegmentTree.h:278
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:576

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
SumAndCountPair<AGG_TYPE> SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate ( int64_t  cur_node_idx,
size_t  cur_node_depth 
)
inlineprivate

Definition at line 213 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::derived_aggregated_, SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_buf_, SegmentTree< INPUT_TYPE, AGG_TYPE >::input_type_null_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_, SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_, SegmentTree< INPUT_TYPE, AGG_TYPE >::ordered_input_col_idx_buf_, SegmentTree< INPUT_TYPE, AGG_TYPE >::original_input_col_idx_buf_, and SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforDerivedAggregate().

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforDerivedAggregate(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

214  {
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  }
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
const int64_t * ordered_input_col_idx_buf_
Definition: SegmentTree.h:555
AGG_TYPE null_val_
Definition: SegmentTree.h:581
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:579
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
std::vector< SumAndCountPair< AGG_TYPE > > prepareChildValuesforDerivedAggregate(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:258
INPUT_TYPE input_type_null_val_
Definition: SegmentTree.h:580
IndexPair leaf_range_
Definition: SegmentTree.h:567

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
std::vector<int64_t> SegmentTree< INPUT_TYPE, AGG_TYPE >::computeChildIndexes ( std::vector< int64_t > &  child_indexes,
int64_t  parent_idx,
size_t  parent_tree_depth 
) const
inlineprivate

Definition at line 506 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::search(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::searchForDerivedAggregate().

508  {
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  }
size_t fan_out_
Definition: SegmentTree.h:559

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
std::pair<size_t, IndexPair> SegmentTree< INPUT_TYPE, AGG_TYPE >::findMaxTreeHeight ( int64_t  num_elem,
int  fan_out 
)
inlineprivate

Definition at line 524 of file SegmentTree.h.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

524  {
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  }
std::pair< int64_t, int64_t > IndexPair

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
AGG_TYPE* SegmentTree< INPUT_TYPE, AGG_TYPE >::getAggregatedValues ( ) const
inline

Definition at line 149 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_.

149 { return aggregated_values_; }
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:576
template<typename INPUT_TYPE , typename AGG_TYPE >
SumAndCountPair<AGG_TYPE>* SegmentTree< INPUT_TYPE, AGG_TYPE >::getDerivedAggregatedValues ( ) const
inline

Definition at line 151 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::derived_aggregated_.

151  {
152  return derived_aggregated_;
153  }
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:574
template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafDepth ( ) const
inline

Definition at line 161 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_depth_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

161 { return leaf_depth_; }
size_t leaf_depth_
Definition: SegmentTree.h:565

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
IndexPair SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafRange ( ) const
inline

Definition at line 165 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

165 { return leaf_range_; }
IndexPair leaf_range_
Definition: SegmentTree.h:567

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafSize ( ) const
inline

Definition at line 155 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_size_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

155 { return leaf_size_; }
size_t leaf_size_
Definition: SegmentTree.h:561

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getNumElems ( ) const
inline

Definition at line 159 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_.

159 { return num_elems_; }
int64_t num_elems_
Definition: SegmentTree.h:557
template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getTreeFanout ( ) const
inline

Definition at line 163 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

163 { return fan_out_; }
size_t fan_out_
Definition: SegmentTree.h:559

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getTreeSize ( ) const
inline

Definition at line 157 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::tree_size_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

157 { return tree_size_; }
size_t tree_size_
Definition: SegmentTree.h:571

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
std::vector<AGG_TYPE> SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforAggregation ( int64_t  parent_idx,
size_t  cur_node_depth 
)
inlineprivate

Definition at line 241 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::build().

242  {
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  }
size_t fan_out_
Definition: SegmentTree.h:559
AGG_TYPE build(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:169

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
std::vector<SumAndCountPair<AGG_TYPE> > SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforDerivedAggregate ( int64_t  parent_idx,
size_t  cur_node_depth 
)
inlineprivate

Definition at line 258 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate().

260  {
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  }
SumAndCountPair< AGG_TYPE > buildForDerivedAggregate(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:213
size_t fan_out_
Definition: SegmentTree.h:559

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
AGG_TYPE SegmentTree< INPUT_TYPE, AGG_TYPE >::query ( const IndexPair query_range) const
inline

Definition at line 112 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::agg_type_, AVG, SumAndCountPair< T >::count, SQLTypeInfo::get_scale(), SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_ti_, SegmentTree< INPUT_TYPE, AGG_TYPE >::input_type_null_val_, SQLTypeInfo::is_decimal(), SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_size_, MAX, MIN, SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_, run_benchmark_import::res, SegmentTree< INPUT_TYPE, AGG_TYPE >::search(), SegmentTree< INPUT_TYPE, AGG_TYPE >::searchForDerivedAggregate(), and SumAndCountPair< T >::sum.

112  {
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  }
SqlWindowFunctionKind agg_type_
Definition: SegmentTree.h:563
HOST DEVICE int get_scale() const
Definition: sqltypes.h:409
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
size_t leaf_size_
Definition: SegmentTree.h:561
AGG_TYPE null_val_
Definition: SegmentTree.h:581
const SQLTypeInfo input_col_ti_
Definition: SegmentTree.h:545
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 input_type_null_val_
Definition: SegmentTree.h:580
bool is_decimal() const
Definition: sqltypes.h:603

+ Here is the call graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
AGG_TYPE SegmentTree< INPUT_TYPE, 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
inlineprivate

Definition at line 410 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_, SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::computeChildIndexes(), SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_, SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_depth_, SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_, and SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::query().

414  {
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  }
AGG_TYPE aggregateValueViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const
Definition: SegmentTree.h:323
int64_t num_elems_
Definition: SegmentTree.h:557
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
AGG_TYPE null_val_
Definition: SegmentTree.h:581
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
INPUT_TYPE invalid_val_
Definition: SegmentTree.h:579
size_t fan_out_
Definition: SegmentTree.h:559
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
Definition: SegmentTree.h:278
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:576
size_t leaf_depth_
Definition: SegmentTree.h:565

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
SumAndCountPair<AGG_TYPE> SegmentTree< INPUT_TYPE, 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
inlineprivate

Definition at line 460 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregateViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::computeChildIndexes(), SegmentTree< INPUT_TYPE, AGG_TYPE >::derived_aggregated_, SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_, SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_depth_, and SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::query().

465  {
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  }
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:574
AGG_TYPE null_val_
Definition: SegmentTree.h:581
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
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
size_t fan_out_
Definition: SegmentTree.h:559
size_t leaf_depth_
Definition: SegmentTree.h:565

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

template<typename INPUT_TYPE , typename AGG_TYPE >
const INPUT_TYPE* SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_buf_
private
template<typename INPUT_TYPE , typename AGG_TYPE >
const SQLTypeInfo SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_ti_
private

Definition at line 545 of file SegmentTree.h.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::query().

template<typename INPUT_TYPE , typename AGG_TYPE >
INPUT_TYPE SegmentTree< INPUT_TYPE, AGG_TYPE >::input_type_null_val_
private
template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_depth_
private
template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_size_
private
template<typename INPUT_TYPE , typename AGG_TYPE >
IndexPair SegmentTree< INPUT_TYPE, AGG_TYPE >::null_range_
private

Definition at line 569 of file SegmentTree.h.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

template<typename INPUT_TYPE , typename AGG_TYPE >
const int64_t* SegmentTree< INPUT_TYPE, AGG_TYPE >::ordered_input_col_idx_buf_
private
template<typename INPUT_TYPE , typename AGG_TYPE >
const int32_t* SegmentTree< INPUT_TYPE, AGG_TYPE >::original_input_col_idx_buf_
private
template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::tree_size_
private

The documentation for this class was generated from the following file: