This is an automated email from the ASF dual-hosted git repository.
HappenLee pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 6104204b401 [improvement](be) Reduce map and string array
deduplication overhead (#69690)
6104204b401 is described below
commit 6104204b401c82b60b402b7810aa7b0c6bf49f83
Author: HappenLee <[email protected]>
AuthorDate: Fri Oct 30 14:28:21 2026 +0800
[improvement](be) Reduce map and string array deduplication overhead
(#69690)
`map(k, v)` serializes its keys and allocates deduplication buffers even
though each output row has only one pair. String `array_distinct` grows
its character buffer and copies each retained value separately.
- Skip `deduplicate_keys()` for a single key/value pair. Multiple-pair
construction keeps its existing last-value-wins deduplication.
- Collect retained positions and call `insert_indices_from()` once for
string batches without NULL elements. Use the existing SIMD NULL-map
scan to select the scalar path when any NULL exists; this avoids copying
hidden string payloads beneath NULLs. Nullable inputs with an all-zero
NULL map still use batch copying.
- Keep scalar copying when the nested element count exceeds the UInt32
selector limit, and use `insert(...).second` to avoid separate hash
lookups.
First-occurrence ordering and SQL NULL semantics are unchanged. Tests
cover NULL keys/values, constant keys, multiple-pair deduplication,
string ordering, hidden NULL payloads, a NULL at the end of the input,
empty inputs, long strings and selector growth.
Paired Release microbenchmarks used the complete original and updated
`execute_impl` entry points in one process with identical inputs.
Results below are median CPU milliseconds per 4,096 rows/arrays on a
pinned Xeon Platinum 8457C CPU, seven repetitions (selected earlier MAP
cases had nine). These are function-level measurements, not end-to-end
SQL speedups.
| Case | Before (ms) | After (ms) | Before / after |
| --- | ---: | ---: | ---: |
| Single-pair MAP, BIGINT key/value | 0.0804 | 0.0629 | 1.28x |
| Single-pair MAP, 16-byte string key, BIGINT value | 0.0986 | 0.0753 |
1.31x |
| Single-pair MAP, 128-byte string key, BIGINT value | 0.1665 | 0.1033 |
1.61x |
| ARRAY, 32 distinct 16-byte strings | 2.063 | 1.664 | 1.24x |
| ARRAY, 32 distinct 128-byte strings | 22.993 | 10.550 | 2.18x |
| ARRAY, 128 distinct 128-byte strings | 116.683 | 57.871 | 2.02x |
| ARRAY, 128 x 128-byte strings, 25% retained | 31.968 | 20.596 | 1.55x
|
| ARRAY, 128 x 128-byte strings, one distinct value | 10.792 | 11.104 |
0.97x |
| ARRAY, 32 NULL elements with empty payloads | 0.1173 | 0.1219 | 0.96x
|
| ARRAY, 8 NULL elements with 4KiB hidden payloads | 0.0400 | 0.0413 |
0.97x |
Highly duplicated and all-NULL inputs showed little benefit; small
differences in these controls were within the observed sample
variability. NULL batches keep scalar copying. Temporary frozen-baseline
benchmark code and build-entry changes are excluded from this PR.
### Release note
Improve execution efficiency of single-pair MAP construction and string
ARRAY_DISTINCT batches without NULL elements, preserving SQL results.
---
.../exprs/function/array/function_array_distinct.h | 82 ++++++----
be/src/exprs/function/function_map.cpp | 5 +-
.../function/function_array_distinct_test.cpp | 177 +++++++++++++++++++++
be/test/exprs/function/function_map_test.cpp | 73 +++++++++
4 files changed, 305 insertions(+), 32 deletions(-)
diff --git a/be/src/exprs/function/array/function_array_distinct.h
b/be/src/exprs/function/array/function_array_distinct.h
index 01babcda365..ae8fa3f0368 100644
--- a/be/src/exprs/function/array/function_array_distinct.h
+++ b/be/src/exprs/function/array/function_array_distinct.h
@@ -23,6 +23,7 @@
#include <glog/logging.h>
#include <cstring>
+#include <limits>
#include <memory>
#include <ostream>
#include <utility>
@@ -48,6 +49,7 @@
#include "core/types.h"
#include "exec/common/hash_table/hash.h"
#include "exprs/function/function.h"
+#include "util/simd/bits.h"
namespace doris {
class FunctionContext;
@@ -188,18 +190,22 @@ private:
return true;
}
+ template <bool batch_copy>
bool _execute_string(const IColumn& src_column, const
ColumnArray::Offsets64& src_offsets,
IColumn& dest_column, ColumnArray::Offsets64&
dest_offsets,
const NullMapType* src_null_map, NullMapType*
dest_null_map) const {
- const auto* src_data_concrete = reinterpret_cast<const
ColumnString*>(&src_column);
- if (!src_data_concrete) {
- return false;
- }
-
- auto& dest_column_string =
reinterpret_cast<ColumnString&>(dest_column);
+ const auto& src_data_concrete = assert_cast<const
ColumnString&>(src_column);
+ auto& dest_column_string = assert_cast<ColumnString&>(dest_column);
ColumnString::Chars& column_string_chars =
dest_column_string.get_chars();
ColumnString::Offsets& column_string_offsets =
dest_column_string.get_offsets();
- column_string_chars.reserve(src_column.size());
+ IColumn::Selector selector;
+ if constexpr (batch_copy) {
+ // _execute_by_type() passes nullptr after ruling out NULL
elements.
+ DCHECK(src_null_map == nullptr);
+ selector.reserve(src_column.size());
+ } else {
+ column_string_chars.reserve(src_column.size());
+ }
using Set = phmap::flat_hash_set<StringRef, DefaultHash<StringRef>>;
Set set;
@@ -211,31 +217,34 @@ private:
set.clear();
size_t null_size = 0;
for (size_t j = prev_src_offset; j < curr_src_offset; ++j) {
- if (null_size != 0 && src_null_map && (*src_null_map)[j]) {
- // ignore duplicated nulls
- continue;
- }
- if (src_null_map && (*src_null_map)[j]) {
- DCHECK(dest_null_map != nullptr);
- // Note: here we need to update the offset of ColumnString
-
column_string_offsets.push_back(column_string_offsets.back());
- (*dest_null_map).push_back(true);
- null_size++;
- continue;
+ if constexpr (!batch_copy) {
+ if (null_size != 0 && src_null_map && (*src_null_map)[j]) {
+ // ignore duplicated nulls
+ continue;
+ }
+ if (src_null_map && (*src_null_map)[j]) {
+ DCHECK(dest_null_map != nullptr);
+
column_string_offsets.push_back(column_string_offsets.back());
+ (*dest_null_map).push_back(true);
+ null_size++;
+ continue;
+ }
}
- StringRef src_str_ref = src_data_concrete->get_data_at(j);
- if (!set.contains(src_str_ref)) {
- set.insert(src_str_ref);
- // copy the src data to column_string_chars
- const size_t old_size = column_string_chars.size();
- const size_t new_size = old_size + src_str_ref.size;
- column_string_chars.resize(new_size);
- if (src_str_ref.size > 0) {
- memcpy(column_string_chars.data() + old_size,
src_str_ref.data,
- src_str_ref.size);
+ StringRef src_str_ref = src_data_concrete.get_data_at(j);
+ if (set.insert(src_str_ref).second) {
+ if constexpr (batch_copy) {
+
selector.push_back(static_cast<IColumn::ColumnIndex>(j));
+ } else {
+ const size_t old_size = column_string_chars.size();
+ const size_t new_size = old_size + src_str_ref.size;
+ column_string_chars.resize(new_size);
+ if (src_str_ref.size > 0) {
+ memcpy(column_string_chars.data() + old_size,
src_str_ref.data,
+ src_str_ref.size);
+ }
+ column_string_offsets.push_back(new_size);
}
- column_string_offsets.push_back(new_size);
if (dest_null_map) {
(*dest_null_map).push_back(false);
@@ -247,6 +256,10 @@ private:
dest_offsets.push_back(res_offset);
prev_src_offset = curr_src_offset;
}
+ if constexpr (batch_copy) {
+ dest_column_string.insert_indices_from(src_column, selector.data(),
+ selector.data() +
selector.size());
+ }
return true;
}
@@ -255,8 +268,15 @@ private:
const NullMapType* src_null_map, NullMapType*
dest_null_map,
DataTypePtr& nested_type) const {
if (is_string_type(nested_type->get_primitive_type())) {
- return _execute_string(src_column, src_offsets, dest_column,
dest_offsets, src_null_map,
- dest_null_map);
+ // NULL rows can carry hidden strings: one 4KiB payload per array
adds 16MiB for
+ // 4096 arrays. Keep scalar copying when any NULL exists or UInt32
indices overflow.
+ if (src_column.size() >
std::numeric_limits<IColumn::ColumnIndex>::max() ||
+ (src_null_map && simd::contain_one(src_null_map->data(),
src_null_map->size()))) {
+ return _execute_string<false>(src_column, src_offsets,
dest_column, dest_offsets,
+ src_null_map, dest_null_map);
+ }
+ return _execute_string<true>(src_column, src_offsets, dest_column,
dest_offsets,
+ nullptr, dest_null_map);
}
auto call = [&](const auto& type) -> bool {
using DispatchType = std::decay_t<decltype(type)>;
diff --git a/be/src/exprs/function/function_map.cpp
b/be/src/exprs/function/function_map.cpp
index c8139403104..01356116870 100644
--- a/be/src/exprs/function/function_map.cpp
+++ b/be/src/exprs/function/function_map.cpp
@@ -378,7 +378,10 @@ public:
result_col_map_offsets[row] = offset;
}
- RETURN_IF_ERROR(map_column->deduplicate_keys());
+ // A single key/value pair per row cannot contain duplicate keys.
+ if (num_element > 2) {
+ RETURN_IF_ERROR(map_column->deduplicate_keys());
+ }
block.replace_by_position(result, std::move(result_col));
return Status::OK();
}
diff --git a/be/test/exprs/function/function_array_distinct_test.cpp
b/be/test/exprs/function/function_array_distinct_test.cpp
new file mode 100644
index 00000000000..559425ea3e8
--- /dev/null
+++ b/be/test/exprs/function/function_array_distinct_test.cpp
@@ -0,0 +1,177 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "exprs/function/array/function_array_distinct.h"
+
+#include <gtest/gtest.h>
+
+#include <optional>
+#include <string>
+#include <vector>
+
+#include "core/column/column_string.h"
+#include "core/data_type/data_type_string.h"
+
+namespace doris {
+
+class FunctionArrayDistinctTest : public testing::Test {
+protected:
+ using StringRow = std::vector<std::optional<std::string>>;
+ using StringRows = std::vector<StringRow>;
+
+ template <bool use_dispatch>
+ // NOLINTNEXTLINE(readability-function-cognitive-complexity): GTest
assertions add branches.
+ static void check_strings(const StringRows& rows, const StringRows&
expected, bool nullable,
+ const std::string& null_payload) {
+ ASSERT_EQ(rows.size(), expected.size());
+ auto source = ColumnString::create();
+ ColumnArray::Offsets64 source_offsets;
+ FunctionArrayDistinct::NullMapType source_nulls;
+ for (const auto& row : rows) {
+ for (const auto& value : row) {
+ ASSERT_TRUE(nullable || value.has_value());
+ const auto& payload = value ? *value : null_payload;
+ source->insert_data(payload.data(), payload.size());
+ source_nulls.push_back(!value.has_value());
+ }
+ source_offsets.push_back(source->size());
+ }
+ const size_t source_bytes = source->get_chars().size();
+
+ auto result = ColumnString::create();
+ ColumnArray::Offsets64 result_offsets;
+ FunctionArrayDistinct::NullMapType result_nulls;
+ FunctionArrayDistinct function;
+ const auto* src_nulls = nullable ? &source_nulls : nullptr;
+ auto* dst_nulls = nullable ? &result_nulls : nullptr;
+ if constexpr (use_dispatch) {
+ DataTypePtr nested_type = std::make_shared<DataTypeString>();
+ ASSERT_TRUE(function._execute_by_type(*source, source_offsets,
*result, result_offsets,
+ src_nulls, dst_nulls,
nested_type));
+ } else {
+ ASSERT_TRUE(function._execute_string<false>(*source,
source_offsets, *result,
+ result_offsets,
src_nulls, dst_nulls));
+ }
+
+ ASSERT_EQ(result_offsets.size(), expected.size());
+ size_t result_row = 0;
+ size_t expected_bytes = 0;
+ for (size_t row = 0; row < expected.size(); ++row) {
+ for (const auto& value : expected[row]) {
+ ASSERT_LT(result_row, result->size());
+ if (nullable) {
+ ASSERT_LT(result_row, result_nulls.size());
+ EXPECT_EQ(result_nulls[result_row], !value.has_value());
+ }
+ if (value) {
+ EXPECT_EQ(result->get_data_at(result_row).to_string(),
*value);
+ expected_bytes += value->size();
+ } else {
+ EXPECT_EQ(result->get_data_at(result_row).size, 0);
+ }
+ ++result_row;
+ }
+ EXPECT_EQ(result_offsets[row], result_row);
+ }
+ EXPECT_EQ(result->size(), result_row);
+ EXPECT_EQ(result->get_chars().size(), expected_bytes);
+ EXPECT_EQ(result_nulls.size(), nullable ? result_row : 0);
+ EXPECT_EQ(source->get_chars().size(), source_bytes);
+ for (size_t row = 0; row < source->size(); ++row) {
+ if (source_nulls[row]) {
+ EXPECT_EQ(source->get_data_at(row).to_string(), null_payload);
+ }
+ }
+ }
+
+ static void check_both_paths(const StringRows& rows, const StringRows&
expected, bool nullable,
+ const std::string& null_payload =
std::string(4096, 'x')) {
+ check_strings<true>(rows, expected, nullable, null_payload);
+ // Exercise the oversized-input fallback without allocating over 2^32
strings.
+ check_strings<false>(rows, expected, nullable, null_payload);
+ }
+};
+
+TEST_F(FunctionArrayDistinctTest, StringsPreserveFirstOccurrenceAcrossArrays) {
+ const std::string long_string(8192, 'a');
+ check_both_paths({{"b", "a", "b", "", ""},
+ {},
+ {"b", "b", "a"},
+ {"中文", "中文", "tail"},
+ {long_string, long_string, "tail"}},
+ {{"b", "a", ""}, {}, {"b", "a"}, {"中文", "tail"},
{long_string, "tail"}},
+ false);
+}
+
+TEST_F(FunctionArrayDistinctTest, NullableStringsWithHiddenPayloads) {
+ check_both_paths({{std::nullopt, "a", std::nullopt, "", "a", std::nullopt},
+ {"b", std::nullopt, "b", "c", std::nullopt},
+ {std::nullopt, std::nullopt},
+ {},
+ {"", std::nullopt}},
+ {{std::nullopt, "a", ""},
+ {"b", std::nullopt, "c"},
+ {std::nullopt},
+ {},
+ {"", std::nullopt}},
+ true);
+}
+
+TEST_F(FunctionArrayDistinctTest, NullableStringsWithEmptyNullPayloads) {
+ check_both_paths({{std::nullopt, "a", std::nullopt, "", "a"},
+ {std::nullopt, std::nullopt},
+ {"b", std::nullopt, "b"}},
+ {{std::nullopt, "a", ""}, {std::nullopt}, {"b",
std::nullopt}}, true, "");
+}
+
+TEST_F(FunctionArrayDistinctTest, EmptyStringsInput) {
+ check_both_paths({}, {}, false);
+ check_both_paths({}, {}, true);
+ check_both_paths({{}, {}}, {{}, {}}, true);
+}
+
+TEST_F(FunctionArrayDistinctTest, AllNullStringElements) {
+ check_both_paths({{std::nullopt, std::nullopt}, {}, {std::nullopt}},
+ {{std::nullopt}, {}, {std::nullopt}}, true);
+}
+
+TEST_F(FunctionArrayDistinctTest, NullableStringsWithoutNulls) {
+ check_both_paths({{"b", "a", "b"}}, {{"b", "a"}}, true);
+}
+
+TEST_F(FunctionArrayDistinctTest, NullAfterManyStrings) {
+ StringRow input;
+ for (size_t i = 0; i < 256; ++i) {
+ input.emplace_back(std::to_string(i));
+ }
+ input.emplace_back(std::nullopt);
+ check_both_paths({input}, {input}, true);
+}
+
+TEST_F(FunctionArrayDistinctTest, ManyDistinctStringsAcrossArrays) {
+ StringRow input;
+ StringRow expected;
+ for (size_t i = 0; i < 40000; ++i) {
+ auto value = std::to_string(i);
+ input.emplace_back(value);
+ input.emplace_back(value);
+ expected.emplace_back(value);
+ }
+ check_both_paths({input, {}, {"0", "0", "last"}}, {expected, {}, {"0",
"last"}}, false);
+}
+
+} // namespace doris
diff --git a/be/test/exprs/function/function_map_test.cpp
b/be/test/exprs/function/function_map_test.cpp
index d61cc4acc2d..dcf99984ce5 100644
--- a/be/test/exprs/function/function_map_test.cpp
+++ b/be/test/exprs/function/function_map_test.cpp
@@ -177,6 +177,79 @@ TEST(FunctionMapTest, deduplicate_map) {
}
}
+TEST(FunctionMapTest, map_single_pair_preserves_nulls) {
+ auto nullable_int = make_nullable(std::make_shared<DataTypeInt32>());
+ auto map_type = std::make_shared<DataTypeMap>(nullable_int, nullable_int);
+ Block block;
+ block.insert({make_nullable_int_column({1, std::nullopt, 3}),
nullable_int, "key"});
+ block.insert({make_nullable_int_column({10, 20, std::nullopt}),
nullable_int, "value"});
+ block.insert({nullptr, map_type, "result"});
+
+ auto status = execute_map_function("map", block, {0, 1}, 2, map_type);
+ ASSERT_TRUE(status.ok()) << status.to_string();
+ const auto& result = assert_cast<const
ColumnMap&>(*block.get_by_position(2).column);
+ ASSERT_EQ(result.size(), 3);
+ for (size_t row = 0; row < 3; ++row) {
+ EXPECT_EQ(result.get_offsets()[row], row + 1);
+ }
+ const auto& keys = assert_cast<const ColumnNullable&>(result.get_keys());
+ const auto& values = assert_cast<const
ColumnNullable&>(result.get_values());
+ EXPECT_TRUE(keys.is_null_at(1));
+ EXPECT_TRUE(values.is_null_at(2));
+ EXPECT_EQ(get_nullable_int(keys, 0), 1);
+ EXPECT_EQ(get_nullable_int(keys, 2), 3);
+ EXPECT_EQ(get_nullable_int(values, 0), 10);
+ EXPECT_EQ(get_nullable_int(values, 1), 20);
+}
+
+TEST(FunctionMapTest, map_single_pair_with_constant_key) {
+ auto int_type = std::make_shared<DataTypeInt32>();
+ auto nullable_int = make_nullable(int_type);
+ auto map_type = std::make_shared<DataTypeMap>(nullable_int, nullable_int);
+ auto key = ColumnInt32::create();
+ key->insert_value(7);
+ auto values = ColumnInt32::create();
+ values->insert_value(10);
+ values->insert_value(20);
+ values->insert_value(30);
+ Block block;
+ block.insert({ColumnConst::create(std::move(key), 3), int_type, "key"});
+ block.insert({std::move(values), int_type, "value"});
+ block.insert({nullptr, map_type, "result"});
+
+ auto status = execute_map_function("map", block, {0, 1}, 2, map_type);
+ ASSERT_TRUE(status.ok()) << status.to_string();
+ const auto& result = assert_cast<const
ColumnMap&>(*block.get_by_position(2).column);
+ ASSERT_EQ(result.size(), 3);
+ for (size_t row = 0; row < 3; ++row) {
+ EXPECT_EQ(result.get_offsets()[row], row + 1);
+ EXPECT_EQ(get_nullable_int(result.get_keys(), row), 7);
+ EXPECT_EQ(get_nullable_int(result.get_values(), row), (row + 1) * 10);
+ }
+}
+
+TEST(FunctionMapTest, map_multiple_pairs_still_deduplicate) {
+ auto nullable_int = make_nullable(std::make_shared<DataTypeInt32>());
+ auto map_type = std::make_shared<DataTypeMap>(nullable_int, nullable_int);
+ Block block;
+ block.insert({make_nullable_int_column({1, std::nullopt}), nullable_int,
"key1"});
+ block.insert({make_nullable_int_column({10, 20}), nullable_int, "value1"});
+ block.insert({make_nullable_int_column({1, std::nullopt}), nullable_int,
"key2"});
+ block.insert({make_nullable_int_column({30, 40}), nullable_int, "value2"});
+ block.insert({nullptr, map_type, "result"});
+
+ auto status = execute_map_function("map", block, {0, 1, 2, 3}, 4,
map_type);
+ ASSERT_TRUE(status.ok()) << status.to_string();
+ const auto& result = assert_cast<const
ColumnMap&>(*block.get_by_position(4).column);
+ ASSERT_EQ(result.size(), 2);
+ EXPECT_EQ(result.get_offsets()[0], 1);
+ EXPECT_EQ(result.get_offsets()[1], 2);
+ EXPECT_EQ(get_nullable_int(result.get_keys(), 0), 1);
+ EXPECT_TRUE(assert_cast<const
ColumnNullable&>(result.get_keys()).is_null_at(1));
+ EXPECT_EQ(get_nullable_int(result.get_values(), 0), 30);
+ EXPECT_EQ(get_nullable_int(result.get_values(), 1), 40);
+}
+
TEST(FunctionMapTest, map_from_arrays) {
auto nullable_int = make_nullable(std::make_shared<DataTypeInt32>());
auto array_type = std::make_shared<DataTypeArray>(nullable_int);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
