Skip to content

Commit 5fb1393

Browse files
authored
[fix](be) Treat non-positive topn expansion rates as unlimited (apache#68246)
### What problem does this PR solve? Issue Number: None Related PR: None Problem Summary: With a zero `space_expand_rate`, `topn` and `topn_array` can return a value in one-stage aggregation but an empty result in two-stage aggregation. The BE computes a zero candidate capacity, so serializing the partial state discards every candidate. For example, `topn(s, 1, 0)` over `['a', 'b', 'a']` should return `{"a":2}` in both aggregation phases. Treat non-positive expansion rates as unlimited candidate capacity in the shared BE state used by `topn`, `topn_array`, and `topn_weighted`. Retain all intermediate candidates and exact counts through serialization and merging; `top_num` still limits the final result. Positive expansion rates and the default rate of 50 keep their existing behavior. Add coverage for zero, negative and minimum INT rates, multiple serialization/merge stages, global winners outside each local top N, weighted values, empty/NULL input, and state reuse. Update the existing aggregate-state parameter tests: non-positive rates describe compatible unlimited states, while unlimited and finite-capacity states are incompatible. The empty-state regression cases now use NULL input. ### Release note `topn`, `topn_array`, and `topn_weighted` now interpret a non-positive `space_expand_rate` as unlimited intermediate candidate retention. The result remains limited by `top_num`. Retaining all distinct candidates can increase intermediate-state memory and network traffic. ### Check List (For Author) - Test - [x] Regression test - [x] Unit Test - [x] Manual test - [ ] No need to test or manual test. Validation before rebasing onto current master: - FE and BE ASAN builds passed. - 10 TOPN BE unit tests passed. - Both `topn` and `topn_unlimited` regression suites passed; expected output was generated by the regression runner. - SQL checks returned `{"a":2}` and `["a"]` for non-positive rates in both aggregation phases; EXPLAIN confirmed partial serialization followed by merge/finalization. - clang-format 16, build hygiene, and clang-tidy passed. Validation on the PR branch: - Updated the reset/reuse test and existing aggregate-state tests for current master. - clang-format 16, build hygiene, and clang-tidy passed. - ASAN unit tests passed on the PR branch: 10 TOPN tests and all 16 `AggregateStateParametersTest` tests (26 total). - Commands: - `./run-be-ut.sh -j 48 --run --filter='AggregateFunctionTopN*.*:*/AggregateFunctionTopN*.*:AggTest.topn*'` - `./run-be-ut.sh -j 48 --run --filter='AggregateStateParametersTest.*'` - The newly adjusted `test_agg_state_parameters` regression suite has not been rerun locally. - Behavior changed: - [ ] No. - [x] Yes. Non-positive expansion rates explicitly mean unlimited candidate retention. - Does this need documentation? - [ ] No. - [x] Yes. The SQL function docs should describe unlimited candidate retention for non-positive expansion rates; a documentation PR is not included. ### Check List (For Reviewer who merge this PR) - [ ] Confirm the release note - [ ] Confirm test cases - [ ] Confirm document - [ ] Add branch pick label
1 parent 14c957e commit 5fb1393

6 files changed

Lines changed: 320 additions & 50 deletions

File tree

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,8 @@ struct AggregateFunctionTopNData {
5959
using DataType = typename PrimitiveTypeTraits<T>::CppType;
6060
void set_paramenters(int input_top_num, int space_expand_rate = 50) {
6161
top_num = input_top_num;
62-
capacity = (uint64_t)top_num * space_expand_rate;
62+
// Non-positive expansion rates retain all candidates during serialization and merging.
63+
capacity = space_expand_rate <= 0 ? UINT64_MAX : (uint64_t)top_num * space_expand_rate;
6364
}
6465

6566
void add(const StringRef& value, const UInt64& increment = 1) {

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

Lines changed: 17 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717

1818
#include <gtest/gtest.h>
1919

20+
#include <cstdint>
2021
#include <limits>
2122

2223
#include "common/exception.h"
@@ -88,12 +89,6 @@ class StateParameterChecks {
8889
});
8990
}
9091

91-
void check_direct_mismatch(const Arguments& first, const Arguments& second) {
92-
auto* destination = create(first);
93-
auto* source = create(second);
94-
expect_incompatible([&] { _function->merge(destination, source, _arena); });
95-
}
96-
9792
void check_merge_result(const Arguments& initial, const Arguments& incoming, bool serialized) {
9893
auto* destination = create();
9994
auto* source = create();
@@ -147,21 +142,6 @@ class StateParameterChecks {
147142
EXPECT_TRUE(ColumnHelper::column_equal(result(destination), result(expected)));
148143
}
149144

150-
void check_configured_empty_payload(const Arguments& arguments) {
151-
// TopN with zero capacity keeps counters in memory but serializes no counters.
152-
// A decoded empty state must not change compatible counters.
153-
auto serialized = serialize(create(arguments));
154-
auto* configured_empty = create();
155-
_function->deserialize_and_merge_from_column(configured_empty, *serialized, _arena);
156-
auto* populated = create(arguments);
157-
EXPECT_NO_THROW(
158-
_function->deserialize_and_merge_from_column(populated, *serialized, _arena));
159-
EXPECT_TRUE(ColumnHelper::column_equal(result(populated), result(create(arguments))));
160-
EXPECT_NO_THROW(_function->merge(configured_empty, create(arguments), _arena));
161-
EXPECT_TRUE(
162-
ColumnHelper::column_equal(result(configured_empty), result(create(arguments))));
163-
}
164-
165145
void check_compatible(const Arguments& arguments) {
166146
auto* destination = create();
167147
auto serialized = serialize(create(arguments));
@@ -394,33 +374,24 @@ TEST(AggregateStateParametersTest, Histogram) {
394374
{value, argument<DataTypeInt32>(3)});
395375
}
396376

397-
TEST(AggregateStateParametersTest, TopNZeroCapacityParameters) {
377+
TEST(AggregateStateParametersTest, TopNUnlimitedParameters) {
398378
for (const auto& name : {"topn", "topn_array", "topn_weighted"}) {
399-
SCOPED_TRACE(name);
400-
Arguments zero_capacity {argument<DataTypeString>("a")};
401-
if (std::string(name) == "topn_weighted") {
402-
zero_capacity.push_back(argument<DataTypeInt64>(1));
403-
}
404-
zero_capacity.push_back(argument<DataTypeInt32>(1));
405-
zero_capacity.push_back(argument<DataTypeInt32>(0));
406-
auto positive_capacity = zero_capacity;
407-
positive_capacity.back() = argument<DataTypeInt32>(2);
408-
DataTypes types;
409-
for (const auto& arg : zero_capacity) {
410-
types.push_back(arg.type);
379+
for (int rate : {0, -1, INT32_MIN}) {
380+
SCOPED_TRACE(rate);
381+
Arguments unlimited {argument<DataTypeString>("a")};
382+
if (std::string(name) == "topn_weighted") {
383+
unlimited.push_back(argument<DataTypeInt64>(1));
384+
}
385+
unlimited.push_back(argument<DataTypeInt32>(1));
386+
unlimited.push_back(argument<DataTypeInt32>(rate));
387+
auto finite = unlimited;
388+
finite.back() = argument<DataTypeInt32>(2);
389+
check_parameters(name, unlimited, finite);
390+
391+
auto zero_rate = unlimited;
392+
zero_rate.back() = argument<DataTypeInt32>(0);
393+
check_compatible_states(name, unlimited, zero_rate);
411394
}
412-
auto function = AggregateFunctionSimpleFactory::instance().get(
413-
name, types, nullptr, false, BeExecVersionManager::get_newest_version());
414-
ASSERT_NE(function, nullptr);
415-
StateParameterChecks checks(function);
416-
// Only the serialized zero-capacity state is empty; in-memory counters contribute.
417-
checks.check_direct_mismatch(zero_capacity, positive_capacity);
418-
checks.check_direct_mismatch(positive_capacity, zero_capacity);
419-
check_ignored_parameters(name, zero_capacity, positive_capacity, true);
420-
checks.check_merge_result({}, zero_capacity, false);
421-
checks.check_merge_result(zero_capacity, {}, false);
422-
checks.check_merge_result(zero_capacity, {}, true);
423-
checks.check_configured_empty_payload(zero_capacity);
424395
}
425396
}
426397

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
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 <cstdint>
21+
#include <string>
22+
23+
#include "core/column/column_string.h"
24+
#include "core/column/column_vector.h"
25+
#include "core/string_buffer.hpp"
26+
#include "exprs/aggregate/aggregate_function_topn.h"
27+
28+
namespace doris {
29+
namespace {
30+
31+
template <PrimitiveType T>
32+
AggregateFunctionTopNData<T> round_trip(const AggregateFunctionTopNData<T>& state) {
33+
auto column = ColumnString::create();
34+
BufferWritable writer(*column);
35+
state.write(writer);
36+
writer.commit();
37+
BufferReadable reader(column->get_data_at(0));
38+
AggregateFunctionTopNData<T> result;
39+
result.read(reader);
40+
return result;
41+
}
42+
43+
class AggregateFunctionTopNUnlimitedTest : public testing::TestWithParam<int> {};
44+
45+
TEST_P(AggregateFunctionTopNUnlimitedTest, SerializeAndMergeStrings) {
46+
AggregateFunctionTopNData<TYPE_STRING> lhs;
47+
AggregateFunctionTopNData<TYPE_STRING> rhs;
48+
lhs.set_paramenters(1, GetParam());
49+
rhs.set_paramenters(1, GetParam());
50+
// The global winner is not the most frequent value in either partial state.
51+
lhs.add(std::string("a"), 3);
52+
lhs.add(std::string("winner"), 2);
53+
rhs.add(std::string("b"), 3);
54+
rhs.add(std::string("winner"), 2);
55+
56+
auto partial = round_trip(lhs);
57+
EXPECT_EQ(partial.counter_map, lhs.counter_map);
58+
AggregateFunctionTopNData<TYPE_STRING> merged;
59+
merged.merge(partial);
60+
merged = round_trip(merged);
61+
merged.merge(round_trip(rhs));
62+
merged = round_trip(merged);
63+
64+
ASSERT_EQ(merged.counter_map.size(), 3);
65+
EXPECT_EQ(merged.counter_map.at("a"), 3);
66+
EXPECT_EQ(merged.counter_map.at("b"), 3);
67+
EXPECT_EQ(merged.counter_map.at("winner"), 4);
68+
EXPECT_EQ(merged.get(), R"({"winner":4})");
69+
70+
AggregateFunctionTopNData<TYPE_STRING> empty;
71+
merged.merge(round_trip(empty));
72+
EXPECT_EQ(merged.get(), R"({"winner":4})");
73+
74+
merged.reset();
75+
EXPECT_EQ(round_trip(merged).get(), "{}");
76+
merged.set_paramenters(1, GetParam());
77+
merged.add(std::string("new"), 7);
78+
EXPECT_EQ(round_trip(merged).get(), R"({"new":7})");
79+
}
80+
81+
TEST_P(AggregateFunctionTopNUnlimitedTest, SerializeAndMergeWeightedIntegers) {
82+
AggregateFunctionTopNData<TYPE_INT> lhs;
83+
AggregateFunctionTopNData<TYPE_INT> rhs;
84+
lhs.set_paramenters(2, GetParam());
85+
rhs.set_paramenters(2, GetParam());
86+
lhs.add(1, 10);
87+
lhs.add(2, 7);
88+
lhs.add(3, 6);
89+
rhs.add(4, 11);
90+
rhs.add(5, 8);
91+
rhs.add(3, 6);
92+
93+
AggregateFunctionTopNData<TYPE_INT> merged;
94+
merged.merge(round_trip(lhs));
95+
merged.merge(round_trip(rhs));
96+
merged = round_trip(merged);
97+
ASSERT_EQ(merged.counter_map.size(), 5);
98+
EXPECT_EQ(merged.counter_map.at(3), 12);
99+
auto result = ColumnInt32::create();
100+
merged.insert_result_into(*result);
101+
ASSERT_EQ(result->size(), 2);
102+
EXPECT_EQ(result->get_element(0), 3);
103+
EXPECT_EQ(result->get_element(1), 4);
104+
}
105+
106+
INSTANTIATE_TEST_SUITE_P(NonPositiveRates, AggregateFunctionTopNUnlimitedTest,
107+
testing::Values(0, -1, INT32_MIN));
108+
109+
TEST(AggregateFunctionTopNTest, PositiveRateStillLimitsSerializedCandidates) {
110+
AggregateFunctionTopNData<TYPE_INT> state;
111+
state.set_paramenters(1, 2);
112+
state.add(1, 3);
113+
state.add(2, 2);
114+
state.add(3, 1);
115+
auto partial = round_trip(state);
116+
ASSERT_EQ(partial.counter_map.size(), 2);
117+
EXPECT_EQ(partial.counter_map.at(1), 3);
118+
EXPECT_EQ(partial.counter_map.at(2), 2);
119+
120+
state.set_paramenters(1);
121+
EXPECT_EQ(round_trip(state).counter_map, state.counter_map);
122+
}
123+
124+
} // namespace
125+
} // namespace doris
Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
-- This file is automatically generated. You should know what you did if you want to edit this
2+
-- !unlimited --
3+
{"a":3,"x":2} ["a", "x"] [1, 4] ["b", "y"] [2, 5]
4+
5+
-- !grouped --
6+
1 {"a":3,"b":2} ["a", "b"] [1, 2] ["b", "a"] [2, 1]
7+
2 {"x":2,"y":1} ["x", "y"] [4, 5] ["y", "x"] [5, 4]
8+
3 \N \N \N \N \N
9+
10+
-- !empty --
11+
\N \N \N
12+
13+
-- !constant_input --
14+
{"a":2} ["a"]
15+
16+
-- !unlimited --
17+
{"a":3,"x":2} ["a", "x"] [1, 4] ["b", "y"] [2, 5]
18+
19+
-- !grouped --
20+
1 {"a":3,"b":2} ["a", "b"] [1, 2] ["b", "a"] [2, 1]
21+
2 {"x":2,"y":1} ["x", "y"] [4, 5] ["y", "x"] [5, 4]
22+
3 \N \N \N \N \N
23+
24+
-- !empty --
25+
\N \N \N
26+
27+
-- !constant_input --
28+
{"a":2} ["a"]
29+
30+
-- !unlimited --
31+
{"a":3,"x":2} ["a", "x"] [1, 4] ["b", "y"] [2, 5]
32+
33+
-- !grouped --
34+
1 {"a":3,"b":2} ["a", "b"] [1, 2] ["b", "a"] [2, 1]
35+
2 {"x":2,"y":1} ["x", "y"] [4, 5] ["y", "x"] [5, 4]
36+
3 \N \N \N \N \N
37+
38+
-- !empty --
39+
\N \N \N
40+
41+
-- !constant_input --
42+
{"a":2} ["a"]
43+
44+
-- !positive_and_default --
45+
{"a":3,"x":2} {"a":3,"x":2} [1, 4] [1, 4] [2, 5] [2, 5]
46+
47+
-- !unlimited --
48+
{"a":3,"x":2} ["a", "x"] [1, 4] ["b", "y"] [2, 5]
49+
50+
-- !grouped --
51+
1 {"a":3,"b":2} ["a", "b"] [1, 2] ["b", "a"] [2, 1]
52+
2 {"x":2,"y":1} ["x", "y"] [4, 5] ["y", "x"] [5, 4]
53+
3 \N \N \N \N \N
54+
55+
-- !empty --
56+
\N \N \N
57+
58+
-- !constant_input --
59+
{"a":2} ["a"]
60+
61+
-- !unlimited --
62+
{"a":3,"x":2} ["a", "x"] [1, 4] ["b", "y"] [2, 5]
63+
64+
-- !grouped --
65+
1 {"a":3,"b":2} ["a", "b"] [1, 2] ["b", "a"] [2, 1]
66+
2 {"x":2,"y":1} ["x", "y"] [4, 5] ["y", "x"] [5, 4]
67+
3 \N \N \N \N \N
68+
69+
-- !empty --
70+
\N \N \N
71+
72+
-- !constant_input --
73+
{"a":2} ["a"]
74+
75+
-- !unlimited --
76+
{"a":3,"x":2} ["a", "x"] [1, 4] ["b", "y"] [2, 5]
77+
78+
-- !grouped --
79+
1 {"a":3,"b":2} ["a", "b"] [1, 2] ["b", "a"] [2, 1]
80+
2 {"x":2,"y":1} ["x", "y"] [4, 5] ["y", "x"] [5, 4]
81+
3 \N \N \N \N \N
82+
83+
-- !empty --
84+
\N \N \N
85+
86+
-- !constant_input --
87+
{"a":2} ["a"]
88+
89+
-- !positive_and_default --
90+
{"a":3,"x":2} {"a":3,"x":2} [1, 4] [1, 4] [2, 5] [2, 5]
91+

‎regression-test/suites/datatype_p0/agg_state/test_agg_state_parameters.groovy‎

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -62,9 +62,9 @@ suite("test_agg_state_parameters") {
6262
def ignoredCases = [
6363
["percentile_approx_weighted", "7, 0, 0.25", "7, 1, 0.75"],
6464
["percentile_array", "7, cast([] as array<double>)", "7, [0.25]"],
65-
["topn_weighted", "1, 1, 1, 0", "1, 1, 1, 2"],
66-
["topn_array", "1, 1, 0", "1, 1, 2"],
67-
["topn", "'a', 1, 0", "'a', 1, 2"]
65+
["topn_weighted", "cast(NULL as int), 1, 1, 0", "nullable(cast(1 as int)), 1, 1, 2"],
66+
["topn_array", "cast(NULL as int), 1, 0", "nullable(cast(1 as int)), 1, 2"],
67+
["topn", "cast(NULL as string), 1, 0", "nullable(cast('a' as string)), 1, 2"]
6868
]
6969
def cases = [
7070
["topn", "'a', 1", "'a', 3"],
@@ -105,6 +105,12 @@ suite("test_agg_state_parameters") {
105105
["sequence_count", "'(?1)', non_nullable(cast('2024-01-01' as datetime)), true, false",
106106
"'(?2)', non_nullable(cast('2024-01-01' as datetime)), true, false"]
107107
]
108+
// Unlimited states retain samples, so they cannot merge with finite-capacity states.
109+
for (def rate : [0, -1, -2147483648]) {
110+
cases.add(["topn", "'a', 1, ${rate}", "'a', 1, 2"])
111+
cases.add(["topn_array", "1, 1, ${rate}", "1, 1, 2"])
112+
cases.add(["topn_weighted", "1, 1, 1, ${rate}", "1, 1, 1, 2"])
113+
}
108114
// States without contributing samples ignore their parameter values.
109115
// Keep AggState argument nullability identical across both sides of the UNION.
110116
for (def quantile : ["0.0", "0.25", "1.0"]) {

0 commit comments

Comments
 (0)