apache / apache/paimon-cpp

[Feature] Support shared-shredding storage layout for MAP columns

Đang mở
#220 0 bình luận 0 reaction 0 người được giao Xem trên GitHub
enhancement
Ngôn ngữ chính
C++
Star
65
Fork
25
Merge trung bình
2 ngày 12 giờ
Pull request đã merge (30 ngày)
80

Mô tả

### Search before asking

- [x] I searched in the [issues](https://github.com/apache/paimon-cpp/issues) and found nothing similar.

### Motivation

In time-series / IoT / observability workloads, a common pattern is storing free-schema fields in a `MAP` column (e.g. `metrics MAP`). The default MAP storage (two KV arrays) provides:

- No per-key columnar access
- No per-key statistics
- No predicate pushdown on individual keys

This makes queries like `SELECT ext_map['usage'] FROM metrics WHERE ext_map['usage'] > 30` scan the entire MAP column — extremely inefficient when only 1–3 keys out of thousands are needed per query.

The [PIP-43: Columnar Storage Optimization for MAP Type in Paimon](https://cwiki.apache.org/confluence/display/PAIMON/PIP-43%3A+Columnar+Storage+Optimization+for+MAP+Type+in+Paimon) proposes a new `shared-shredding` storage layout that stores MAP values in `K` reusable physical columns within a Struct, achieving near-full columnar access with per-key statistics and predicate pushdown — without changing the logical type (`MAP`).

### Solution

#### Physical Layout

Each `MAP` column configured with `fields..map.storage-layout = shared-shredding` is physically stored as:

```
STRUCT<
__field_mapping: FixedSizeList, -- per-row: which field_id each col holds
__col_0: T, __col_1: T, ..., __col_{K-1}: T, -- reusable typed columns
__overflow: MAP -- rare fallback for rows with > K fields
>
```

`fields..map.shared-shredding.max-columns` controls K_max, and `fields..map.shared-shredding.column-placement-policy` controls column placement.

File metadata (footer) stores: field name↔id dictionary, field_id→physical column set S, overflow set O, K, and max row width.

#### Write Path

1. **Schema conversion utilities** — Logical MAP → physical Struct schema rewriting; metadata serialization/deserialization; shared-shredding column detection via field metadata marker.

2. **`FormatWriter::AddMetadata`** — New virtual method (default no-op) for writing key-value metadata to file footer before `Finish()`. Parquet implementation calls `AddKeyValueMetadata`.

3. **Column allocator** — Per-row slot allocator that maps field IDs to up to `K` physical columns and sends the rest to overflow. Placement policy is configurable (`plain`, `sequential`, `lru`; default `plain`). Accumulates file-level statistics (S, O, max row width).

4. **Logical→physical batch converter** — Parses logical MAP, encodes field names to integer IDs (file-level dictionary), invokes allocator per row, assembles physical Struct array.

5. **Writer integration** — Extended DataFileWriter that performs conversion before writing + injects metadata on close. AppendOnlyWriter detects shared-shredding columns and routes accordingly. Cross-file K adaptation (P99 of recent max row widths, capped by K_max).

#### Read Path

1. **File metadata parsing** — Parse shared-shredding metadata from file footer (dictionary, S, O, K). New `GetFileKeyValueMetadata()` method on `FileBatchReader` with Parquet implementation.

2. **Predicate translation** — Translate logical predicates on MAP keys into conservative OR predicates over physical sub-columns. Requires extending `LeafPredicate` to support nested field paths and updating `PredicateConverter` to emit nested `FieldRef`.

3. **Read planning** — At `SetReadSchema` time: look up which physical columns to read (from S), decide whether `__overflow` is needed (from O), translate predicates, and pass the physical schema + physical predicate down to the inner `FileBatchReader` unchanged.

4. **Batch reconstruction** — After `NextBatch`: read `__field_mapping` per row to identify which column holds which field (fine-grained filter), gather values into logical `MAP`. Merge overflow when needed. Correctness relies on per-row `__field_mapping`, not on pushdown precision.

5. **Reader integration** — A wrapper reader (implements `FileBatchReader`) sits between the upper layer and the format-level reader. Per-file instance. Compatible with varying K across files. Orthogonal to `DataEvolutionFileReader` (schema evolution).

### Anything else?

_No response_

### Are you willing to submit a PR?

- [x] I'm willing to submit a PR!

Hướng dẫn đóng góp

Mở hướng dẫn đóng góp

Hướng nghiên cứu

Bắt đầu với PIP-43 và lần theo các interface hiện có FormatWriter, FileBatchReader, AppendOnlyWriter, LeafPredicate và PredicateConverter. Lập sơ đồ các đường đi của việc ghi và đọc trước khi triển khai các phần chuyển đổi schema, metadata, cấp phát, dịch predicate và tái dựng. Hoàn thành có nghĩa là các cột MAP sử dụng shared-shredding hoạt động trong quá trình ghi, đọc, lọc, overflow và với các giá trị K khác nhau giữa các tệp.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Đánh giá

Công nghệ
cpp
Lĩnh vực
databases
Loại issue
Tính năng
Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức độ hoạt động
Sôi nổi
Độ rõ ràng
Khá rõ ràng
Mức phù hợp với người mới
35/100

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.