Address review comments on apache#11235

Co-Authored-By: Claude Opus 5.5 <[email protected]>

# Which issue does this PR close?

- Part of apache#11234.

# Rationale for this change

`ParquetPushDecoder` keeps the pushed buffers in a `PushBuffers` list.
Each lookup scans the full list. If a caller pushes one buffer per
requested range (one per column chunk, or one per page), the work for
one row group grows with the square of the number of buffers. The
existing `push_decoder` benchmark shows this for wide files:

| Benchmark (`benches/push_decoder.rs`) | `main` | This PR | Speedup,
run 1 / run 2 | Control (`main` vs `main`) |
|---|---:|---:|---:|---:|
| `Nbuf/100000ranges` | 893 ms | 58 ms | 15.4× / 14.6× | 1.03 |
| `Nbuf/10000ranges` | 13.0 ms | 5.5 ms | 2.4× / 2.3× | 1.02 |
| `Nbuf/1000ranges` | 581 µs | 541 µs | 1.07× / 1.05× | 1.01 |
| `1buf/*` (one pushed buffer) | | | no change (±2%) | ±6% |

(`Nbuf`: one pushed buffer per column chunk. Benchmark bot runs: [run
1](apache#11237 (comment)),
[run
2](apache#11237 (comment)),
[control](apache#11237 (comment)),
which compares `main` with itself to show the noise.)

The batch mode of apache#11234 pushes
one buffer per page, which makes the list much longer.

# What changes are included in this PR?

`PushBuffers` keeps its buffers sorted by start offset, so a lookup is a
binary search plus a short backward scan. Pushed buffers can still
overlap. Removing buffers keeps the maximum buffer length exact, so a
large buffer that was removed does not slow down later lookups.

This PR is independent of apache#11235,
which also changes `push_buffers.rs`. The PR that merges second gets a
small rebase. A `max_len` that is too large is still correct (lookups
only scan further), so the rebase updates `max_len` in `release_ranges`
for performance, not for correctness.

# Are these changes tested?

Yes. Unit tests for out-of-order pushes, overlapping pushes, and
`clear_ranges`, and a randomized test (200 seeds) that compares pushes,
clears and lookups with a full scan and checks the sort order and the
maximum length.

# Are there any user-facing changes?

No.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

---------

Co-authored-by: Claude Opus 5.5 <[email protected]>

…of the buffer count (apache#11459)

# Which issue does this PR close?

- Closes apache#11458.

Follow-up to apache#11235, which is
merged. This PR has four commits:

1.
apache@8087cef
(new `push_decoder/prefetch` benchmark)
2.
apache@c0857e7
(binary search in `release_ranges`)
3.
apache@04faa64
(binary search in `clear_ranges`)
4.
apache@8b98d70
(`VecDeque` and `max_len_count`)

# Rationale for this change

When a caller pushes many buffers before the decoder reads them (for
example, read-ahead for many row groups), the push decoder pays
`O(buffers)` for each row group. Thus, the full scan is quadratic.

The new `push_decoder/prefetch` benchmark shows this. It pushes one
buffer for each column chunk of the file, then builds all row group
readers. Time for each iteration on the GKE runner:

| Buffers | Before | After | Change |
|--|--|--|--|
| 1,000 | 1.12 ms | 0.60 ms | 1.9x faster |
| 10,000 | 56.6 ms | 6.3 ms | 9x faster |
| 30,000 | 478 ms | 19.2 ms | 25x faster |

After this PR, the time is linear in the number of buffers.

The cost: the `VecDeque` commit makes the existing `push_decoder/1buf`
and `push_decoder/Nbuf` cases 1% to 6% slower, because an index into a
`VecDeque` costs more than an index into a `Vec`. Those cases hold few
buffers at a time, so they get no gain from this PR.

# What changes are included in this PR?

For each row group, the decoder calls `clear_ranges` and then
`release_ranges`. Each call visited all buffers:

```diff
 for each row group
   clear_ranges(requested ranges)
-    rebuild all buffers, keep those that are not requested
-    scan all buffers for max_len
+    binary search for the buffers that start at each requested range
+    remove them, move no other buffer (VecDeque)
+    scan for max_len only if no buffer of that length remains
   release_ranges(column chunk ranges)
-    scan all buffers for an overlap
+    binary search for the buffers that can overlap
```

- **`release_ranges` (commit 2):** finds the buffers that can overlap a
released range with a binary search, as `PushBuffers::find` does. The
trim and split logic does not change.
- **`clear_ranges` (commit 3):** finds the buffers to remove with a
binary search. Before, it built new buffer lists on each call. This
commit gives most of the gain.
- **`VecDeque` and `max_len_count` (commit 4):** `PushBuffers` stores
the buffers in a `VecDeque`, so a removal at the start or at the end
moves no other buffer. A count of the buffers with length `max_len` lets
a removal skip the scan that updates `max_len` while other buffers of
that length remain.

<details>
<summary>Benchmark numbers for each commit, and edge cases</summary>

`push_decoder/prefetch` on the GKE runner. Each column adds one commit:

| Buffers | Benchmark only | + `release_ranges` | + `clear_ranges` | +
`VecDeque` |
|--|--|--|--|--|
| 1,000 | 1.12 ms | 1.09 ms | 0.64 ms | 0.60 ms |
| 10,000 | 56.6 ms | 53.1 ms | 11.9 ms | 6.3 ms |
| 30,000 | 478 ms | 447 ms | 73.4 ms | 19.2 ms |

Change of the existing `1buf` and `Nbuf` cases for each commit:

| Step | Change |
|--|--|
| Control (same code on both sides) | −3% to +2% |
| + `release_ranges` | −1% to +2% |
| + `clear_ranges` | −2% to +2% |
| + `VecDeque` | +1% to +6% (slower in all seven cases) |

Runs:

- Benchmark only compared with `release_ranges`:
apache#11459 (comment)
- `release_ranges` compared with `clear_ranges`:
apache#11459 (comment)
- `clear_ranges` compared with `VecDeque`:
apache#11459 (comment)
- Control:
apache#11459 (comment)

These runs used the commits before the rebase onto `main`. The rebase
changed only the benchmark file.

Time for each `release_ranges` call, from temporary timing tests that
are not part of this PR (release build, Apple silicon):

| Buffers | Call | Before | After commit 2 |
|--|--|--|--|
| 1,000 | releases nothing | 495 ns | 55 ns |
| 10,000 | releases nothing | 3.5 µs | 67 ns |
| 100,000 | releases nothing | 37 µs | 61 ns |
| 1,000 | trims one buffer | 1.5 µs | 82 ns |
| 10,000 | trims one buffer | 8.5 µs | 91 ns |
| 100,000 | trims one buffer | 86 µs | 81 ns |

Edge cases:

- Removal in the middle: `VecDeque::drain` moves the buffers on the
shorter side of the removed buffers. Thus, only a removal at the start
or at the end moves none.
- `max_len`: it stays exact. It is computed again from all buffers only
when the last buffer of length `max_len` is removed or trimmed.
- Empty buffers: `push_range` accepts empty and inverted ranges, and
`release_ranges` removes all of them when it releases bytes. To keep
this behavior without a visit of all buffers, `PushBuffers` counts the
empty buffers. `release_ranges` looks at all buffers only if the count
is not zero.
- Sort order: a trim moves the start of a buffer only past released
bytes, so the trimmed buffers stay in order. Only split parts can be out
of order, and the sort runs only after a split.
- Buffers with the same start: they are adjacent but not sorted by end.
`clear_ranges` checks each of them for an exact match.

</details>

# Are these changes tested?

Yes. The existing tests cover this, in particular
`fuzz_release_ranges_matches_rebuild`, which compares `release_ranges`
with a full rebuild, and `fuzz_matches_a_linear_scan`, which includes
random calls to `clear_ranges`. The new test
`clear_ranges_with_buffers_of_the_same_start` covers buffers that share
a start and ranges that are given more than once. `assert_invariants`
now also checks the count of empty buffers and the count of buffers with
length `max_len`.

# Are there any user-facing changes?

No. All changes are in `pub(crate)` functions and private fields, so a
revert is safe if a regression shows.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

---------

Co-authored-by: Claude Opus 5.5 <[email protected]>