Re: [PR] [POC for #9934] parquet: add ReverseSerializedPageReader [arrow-rs]

[via GitHub]

github-actions[bot] commented on PR #9937:
URL: https://github.com/apache/arrow-rs/pull/9937#issuecomment-4964776876

   Thank you for your contribution. Unfortunately, this pull request is stale 
because it has been open 60 days with no activity. Please remove the stale 
label or comment or this will be closed in 7 days.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org

Re: [PR] [POC for #9934] parquet: add ReverseSerializedPageReader [arrow-rs]

[via GitHub]

zhuqi-lucas commented on PR #9937:
URL: https://github.com/apache/arrow-rs/pull/9937#issuecomment-4415297373

   Thanks for the review @alamb — your concern about maintaining two 
near-identical reader paths was exactly right. I dug into the diff and ~95% of 
`ReverseSerializedPageReader` was just `SerializedPageReader::Pages` mode with 
`pop_back` instead of `pop_front`. Pushed `4c8b46e` collapsing the two:
   
   **API now:**
   
   ```rust
   let reader = SerializedPageReader::new(
   chunk_reader, meta, total_rows, Some(page_locations),
   )?
   .with_reverse_pages(true);   // ← new builder flag
   ```
   
   **What changed under the hood:**
   
   - `SerializedPageReaderState::Pages` gains a `reverse: bool` field
   - `with_reverse_pages(true)` flips the flag and seeds `page_index` to `len - 
1` so the page ordinal stays correct (this matters for encryption AAD — reverse 
mode emits the back-most page first, which has ordinal `N - 1` in the original 
forward order)
   - `get_next_page` / `peek_next_page` / `skip_next_page` / 
`peek_next_page_offset` branch `pop_front` ↔ `pop_back`, `front` ↔ `back`, and 
`+= 1` ↔ `saturating_sub(1)` under the flag
   - Dictionary handling is unchanged — it's still emitted first in both modes 
(data pages depend on the loaded dict)
   
   **The dedicated `reverse_serialized_reader.rs` module is gone** (~1080 lines 
deleted). Net change: **−190 lines source, single code path**. Encryption now 
works for reverse iteration too, which it didn't in the standalone reader.
   
   **On the dict-detection wrinkle I mentioned**: I considered the "pass a 
pre-reversed `Vec`" route but it breaks the existing dict 
inference (which uses the gap between `chunk_start` and 
`page_locations[0].offset`). The flag-based approach keeps the existing builder 
logic untouched and only flips iteration direction at the per-call site, so I 
went that way. Happy to reconsider if you'd prefer the alternative.
   
   **Tests:** all 21 reverse-correctness tests are migrated to a 
`reverse_pages_tests` sub-module in `serialized_reader.rs`. Added one new test 
(`with_reverse_pages_is_noop_in_values_mode`) verifying the flag is harmless in 
`Values` mode. The bench is updated to call the new API; numbers are within 
noise of the pre-refactor result (~50x speedup for `n ≤ one page`, scaling down 
with `n` as expected).
   
   PR description has been updated to match.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org

Re: [PR] [POC for #9934] parquet: add ReverseSerializedPageReader [arrow-rs]

[via GitHub]

zhuqi-lucas commented on PR #9937:
URL: https://github.com/apache/arrow-rs/pull/9937#issuecomment-4397057421

   Following up — added a **cross-page** version of the comparison bench 
(`0b52384`) so the speedup shape is visible across the full range of `n`, not 
only `n <= one page`.
   
   The new function (`time_to_first_n_page_reverse_cross_page`) reverses each 
page segment individually before continuing, which is correct for any `n` and 
matches the algorithmic shape Phase 2 will use (per-page reverse + emit, no 
cross-page accumulation).
   
   Numbers on Apple M-series (`--quick`, 100k INT32, 98 pages, no dict, 
uncompressed):
   
   | n | row_group_sim | page_reverse(_cross) | Speedup |
   |---:|---:|---:|---:|
   | 10 (single page) | 26.7 µs | 565 ns | ~47x |
   | 100 (single page) | 26.7 µs | 565 ns | ~47x |
   | 1024 (single page) | 26.7 µs | 472 ns | ~57x |
   | **2 000 (~2 pages)** | 26.8 µs | **770 ns** | **~35x** |
   | **10 000 (~10 pages)** | 26.6 µs | **2.85 µs** | **~9.3x** |
   | **50 000 (~half file)** | 26.7 µs | **14.5 µs** | **~1.8x** |
   
   Speedup follows `total_pages / pages_needed_for_n` and converges to ~1x as 
`n` approaches the full chunk — the expected shape for a primitive that saves 
work proportional to the unread tail.
   
   The original single-trailing-reverse function 
(`time_to_first_n_page_reverse`) is left in place for the small-`n` cases where 
it produces the same result, with a doc comment noting it is only correct when 
`n <= PAGE_ROW_COUNT_LIMIT`.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org

Re: [PR] [POC for #9934] parquet: add ReverseSerializedPageReader [arrow-rs]

[via GitHub]

zhuqi-lucas commented on PR #9937:
URL: https://github.com/apache/arrow-rs/pull/9937#issuecomment-4394540262

   cc @alamb @adriangb 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org

Re: [PR] [POC for #9934] parquet: add ReverseSerializedPageReader [arrow-rs]

[via GitHub]

zhuqi-lucas commented on PR #9937:
URL: https://github.com/apache/arrow-rs/pull/9937#issuecomment-4394522328

   Following up on the question of "where's the speedup" — added a more 
compelling benchmark in `14479b7` that simulates the existing **row-group-level 
reverse** strategy (DataFusion apache/datafusion#18817: forward-decode the 
whole chunk, reverse the value buffer, take N) and compares it against the 
**page-level reverse** strategy enabled by this PR.
   
   Numbers on Apple M-series (`--quick`, 100k INT32 values, 98 pages, no 
dictionary, uncompressed):
   
   | N | row_group_sim | page_reverse | Speedup |
   |---:|---:|---:|---:|
   | 10   | 28.8 µs | 564 ns | **~51x** |
   | 100  | 29.0 µs | 602 ns | **~48x** |
   | 1024 | 28.9 µs | 505 ns | **~57x** |
   
   **Why the speedup**: row-group reverse must decode all 98 pages even when 
only the last 10 reversed values are wanted; page reverse decodes one page (the 
last one) and reverses its values in place. The ratio scales with the number of 
pages — i.e. the bigger the row group, the larger the win.
   
   **What this models**: it's the closest in-crate proxy for the `ORDER BY DESC 
LIMIT N` query path that DataFusion currently runs through its row-group 
reverse rule. A real query-engine integration (Phase 2) would emit 
`RecordBatch`es page by page rather than gather a `Vec`, but the 
underlying decode-work ratio is the same.
   
   **Caveats** (called out so this isn't oversold):
   - Both readers run from in-memory `Bytes`, so I/O latency is not modeled. On 
real S3/object storage, both readers issue one byte-range read per page, so the 
page-reverse advantage holds and is amplified by network round-trips dominating 
decode cost.
   - This bench is no-filter. With `RowFilter` pushdown, both strategies pay 
filter-evaluation cost; the page-reverse advantage compounds because the 
row-group strategy filter-evaluates pages it ultimately discards.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org

Re: [PR] [POC for #9934] parquet: add ReverseSerializedPageReader [arrow-rs]

[via GitHub]

zhuqi-lucas commented on PR #9937:
URL: https://github.com/apache/arrow-rs/pull/9937#issuecomment-4394494848

   Added a criterion benchmark in `e3d7ddb` 
(`parquet/benches/reverse_page_reader.rs`).
   
   Phase 1's empirical claim is **per-page cost parity** with the existing 
forward `SerializedPageReader`, not a flashy speedup — the speedup comes at 
higher levels (Phase 2/3). Numbers from `cargo bench -- --quick` on Apple 
M-series, 100k INT32 values, ~98 data pages, no dictionary:
   
   | Bench | Forward | Reverse | Δ |
   |---|---:|---:|---:|
   | uncompressed / drain (full chunk) | 9.73 µs | 9.34 µs | -4% |
   | uncompressed / first_page latency | 164 ns | 156 ns | -5% |
   | snappy / drain (full chunk) | 21.5 µs | 21.2 µs | -1% |
   | snappy / first_page latency | 313 ns | 283 ns | -10% |
   
   All within measurement noise; reverse iteration adds no per-page overhead.
   
   Phase 2's value-add (early termination + low peak memory under `WHERE filter 
ORDER BY DESC LIMIT N`) is not exercised here — that requires 
record-batch-level integration and a different benchmark setup. Filed under 
future work.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org

Re: [PR] [POC for #9934] parquet: add ReverseSerializedPageReader [arrow-rs]

[via GitHub]

Copilot commented on code in PR #9937:
URL: https://github.com/apache/arrow-rs/pull/9937#discussion_r3198907619


##
parquet/src/file/reverse_serialized_reader.rs:
##
@@ -0,0 +1,1034 @@
+// 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.
+
+//! Reverse page-order [`PageReader`] backed by [`OffsetIndexMetaData`].
+//!
+//! Tracking issue: .
+//!
+//! This reader emits pages from a Parquet column chunk in **reverse page 
order**:
+//! the dictionary page (if any) is emitted first because data pages depend on 
it,
+//! followed by data pages from the last `PageLocation` to the first.
+//!
+//! Pages are still **decoded in their native forward direction** — only the 
page
+//! traversal order is reversed. Reversing rows *within* a page is impossible
+//! because Parquet's RLE / bit-packing / delta / dictionary encodings are
+//! forward streams; that responsibility belongs to a higher layer.
+//!
+//! ## Limitations (Phase 1 POC)
+//!
+//! * Encryption is not supported.
+//! * `peek_next_page` does not populate `num_rows`.
+//! * Requires the column chunk to have an `OffsetIndex` (i.e. page index).
+
+use std::sync::Arc;
+
+use crate::basic::Type;
+use crate::column::page::{Page, PageMetadata, PageReader};
+use crate::compression::{Codec, create_codec};
+use crate::errors::{ParquetError, Result};
+use crate::file::metadata::ColumnChunkMetaData;
+use crate::file::metadata::thrift::PageHeader;
+use crate::file::page_index::offset_index::{OffsetIndexMetaData, PageLocation};
+use crate::file::properties::{ReaderProperties, ReaderPropertiesPtr};
+use crate::file::reader::ChunkReader;
+use crate::file::serialized_reader::decode_page;
+use crate::parquet_thrift::{ReadThrift, ThriftSliceInputProtocol};
+
+/// A [`PageReader`] that emits pages in reverse order using `OffsetIndex`.
+///
+/// See the module-level documentation for details.
+pub struct ReverseSerializedPageReader {
+reader: Arc,
+decompressor: Option>,
+physical_type: Type,
+state: ReverseState,
+read_stats: bool,
+}
+
+enum ReverseState {
+/// Initial state. The dictionary page (if any) is emitted on the next 
call,
+/// then the state transitions to [`ReverseState::Data`].
+NeedDict {
+dictionary_page: Option,
+page_locations: Vec,
+},
+/// Iterate `page_locations[..cursor]` from the back: emit
+/// `page_locations[cursor - 1]` and decrement `cursor`.
+Data {
+page_locations: Vec,
+cursor: usize,
+},
+Exhausted,
+}
+
+impl ReverseSerializedPageReader {
+/// Create a new [`ReverseSerializedPageReader`] with default
+/// [`ReaderProperties`].
+pub fn new(
+reader: Arc,
+meta: &ColumnChunkMetaData,
+offset_index: &OffsetIndexMetaData,
+) -> Result {
+let props = Arc::new(ReaderProperties::builder().build());
+Self::new_with_properties(reader, meta, offset_index, props)
+}
+
+/// Create a new [`ReverseSerializedPageReader`] with explicit
+/// [`ReaderProperties`].
+pub fn new_with_properties(
+reader: Arc,
+meta: &ColumnChunkMetaData,
+offset_index: &OffsetIndexMetaData,
+props: ReaderPropertiesPtr,
+) -> Result {
+let decompressor = create_codec(meta.compression(), 
props.codec_options())?;
+let (chunk_start, _chunk_len) = meta.byte_range();
+let locations = offset_index.page_locations().clone();
+
+// If the first data page does not start at the column chunk's start, a
+// dictionary page sits in front. Synthesize a `PageLocation` for it
+// (mirrors `SerializedPageReader::new_with_properties`).
+let dictionary_page = match locations.first() {
+Some(first) if (first.offset as u64) != chunk_start => 
Some(PageLocation {
+offset: chunk_start as i64,
+compressed_page_size: (first.offset as u64 - chunk_start) as 
i32,
+first_row_index: 0,
+}),
+_ => None,
+};
+
+Ok(Self {
+reader,
+decompressor,
+physical_type: meta.column_type(),
+state: ReverseState:

[PR] [POC for #9934] parquet: add ReverseSerializedPageReader [arrow-rs]

[via GitHub]

zhuqi-lucas opened a new pull request, #9937:
URL: https://github.com/apache/arrow-rs/pull/9937

   # Which issue does this PR close?
   
   Tracking issue: #9934 — *parquet: Support reverse page iteration for reverse 
streaming with filter pushdown*.
   
   This PR is a **proof-of-concept (Phase 1)** for the building block proposed 
in that issue. It is **not** intended for immediate merge — its purpose is to 
ground the design discussion in real code, demonstrate feasibility, and gather 
feedback on the API shape before a final PR.
   
   # Rationale for this change
   
   DataFusion has merged a row-group-level reverse scan 
(apache/datafusion#18817) for `ORDER BY DESC LIMIT N` queries on 
ascending-sorted Parquet files. The current granularity (~128MB per row group) 
means high first-batch latency and high peak memory; for `WHERE filter ORDER BY 
DESC LIMIT N`, where `RowSelection` cannot pre-select matching rows, the 
reverse stream is the only correct strategy.
   
   A page-level reverse iterator is the missing primitive. The key insight (per 
#9934) is to separate **two distinct concepts**:
   
   | | Possible? |
   |---|---|
   | Reverse-decoding rows *within* a single page | ❌ No (RLE / dict / delta / 
bit-packing are forward streams) |
   | Iterating page **traversal order** in reverse, decoding each page forward 
| ✅ Yes (via `OffsetIndex.page_locations`) |
   
   This PR implements the second.
   
   # What changes are included in this PR?
   
   A new `pub mod reverse_serialized_reader` exposing 
`ReverseSerializedPageReader`:
   
   - Implements `PageReader + Iterator>`
   - Emits the dictionary page (if any) first, then data pages from the last 
`PageLocation` to the first
   - Reuses existing `decode_page`, `ThriftSliceInputProtocol`, and `Codec` 
plumbing — **no changes to `serialized_reader.rs`**
   
   ```rust
   let reader = ReverseSerializedPageReader::new(
   chunk_reader,
   column_chunk_metadata,
   offset_index,
   )?;
   for page in reader {
   // page is decoded forward, but pages are emitted in reverse order
   }
   ```
   
   ## Limitations (Phase 1 POC, intentional)
   
   - Encryption is not supported.
   - `peek_next_page` does not populate `num_rows`.
   - Requires the column chunk to have an `OffsetIndex` (page index).
   
   ## Test coverage (20 tests)
   
   | Category | Tests |
   |---|---|
   | Page buffer / metadata equivalence | UNCOMPRESSED / SNAPPY / GZIP / ZSTD; 
V1 + V2 pages; with / without dict |
   | Value-level decode equivalence (via `ColumnReaderImpl`) | INT32 / INT64 / 
BYTE_ARRAY; with / without dict; V1 + V2 |
   | NULL handling | OPTIONAL columns, V1 + V2, ~30% nulls |
   | State machine | `peek_next_page` over full lifecycle; `skip_next_page` 
with / without dict |
   | Edge cases | Single-data-page chunks; 50k-row stress (> 20 pages); 
`Iterator` impl |
   
   The page-level tests verify byte-identical buffers between forward 
(`SerializedPageReader`) and reverse readers. The decode-level tests further 
verify that, after page-boundary slicing and re-arrangement, `ColumnReaderImpl` 
produces identical values and `def_levels`.
   
   # Why is this an RFC / draft?
   
   The remaining work for end-to-end usefulness sits **above** this primitive:
   
   - **Phase 2**: a `ParquetRecordBatchReader` mode that aligns batch 
boundaries with page boundaries and reverses each page's `RecordBatch` after 
decoding, so the final stream is fully reversed. This requires deciding whether 
to integrate with `ParquetRecordBatchReaderBuilder` or expose a separate 
reverse-reader path.
   - **Phase 3**: filter + limit early termination (the killer use case from 
#9934).
   
   Specific feedback I'd appreciate:
   
   1. **API surface**: low-level `ReverseSerializedPageReader` (this PR) vs. a 
high-level `ArrowReaderBuilder::with_reverse_pages(true)` — or both?
   2. **Module placement**: keep as a sibling module 
`file/reverse_serialized_reader.rs`, or fold the reverse path into 
`serialized_reader.rs` itself?
   3. **Encryption**: extend `SerializedPageReaderContext` to be reusable, or 
defer encryption support to a later PR?
   4. **`peek_next_page` semantics**: precise `num_rows` requires threading 
`total_rows` through; worth doing in this PR?
   
   # Are there any user-facing changes?
   
   A new public type 
`parquet::file::reverse_serialized_reader::ReverseSerializedPageReader`. No 
existing APIs are changed.
   
   # Verification
   
   ```
   cargo build -p parquet
   cargo check -p parquet --all-features --tests
   cargo test  -p parquet --lib reverse_serialized_reader   # 20 passed
   cargo clippy -p parquet --all-targets -- -D warnings
   cargo fmt -p parquet --check
   ```
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscr...@arrow.apache.org

For queries about this service, ple