OmniSciDB  c1a53651b2
 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 (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)
 
 ~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 fetch_col_for_count (size_t const idx)
 
AGG_TYPE fetch_col_for_non_cond_agg (size_t const idx)
 
AGG_TYPE fetch_col_for_cond_agg (size_t const idx)
 
AGG_TYPE build (int64_t cur_node_idx, size_t cur_node_depth)
 
AGG_TYPE buildForCondAgg (int64_t cur_node_idx, size_t cur_node_depth)
 
AGG_TYPE buildForCount (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< AGG_TYPE > prepareChildValuesforConditionalAggregation (int64_t parent_idx, size_t cur_node_depth)
 
std::vector< AGG_TYPE > prepareChildValuesforAggregationForCount (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 *const input_col_buf_
 
const int8_t *const cond_col_buf_
 
SQLTypeInfo const input_col_ti_
 
const int32_t *const original_input_col_idx_buf_
 
const int64_t *const ordered_input_col_idx_buf_
 
int64_t const num_elems_
 
size_t const fan_out_
 
SqlWindowFunctionKind const agg_type_
 
bool const is_conditional_agg_
 
INPUT_TYPE const input_type_null_val_
 
AGG_TYPE const null_val_
 
INPUT_TYPE const invalid_val_
 
size_t leaf_size_
 
size_t leaf_depth_
 
IndexPair leaf_range_
 
size_t tree_size_
 
SumAndCountPair< AGG_TYPE > * derived_aggregated_
 
AGG_TYPE * aggregated_values_
 

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 ( 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 
)
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 >::buildForCondAgg(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForCount(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), CHECK_GT, checked_malloc(), COUNT, 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 >::is_conditional_agg_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_depth_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_size_, SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_, and SegmentTree< INPUT_TYPE, AGG_TYPE >::tree_size_.

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)
58  , input_type_null_val_(inline_null_value<INPUT_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  }
const int64_t *const ordered_input_col_idx_buf_
Definition: SegmentTree.h:648
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:670
SQLTypeInfo const input_col_ti_
Definition: SegmentTree.h:638
size_t const fan_out_
Definition: SegmentTree.h:652
const INPUT_TYPE *const input_col_buf_
Definition: SegmentTree.h:635
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:305
AGG_TYPE buildForCount(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:235
bool const is_conditional_agg_
Definition: SegmentTree.h:655
void * checked_malloc(const size_t size)
Definition: checked_alloc.h:45
AGG_TYPE buildForCondAgg(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:205
INPUT_TYPE const input_type_null_val_
Definition: SegmentTree.h:656
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
SqlWindowFunctionKind const agg_type_
Definition: SegmentTree.h:654
AGG_TYPE build(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:174
std::pair< size_t, IndexPair > findMaxTreeHeight(int64_t num_elem, int fan_out)
Definition: SegmentTree.h:615
IndexPair leaf_range_
Definition: SegmentTree.h:665
const int8_t *const cond_col_buf_
Definition: SegmentTree.h:637
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

+ 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 88 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_.

88  {
89  if (num_elems_ > 0) {
91  free(derived_aggregated_);
92  } else {
93  free(aggregated_values_);
94  }
95  }
96  }
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:670
SqlWindowFunctionKind const agg_type_
Definition: SegmentTree.h:654
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:672
int64_t const num_elems_
Definition: SegmentTree.h:650

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 369 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(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForCondAgg(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForCount(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::search().

369  {
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  }
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
SqlWindowFunctionKind const agg_type_
Definition: SegmentTree.h:654
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659

+ 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 460 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().

461  {
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  }
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659

+ 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 479 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().

481  {
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  }
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:672
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659

+ 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 414 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().

414  {
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  }
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
SqlWindowFunctionKind const agg_type_
Definition: SegmentTree.h:654
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:672
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659

+ 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 174 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_, SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue(), SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_non_cond_agg(), SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_, 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().

174  {
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  }
const int64_t *const ordered_input_col_idx_buf_
Definition: SegmentTree.h:648
AGG_TYPE fetch_col_for_non_cond_agg(size_t const idx)
Definition: SegmentTree.h:160
const int32_t *const original_input_col_idx_buf_
Definition: SegmentTree.h:646
std::vector< AGG_TYPE > prepareChildValuesforAggregation(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:295
IndexPair leaf_range_
Definition: SegmentTree.h:665
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
Definition: SegmentTree.h:369
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:672
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659
int64_t const num_elems_
Definition: SegmentTree.h:650

+ 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 >::buildForCondAgg ( int64_t  cur_node_idx,
size_t  cur_node_depth 
)
inlineprivate

Definition at line 205 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_, SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue(), SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_cond_agg(), SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_, 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 >::prepareChildValuesforConditionalAggregation().

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

205  {
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  }
const int64_t *const ordered_input_col_idx_buf_
Definition: SegmentTree.h:648
std::vector< AGG_TYPE > prepareChildValuesforConditionalAggregation(int64_t parent_idx, size_t cur_node_depth)
Definition: SegmentTree.h:313
const int32_t *const original_input_col_idx_buf_
Definition: SegmentTree.h:646
AGG_TYPE fetch_col_for_cond_agg(size_t const idx)
Definition: SegmentTree.h:165
IndexPair leaf_range_
Definition: SegmentTree.h:665
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
Definition: SegmentTree.h:369
AGG_TYPE * aggregated_values_
Definition: SegmentTree.h:672
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659
int64_t const num_elems_
Definition: SegmentTree.h:650

+ 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 >::buildForCount ( int64_t  cur_node_idx,
size_t  cur_node_depth 
)
inlineprivate

Definition at line 235 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_, SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue(), SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_count(), SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_, 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 >::prepareChildValuesforAggregationForCount().

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

235  {
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  }
const int64_t *const ordered_input_col_idx_buf_
Definition: SegmentTree.h:648
const int32_t *const original_input_col_idx_buf_
Definition: SegmentTree.h:646
AGG_TYPE fetch_col_for_count(size_t const idx)
Definition: SegmentTree.h:156
IndexPair leaf_range_
Definition: SegmentTree.h:665
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
Definition: SegmentTree.h:369
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
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659
int64_t const num_elems_
Definition: SegmentTree.h:650

+ 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 267 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().

268  {
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  }
const int64_t *const ordered_input_col_idx_buf_
Definition: SegmentTree.h:648
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:670
const INPUT_TYPE *const input_col_buf_
Definition: SegmentTree.h:635
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregate(const std::vector< SumAndCountPair< AGG_TYPE >> &vals) const
Definition: SegmentTree.h:460
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
const int32_t *const original_input_col_idx_buf_
Definition: SegmentTree.h:646
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
IndexPair leaf_range_
Definition: SegmentTree.h:665
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659
int64_t const num_elems_
Definition: SegmentTree.h:650

+ 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 597 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().

599  {
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  }
size_t const fan_out_
Definition: SegmentTree.h:652

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
AGG_TYPE SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_cond_agg ( size_t const  idx)
inlineprivate

Definition at line 165 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::cond_col_buf_, SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_buf_, SegmentTree< INPUT_TYPE, AGG_TYPE >::input_type_null_val_, SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_, and run_benchmark_import::res.

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

165  {
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  }
const INPUT_TYPE *const input_col_buf_
Definition: SegmentTree.h:635
INPUT_TYPE const input_type_null_val_
Definition: SegmentTree.h:656
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
const int8_t *const cond_col_buf_
Definition: SegmentTree.h:637

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
AGG_TYPE SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_count ( size_t const  idx)
inlineprivate

Definition at line 156 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_buf_, SegmentTree< INPUT_TYPE, AGG_TYPE >::input_type_null_val_, and SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_.

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

156  {
158  }
const INPUT_TYPE *const input_col_buf_
Definition: SegmentTree.h:635
INPUT_TYPE const input_type_null_val_
Definition: SegmentTree.h:656
AGG_TYPE const null_val_
Definition: SegmentTree.h:657

+ Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >
AGG_TYPE SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_non_cond_agg ( size_t const  idx)
inlineprivate

Definition at line 160 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_buf_, SegmentTree< INPUT_TYPE, AGG_TYPE >::input_type_null_val_, and SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_.

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

160  {
161  auto const col_val = input_col_buf_[idx];
162  return col_val != input_type_null_val_ ? col_val : null_val_;
163  }
const INPUT_TYPE *const input_col_buf_
Definition: SegmentTree.h:635
INPUT_TYPE const input_type_null_val_
Definition: SegmentTree.h:656
AGG_TYPE const null_val_
Definition: SegmentTree.h:657

+ 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 615 of file SegmentTree.h.

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

615  {
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  }
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 136 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_.

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

Definition at line 138 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::derived_aggregated_.

138  {
139  return derived_aggregated_;
140  }
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:670
template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafDepth ( ) const
inline

Definition at line 148 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_depth_.

148 { return leaf_depth_; }
size_t leaf_depth_
Definition: SegmentTree.h:663
template<typename INPUT_TYPE , typename AGG_TYPE >
IndexPair SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafRange ( ) const
inline

Definition at line 152 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_.

152 { return leaf_range_; }
IndexPair leaf_range_
Definition: SegmentTree.h:665
template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafSize ( ) const
inline

Definition at line 142 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_size_.

142 { return leaf_size_; }
size_t leaf_size_
Definition: SegmentTree.h:661
template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getNumElems ( ) const
inline

Definition at line 146 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_.

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

Definition at line 150 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_.

150 { return fan_out_; }
size_t const fan_out_
Definition: SegmentTree.h:652
template<typename INPUT_TYPE , typename AGG_TYPE >
size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getTreeSize ( ) const
inline

Definition at line 144 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::tree_size_.

144 { return tree_size_; }
size_t tree_size_
Definition: SegmentTree.h:667
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 295 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().

296  {
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  }
size_t const fan_out_
Definition: SegmentTree.h:652
AGG_TYPE build(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:174

+ 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<AGG_TYPE> SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforAggregationForCount ( int64_t  parent_idx,
size_t  cur_node_depth 
)
inlineprivate

Definition at line 332 of file SegmentTree.h.

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

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

333  {
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  }
size_t const fan_out_
Definition: SegmentTree.h:652
AGG_TYPE buildForCount(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:235

+ 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<AGG_TYPE> SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforConditionalAggregation ( int64_t  parent_idx,
size_t  cur_node_depth 
)
inlineprivate

Definition at line 313 of file SegmentTree.h.

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

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

315  {
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  }
size_t const fan_out_
Definition: SegmentTree.h:652
AGG_TYPE buildForCondAgg(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:205

+ 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 349 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().

351  {
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  }
size_t const fan_out_
Definition: SegmentTree.h:652
SumAndCountPair< AGG_TYPE > buildForDerivedAggregate(int64_t cur_node_idx, size_t cur_node_depth)
Definition: SegmentTree.h:267

+ 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 99 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.

99  {
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  }
SQLTypeInfo const input_col_ti_
Definition: SegmentTree.h:638
HOST DEVICE int get_scale() const
Definition: sqltypes.h:386
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
size_t leaf_size_
Definition: SegmentTree.h:661
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
INPUT_TYPE const input_type_null_val_
Definition: SegmentTree.h:656
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
SqlWindowFunctionKind const agg_type_
Definition: SegmentTree.h:654
bool is_decimal() const
Definition: sqltypes.h:583

+ 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 501 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().

505  {
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  }
AGG_TYPE aggregateValueViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const
Definition: SegmentTree.h:414
size_t const fan_out_
Definition: SegmentTree.h:652
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
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
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
AGG_TYPE aggregateValue(const std::vector< AGG_TYPE > &vals) const
Definition: SegmentTree.h:369
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

+ 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 551 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().

556  {
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  }
SumAndCountPair< AGG_TYPE > * derived_aggregated_
Definition: SegmentTree.h:670
size_t const fan_out_
Definition: SegmentTree.h:652
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
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregateViaColumnAccess(int64_t cur_col_idx, size_t num_visits) const
Definition: SegmentTree.h:479
SumAndCountPair< AGG_TYPE > aggregateValueForDerivedAggregate(const std::vector< SumAndCountPair< AGG_TYPE >> &vals) const
Definition: SegmentTree.h:460
AGG_TYPE const null_val_
Definition: SegmentTree.h:657
size_t leaf_depth_
Definition: SegmentTree.h:663
INPUT_TYPE const invalid_val_
Definition: SegmentTree.h:659

+ 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 int8_t* const SegmentTree< INPUT_TYPE, AGG_TYPE >::cond_col_buf_
private
template<typename INPUT_TYPE , typename AGG_TYPE >
SQLTypeInfo const SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_ti_
private

Definition at line 638 of file SegmentTree.h.

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

template<typename INPUT_TYPE , typename AGG_TYPE >
bool const SegmentTree< INPUT_TYPE, AGG_TYPE >::is_conditional_agg_
private

Definition at line 655 of file SegmentTree.h.

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

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 >
const int64_t* const SegmentTree< INPUT_TYPE, AGG_TYPE >::ordered_input_col_idx_buf_
private
template<typename INPUT_TYPE , typename AGG_TYPE >
const int32_t* const 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: