OmniSciDB
c0231cc57d
|
#include <SegmentTree.h>
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, IndexPair > | findMaxTreeHeight (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_ |
Definition at line 38 of file SegmentTree.h.
|
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.
|
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_.
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
inlineprivate |
Definition at line 524 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().
|
inline |
Definition at line 149 of file SegmentTree.h.
References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_.
|
inline |
Definition at line 151 of file SegmentTree.h.
References SegmentTree< INPUT_TYPE, AGG_TYPE >::derived_aggregated_.
|
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().
|
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().
|
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().
|
inline |
Definition at line 159 of file SegmentTree.h.
References SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_.
|
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().
|
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().
|
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().
|
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().
|
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.
|
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().
|
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().
|
private |
Definition at line 563 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), SegmentTree< INPUT_TYPE, AGG_TYPE >::query(), SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::~SegmentTree().
|
private |
Definition at line 576 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregateViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getAggregatedValues(), SegmentTree< INPUT_TYPE, AGG_TYPE >::search(), SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::~SegmentTree().
|
private |
Definition at line 574 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getDerivedAggregatedValues(), SegmentTree< INPUT_TYPE, AGG_TYPE >::searchForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::~SegmentTree().
|
private |
Definition at line 559 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::computeChildIndexes(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getTreeFanout(), SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforAggregation(), SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::search(), SegmentTree< INPUT_TYPE, AGG_TYPE >::searchForDerivedAggregate(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().
|
private |
Definition at line 544 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate().
|
private |
Definition at line 545 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::query().
|
private |
Definition at line 580 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::query(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().
|
private |
Definition at line 579 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregateViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::search(), SegmentTree< INPUT_TYPE, AGG_TYPE >::searchForDerivedAggregate(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().
|
private |
|
private |
|
private |
Definition at line 561 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafSize(), SegmentTree< INPUT_TYPE, AGG_TYPE >::query(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().
|
private |
Definition at line 569 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().
|
private |
Definition at line 581 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueForDerivedAggregateViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::query(), SegmentTree< INPUT_TYPE, AGG_TYPE >::search(), SegmentTree< INPUT_TYPE, AGG_TYPE >::searchForDerivedAggregate(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().
|
private |
Definition at line 557 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getNumElems(), SegmentTree< INPUT_TYPE, AGG_TYPE >::search(), SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::~SegmentTree().
|
private |
Definition at line 555 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate().
|
private |
Definition at line 553 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate().
|
private |
Definition at line 571 of file SegmentTree.h.
Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::getTreeSize(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().