#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, IndexPair >	findMaxTreeHeight (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.

       : input_col_buf_(!input_col_bufs.empty()
                            ? reinterpret_cast<const INPUT_TYPE*>(input_col_bufs.front())
                            : nullptr)
       , cond_col_buf_(input_col_bufs.size() == 2 ? input_col_bufs[1] : nullptr)
       , input_col_ti_(input_col_ti)
       , original_input_col_idx_buf_(original_input_col_idx_buf)
       , ordered_input_col_idx_buf_(ordered_input_col_idx_buf)
       , num_elems_(num_elems)
       , fan_out_(fan_out)
       , agg_type_(agg_type)
       , is_conditional_agg_(agg_type == SqlWindowFunctionKind::SUM_IF)
       , input_type_null_val_(inline_null_value<INPUT_TYPE>())
       , null_val_(inline_null_value<AGG_TYPE>())
       , invalid_val_(agg_type_ == SqlWindowFunctionKind::MIN
                          ? std::numeric_limits<INPUT_TYPE>::max()
                          : agg_type_ == SqlWindowFunctionKind::MAX
                                ? std::numeric_limits<INPUT_TYPE>::min()
                                : 0) {
     CHECK_GT(num_elems_, (int64_t)0);
     auto max_tree_height_and_leaf_range = findMaxTreeHeight(num_elems_, fan_out_);
     leaf_depth_ = max_tree_height_and_leaf_range.first;
     leaf_range_ = max_tree_height_and_leaf_range.second;
     // the index of the last elem of the leaf level is the same as the tree's size
     tree_size_ = leaf_range_.second;
     leaf_size_ = leaf_range_.second - leaf_range_.first;
     // for derived aggregate, we maintain both "sum" aggregates and element counts
     // to compute the value correctly
     if (agg_type_ == SqlWindowFunctionKind::AVG) {
       derived_aggregated_ = reinterpret_cast<SumAndCountPair<AGG_TYPE>*>(
           checked_malloc(tree_size_ * sizeof(SumAndCountPair<AGG_TYPE>)));
       buildForDerivedAggregate(0, 0);
     } else {
       // we can use an array as a segment tree for the rest of aggregates
       aggregated_values_ =
           reinterpret_cast<AGG_TYPE*>(checked_malloc(tree_size_ * sizeof(AGG_TYPE)));
       agg_type_ == SqlWindowFunctionKind::COUNT
           ? buildForCount(0, 0)
           : is_conditional_agg_ ? buildForCondAgg(0, 0) : build(0, 0);
     }
   }

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

                  {
     if (num_elems_ > 0) {
       if (agg_type_ == SqlWindowFunctionKind::AVG) {
         free(derived_aggregated_);
       } else {
         free(aggregated_values_);
       }
     }
   }

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

                                                                  {
     // todo (yoonmin) : optimize logic for a non-null column
     bool all_nulls = true;
     if (agg_type_ == SqlWindowFunctionKind::MIN) {
       AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
       std::for_each(
           vals.begin(), vals.end(), [&min_val, &all_nulls, this](const AGG_TYPE val) {
             if (val != null_val_ && val != invalid_val_) {
               all_nulls = false;
               min_val = std::min(min_val, val);
             }
           });
       if (all_nulls) {
         min_val = null_val_;
       }
       return min_val;
     } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
       AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
       std::for_each(
           vals.begin(), vals.end(), [&max_val, &all_nulls, this](const AGG_TYPE val) {
             if (val != null_val_ && val != invalid_val_) {
               all_nulls = false;
               max_val = std::max(max_val, val);
             }
           });
       if (all_nulls) {
         max_val = null_val_;
       }
       return max_val;
     } else {
       AGG_TYPE agg_val = 0;
       std::for_each(
           vals.begin(), vals.end(), [&agg_val, &all_nulls, this](const AGG_TYPE val) {
             if (val != null_val_ && val != invalid_val_) {
               agg_val += val;
               all_nulls = false;
             }
           });
       if (all_nulls) {
         agg_val = null_val_;
       }
       return agg_val;
     }
   }

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

                                                               {
     SumAndCountPair<AGG_TYPE> res{0, 0};
     bool all_nulls = true;
     std::for_each(vals.begin(),
                   vals.end(),
                   [&res, &all_nulls, this](const SumAndCountPair<AGG_TYPE>& pair) {
                     if (pair.sum != null_val_ && pair.sum != invalid_val_) {
                       res.sum += pair.sum;
                       res.count += pair.count;
                       all_nulls = false;
                     }
                   });
     if (all_nulls) {
       return {null_val_, 0};
     }
     return res;
   }

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

                                {
     SumAndCountPair<AGG_TYPE> res{0, 0};
     bool all_nulls = true;
     auto end_idx = cur_col_idx + num_visits;
     for (size_t i = cur_col_idx; i < end_idx; ++i) {
       const SumAndCountPair<AGG_TYPE> cur_pair_val = aggregated_values_[i];
       if (cur_pair_val.sum != null_val_ && cur_pair_val.sum != invalid_val_) {
         res.sum += cur_pair_val.sum;
         res.count += cur_pair_val.count;
         all_nulls = false;
       }
     }
     if (all_nulls) {
       return {null_val_, 0};
     }
     return res;
   }

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

                                                                                        {
     // todo (yoonmin) : optimize logic for a non-null column
     bool all_nulls = true;
     auto end_idx = cur_col_idx + num_visits;
     if (agg_type_ == SqlWindowFunctionKind::MIN) {
       AGG_TYPE min_val = std::numeric_limits<AGG_TYPE>::max();
       for (size_t i = cur_col_idx; i < end_idx; ++i) {
         AGG_TYPE val = aggregated_values_[i];
         if (val != null_val_ && val != invalid_val_) {
           all_nulls = false;
           min_val = std::min(min_val, val);
         }
       }
       if (all_nulls) {
         min_val = null_val_;
       }
       return min_val;
     } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
       AGG_TYPE max_val = std::numeric_limits<AGG_TYPE>::min();
       for (size_t i = cur_col_idx; i < end_idx; ++i) {
         AGG_TYPE val = aggregated_values_[i];
         if (val != null_val_ && val != invalid_val_) {
           all_nulls = false;
           max_val = std::max(max_val, val);
         }
       }
       if (all_nulls) {
         max_val = null_val_;
       }
       return max_val;
     } else {
       AGG_TYPE agg_val = 0;
       for (size_t i = cur_col_idx; i < end_idx; ++i) {
         AGG_TYPE val = aggregated_values_[i];
         if (val != null_val_ && val != invalid_val_) {
           agg_val += val;
           all_nulls = false;
         }
       }
       if (all_nulls) {
         agg_val = null_val_;
       }
       return agg_val;
     }
   }

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.

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

                                                               {
     if (cur_node_idx >= leaf_range_.first && cur_node_idx < leaf_range_.second) {
       // arrive at leaf level, so try to put a corresponding input column value
       int64_t input_col_idx = cur_node_idx - leaf_range_.first;
       if (input_col_idx >= num_elems_) {
         // fill an invalid value
         aggregated_values_[cur_node_idx] = invalid_val_;
         return invalid_val_;
       }
       // try to get the current row's column value
       const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
       const auto refined_input_col_idx =
           original_input_col_idx_buf_[input_col_idx_ordered];
       aggregated_values_[cur_node_idx] =
           fetch_col_for_non_cond_agg(refined_input_col_idx);
       // return the current value to fill a parent node
       return aggregated_values_[cur_node_idx];
     }
 
     // when reaching here, we need to take care of a node having child nodes,
     // and we compute an aggregated value from its child nodes
     std::vector<AGG_TYPE> child_vals =
         prepareChildValuesforAggregation(cur_node_idx, cur_node_depth);
 
     // compute the new aggregated value
     aggregated_values_[cur_node_idx] = aggregateValue(child_vals);
 
     // return the value for the upper-level aggregation
     return aggregated_values_[cur_node_idx];
   }

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.

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

                                                                         {
     if (cur_node_idx >= leaf_range_.first && cur_node_idx < leaf_range_.second) {
       // arrive at leaf level, so try to put a corresponding input column value
       int64_t input_col_idx = cur_node_idx - leaf_range_.first;
       if (input_col_idx >= num_elems_) {
         // fill an invalid value
         aggregated_values_[cur_node_idx] = invalid_val_;
         return invalid_val_;
       }
       // try to get the current row's column value
       const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
       const auto refined_input_col_idx =
           original_input_col_idx_buf_[input_col_idx_ordered];
       aggregated_values_[cur_node_idx] = fetch_col_for_cond_agg(refined_input_col_idx);
       // return the current value to fill a parent node
       return aggregated_values_[cur_node_idx];
     }
 
     // when reaching here, we need to take care of a node having child nodes,
     // and we compute an aggregated value from its child nodes
     std::vector<AGG_TYPE> child_vals =
         prepareChildValuesforConditionalAggregation(cur_node_idx, cur_node_depth);
 
     // compute the new aggregated value
     aggregated_values_[cur_node_idx] = aggregateValue(child_vals);
 
     // return the value for the upper-level aggregation
     return aggregated_values_[cur_node_idx];
   }

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.

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

                                                                       {
     if (cur_node_idx >= leaf_range_.first && cur_node_idx <= leaf_range_.second) {
       // arrive at leafs, so try to put a corresponding input column value
       int64_t input_col_idx = cur_node_idx - leaf_range_.first;
       if (input_col_idx >= num_elems_) {
         // fill an invalid value
         aggregated_values_[cur_node_idx] = invalid_val_;
         return invalid_val_;
       }
       // try to get the current row's column value
       const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
       const auto refined_input_col_idx =
           original_input_col_idx_buf_[input_col_idx_ordered];
       aggregated_values_[cur_node_idx] = fetch_col_for_count(refined_input_col_idx);
       // return the current value to fill a parent node
       return aggregated_values_[cur_node_idx];
     }
 
     // when reaching here, we need to take care of a node having child nodes,
     // and we compute an aggregated value from its child nodes
     std::vector<AGG_TYPE> child_vals =
         prepareChildValuesforAggregationForCount(cur_node_idx, cur_node_depth);
 
     // compute the new aggregated value
     aggregated_values_[cur_node_idx] = aggregateValue(child_vals);
 
     // return the value for the upper-level aggregation
     return aggregated_values_[cur_node_idx];
   }

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.

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

                                                                             {
     if (cur_node_idx >= leaf_range_.first && cur_node_idx <= leaf_range_.second) {
       int64_t input_col_idx = cur_node_idx - leaf_range_.first;
       if (input_col_idx >= num_elems_) {
         derived_aggregated_[cur_node_idx] = {invalid_val_, 0};
       } else {
         const auto input_col_idx_ordered = ordered_input_col_idx_buf_[input_col_idx];
         const auto refined_input_col_idx =
             original_input_col_idx_buf_[input_col_idx_ordered];
         auto col_val = input_col_buf_[refined_input_col_idx];
         if (col_val != input_type_null_val_) {
           derived_aggregated_[cur_node_idx] = {col_val, 1};
         } else {
           derived_aggregated_[cur_node_idx] = {null_val_, 0};
         }
       }
       return derived_aggregated_[cur_node_idx];
     }
 
     std::vector<SumAndCountPair<AGG_TYPE>> child_vals =
         prepareChildValuesforDerivedAggregate(cur_node_idx, cur_node_depth);
 
     derived_aggregated_[cur_node_idx] = aggregateValueForDerivedAggregate(child_vals);
     return derived_aggregated_[cur_node_idx];
   }

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

                                                                            {
     if (parent_tree_depth == 0) {
       for (size_t i = 0; i < fan_out_; ++i) {
         child_indexes[i] = i + 1;
       }
     } else {
       int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
       for (size_t i = 0; i < fan_out_; ++i) {
         child_indexes[i] = cur_depth_start_offset + i;
       }
     }
     return child_indexes;
   }

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

                                                            {
     AGG_TYPE res{null_val_};
     if (cond_col_buf_[idx] == 1) {
       auto const col_val = input_col_buf_[idx];
       res = col_val != input_type_null_val_ ? col_val : null_val_;
     }
     return res;
   }

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

                                                         {
     return input_col_buf_ && input_col_buf_[idx] == input_type_null_val_ ? null_val_ : 1;
   }

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

                                                                {
     auto const col_val = input_col_buf_[idx];
     return col_val != input_type_null_val_ ? col_val : null_val_;
   }

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

                                                                               {
     if (num_elem <= 0) {
       return std::make_pair(0, std::make_pair(0, 0));
     }
     int64_t cur_level_start_offset = 0;
     size_t depth = 0;
     IndexPair index_pair = std::make_pair(0, 0);
     while (true) {
       size_t maximum_node_at_next_level = pow(fan_out, depth);
       if (num_elem < maximum_node_at_next_level) {
         index_pair = std::make_pair(cur_level_start_offset,
                                     cur_level_start_offset + maximum_node_at_next_level);
         return std::make_pair(depth, index_pair);
       }
       depth++;
       cur_level_start_offset += maximum_node_at_next_level;
     }
   }

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_; }

SegmentTree::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_.

                                                                 {
     return derived_aggregated_;
   }

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_; }

SegmentTree::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_; }

SegmentTree::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_; }

SegmentTree::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_; }

SegmentTree::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_; }

SegmentTree::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_; }

SegmentTree::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().

                                                                                 {
     std::vector<AGG_TYPE> child_vals(fan_out_);
     size_t next_node_depth = cur_node_depth + 1;
     if (cur_node_depth == 0) {
       for (size_t i = 0; i < fan_out_; ++i) {
         child_vals[i] = build(i + 1, next_node_depth);
       }
     } else {
       int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
       for (size_t i = 0; i < fan_out_; ++i) {
         child_vals[i] = build(cur_depth_start_offset + i, next_node_depth);
       }
     }
     return child_vals;
   }

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

                                                                                         {
     std::vector<AGG_TYPE> child_vals(fan_out_);
     size_t next_node_depth = cur_node_depth + 1;
     if (cur_node_depth == 0) {
       for (size_t i = 0; i < fan_out_; ++i) {
         child_vals[i] = buildForCount(i + 1, next_node_depth);
       }
     } else {
       int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
       for (size_t i = 0; i < fan_out_; ++i) {
         child_vals[i] = buildForCount(cur_depth_start_offset + i, next_node_depth);
       }
     }
     return child_vals;
   }

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

                              {
     std::vector<AGG_TYPE> child_vals(fan_out_);
     size_t next_node_depth = cur_node_depth + 1;
     if (cur_node_depth == 0) {
       for (size_t i = 0; i < fan_out_; ++i) {
         child_vals[i] = buildForCondAgg(i + 1, next_node_depth);
       }
     } else {
       int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
       for (size_t i = 0; i < fan_out_; ++i) {
         child_vals[i] = buildForCondAgg(cur_depth_start_offset + i, next_node_depth);
       }
     }
     return child_vals;
   }

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

                              {
     std::vector<SumAndCountPair<AGG_TYPE>> child_vals(fan_out_);
     size_t next_node_depth = cur_node_depth + 1;
     if (cur_node_depth == 0) {
       for (size_t i = 0; i < fan_out_; ++i) {
         child_vals[i] = buildForDerivedAggregate(i + 1, next_node_depth);
       }
     } else {
       int64_t cur_depth_start_offset = parent_idx * fan_out_ + 1;
       for (size_t i = 0; i < fan_out_; ++i) {
         child_vals[i] =
             buildForDerivedAggregate(cur_depth_start_offset + i, next_node_depth);
       }
     }
     return child_vals;
   }

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.

                                                      {
     if (query_range.first > query_range.second || query_range.first < 0 ||
         query_range.second > leaf_size_) {
       return null_val_;
     }
     // todo (yoonmin) : support more derived aggregate functions
     if (agg_type_ == SqlWindowFunctionKind::AVG) {
       SumAndCountPair<AGG_TYPE> sum_and_count_pair =
           searchForDerivedAggregate(query_range, 0, 0, 0, leaf_size_);
       if (sum_and_count_pair.sum == null_val_) {
         return null_val_;
       } else if (sum_and_count_pair.count == 0) {
         return 0;
       } else {
         if (input_col_ti_.is_decimal()) {
           return (static_cast<double>(sum_and_count_pair.sum) /
                   pow(10, input_col_ti_.get_scale())) /
                  sum_and_count_pair.count;
         } else {
           return sum_and_count_pair.sum / sum_and_count_pair.count;
         }
       }
     } else {
       const auto res = search(query_range, 0, 0, 0, leaf_size_);
       if (res == null_val_) {
         switch (agg_type_) {
           case SqlWindowFunctionKind::MIN:
           case SqlWindowFunctionKind::MAX:
             return input_type_null_val_;
           default:
             return null_val_;
         }
       }
       return res;
     }
   }

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.

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

                                                       {
     if (num_elems_ <= 0) {
       return null_val_;
     }
     if (search_range_end_idx < query_range.first ||
         query_range.second < search_range_start_idx) {
       // completely out-of-bound
       return invalid_val_;
     } else if (query_range.first <= search_range_start_idx &&
                search_range_end_idx <= query_range.second) {
       // perfectly fitted in a range of the current node
       return aggregated_values_[cur_node_idx];
     } else {
       // this node is partially within left and right indexes
       if (cur_node_depth == leaf_depth_) {
         // we already reach the leaf level, so do not need to proceed to the next level
         // and so aggregate the value in the range by using a simple loop
         size_t num_visits = query_range.second - search_range_start_idx + 1;
         return aggregateValueViaColumnAccess(
             cur_node_idx, num_visits, null_val_, invalid_val_);
       } else {
         // find aggregated value from child nodes
         int64_t pivot_idx = search_range_start_idx +
                             ((search_range_end_idx - search_range_start_idx) / fan_out_);
         int64_t child_search_start_idx = search_range_start_idx;
         int64_t child_search_end_idx = pivot_idx;
         std::vector<size_t> child_indexes(fan_out_);
         computeChildIndexes(child_indexes, cur_node_idx, cur_node_depth);
         std::vector<AGG_TYPE> child_vals(fan_out_);
         for (size_t i = 0; i < child_indexes.size(); ++i) {
           child_vals[i] = search(query_range,
                                  child_indexes[i],
                                  cur_node_depth + 1,
                                  child_search_start_idx,
                                  child_search_end_idx);
           child_search_start_idx = child_search_end_idx + 1;
           child_search_end_idx = child_search_start_idx + pivot_idx;
           if (child_search_end_idx > search_range_end_idx) {
             child_search_end_idx = search_range_end_idx;
           }
         }
         return aggregateValue(child_vals);
       }
     }
   }

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

                                           {
     if (search_range_end_idx < query_range.first ||
         query_range.second < search_range_start_idx) {
       return {invalid_val_, 0};
     } else if (query_range.first <= search_range_start_idx &&
                search_range_end_idx <= query_range.second) {
       return derived_aggregated_[cur_node_idx];
     } else {
       if (cur_node_depth == leaf_depth_) {
         size_t num_visits = query_range.second - search_range_start_idx + 1;
         return aggregateValueForDerivedAggregateViaColumnAccess(
             cur_node_idx, num_visits, null_val_, invalid_val_);
       } else {
         // find aggregated value from child nodes
         std::vector<int64_t> child_indexes(fan_out_);
         computeChildIndexes(child_indexes, cur_node_idx, cur_node_depth);
         std::vector<SumAndCountPair<AGG_TYPE>> child_vals(fan_out_, {invalid_val_, 0});
         int64_t pivot_idx = search_range_start_idx +
                             ((search_range_end_idx - search_range_start_idx) / fan_out_);
         int64_t child_search_start_idx = search_range_start_idx;
         int64_t child_search_end_idx = pivot_idx;
         for (size_t i = 0; i < child_indexes.size(); ++i) {
           child_vals[i] = searchForDerivedAggregate(query_range,
                                                     child_indexes[i],
                                                     cur_node_depth + 1,
                                                     child_search_start_idx,
                                                     child_search_end_idx);
           child_search_start_idx = child_search_end_idx + 1;
           child_search_end_idx = child_search_start_idx + pivot_idx;
           if (child_search_end_idx > search_range_end_idx) {
             child_search_end_idx = search_range_end_idx;
           }
         }
         return aggregateValueForDerivedAggregate(child_vals);
       }
     }
   }

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 >

SqlWindowFunctionKind const SegmentTree< INPUT_TYPE, AGG_TYPE >::agg_type_

private

Definition at line 654 of file SegmentTree.h.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValue(), SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregateValueViaColumnAccess(), SegmentTree< INPUT_TYPE, AGG_TYPE >::query(), SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::~SegmentTree().

template<typename INPUT_TYPE , typename AGG_TYPE >

AGG_TYPE* SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_

private

Definition at line 672 of file SegmentTree.h.

template<typename INPUT_TYPE , typename AGG_TYPE >

const int8_t* const SegmentTree< INPUT_TYPE, AGG_TYPE >::cond_col_buf_

private

Definition at line 637 of file SegmentTree.h.

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

template<typename INPUT_TYPE , typename AGG_TYPE >

SumAndCountPair<AGG_TYPE>* SegmentTree< INPUT_TYPE, AGG_TYPE >::derived_aggregated_

private

Definition at line 670 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().

template<typename INPUT_TYPE , typename AGG_TYPE >

size_t const SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_

private

Definition at line 652 of file SegmentTree.h.

template<typename INPUT_TYPE , typename AGG_TYPE >

const INPUT_TYPE* const SegmentTree< INPUT_TYPE, AGG_TYPE >::input_col_buf_

private

Definition at line 635 of file SegmentTree.h.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_cond_agg(), SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_count(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_non_cond_agg().

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 >

INPUT_TYPE const SegmentTree< INPUT_TYPE, AGG_TYPE >::input_type_null_val_

private

Definition at line 656 of file SegmentTree.h.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_cond_agg(), SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_count(), SegmentTree< INPUT_TYPE, AGG_TYPE >::fetch_col_for_non_cond_agg(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::query().

template<typename INPUT_TYPE , typename AGG_TYPE >

INPUT_TYPE const SegmentTree< INPUT_TYPE, AGG_TYPE >::invalid_val_

private

Definition at line 659 of file SegmentTree.h.

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

Definition at line 663 of file SegmentTree.h.

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

template<typename INPUT_TYPE , typename AGG_TYPE >

IndexPair SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_

private

Definition at line 665 of file SegmentTree.h.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForCondAgg(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForCount(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForDerivedAggregate(), SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafRange(), and SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree().

template<typename INPUT_TYPE , typename AGG_TYPE >

size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_size_

private

Definition at line 661 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().

template<typename INPUT_TYPE , typename AGG_TYPE >

AGG_TYPE const SegmentTree< INPUT_TYPE, AGG_TYPE >::null_val_

private

Definition at line 657 of file SegmentTree.h.

template<typename INPUT_TYPE , typename AGG_TYPE >

int64_t const SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_

private

Definition at line 650 of file SegmentTree.h.

Referenced by SegmentTree< INPUT_TYPE, AGG_TYPE >::build(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForCondAgg(), SegmentTree< INPUT_TYPE, AGG_TYPE >::buildForCount(), 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().

template<typename INPUT_TYPE , typename AGG_TYPE >

const int64_t* const SegmentTree< INPUT_TYPE, AGG_TYPE >::ordered_input_col_idx_buf_

private

Definition at line 648 of file SegmentTree.h.

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 >::buildForDerivedAggregate().

template<typename INPUT_TYPE , typename AGG_TYPE >

const int32_t* const SegmentTree< INPUT_TYPE, AGG_TYPE >::original_input_col_idx_buf_

private

Definition at line 646 of file SegmentTree.h.

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 >::buildForDerivedAggregate().

template<typename INPUT_TYPE , typename AGG_TYPE >

size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::tree_size_

private

Definition at line 667 of file SegmentTree.h.

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

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

/home/jenkins-slave/workspace/core-os-doxygen/QueryEngine/Utils/SegmentTree.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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