Skip to content

Commit 3adf7b3

Browse files
authored
feat: add deletion vector support with bitmap implementation and index file I/O (alibaba#69)
1 parent 6a658f6 commit 3adf7b3

20 files changed

Lines changed: 2282 additions & 0 deletions
Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
/*
2+
* Licensed to the Apache Software Foundation (ASF) under one
3+
* or more contributor license agreements. See the NOTICE file
4+
* distributed with this work for additional information
5+
* regarding copyright ownership. The ASF licenses this file
6+
* to you under the Apache License, Version 2.0 (the
7+
* "License"); you may not use this file except in compliance
8+
* with the License. You may obtain a copy of the License at
9+
*
10+
* http://www.apache.org/licenses/LICENSE-2.0
11+
*
12+
* Unless required by applicable law or agreed to in writing,
13+
* software distributed under the License is distributed on an
14+
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15+
* KIND, either express or implied. See the License for the
16+
* specific language governing permissions and limitations
17+
* under the License.
18+
*/
19+
#pragma once
20+
#include <cassert>
21+
#include <cstdint>
22+
#include <memory>
23+
#include <utility>
24+
25+
#include "arrow/c/abi.h"
26+
#include "arrow/c/bridge.h"
27+
#include "arrow/c/helpers.h"
28+
#include "paimon/common/reader/reader_utils.h"
29+
#include "paimon/core/deletionvectors/deletion_vector.h"
30+
#include "paimon/memory/memory_pool.h"
31+
#include "paimon/reader/file_batch_reader.h"
32+
#include "paimon/result.h"
33+
#include "paimon/status.h"
34+
#include "paimon/utils/roaring_bitmap32.h"
35+
36+
namespace paimon {
37+
class Metrics;
38+
39+
class ApplyDeletionVectorBatchReader : public FileBatchReader {
40+
public:
41+
ApplyDeletionVectorBatchReader(std::unique_ptr<FileBatchReader>&& reader,
42+
const std::shared_ptr<DeletionVector>& deletion_vector)
43+
: reader_(std::move(reader)), deletion_vector_(deletion_vector) {
44+
assert(reader_);
45+
}
46+
47+
Result<ReadBatch> NextBatch() override {
48+
return Status::Invalid(
49+
"paimon inner reader ApplyDeletionVectorBatchReader should use NextBatchWithBitmap");
50+
}
51+
52+
Result<ReadBatchWithBitmap> NextBatchWithBitmap() override {
53+
while (true) {
54+
PAIMON_ASSIGN_OR_RAISE(ReadBatchWithBitmap batch_with_bitmap,
55+
reader_->NextBatchWithBitmap());
56+
if (BatchReader::IsEofBatch(batch_with_bitmap)) {
57+
return batch_with_bitmap;
58+
}
59+
auto& [batch, bitmap] = batch_with_bitmap;
60+
PAIMON_ASSIGN_OR_RAISE(RoaringBitmap32 valid_bitmap, Filter(batch.first->length));
61+
bitmap &= valid_bitmap;
62+
if (bitmap.IsEmpty()) {
63+
ReaderUtils::ReleaseReadBatch(std::move(batch));
64+
continue;
65+
}
66+
return batch_with_bitmap;
67+
}
68+
}
69+
70+
void Close() override {
71+
return reader_->Close();
72+
}
73+
74+
std::shared_ptr<Metrics> GetReaderMetrics() const override {
75+
return reader_->GetReaderMetrics();
76+
}
77+
78+
Result<std::unique_ptr<::ArrowSchema>> GetFileSchema() const override {
79+
return reader_->GetFileSchema();
80+
}
81+
82+
Status SetReadSchema(::ArrowSchema* read_schema, const std::shared_ptr<Predicate>& predicate,
83+
const std::optional<RoaringBitmap32>& selection_bitmap) override {
84+
return Status::Invalid("ApplyDeletionVectorBatchReader does not support SetReadSchema");
85+
}
86+
87+
Result<uint64_t> GetPreviousBatchFirstRowNumber() const override {
88+
return reader_->GetPreviousBatchFirstRowNumber();
89+
}
90+
91+
Result<uint64_t> GetNumberOfRows() const override {
92+
return reader_->GetNumberOfRows();
93+
}
94+
95+
bool SupportPreciseBitmapSelection() const override {
96+
return reader_->SupportPreciseBitmapSelection();
97+
}
98+
99+
private:
100+
Result<RoaringBitmap32> Filter(int32_t batch_size) const {
101+
PAIMON_ASSIGN_OR_RAISE(uint64_t previous_batch_first_row_number,
102+
reader_->GetPreviousBatchFirstRowNumber());
103+
return deletion_vector_->IsValid(previous_batch_first_row_number, batch_size);
104+
}
105+
106+
private:
107+
std::unique_ptr<FileBatchReader> reader_;
108+
std::shared_ptr<DeletionVector> deletion_vector_;
109+
};
110+
} // namespace paimon
Lines changed: 169 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,169 @@
1+
/*
2+
* Licensed to the Apache Software Foundation (ASF) under one
3+
* or more contributor license agreements. See the NOTICE file
4+
* distributed with this work for additional information
5+
* regarding copyright ownership. The ASF licenses this file
6+
* to you under the Apache License, Version 2.0 (the
7+
* "License"); you may not use this file except in compliance
8+
* with the License. You may obtain a copy of the License at
9+
*
10+
* http://www.apache.org/licenses/LICENSE-2.0
11+
*
12+
* Unless required by applicable law or agreed to in writing,
13+
* software distributed under the License is distributed on an
14+
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15+
* KIND, either express or implied. See the License for the
16+
* specific language governing permissions and limitations
17+
* under the License.
18+
*/
19+
#include "paimon/core/deletionvectors/apply_deletion_vector_batch_reader.h"
20+
21+
#include <string>
22+
#include <vector>
23+
24+
#include "arrow/api.h"
25+
#include "arrow/array/array_nested.h"
26+
#include "arrow/ipc/json_simple.h"
27+
#include "gtest/gtest.h"
28+
#include "paimon/common/reader/prefetch_file_batch_reader_impl.h"
29+
#include "paimon/executor.h"
30+
#include "paimon/testing/mock/mock_file_batch_reader.h"
31+
#include "paimon/testing/mock/mock_file_system.h"
32+
#include "paimon/testing/mock/mock_format_reader_builder.h"
33+
#include "paimon/testing/utils/read_result_collector.h"
34+
#include "paimon/testing/utils/testharness.h"
35+
#include "paimon/utils/read_ahead_cache.h"
36+
37+
namespace arrow {
38+
class Array;
39+
} // namespace arrow
40+
namespace paimon {
41+
class FileSystem;
42+
} // namespace paimon
43+
44+
namespace paimon::test {
45+
class ApplyDeletionVectorBatchReaderTest : public ::testing::Test,
46+
public ::testing::WithParamInterface<bool> {
47+
public:
48+
void SetUp() override {
49+
int_type_ = arrow::int32();
50+
target_type_ = arrow::struct_({arrow::field("f1", int_type_)});
51+
52+
pool_ = GetDefaultPool();
53+
fs_ = std::make_shared<MockFileSystem>();
54+
executor_ = CreateDefaultExecutor(/*thread_count=*/2);
55+
}
56+
void TearDown() override {}
57+
58+
void CheckResult(BatchReader* apply_dv_batch_reader,
59+
const std::shared_ptr<arrow::ChunkedArray>& expected_chunk_array) {
60+
ASSERT_OK_AND_ASSIGN(auto result_chunk_array,
61+
ReadResultCollector::CollectResult(apply_dv_batch_reader));
62+
if (expected_chunk_array) {
63+
ASSERT_EQ(expected_chunk_array->length(), result_chunk_array->length());
64+
ASSERT_TRUE(expected_chunk_array->Equals(result_chunk_array));
65+
} else {
66+
ASSERT_FALSE(result_chunk_array);
67+
}
68+
}
69+
70+
void CheckResult(const std::string& data_str, const std::vector<char>& dv_data,
71+
const std::string& expected_str) {
72+
auto f1 = arrow::ipc::internal::json::ArrayFromJSON(int_type_, data_str).ValueOrDie();
73+
std::shared_ptr<arrow::Array> data =
74+
arrow::StructArray::Make({f1}, target_type_->fields()).ValueOrDie();
75+
76+
int32_t prefetch_batch_count = 3;
77+
for (int32_t batch_size : {1, 2, 4, 10}) {
78+
auto dv = DeletionVector::FromPrimitiveArray(dv_data, pool_.get());
79+
std::unique_ptr<FileBatchReader> file_batch_reader;
80+
bool enable_prefetch = GetParam();
81+
if (enable_prefetch) {
82+
MockFormatReaderBuilder reader_builder(data, target_type_, batch_size);
83+
ASSERT_OK_AND_ASSIGN(
84+
file_batch_reader,
85+
PrefetchFileBatchReaderImpl::Create(
86+
/*data_file_path=*/"DUMMY", &reader_builder, fs_, prefetch_batch_count,
87+
batch_size, prefetch_batch_count * 2,
88+
/*enable_adaptive_prefetch_strategy=*/false, executor_,
89+
/*initialize_read_ranges=*/true,
90+
/*prefetch_cache_mode=*/PrefetchCacheMode::ALWAYS, CacheConfig(), pool_));
91+
} else {
92+
file_batch_reader =
93+
std::make_unique<MockFileBatchReader>(data, target_type_, batch_size);
94+
}
95+
auto apply_dv_batch_reader = std::make_unique<ApplyDeletionVectorBatchReader>(
96+
std::move(file_batch_reader), std::move(dv));
97+
if (expected_str.empty()) {
98+
CheckResult(apply_dv_batch_reader.get(), nullptr);
99+
} else {
100+
auto expected =
101+
arrow::ipc::internal::json::ArrayFromJSON(int_type_, expected_str).ValueOrDie();
102+
std::shared_ptr<arrow::Array> expect_array =
103+
arrow::StructArray::Make({expected}, target_type_->fields()).ValueOrDie();
104+
auto expected_chunk_array = std::make_shared<arrow::ChunkedArray>(expect_array);
105+
CheckResult(apply_dv_batch_reader.get(), expected_chunk_array);
106+
}
107+
auto read_metrics = apply_dv_batch_reader->GetReaderMetrics();
108+
ASSERT_TRUE(read_metrics);
109+
apply_dv_batch_reader->Close();
110+
}
111+
}
112+
113+
private:
114+
std::shared_ptr<arrow::DataType> int_type_;
115+
std::shared_ptr<arrow::DataType> target_type_;
116+
std::shared_ptr<MemoryPool> pool_;
117+
std::shared_ptr<FileSystem> fs_;
118+
std::shared_ptr<Executor> executor_;
119+
};
120+
121+
TEST_P(ApplyDeletionVectorBatchReaderTest, TestSimple) {
122+
std::string data_str = "[10, 11, 12, 13]";
123+
{
124+
std::vector<char> dv_data = {0, 1, 1, 0};
125+
CheckResult(data_str, dv_data, "[10, 13]");
126+
}
127+
{
128+
std::vector<char> dv_data = {1, 0, 0, 1};
129+
CheckResult(data_str, dv_data, "[11, 12]");
130+
}
131+
{
132+
std::vector<char> dv_data = {1, 1, 1, 1};
133+
// empty result
134+
CheckResult(data_str, dv_data, "");
135+
}
136+
{
137+
std::vector<char> dv_data = {0, 0, 0, 0};
138+
CheckResult(data_str, dv_data, "[10, 11, 12, 13]");
139+
}
140+
}
141+
142+
TEST_P(ApplyDeletionVectorBatchReaderTest, TestSimple2) {
143+
std::string data_str = "[10, 11, 12, 13, 14, 15, 16]";
144+
{
145+
std::vector<char> dv_data = {0, 1, 1, 0, 1, 0, 0};
146+
CheckResult(data_str, dv_data, "[10, 13, 15, 16]");
147+
}
148+
{
149+
std::vector<char> dv_data = {0, 1, 1, 0, 0, 0, 1};
150+
CheckResult(data_str, dv_data, "[10, 13, 14, 15]");
151+
}
152+
{
153+
std::vector<char> dv_data = {1, 1, 1, 1, 0, 0, 1};
154+
CheckResult(data_str, dv_data, "[14, 15]");
155+
}
156+
157+
{
158+
std::vector<char> dv_data = {1, 1, 1, 1, 1, 1, 1};
159+
// empty result
160+
CheckResult(data_str, dv_data, "");
161+
}
162+
{
163+
std::vector<char> dv_data = {0, 0, 0, 0, 0, 0, 0};
164+
CheckResult(data_str, dv_data, "[10, 11, 12, 13, 14, 15, 16]");
165+
}
166+
}
167+
INSTANTIATE_TEST_SUITE_P(EnablePrefetch, ApplyDeletionVectorBatchReaderTest,
168+
::testing::Values(false, true));
169+
} // namespace paimon::test
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/*
2+
* Licensed to the Apache Software Foundation (ASF) under one
3+
* or more contributor license agreements. See the NOTICE file
4+
* distributed with this work for additional information
5+
* regarding copyright ownership. The ASF licenses this file
6+
* to you under the Apache License, Version 2.0 (the
7+
* "License"); you may not use this file except in compliance
8+
* with the License. You may obtain a copy of the License at
9+
*
10+
* http://www.apache.org/licenses/LICENSE-2.0
11+
*
12+
* Unless required by applicable law or agreed to in writing,
13+
* software distributed under the License is distributed on an
14+
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15+
* KIND, either express or implied. See the License for the
16+
* specific language governing permissions and limitations
17+
* under the License.
18+
*/
19+
#pragma once
20+
21+
#include "paimon/core/deletionvectors/deletion_vector.h"
22+
23+
namespace paimon {
24+
25+
class Bitmap64DeletionVector : public DeletionVector {
26+
public:
27+
static constexpr int32_t MAGIC_NUMBER = 1681511377;
28+
};
29+
30+
} // namespace paimon

0 commit comments

Comments
 (0)