Skip to content

Commit e207589

Browse files
branch-4.1: [fix](window) Recompute sliding frames for floating-point sum/avg #68113 (#68736)
Cherry-picked from #68113 Co-authored-by: Jerry Hu <[email protected]>
1 parent 8cd9bf9 commit e207589

7 files changed

Lines changed: 362 additions & 2 deletions

File tree

‎be/src/exprs/aggregate/aggregate_function_avg.h‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -306,7 +306,10 @@ class AggregateFunctionAvg<T, TResult, Data> final
306306
return std::make_shared<DataTypeFixedLengthObject>();
307307
}
308308

309-
bool supported_incremental_mode() const override { return true; }
309+
// Floating-point accumulation is not exactly invertible: subtracting an outgoing
310+
// value cannot restore the rounding lost when it was added, so a value that has
311+
// left the frame would still distort later results. Recompute such frames instead.
312+
bool supported_incremental_mode() const override { return !std::is_floating_point_v<DataType>; }
310313

311314
void execute_function_with_incremental(int64_t partition_start, int64_t partition_end,
312315
int64_t frame_start, int64_t frame_end,

‎be/src/exprs/aggregate/aggregate_function_sum.h‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@
2323
#include <stddef.h>
2424

2525
#include <memory>
26+
#include <type_traits>
2627
#include <vector>
2728

2829
#include "core/assert_cast.h"
@@ -207,7 +208,12 @@ class AggregateFunctionSum<T, TResult, Data> final
207208
return std::make_shared<DataTypeFixedLengthObject>();
208209
}
209210

210-
bool supported_incremental_mode() const override { return true; }
211+
// Floating-point accumulation is not exactly invertible: subtracting an outgoing
212+
// value cannot restore the rounding lost when it was added, so a value that has
213+
// left the frame would still distort later results. Recompute such frames instead.
214+
bool supported_incremental_mode() const override {
215+
return !std::is_floating_point_v<typename PrimitiveTypeTraits<TResult>::CppType>;
216+
}
211217

212218
NO_SANITIZE_UNDEFINED void execute_function_with_incremental(
213219
int64_t partition_start, int64_t partition_end, int64_t frame_start, int64_t frame_end,

‎be/test/exec/operator/analytic_sink_operator_test.cpp‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -569,6 +569,85 @@ TEST_F(AnalyticSinkOperatorTest, SlidingRowsSumRetainsOutgoingRowDuringEviction)
569569
std::cout << "######### sliding rows sum eviction test end #########" << std::endl;
570570
}
571571

572+
// Floating-point sum/avg cannot be rolled back exactly: once 2^54 + 1 rounds to 2^54,
573+
// removing 2^54 leaves 0 instead of 1. Sliding frames must be recomputed so that a value
574+
// which already left the frame cannot distort the current result.
575+
TEST_F(AnalyticSinkOperatorTest, SlidingRowsDoubleAvgIgnoresRoundingOfOutgoingRow) {
576+
const std::vector<double> data_vals {18014398509481984.0, 1.0, 1.0};
577+
const std::vector<double> expect_vals {18014398509481984.0, 9007199254740992.0, 1.0};
578+
Initialize(data_vals.size());
579+
create_operator(true, 1, "avg", {std::make_shared<DataTypeFloat64>()},
580+
std::make_shared<DataTypeFloat64>());
581+
sink->_agg_expr_ctxs.resize(1);
582+
sink->_agg_expr_ctxs[0] =
583+
MockSlotRef::create_mock_contexts(0, std::make_shared<DataTypeFloat64>());
584+
TAnalyticWindow temp_window;
585+
temp_window.type = TAnalyticWindowType::ROWS;
586+
TAnalyticWindowBoundary window_start;
587+
window_start.type = TAnalyticWindowBoundaryType::PRECEDING;
588+
window_start.__set_rows_offset_value(1);
589+
temp_window.__set_window_start(window_start);
590+
TAnalyticWindowBoundary window_end;
591+
window_end.type = TAnalyticWindowBoundaryType::CURRENT_ROW;
592+
temp_window.__set_window_end(window_end);
593+
create_window_type(true, true, temp_window);
594+
create_local_state();
595+
EXPECT_FALSE(sink_local_state->_support_incremental_calculate);
596+
597+
{
598+
Block block = ColumnHelper::create_block<DataTypeFloat64>(data_vals);
599+
auto st = sink->sink(state.get(), &block, true);
600+
EXPECT_TRUE(st.ok()) << st.msg();
601+
}
602+
{
603+
Block block = ColumnHelper::create_block<DataTypeFloat64>({});
604+
bool eos = false;
605+
auto st = source->get_block(state.get(), &block, &eos);
606+
EXPECT_TRUE(st.ok()) << st.msg();
607+
EXPECT_TRUE(ColumnHelper::block_equal(
608+
block, ColumnHelper::create_block<DataTypeFloat64>(data_vals, expect_vals)))
609+
<< block.dump_data();
610+
}
611+
}
612+
613+
TEST_F(AnalyticSinkOperatorTest, SlidingRowsDoubleSumIgnoresRoundingOfOutgoingRow) {
614+
const std::vector<double> data_vals {18014398509481984.0, 1.0, 1.0};
615+
const std::vector<double> expect_vals {18014398509481984.0, 18014398509481984.0, 2.0};
616+
Initialize(data_vals.size());
617+
create_operator(true, 1, "sum", {std::make_shared<DataTypeFloat64>()},
618+
std::make_shared<DataTypeFloat64>());
619+
sink->_agg_expr_ctxs.resize(1);
620+
sink->_agg_expr_ctxs[0] =
621+
MockSlotRef::create_mock_contexts(0, std::make_shared<DataTypeFloat64>());
622+
TAnalyticWindow temp_window;
623+
temp_window.type = TAnalyticWindowType::ROWS;
624+
TAnalyticWindowBoundary window_start;
625+
window_start.type = TAnalyticWindowBoundaryType::PRECEDING;
626+
window_start.__set_rows_offset_value(1);
627+
temp_window.__set_window_start(window_start);
628+
TAnalyticWindowBoundary window_end;
629+
window_end.type = TAnalyticWindowBoundaryType::CURRENT_ROW;
630+
temp_window.__set_window_end(window_end);
631+
create_window_type(true, true, temp_window);
632+
create_local_state();
633+
EXPECT_FALSE(sink_local_state->_support_incremental_calculate);
634+
635+
{
636+
Block block = ColumnHelper::create_block<DataTypeFloat64>(data_vals);
637+
auto st = sink->sink(state.get(), &block, true);
638+
EXPECT_TRUE(st.ok()) << st.msg();
639+
}
640+
{
641+
Block block = ColumnHelper::create_block<DataTypeFloat64>({});
642+
bool eos = false;
643+
auto st = source->get_block(state.get(), &block, &eos);
644+
EXPECT_TRUE(st.ok()) << st.msg();
645+
EXPECT_TRUE(ColumnHelper::block_equal(
646+
block, ColumnHelper::create_block<DataTypeFloat64>(data_vals, expect_vals)))
647+
<< block.dump_data();
648+
}
649+
}
650+
572651
TEST_F(AnalyticSinkOperatorTest, AggFunction5) {
573652
int batch_size = 2;
574653
Initialize(batch_size);

‎be/test/exprs/aggregate/agg_avg_test.cpp‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,4 +31,15 @@ TEST_F(AggregateFunctionAvgTest, test_int64) {
3131
execute(Block({ColumnHelper::create_column_with_name<DataTypeInt64>({1, 2, 3})}),
3232
ColumnHelper::create_column_with_name<DataTypeFloat64>({2}));
3333
}
34+
35+
TEST_F(AggregateFunctionAvgTest, test_incremental_mode_only_for_exact_sum) {
36+
create_agg("avg", false, {std::make_shared<DataTypeInt64>()},
37+
std::make_shared<DataTypeFloat64>());
38+
EXPECT_TRUE(agg_fn->function()->supported_incremental_mode());
39+
40+
// Floating-point sums are not exactly invertible, so sliding frames must be recomputed.
41+
create_agg("avg", false, {std::make_shared<DataTypeFloat64>()},
42+
std::make_shared<DataTypeFloat64>());
43+
EXPECT_FALSE(agg_fn->function()->supported_incremental_mode());
44+
}
3445
} // namespace doris
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
#include <gtest/gtest.h>
19+
20+
#include "core/data_type/data_type_number.h"
21+
#include "exprs/aggregate/agg_function_test.h"
22+
23+
namespace doris {
24+
25+
struct AggregateFunctionSumTest : public AggregateFunctiontest {};
26+
27+
TEST_F(AggregateFunctionSumTest, test_int64) {
28+
create_agg("sum", false, {std::make_shared<DataTypeInt64>()},
29+
std::make_shared<DataTypeInt64>());
30+
31+
execute(Block({ColumnHelper::create_column_with_name<DataTypeInt64>({1, 2, 3})}),
32+
ColumnHelper::create_column_with_name<DataTypeInt64>({6}));
33+
}
34+
35+
TEST_F(AggregateFunctionSumTest, test_incremental_mode_only_for_exact_sum) {
36+
create_agg("sum", false, {std::make_shared<DataTypeInt64>()},
37+
std::make_shared<DataTypeInt64>());
38+
EXPECT_TRUE(agg_fn->function()->supported_incremental_mode());
39+
40+
// Floating-point sums are not exactly invertible, so sliding frames must be recomputed.
41+
create_agg("sum", false, {std::make_shared<DataTypeFloat64>()},
42+
std::make_shared<DataTypeFloat64>());
43+
EXPECT_FALSE(agg_fn->function()->supported_incremental_mode());
44+
}
45+
} // namespace doris
Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
-- This file is automatically generated. You should know what you did if you want to edit this
2+
-- !avg_double_preceding_1 --
3+
1 1.8014398509481984e+16 1.8014398509481984e+16
4+
2 0.5 9007199254740992
5+
3 0.5 0.5
6+
4 0.5 0.5
7+
8+
-- !sum_double_preceding_1 --
9+
1 1.8014398509481984e+16 1.8014398509481984e+16
10+
2 0.5 1.8014398509481984e+16
11+
3 0.5 1
12+
4 0.5 1
13+
14+
-- !avg_sum_float_preceding_1 --
15+
1 1.80143985E16 1.8014398509481984e+16 1.8014398509481984e+16
16+
2 0.5 9007199254740992 1.8014398509481984e+16
17+
3 0.5 0.5 1
18+
4 0.5 0.5 1
19+
20+
-- !avg_sum_double_sign_flip --
21+
5 1.8014398509481984e+16 1.8014398509481984e+16 1.8014398509481984e+16
22+
6 0.5 9007199254740992 1.8014398509481984e+16
23+
7 -1.8014398509481984e+16 -9007199254740992 -1.8014398509481984e+16
24+
8 0.5 -9007199254740992 -1.8014398509481984e+16
25+
9 0.5 0.5 1
26+
27+
-- !avg_sum_double_wider_frames --
28+
10 1.8014398509481984e+16 1.8014398509481984e+16 1.8014398509481984e+16 9007199254740992 1.8014398509481984e+16 6004799503160661
29+
11 0.5 9007199254740992 1.8014398509481984e+16 6004799503160661 1.8014398509481984e+16 0.5
30+
12 0.5 6004799503160661 1.8014398509481984e+16 0.5 1.5 0.5
31+
13 0.5 0.5 1.5 0.5 1.5 0.5
32+
14 0.5 0.5 1.5 0.5 1 0.5
33+
34+
-- !avg_sum_nullable_partitioned --
35+
1 1 1.8014398509481984e+16 1.8014398509481984e+16 1.8014398509481984e+16
36+
10 3 \N \N \N
37+
11 3 0.5 0.5 0.5
38+
12 3 0.5 0.5 1
39+
13 3 0.5 0.5 1
40+
14 3 0.5 0.5 1
41+
2 1 0.5 9007199254740992 1.8014398509481984e+16
42+
3 1 0.5 0.5 1
43+
4 1 \N 0.5 0.5
44+
5 2 1.8014398509481984e+16 1.8014398509481984e+16 1.8014398509481984e+16
45+
6 2 0.5 9007199254740992 1.8014398509481984e+16
46+
7 2 -1.8014398509481984e+16 -9007199254740992 -1.8014398509481984e+16
47+
8 2 0.5 -9007199254740992 -1.8014398509481984e+16
48+
9 2 0.5 0.5 1
49+
50+
-- !avg_sum_double_unbounded --
51+
1 1.8014398509481984e+16 1.8014398509481984e+16 1.8014398509481984e+16
52+
2 0.5 9007199254740992 1.8014398509481984e+16
53+
3 0.5 6004799503160661 1.8014398509481984e+16
54+
4 0.5 4503599627370496 1.8014398509481984e+16
55+
56+
-- !avg_sum_exact_types --
57+
1 1.8014398509481984e+16 3.602879701896397e+16 36028797018963968 18014398509481984.0000 18014398509481984.000
58+
2 0.5 1.8014398509481984e+16 36028797018963969 9007199254740992.2500 18014398509481984.500
59+
3 0.5 1 2 0.5000 1.000
60+
4 0.5 1 2 0.5000 1.000
61+
62+
-- !avg_double_cte --
63+
1 1.8014398509481984e+16 1.8014398509481984e+16
64+
2 1 9007199254740992
65+
3 1 1
66+
Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
// Sliding ROWS frames over floating-point columns must not carry the rounding
19+
// loss of a value that already left the frame into the current result.
20+
//
21+
// Expected values must not depend on how the compiler groups the additions
22+
// (the accumulators allow floating-point reassociation). The data therefore
23+
// uses 2^54 as the large value and 0.5 as the small value: half an ulp of 2^54
24+
// is 2, so as long as the small values inside a frame sum to less than 2 in
25+
// magnitude, any grouping rounds the frame sum back to 2^54, while removing
26+
// 2^54 incrementally would still leave 0 instead of the exact small sum.
27+
// Frames that mix the large positive and negative value hold two operands
28+
// only, because a two-operand IEEE addition has a single correctly rounded
29+
// result.
30+
suite("test_window_float_sliding_frame") {
31+
sql "DROP TABLE IF EXISTS test_window_float_sliding_frame"
32+
sql """
33+
CREATE TABLE test_window_float_sliding_frame (
34+
id INT,
35+
grp INT,
36+
v_double DOUBLE,
37+
v_float FLOAT,
38+
v_nullable DOUBLE NULL
39+
) ENGINE = OLAP
40+
DUPLICATE KEY(id)
41+
DISTRIBUTED BY HASH(id) BUCKETS 1
42+
PROPERTIES ("replication_allocation" = "tag.location.default: 1")
43+
"""
44+
45+
// grp 1: a large value (2^54) leaves the frame, then only small values remain.
46+
// grp 2: sign flip of a large value around small values.
47+
// grp 3: consecutive small values after a large one, with NULL in the nullable column.
48+
sql """
49+
INSERT INTO test_window_float_sliding_frame VALUES
50+
(1, 1, 18014398509481984, 18014398509481984, 18014398509481984),
51+
(2, 1, 0.5, 0.5, 0.5),
52+
(3, 1, 0.5, 0.5, 0.5),
53+
(4, 1, 0.5, 0.5, NULL),
54+
(5, 2, 18014398509481984, 18014398509481984, 18014398509481984),
55+
(6, 2, 0.5, 0.5, 0.5),
56+
(7, 2, -18014398509481984, -18014398509481984, -18014398509481984),
57+
(8, 2, 0.5, 0.5, 0.5),
58+
(9, 2, 0.5, 0.5, 0.5),
59+
(10, 3, 18014398509481984, 18014398509481984, NULL),
60+
(11, 3, 0.5, 0.5, 0.5),
61+
(12, 3, 0.5, 0.5, 0.5),
62+
(13, 3, 0.5, 0.5, 0.5),
63+
(14, 3, 0.5, 0.5, 0.5)
64+
"""
65+
66+
// The reported case: after row 1 leaves the frame, avg over [0.5, 0.5] must be 0.5.
67+
order_qt_avg_double_preceding_1 """
68+
SELECT id, v_double,
69+
avg(v_double) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS got
70+
FROM test_window_float_sliding_frame
71+
WHERE grp = 1
72+
"""
73+
74+
order_qt_sum_double_preceding_1 """
75+
SELECT id, v_double,
76+
sum(v_double) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS got
77+
FROM test_window_float_sliding_frame
78+
WHERE grp = 1
79+
"""
80+
81+
order_qt_avg_sum_float_preceding_1 """
82+
SELECT id, v_float,
83+
avg(v_float) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS got_avg,
84+
sum(v_float) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS got_sum
85+
FROM test_window_float_sliding_frame
86+
WHERE grp = 1
87+
"""
88+
89+
// Sign flip: a large positive value leaves, then a large negative value
90+
// enters and leaves. Two-operand frames keep the expected sums exact.
91+
order_qt_avg_sum_double_sign_flip """
92+
SELECT id, v_double,
93+
avg(v_double) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS got_avg,
94+
sum(v_double) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS got_sum
95+
FROM test_window_float_sliding_frame
96+
WHERE grp = 2
97+
"""
98+
99+
// Consecutive small values after the large one, wider frames and following bounds.
100+
order_qt_avg_sum_double_wider_frames """
101+
SELECT id, v_double,
102+
avg(v_double) OVER (ORDER BY id ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS avg_p2,
103+
sum(v_double) OVER (ORDER BY id ROWS BETWEEN 2 PRECEDING AND CURRENT ROW) AS sum_p2,
104+
avg(v_double) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING) AS avg_p1f1,
105+
sum(v_double) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING) AS sum_p1f1,
106+
avg(v_double) OVER (ORDER BY id ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING) AS avg_f2
107+
FROM test_window_float_sliding_frame
108+
WHERE grp = 3
109+
"""
110+
111+
// Nullable input: NULL rows are skipped while the frame keeps sliding.
112+
order_qt_avg_sum_nullable_partitioned """
113+
SELECT id, grp, v_nullable,
114+
avg(v_nullable) OVER (PARTITION BY grp ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS got_avg,
115+
sum(v_nullable) OVER (PARTITION BY grp ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS got_sum
116+
FROM test_window_float_sliding_frame
117+
"""
118+
119+
// Frames that only grow keep the incremental path and stay unchanged.
120+
order_qt_avg_sum_double_unbounded """
121+
SELECT id, v_double,
122+
avg(v_double) OVER (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS got_avg,
123+
sum(v_double) OVER (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS got_sum
124+
FROM test_window_float_sliding_frame
125+
WHERE grp = 1
126+
"""
127+
128+
// Exact accumulators (integer / decimal) still use the incremental path and stay exact.
129+
order_qt_avg_sum_exact_types """
130+
SELECT id, v_double,
131+
avg(CAST(v_double * 2 AS BIGINT)) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS avg_bigint,
132+
sum(CAST(v_double * 2 AS BIGINT)) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS sum_bigint,
133+
avg(CAST(v_double AS DECIMAL(27, 3))) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS avg_decimal,
134+
sum(CAST(v_double AS DECIMAL(27, 3))) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS sum_decimal
135+
FROM test_window_float_sliding_frame
136+
WHERE grp = 1
137+
"""
138+
139+
// The reported shape without a table.
140+
order_qt_avg_double_cte """
141+
WITH t AS (
142+
SELECT 1 AS id, CAST(18014398509481984 AS DOUBLE) AS v
143+
UNION ALL SELECT 2, CAST(1 AS DOUBLE)
144+
UNION ALL SELECT 3, CAST(1 AS DOUBLE)
145+
)
146+
SELECT id, v,
147+
avg(v) OVER (ORDER BY id ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS got
148+
FROM t
149+
"""
150+
}

0 commit comments

Comments
 (0)