Skip to content
Closed
Show file tree
Hide file tree
Changes from 1 commit
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
[feature](be) Add linear file range coalescing
### What problem does this PR solve?

Issue Number: None

Related PR: #67292

Problem Summary: Read-ahead and background hole filling both need to combine sparse logical ranges into bounded physical reads. Add a pure one-pass coalescer whose contract requires validated options and sorted, disjoint, non-empty inputs. Each merge checks the maximum gap, resulting span, and cumulative read amplification. The range-size limit controls merging; an indivisible input larger than the limit remains one read.

### Release note

None

### Check List (For Author)

- Test: Unit Test
    - ./run-be-ut.sh -j100 --run '--filter=FileRangeCoalescerTest.*'
- Behavior changed: No; this commit adds an internal planning primitive.
- Does this need documentation: No
  • Loading branch information
bobhan1 committed Oct 14, 2026
commit 320ccaa05c712800c52498f8d92de47abfd8bd31
80 changes: 80 additions & 0 deletions be/src/io/fs/file_range_coalescer.cpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,80 @@
// 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 "io/fs/file_range_coalescer.h"

#include <cmath>
#include <limits>

#include "common/logging.h"

namespace doris::io {

Status FileRangeCoalesceOptions::validate() const {
if (max_range_bytes == 0) {
return Status::InvalidArgument("file range coalescing max range bytes must be positive");
}
if (!std::isfinite(max_read_amplification_ratio) || max_read_amplification_ratio < 1.0) {
return Status::InvalidArgument(
"file range coalescing read amplification ratio must be finite and at least 1");
}
return Status::OK();
}

namespace {

bool within_read_amplification(size_t range_bytes, size_t input_bytes,
double max_read_amplification_ratio) {
return static_cast<long double>(range_bytes) <=
static_cast<long double>(input_bytes) * max_read_amplification_ratio;
}

} // namespace

std::vector<FileRange> FileRangeCoalescer::coalesce(const std::vector<FileRange>& input_ranges,
const FileRangeCoalesceOptions& options) {
std::vector<FileRange> result;
result.reserve(input_ranges.size());
size_t current_input_bytes = 0;
for (const auto& range : input_ranges) {
DCHECK(range.size > 0);
DCHECK(range.offset <= std::numeric_limits<size_t>::max() - range.size);
if (result.empty()) {
result.push_back(range);
current_input_bytes = range.size;
continue;
}

auto& current = result.back();
DCHECK(current.end() <= range.offset);
const size_t gap_bytes = range.offset - current.end();
const size_t merged_bytes = range.end() - current.offset;
const size_t merged_input_bytes = current_input_bytes + range.size;
if (gap_bytes <= options.max_gap_bytes && merged_bytes <= options.max_range_bytes &&
within_read_amplification(merged_bytes, merged_input_bytes,
options.max_read_amplification_ratio)) {
current.size = merged_bytes;
current_input_bytes = merged_input_bytes;
} else {
result.push_back(range);
current_input_bytes = range.size;
}
}
return result;
}

} // namespace doris::io
62 changes: 62 additions & 0 deletions be/src/io/fs/file_range_coalescer.h
Original file line number Diff line number Diff line change
@@ -0,0 +1,62 @@
// 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.

#pragma once

#include <cstddef>
#include <vector>

#include "common/status.h"

namespace doris::io {

/// A half-open byte range [offset, offset + size) in one file.
struct FileRange {
size_t offset {0};
size_t size {0};

size_t end() const { return offset + size; }

bool operator==(const FileRange&) const = default;
};

/// Limits applied while adjacent input ranges are grouped into one physical read.
struct FileRangeCoalesceOptions {
/// Maximum unread gap that may be included between two input ranges.
size_t max_gap_bytes {0};
/// Maximum size of a combined range. One indivisible input may exceed this limit.
size_t max_range_bytes {1};
/// Maximum combined-range bytes divided by bytes covered by its input ranges.
double max_read_amplification_ratio {1.0};

/// Validate the option values independently of any input ranges.
Status validate() const;
};

/// Groups sorted file ranges without performing file IO.
class FileRangeCoalescer {
public:
/// `options` must have passed validation. Each input range must be non-empty. Input ranges
/// must be sorted by offset and mutually disjoint. Callers establish these invariants before
/// entering the hot path.
/// `max_range_bytes` limits combining multiple inputs; one indivisible input may be larger and
/// is returned unchanged.
static std::vector<FileRange> coalesce(const std::vector<FileRange>& input_ranges,
const FileRangeCoalesceOptions& options);
};

} // namespace doris::io
95 changes: 95 additions & 0 deletions be/test/io/fs/file_range_coalescer_test.cpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,95 @@
// 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 "io/fs/file_range_coalescer.h"

#include <gtest/gtest.h>

#include <vector>

namespace doris::io {
namespace {

FileRangeCoalesceOptions options(size_t max_gap_bytes, size_t max_range_bytes,
double max_read_amplification_ratio) {
return {.max_gap_bytes = max_gap_bytes,
.max_range_bytes = max_range_bytes,
.max_read_amplification_ratio = max_read_amplification_ratio};
}

FileRange file_range(size_t offset, size_t size) {
return {.offset = offset, .size = size};
}

std::vector<FileRange> coalesce(const std::vector<FileRange>& ranges,
const FileRangeCoalesceOptions& coalesce_options) {
EXPECT_TRUE(coalesce_options.validate().ok());
return FileRangeCoalescer::coalesce(ranges, coalesce_options);
}

TEST(FileRangeCoalescerTest, EmptyInputProducesEmptyOutput) {
EXPECT_TRUE(coalesce({}, options(0, 1, 1.0)).empty());
}

TEST(FileRangeCoalescerTest, AcceptsAllThreeLimitsAtTheirBoundary) {
const std::vector<FileRange> ranges {file_range(0, 32), file_range(96, 32)};
const auto result = coalesce(ranges, options(64, 128, 2.0));

ASSERT_EQ(result.size(), 1);
EXPECT_EQ(result.front(), file_range(0, 128));
}

TEST(FileRangeCoalescerTest, SplitsWhenGapExceedsLimit) {
const std::vector<FileRange> ranges {file_range(0, 32), file_range(97, 32)};
const auto result = coalesce(ranges, options(64, 1024, 4.0));

EXPECT_EQ(result, (std::vector<FileRange> {file_range(0, 32), file_range(97, 32)}));
}

TEST(FileRangeCoalescerTest, SplitsWhenRangeSpanExceedsLimit) {
const std::vector<FileRange> ranges {file_range(0, 80), file_range(100, 80)};
const auto result = coalesce(ranges, options(32, 160, 2.0));

EXPECT_EQ(result, (std::vector<FileRange> {file_range(0, 80), file_range(100, 80)}));
}

TEST(FileRangeCoalescerTest, AppliesReadAmplificationToTheWholeCandidateRange) {
const std::vector<FileRange> ranges {file_range(0, 100), file_range(150, 100),
file_range(300, 100)};
const auto result = coalesce(ranges, options(50, 1024, 1.3));

EXPECT_EQ(result, (std::vector<FileRange> {file_range(0, 250), file_range(300, 100)}));
}

TEST(FileRangeCoalescerTest, KeepsContiguousInputSplittableAtAtomicBoundaries) {
const std::vector<FileRange> ranges {file_range(0, 80), file_range(80, 80),
file_range(160, 80)};
const auto result = coalesce(ranges, options(0, 160, 1.0));

EXPECT_EQ(result, (std::vector<FileRange> {file_range(0, 160), file_range(160, 80)}));
}

TEST(FileRangeCoalescerTest, KeepsInputLargerThanMaxRangeAsOneRead) {
const std::vector<FileRange> ranges {file_range(0, 192), file_range(192, 32),
file_range(256, 32)};
const auto result = coalesce(ranges, options(64, 128, 2.0));

EXPECT_EQ(result, (std::vector<FileRange> {file_range(0, 192), file_range(192, 96)}));
}

} // namespace
} // namespace doris::io