Skip to content

Commit a92b68c

Browse files
morningmanclaude
andcommitted
[opt](fluss) Retain each log-tail key once, not once per change-log record
A tail is read as one row per change-log record, so it names each key once for every record it wrote about it -- an update alone writes two. That block is what the scan then holds for its whole life, once per bucket per partition, and what the suppression predicate builds its hash map from. Suppression asks only whether a key is in the set, so every repeat is retained and indexed for nothing. `EqualityDeletePredicate::distinct_rows` lives on the predicate rather than beside its caller because that class already owns the definition of when two key rows are the same. A caller that decided for itself could call two keys equal where the matching would not, and the row it then dropped would be a suppression that silently stops happening. The test pins the invariant directly: the predicate built from the deduplicated block answers exactly what the one built from the raw block answers, across composite keys, NULLs and hash-colliding neighbours. Deduplicated only once the tail has been read in full, never during accumulation: the limit counts change-log records, which is the yardstick the Java side applies to this very range, and a limit that counted distinct keys instead would let the two halves of one table disagree about whether the table can be read at all. The record count is kept beside the keys so the profile can report both -- `FlussUnionTailKeysRead` against the new `FlussUnionTailKeysRetained` is what says whether a scan's retention is bounded. Co-Authored-By: Claude Opus 5 (1M context) <[email protected]>
1 parent 0ff6ed4 commit a92b68c

6 files changed

Lines changed: 239 additions & 12 deletions

File tree

‎be/src/format_v2/expr/equality_delete_predicate.cpp‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,9 @@
2020
#include <gen_cpp/Exprs_types.h>
2121

2222
#include <algorithm>
23+
#include <unordered_map>
2324
#include <utility>
25+
#include <vector>
2426

2527
#include "common/status.h"
2628
#include "core/assert_cast.h"
@@ -214,6 +216,44 @@ bool EqualityDeletePredicate::_equal(const Block& data_block, size_t data_row,
214216
return true;
215217
}
216218

219+
Block EqualityDeletePredicate::distinct_rows(const Block& keys) {
220+
const size_t rows = keys.rows();
221+
if (rows <= 1) {
222+
return keys;
223+
}
224+
const auto hashes = _build_hashes(keys);
225+
// Grouped by the same hash the matching uses, then settled by the same comparison: a hash collision
226+
// must not be allowed to drop a key that is merely similar to one already kept.
227+
std::unordered_map<uint64_t, std::vector<size_t>> kept_by_hash;
228+
kept_by_hash.reserve(rows);
229+
IColumn::Filter keep(rows, 0);
230+
size_t distinct = 0;
231+
for (size_t row = 0; row < rows; ++row) {
232+
auto& candidates = kept_by_hash[hashes[row]];
233+
const bool duplicate = std::ranges::any_of(candidates, [&](size_t candidate) {
234+
for (size_t column_idx = 0; column_idx < keys.columns(); ++column_idx) {
235+
const auto& column = keys.get_by_position(column_idx).column;
236+
if (!column_value_equal(column, row, column, candidate)) {
237+
return false;
238+
}
239+
}
240+
return true;
241+
});
242+
if (!duplicate) {
243+
candidates.push_back(row);
244+
keep[row] = 1;
245+
++distinct;
246+
}
247+
}
248+
if (distinct == rows) {
249+
// Nothing to drop, and filtering would copy every column to say so.
250+
return keys;
251+
}
252+
Block distinct_block = keys;
253+
Block::filter_block_internal(&distinct_block, keep);
254+
return distinct_block;
255+
}
256+
217257
std::string EqualityDeletePredicate::debug_string() const {
218258
return _expr_name;
219259
}

‎be/src/format_v2/expr/equality_delete_predicate.h‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,17 @@ class EqualityDeletePredicate final : public VExpr {
5555
uint64_t get_digest(uint64_t seed) const override { return 0; }
5656
const std::string& expr_name() const override { return _expr_name; }
5757

58+
/**
59+
* The distinct rows of a key block, by the same equality this predicate matches with.
60+
*
61+
* <p>Which is why it lives here rather than beside its caller: a caller that decided for itself when
62+
* two keys are the same could call two of them equal where this class would not, and the row it then
63+
* dropped would be a suppression the predicate no longer performs. Building a predicate from the
64+
* result answers exactly what building it from the input would -- a delete set is a set -- while the
65+
* hash map it carries, and any cache holding the block, shrink by whatever the duplicates were.
66+
*/
67+
static Block distinct_rows(const Block& keys);
68+
5869
private:
5970
static std::vector<uint64_t> _build_hashes(const Block& block);
6071
ColumnPtr _evaluate_key_block(const Block& data_key_block) const;

‎be/src/format_v2/table/fluss_union_lake_reader.cpp‎

Lines changed: 15 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -246,6 +246,10 @@ void FlussUnionLakeReader::_init_union_profile() {
246246
_scanner_profile, "FlussUnionSuppressedRows", TUnit::UNIT, table_profile, 1);
247247
_tail_keys_read_counter = ADD_CHILD_COUNTER_WITH_LEVEL(
248248
_scanner_profile, "FlussUnionTailKeysRead", TUnit::UNIT, table_profile, 1);
249+
// Change-log records read against distinct keys retained: the second is what the scan holds for its
250+
// whole life, once per bucket per partition, so the two apart are what says whether it is bounded.
251+
_tail_keys_retained_counter = ADD_CHILD_COUNTER_WITH_LEVEL(
252+
_scanner_profile, "FlussUnionTailKeysRetained", TUnit::UNIT, table_profile, 1);
249253
_tail_cache_hit_counter = ADD_CHILD_COUNTER_WITH_LEVEL(
250254
_scanner_profile, "FlussUnionTailCacheHitCount", TUnit::UNIT, table_profile, 1);
251255
}
@@ -307,7 +311,7 @@ Status FlussUnionLakeReader::_load_suppression_keys(const format::SplitReadOptio
307311
cache_key,
308312
[&]() -> SuppressionKeys* {
309313
auto keys = std::make_unique<SuppressionKeys>();
310-
read_status = _read_tail_keys(tail, &keys->keys);
314+
read_status = _read_tail_keys(tail, keys.get());
311315
if (!read_status.ok()) {
312316
return nullptr;
313317
}
@@ -319,7 +323,8 @@ Status FlussUnionLakeReader::_load_suppression_keys(const format::SplitReadOptio
319323
if (cache_hit) {
320324
update_counter(_tail_cache_hit_counter, 1);
321325
} else {
322-
update_counter(_tail_keys_read_counter, cast_set<int64_t>(cached->keys.rows()));
326+
update_counter(_tail_keys_read_counter, cached->records);
327+
update_counter(_tail_keys_retained_counter, cast_set<int64_t>(cached->keys.rows()));
323328
}
324329
return _build_suppression_predicate(cached->keys);
325330
}
@@ -333,7 +338,7 @@ Block FlussUnionLakeReader::_empty_key_block() const {
333338
}
334339

335340
Status FlussUnionLakeReader::_accumulate_tail_keys(const Tail& tail, const NextBatch& next_batch,
336-
Block* keys) {
341+
SuppressionKeys* keys) {
337342
auto builder = MutableBlock::build_mutable_block(_empty_key_block());
338343
Block batch = _empty_key_block();
339344
while (true) {
@@ -357,13 +362,18 @@ Status FlussUnionLakeReader::_accumulate_tail_keys(const Tail& tail, const NextB
357362
}
358363
}
359364
if (eos) {
360-
*keys = builder.to_block();
365+
// Deduplicated only here, never during accumulation: the limit above counts change-log
366+
// records, which is the yardstick the Java side applies to this very range, and a limit
367+
// that counted distinct keys instead would let the two halves of one table disagree about
368+
// whether the table can be read at all.
369+
keys->records = cast_set<int64_t>(builder.rows());
370+
keys->keys = EqualityDeletePredicate::distinct_rows(builder.to_block());
361371
return Status::OK();
362372
}
363373
}
364374
}
365375

366-
Status FlussUnionLakeReader::_read_tail_keys(const Tail& tail, Block* keys) {
376+
Status FlussUnionLakeReader::_read_tail_keys(const Tail& tail, SuppressionKeys* keys) {
367377
DORIS_CHECK(keys != nullptr);
368378
#ifdef BE_TEST
369379
if (_test_tail_reader) {

‎be/src/format_v2/table/fluss_union_lake_reader.h‎

Lines changed: 14 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -74,11 +74,19 @@ class FlussUnionLakeReader final : public format::TableReader {
7474
};
7575

7676
/**
77-
* The keys of one bucket's log tail, one row per change-log record and one column per key
78-
* column. Held by the scan node's split cache so every split of that bucket shares one read.
77+
* The DISTINCT keys of one bucket's log tail, one column per key column. Held by the scan node's
78+
* split cache so every split of that bucket shares one read.
79+
*
80+
* <p>Distinct rather than one row per change-log record, which is what the tail is read as: a tail
81+
* names each key it touched once for every record it wrote about it, an update alone writes two,
82+
* and suppression asks only whether a key is in the set. What is retained for the life of the scan
83+
* therefore has no reason to carry the repeats -- and the scan retains one of these per bucket per
84+
* partition it reads, all of them at once.
7985
*/
8086
struct SuppressionKeys {
8187
Block keys;
88+
/** Change-log records those keys came from, for the profile: kept so the ratio is visible. */
89+
int64_t records = 0;
8290
};
8391

8492
~FlussUnionLakeReader() override = default;
@@ -110,8 +118,9 @@ class FlussUnionLakeReader final : public format::TableReader {
110118
Status _resolve_union_properties();
111119
Status _prepare_suppression(const format::SplitReadOptions& options);
112120
Status _load_suppression_keys(const format::SplitReadOptions& options, const Tail& tail);
113-
Status _accumulate_tail_keys(const Tail& tail, const NextBatch& next_batch, Block* keys);
114-
Status _read_tail_keys(const Tail& tail, Block* keys);
121+
Status _accumulate_tail_keys(const Tail& tail, const NextBatch& next_batch,
122+
SuppressionKeys* keys);
123+
Status _read_tail_keys(const Tail& tail, SuppressionKeys* keys);
115124
Status _build_suppression_predicate(const Block& keys);
116125
Status _suppress(Block* block);
117126
Block _empty_key_block() const;
@@ -131,6 +140,7 @@ class FlussUnionLakeReader final : public format::TableReader {
131140

132141
RuntimeProfile::Counter* _suppressed_rows_counter = nullptr;
133142
RuntimeProfile::Counter* _tail_keys_read_counter = nullptr;
143+
RuntimeProfile::Counter* _tail_keys_retained_counter = nullptr;
134144
RuntimeProfile::Counter* _tail_cache_hit_counter = nullptr;
135145

136146
#ifdef BE_TEST

‎be/test/format_v2/expr/equality_delete_predicate_test.cpp‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -183,6 +183,87 @@ TEST_F(EqualityDeletePredicateTest, MatchAfterCastToDeleteKeyType) {
183183
context->close();
184184
}
185185

186+
// A delete set is a set, so the repeats a caller happens to hand over cost memory and hash-map entries
187+
// without changing a single answer.
188+
TEST_F(EqualityDeletePredicateTest, DistinctRowsKeepsOneOfEachRepeatedKey) {
189+
Block keys;
190+
keys.insert(make_nullable_int_column("id", {1, 2, 1, 1, 3, 2}));
191+
192+
const Block distinct = EqualityDeletePredicate::distinct_rows(keys);
193+
194+
ASSERT_EQ(distinct.rows(), 3);
195+
// First occurrence wins, so the surviving order is the order they were first named in.
196+
Block data_block;
197+
data_block.insert(make_nullable_int_column("id", {1, 2, 3, 4}));
198+
int result_column_id = -1;
199+
auto status = execute_equality_delete_predicate(distinct, {1}, &data_block, &result_column_id);
200+
ASSERT_TRUE(status.ok()) << status;
201+
EXPECT_EQ(result_column_data(data_block, result_column_id), std::vector<UInt8>({1, 1, 1, 0}));
202+
}
203+
204+
// The invariant the whole thing rests on: whatever a caller deduplicates with this, the predicate it
205+
// then builds answers exactly what the predicate built from the raw block answers. A dedup that called
206+
// two keys the same where the matching would not would silently stop deleting one of them.
207+
TEST_F(EqualityDeletePredicateTest, DistinctRowsAnswersWhatTheRawBlockAnswers) {
208+
// Composite, nullable, with repeats that agree on one column only -- and a NULL named twice, which
209+
// matching treats as one value and so must dedup as one value.
210+
const auto ids = std::vector<std::optional<int>> {1, 1, 2, 1, std::nullopt, std::nullopt, 2};
211+
const auto names =
212+
std::vector<std::optional<std::string>> {"a", "b", "a", "a", "z", "z", std::nullopt};
213+
const auto make_keys = [&]() {
214+
Block keys;
215+
keys.insert(make_nullable_int_column("id", ids));
216+
keys.insert(make_nullable_string_column("name", names));
217+
return keys;
218+
};
219+
const auto make_data = [&]() {
220+
Block data_block;
221+
data_block.insert(
222+
make_nullable_int_column("id", {1, 1, 2, std::nullopt, std::nullopt, 2, 3}));
223+
data_block.insert(
224+
make_nullable_string_column("name", {"a", "c", "a", "z", "y", std::nullopt, "a"}));
225+
return data_block;
226+
};
227+
228+
const Block distinct = EqualityDeletePredicate::distinct_rows(make_keys());
229+
EXPECT_EQ(distinct.rows(), 5) << "expected only the exact repeats to be dropped";
230+
231+
Block raw_data = make_data();
232+
int raw_result = -1;
233+
ASSERT_TRUE(
234+
execute_equality_delete_predicate(make_keys(), {1, 2}, &raw_data, &raw_result).ok());
235+
236+
Block distinct_data = make_data();
237+
int distinct_result = -1;
238+
ASSERT_TRUE(
239+
execute_equality_delete_predicate(distinct, {1, 2}, &distinct_data, &distinct_result)
240+
.ok());
241+
242+
EXPECT_EQ(result_column_data(distinct_data, distinct_result),
243+
result_column_data(raw_data, raw_result));
244+
// Pinned, so that "they agree" cannot become "they agree on nothing at all".
245+
EXPECT_EQ(result_column_data(raw_data, raw_result), std::vector<UInt8>({1, 0, 1, 1, 0, 1, 0}));
246+
}
247+
248+
// Nothing to drop must not cost a copy of every column, and the degenerate sizes must not need a
249+
// special case at every call site.
250+
TEST_F(EqualityDeletePredicateTest, DistinctRowsPassesThroughWhenThereAreNoRepeats) {
251+
Block empty;
252+
empty.insert(make_nullable_int_column("id", {}));
253+
EXPECT_EQ(EqualityDeletePredicate::distinct_rows(empty).rows(), 0);
254+
255+
Block one;
256+
one.insert(make_nullable_int_column("id", {7}));
257+
EXPECT_EQ(EqualityDeletePredicate::distinct_rows(one).rows(), 1);
258+
259+
Block all_distinct;
260+
all_distinct.insert(make_nullable_int_column("id", {3, 1, 2}));
261+
const Block result = EqualityDeletePredicate::distinct_rows(all_distinct);
262+
ASSERT_EQ(result.rows(), 3);
263+
EXPECT_EQ(result.get_by_position(0).column.get(), all_distinct.get_by_position(0).column.get())
264+
<< "a block with no repeats should be returned as-is, not rebuilt";
265+
}
266+
186267
TEST_F(EqualityDeletePredicateTest, ChildCountMismatchReturnsError) {
187268
Block delete_block;
188269
delete_block.insert(make_nullable_int_column("id", {1}));

‎be/test/format_v2/table/fluss_union_lake_reader_test.cpp‎

Lines changed: 78 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -182,6 +182,16 @@ std::vector<int32_t> ids_of(const Block& block) {
182182
return ids;
183183
}
184184

185+
// The second key column, for the cases where the first one alone cannot tell two keys apart.
186+
std::vector<std::string> names_of(const Block& block) {
187+
std::vector<std::string> names;
188+
const auto& column = assert_cast<const ColumnString&>(*block.get_by_position(1).column);
189+
for (size_t row = 0; row < column.size(); ++row) {
190+
names.emplace_back(column.get_data_at(row).to_string());
191+
}
192+
return names;
193+
}
194+
185195
// ------------------------------------------------------------------ the tail descriptor
186196

187197
// The four fields are how a split says which slice of which bucket's log may contradict it. A tail
@@ -481,7 +491,39 @@ TEST(FlussUnionLakeReaderTest, AccumulatesATailThatArrivesInSeveralBatches) {
481491
std::vector<Block> batches {make_key_block({1}, {"a"}), make_key_block({}, {}),
482492
make_key_block({3}, {"c"})};
483493
size_t delivered = 0;
484-
Block keys;
494+
FlussUnionLakeReader::SuppressionKeys keys;
495+
ASSERT_TRUE(reader._accumulate_tail_keys(
496+
tail,
497+
[&](Block* batch, bool* eos) {
498+
if (delivered < batches.size()) {
499+
*batch = batches[delivered++];
500+
}
501+
*eos = delivered >= batches.size();
502+
return Status::OK();
503+
},
504+
&keys)
505+
.ok());
506+
EXPECT_EQ(keys.keys.rows(), 2);
507+
EXPECT_EQ(keys.records, 2);
508+
EXPECT_EQ(ids_of(keys.keys), (std::vector<int32_t> {1, 3}));
509+
}
510+
511+
// A tail names a key once per record it wrote about it -- an update alone writes two -- and what the
512+
// scan then holds for its whole life, once per bucket per partition, is that block. Suppression asks
513+
// only whether a key is in the set, so the repeats are retained for nothing. The record count is kept
514+
// beside them because it, not the retained size, is what the limit counts.
515+
TEST(FlussUnionLakeReaderTest, RetainsEachTailKeyOnceHoweverOftenTheTailNamesIt) {
516+
FlussUnionLakeReader reader;
517+
auto scan_params = union_scan_params();
518+
ASSERT_TRUE(init_reader(&reader, &scan_params).ok());
519+
Tail tail;
520+
ASSERT_TRUE(FlussUnionLakeReader::parse_tail(":0:10:20", &tail).ok());
521+
522+
// Key 1 updated twice (four change-log records), key 3 written once.
523+
std::vector<Block> batches {make_key_block({1, 1}, {"a", "a"}),
524+
make_key_block({1, 1, 3}, {"a", "a", "c"})};
525+
size_t delivered = 0;
526+
FlussUnionLakeReader::SuppressionKeys keys;
485527
ASSERT_TRUE(reader._accumulate_tail_keys(
486528
tail,
487529
[&](Block* batch, bool* eos) {
@@ -493,8 +535,41 @@ TEST(FlussUnionLakeReaderTest, AccumulatesATailThatArrivesInSeveralBatches) {
493535
},
494536
&keys)
495537
.ok());
496-
EXPECT_EQ(keys.rows(), 2);
497-
EXPECT_EQ(ids_of(keys), (std::vector<int32_t> {1, 3}));
538+
539+
EXPECT_EQ(keys.records, 5);
540+
EXPECT_EQ(keys.keys.rows(), 2);
541+
EXPECT_EQ(ids_of(keys.keys), (std::vector<int32_t> {1, 3}));
542+
}
543+
544+
// Only whole key rows are duplicates. A dedup that compared the first key column alone would collapse
545+
// two different composite keys into one, and every lake row carrying the one it dropped would survive
546+
// a suppression that was supposed to remove it.
547+
TEST(FlussUnionLakeReaderTest, KeysThatShareOnlyPartOfACompositeKeyAreBothRetained) {
548+
FlussUnionLakeReader reader;
549+
auto scan_params = union_scan_params();
550+
ASSERT_TRUE(init_reader(&reader, &scan_params).ok());
551+
Tail tail;
552+
ASSERT_TRUE(FlussUnionLakeReader::parse_tail(":0:10:20", &tail).ok());
553+
554+
std::vector<Block> batches {make_key_block({1, 1, 1}, {"a", "b", "a"})};
555+
size_t delivered = 0;
556+
FlussUnionLakeReader::SuppressionKeys keys;
557+
ASSERT_TRUE(reader._accumulate_tail_keys(
558+
tail,
559+
[&](Block* batch, bool* eos) {
560+
if (delivered < batches.size()) {
561+
*batch = batches[delivered++];
562+
}
563+
*eos = delivered >= batches.size();
564+
return Status::OK();
565+
},
566+
&keys)
567+
.ok());
568+
569+
EXPECT_EQ(keys.records, 3);
570+
EXPECT_EQ(keys.keys.rows(), 2);
571+
EXPECT_EQ(ids_of(keys.keys), (std::vector<int32_t> {1, 1}));
572+
EXPECT_EQ(names_of(keys.keys), (std::vector<std::string> {"a", "b"}));
498573
}
499574

500575
// A split that says nothing about which tail supersedes it cannot be read: reading it as-is returns

0 commit comments

Comments
 (0)