#include <SegmentTree.h>

Collaboration diagram for SegmentTree< INPUT_TYPE, AGG_TYPE >:

Public Member Functions
	SegmentTree (const int8_t input_col_buf, const SQLTypeInfo &input_col_ti, const int32_t original_input_col_idx_buf, const int64_t *ordered_input_col_idx_buf, IndexPair order_col_null_range, int64_t num_elems, SqlWindowFunctionKind agg_type, size_t fan_out)

	~SegmentTree ()

AGG_TYPE	query (const IndexPair &query_range) const

AGG_TYPE *	getAggregatedValues () const

SumAndCountPair< AGG_TYPE > *	getDerivedAggregatedValues () const

size_t	getLeafSize () const

size_t	getTreeSize () const

size_t	getNumElems () const

size_t	getLeafDepth () const

size_t	getTreeFanout () const

IndexPair	getLeafRange () const

Private Member Functions
AGG_TYPE	build (int64_t cur_node_idx, size_t cur_node_depth)

SumAndCountPair< AGG_TYPE >	buildForDerivedAggregate (int64_t cur_node_idx, size_t cur_node_depth)

std::vector< AGG_TYPE >	prepareChildValuesforAggregation (int64_t parent_idx, size_t cur_node_depth)

std::vector< SumAndCountPair < AGG_TYPE > >	prepareChildValuesforDerivedAggregate (int64_t parent_idx, size_t cur_node_depth)

AGG_TYPE	aggregateValue (const std::vector< AGG_TYPE > &vals) const

AGG_TYPE	aggregateValueViaColumnAccess (int64_t cur_col_idx, size_t num_visits) const

SumAndCountPair< AGG_TYPE >	aggregateValueForDerivedAggregate (const std::vector< SumAndCountPair< AGG_TYPE >> &vals) const

SumAndCountPair< AGG_TYPE >	aggregateValueForDerivedAggregateViaColumnAccess (int64_t cur_col_idx, size_t num_visits) const

AGG_TYPE	search (const IndexPair &query_range, int64_t cur_node_idx, size_t cur_node_depth, int64_t search_range_start_idx, int64_t search_range_end_idx) const

SumAndCountPair< AGG_TYPE >	searchForDerivedAggregate (const IndexPair &query_range, int64_t cur_node_idx, size_t cur_node_depth, int64_t search_range_start_idx, int64_t search_range_end_idx) const

std::vector< int64_t >	computeChildIndexes (std::vector< int64_t > &child_indexes, int64_t parent_idx, size_t parent_tree_depth) const

std::pair< size_t, 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_

Detailed Description

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

Definition at line 38 of file SegmentTree.h.

Constructor & Destructor Documentation

template<typename INPUT_TYPE , typename AGG_TYPE >

SegmentTree< INPUT_TYPE, AGG_TYPE >::SegmentTree	(	const int8_t *	input_col_buf,
		const SQLTypeInfo &	input_col_ti,
		const int32_t *	original_input_col_idx_buf,
		const int64_t *	ordered_input_col_idx_buf,
		IndexPair	order_col_null_range,
		int64_t	num_elems,
		SqlWindowFunctionKind	agg_type,
		size_t	fan_out
	)

inline

Definition at line 40 of file SegmentTree.h.

       : input_col_buf_(reinterpret_cast<const INPUT_TYPE*>(input_col_buf))
       , 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)
       , null_range_(order_col_null_range) {
     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;
     // since the input column is ordered we can know the exact range of null values
     // and can use this information to elaborate a query range to do better finding
     // of lower and upper bounds while computing the aggregate operation
     null_range_.first = std::numeric_limits<int64_t>::max();
     null_range_.second = std::numeric_limits<int64_t>::min();
     // 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;
     // invalid_val is required to fill an empty node for a correct aggregation
     if (agg_type_ == SqlWindowFunctionKind::MIN) {
       invalid_val_ = std::numeric_limits<INPUT_TYPE>::max();
     } else if (agg_type_ == SqlWindowFunctionKind::MAX) {
       invalid_val_ = std::numeric_limits<INPUT_TYPE>::min();
     } else {
       invalid_val_ = 0;
     }
     // sometimes, we need to fill the null value to internal nodes
     null_val_ = inline_null_value<AGG_TYPE>();
     // and we also need to know the null value of the input column type
     // to recognize it while building a segment tree
     input_type_null_val_ = inline_null_value<INPUT_TYPE>();
     // 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)));
       build(0, 0);
     }
 #ifndef __CUDACC__
     VLOG(1) << "tree size: " << getTreeSize() << ", tree fanout: " << getTreeFanout()
             << ", leaf depth: " << getLeafDepth()
             << ", leaf range: " << getLeafRange().first << " ~ " << getLeafRange().second
             << ", leaf size: " << getLeafSize();
 #endif
   }

Here is the call graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >

SegmentTree< INPUT_TYPE, AGG_TYPE >::~SegmentTree ( )

inline

Definition at line 101 of file SegmentTree.h.

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

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

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

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

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

                                                                                        {
     // 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 169 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 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];
       const auto col_val = input_col_buf_[refined_input_col_idx];
       if (col_val != input_type_null_val_) {
         if (agg_type_ == SqlWindowFunctionKind::COUNT) {
           // for count aggregation, we fill '1` instead of the col_val
           aggregated_values_[cur_node_idx] = 1;
         } else {
           // otherwise, we fill the `col_val` to leaf nodes
           aggregated_values_[cur_node_idx] = col_val;
         }
       } else {
         // fill null val
         aggregated_values_[cur_node_idx] = null_val_;
       }
       // 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 >

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

inlineprivate

Definition at line 213 of file SegmentTree.h.

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

                                                                            {
     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 >

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

inlineprivate

Definition at line 524 of file SegmentTree.h.

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

                                                                               {
     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 149 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::aggregated_values_.

149 { return aggregated_values_; }

SegmentTree::aggregated_values_

AGG_TYPE * aggregated_values_

Definition: SegmentTree.h:576

template<typename INPUT_TYPE , typename AGG_TYPE >

SumAndCountPair<AGG_TYPE>* SegmentTree< INPUT_TYPE, AGG_TYPE >::getDerivedAggregatedValues ( ) const

inline

Definition at line 151 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::derived_aggregated_.

                                                                 {
     return derived_aggregated_;
   }

template<typename INPUT_TYPE , typename AGG_TYPE >

size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getLeafDepth ( ) const

inline

Definition at line 161 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_depth_.

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

161 { return leaf_depth_; }

SegmentTree::leaf_depth_

size_t leaf_depth_

Definition: SegmentTree.h:565

Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >

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

inline

Definition at line 165 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_range_.

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

165 { return leaf_range_; }

SegmentTree::leaf_range_

IndexPair leaf_range_

Definition: SegmentTree.h:567

Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >

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

inline

Definition at line 155 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::leaf_size_.

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

155 { return leaf_size_; }

SegmentTree::leaf_size_

size_t leaf_size_

Definition: SegmentTree.h:561

Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >

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

inline

Definition at line 159 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::num_elems_.

159 { return num_elems_; }

SegmentTree::num_elems_

int64_t num_elems_

Definition: SegmentTree.h:557

template<typename INPUT_TYPE , typename AGG_TYPE >

size_t SegmentTree< INPUT_TYPE, AGG_TYPE >::getTreeFanout ( ) const

inline

Definition at line 163 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::fan_out_.

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

163 { return fan_out_; }

SegmentTree::fan_out_

size_t fan_out_

Definition: SegmentTree.h:559

Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >

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

inline

Definition at line 157 of file SegmentTree.h.

References SegmentTree< INPUT_TYPE, AGG_TYPE >::tree_size_.

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

157 { return tree_size_; }

SegmentTree::tree_size_

size_t tree_size_

Definition: SegmentTree.h:571

Here is the caller graph for this function:

template<typename INPUT_TYPE , typename AGG_TYPE >

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

inlineprivate

Definition at line 241 of file SegmentTree.h.

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

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

                                                                                 {
     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<SumAndCountPair<AGG_TYPE> > SegmentTree< INPUT_TYPE, AGG_TYPE >::prepareChildValuesforDerivedAggregate	(	int64_t	parent_idx,
		size_t	cur_node_depth
	)

inlineprivate

Definition at line 258 of file SegmentTree.h.

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

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

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

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

                                           {
     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);
       }
     }
   }