1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/execution/window_segment_tree.hpp
5//
6//
7//===----------------------------------------------------------------------===//
8
9#pragma once
10
11#include "duckdb/common/types/data_chunk.hpp"
12#include "duckdb/execution/physical_operator.hpp"
13#include "duckdb/function/aggregate_function.hpp"
14#include "duckdb/common/enums/window_aggregation_mode.hpp"
15#include "duckdb/execution/operator/aggregate/aggregate_object.hpp"
16
17namespace duckdb {
18
19class WindowAggregateState {
20public:
21 WindowAggregateState(AggregateObject aggr, const LogicalType &result_type_p);
22 virtual ~WindowAggregateState();
23
24 virtual void Sink(DataChunk &payload_chunk, SelectionVector *filter_sel, idx_t filtered);
25 virtual void Finalize();
26 virtual void Compute(Vector &result, idx_t rid, idx_t start, idx_t end);
27
28protected:
29 void AggregateInit();
30 void AggegateFinal(Vector &result, idx_t rid);
31
32 AggregateObject aggr;
33 //! The result type of the window function
34 LogicalType result_type;
35
36 //! Data pointer that contains a single state, used for intermediate window segment aggregation
37 vector<data_t> state;
38 //! Reused result state container for the window functions
39 Vector statev;
40 //! A vector of pointers to "state", used for intermediate window segment aggregation
41 Vector statep;
42 //! Input data chunk, used for intermediate window segment aggregation
43 DataChunk inputs;
44};
45
46class WindowConstantAggregate : public WindowAggregateState {
47public:
48 static bool IsConstantAggregate(const BoundWindowExpression &wexpr);
49
50 WindowConstantAggregate(AggregateObject aggr, const LogicalType &result_type_p, const ValidityMask &partition_mask,
51 const idx_t count);
52 ~WindowConstantAggregate() override {
53 }
54
55 void Sink(DataChunk &payload_chunk, SelectionVector *filter_sel, idx_t filtered) override;
56 void Finalize() override;
57 void Compute(Vector &result, idx_t rid, idx_t start, idx_t end) override;
58
59private:
60 //! Partition starts
61 vector<idx_t> partition_offsets;
62 //! Aggregate results
63 unique_ptr<Vector> results;
64 //! The current result partition being built/read
65 idx_t partition;
66 //! The current input row being built/read
67 idx_t row;
68};
69
70class WindowSegmentTree {
71public:
72 using FrameBounds = std::pair<idx_t, idx_t>;
73
74 WindowSegmentTree(AggregateObject aggr, const LogicalType &result_type, DataChunk *input,
75 const ValidityMask &filter_mask, WindowAggregationMode mode);
76 ~WindowSegmentTree();
77
78 //! First row contains the result.
79 void Compute(Vector &result, idx_t rid, idx_t start, idx_t end);
80
81private:
82 void ConstructTree();
83 void ExtractFrame(idx_t begin, idx_t end);
84 void WindowSegmentValue(idx_t l_idx, idx_t begin, idx_t end);
85 void AggregateInit();
86 void AggegateFinal(Vector &result, idx_t rid);
87
88 //! Use the window API, if available
89 inline bool UseWindowAPI() const {
90 return mode < WindowAggregationMode::COMBINE;
91 }
92 //! Use the combine API, if available
93 inline bool UseCombineAPI() const {
94 return mode < WindowAggregationMode::SEPARATE;
95 }
96
97 //! The aggregate that the window function is computed over
98 AggregateObject aggr;
99 //! The result type of the window function
100 LogicalType result_type;
101
102 //! Data pointer that contains a single state, used for intermediate window segment aggregation
103 vector<data_t> state;
104 //! Input data chunk, used for intermediate window segment aggregation
105 DataChunk inputs;
106 //! The filtered rows in inputs.
107 SelectionVector filter_sel;
108 //! A vector of pointers to "state", used for intermediate window segment aggregation
109 Vector statep;
110 //! The frame boundaries, used for the window functions
111 FrameBounds frame;
112 //! Reused result state container for the window functions
113 Vector statev;
114
115 //! The actual window segment tree: an array of aggregate states that represent all the intermediate nodes
116 unsafe_unique_array<data_t> levels_flat_native;
117 //! For each level, the starting location in the levels_flat_native array
118 vector<idx_t> levels_flat_start;
119
120 //! The total number of internal nodes of the tree, stored in levels_flat_native
121 idx_t internal_nodes;
122
123 //! The (sorted) input chunk collection on which the tree is built
124 DataChunk *input_ref;
125
126 //! The filtered rows in input_ref.
127 const ValidityMask &filter_mask;
128
129 //! Use the window API, if available
130 WindowAggregationMode mode;
131
132 // TREE_FANOUT needs to cleanly divide STANDARD_VECTOR_SIZE
133 static constexpr idx_t TREE_FANOUT = 64;
134};
135
136} // namespace duckdb
137