Blosc / Blosc/python-blosc2

[CTable] Add offset indirection layer to ListArray for a better sort cost

Open
#635 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
211
Forks
58
Avg merge
1d 17h
Merged PRs (30d)
6

Description

## Background

CTable stores list-typed columns (declared as `blosc2.list(item_spec)`) in a `ListArray`
object backed by a `BatchArray` (or `ObjectArray`). The `BatchArray` stores rows in
compressed batches of fixed size (`batch_rows`). Individual rows are located using a
prefix-sum array over batch lengths.

Example schema:

@dataclass
class Food:
id: str = blosc2.field(blosc2.string(max_length=64))
ingredients: list = blosc2.field(blosc2.list(blosc2.string(max_length=32)))

---

## Current problem: sort_by() on tables with list columns is expensive

When `CTable.sort_by("id")` is called on a table that also has a `ListArray` column
(`ingredients`), the column must be physically rewritten in the new order. The relevant
code is in `ctable.py`, `sort_by()`:

# inplace=True path (simplified)
new_arr = ListArray(spec=col.spec)
new_arr.extend((arr[int(pos)] for pos in sorted_pos), validate=False)
new_arr.flush()
self._cols[name] = new_arr

Each `arr[int(pos)]` call locates the batch that contains row `pos`, decompresses it,
and extracts the value. For a table with n rows and batch_rows=B, this causes up to
n batch decompressions (O(n) decompress + O(n) recompress into the new array).

For large tables with many/large list values this is very slow.

---

## Proposed solution: offset indirection array

Add a companion NDArray of int64 to each ListArray column. This array is called the
**offset** and maps `logical_physical_pos → true_physical_pos_in_batch_array`.

### Initial state (4 rows, no sort yet)

id column (NDArray): ["chocolate", "tortilla", "paella", "albondigas"]
ingredients (BatchArray): [choc_list, tort_list, pae_list, alb_list ] ← physical
ingredients offset (NDArray):[0, 1, 2, 3 ] ← identity

### After sort_by("id") — only the offset changes, BatchArray untouched

id column (NDArray): ["albondigas", "chocolate", "paella", "tortilla"]
ingredients (BatchArray): [choc_list, tort_list, pae_list, alb_list ] ← unchanged
ingredients offset (NDArray):[3, 0, 2, 1 ]

Reading `ingredients` for row 1 ("chocolate"):
1. Look up `offset[1]` → `0`
2. Read `batch_array[0]` → `choc_list`

Sort cost is now O(n) NDArray write instead of O(n) BatchArray decompress+recompress.

### The offset is lazy

The BatchArray is only accessed when list data is actually needed. Operations that sort
or filter on other columns never touch the BatchArray at all. This means:

- sort_by("id") → permute offset only, BatchArray untouched
- where("id == 'paella'") → BatchArray untouched
- head() / tail() → only a few offset lookups, trivial cost
- aggregate on other cols → BatchArray untouched

The only time the fragmented-access cost is paid is a full scan of the list column
(e.g. to_arrow(), to_csv(), or iterating every row's ingredients). Even then the data
is correct; it just may access BatchArray batches out of sequential order.

### Compaction restores physical order

`CTable.copy(compact=True)` is the existing idiom to reclaim space and rewrite data.
When compact copy is triggered, the BatchArray should be rewritten following the current
offset order and the offset reset to identity:

After copy(compact=True) of the sorted example above (and "chocolate" deleted):

id column (NDArray): ["albondigas", "paella", "tortilla"]
ingredients (BatchArray): [alb_list, pae_list, tort_list ] ← physically reordered
ingredients offset (NDArray):[0, 1, 2 ] ← identity again

---

## Impact on each CTable operation

| Operation | Current behaviour (list cols) | With offset |
|--------------------|-------------------------------------------------------|----------------------------------------------------------|
| sort_by | new ListArray, extend one-by-one via generator | permute offset NDArray only; BatchArray untouched |
| append | push to _pending_cells / _backend | same + append next_phys_idx to offset |
| extend | batch-extend _pending_cells | same + append range of phys indices to offset |
| __getitem__ (read) | valid_rows → phys_pos → batch_array[phys_pos] | valid_rows → phys_pos → offset[phys_pos] → batch_array |
| __setitem__ (write)| batch_array[phys_pos] = val | batch_array[offset[phys_pos]] = val |
| delete | tombstone in _valid_rows, ListArray untouched | same, offset untouched |
| compact | new ListArray with live rows | new ListArray in offset order, reset offset to identity |
| copy(compact=True) | iterate live positions, fresh ListArray | iterate via offset order, fresh identity offset |
| copy(compact=False)| copy all rows including gaps | copy all rows (offset included as-is) |
| to_arrow / to_csv | sequential scan, BatchArray cache-friendly | permuted scan — consider copy(compact=True) first |

---

## Implementation notes

### Where the offset lives

The offset NDArray is a peer of the other NDArray columns inside `CTable._cols` or can
be stored as internal state inside `ListArray` itself. Keeping it inside `ListArray`
is the cleaner option: ListArray owns its own permutation state and callers need no
changes to how they access it.

If kept inside `ListArray`:
- `self._offset: blosc2.NDArray | None` (None = identity, lazily allocated on first sort)
- `_resolve(phys_pos)` → `self._offset[phys_pos] if self._offset is not None else phys_pos`

### Pending cells and flush()

`ListArray` for `storage="batch"` buffers rows in `self._pending_cells` before they are
flushed into the BatchArray. When a flush happens, the newly persisted rows get physical
indices `[prev_persisted_count, ..., prev_persisted_count + batch_size - 1]`. These
need to be appended to the offset array in the same order they were in `_pending_cells`.

As long as appends always go to the end (no insert-in-middle), the offset for new rows
is always the identity range and the invariant is easy to maintain.

### Persistence

For file-backed tables the offset needs to be stored alongside the BatchArray. A simple
option is a `.b2nd` file next to the `.b2b` file:

_cols/ingredients.b2b ← BatchArray data (unchanged)
_cols/ingredients.offset.b2nd ← offset NDArray (new)

On open, if the offset file is missing it is treated as an identity permutation (backward
compatibility with existing archives).

### Backward compatibility

- Existing `.b2z` and `.b2d` archives without an offset file → treat as identity (no migration needed).
- Schema serialization does not need to change; the offset is operational state, not schema.

---

## Known trade-offs

1. **Read overhead after unsorted state.** A full sequential scan of a list column after
sort (without compacting) accesses BatchArray batches out of order. For large `batch_rows`
this means decompressing a full batch to read one element. Mitigation: call
`copy(compact=True)` before bulk-reading list data if performance matters.

2. **Extra indirection on every list read.** One additional NDArray lookup per row.
For small tables or point lookups this is negligible. For large scans the NDArray is
accessed sequentially (offset itself is sequential even if the values it points to are
not), so it stays cache-warm.

3. **_pending_cells bookkeeping.** The offset must be kept in sync with the pending buffer
during flush. This is the trickiest part of the implementation; see notes above.

---

## Files to touch

- `src/blosc2/list_array.py` — add `_offset` field, `_resolve()`, update all read/write paths
- `src/blosc2/ctable.py` — update `sort_by()` to permute offset instead of rewriting ListArray;
update `compact()` and `copy()` to rebuild offset
- `src/blosc2/ctable_storage.py` — persist/load `.offset.b2nd` sidecar file alongside `.b2b`
- `tests/ctable/` — add tests: sort with list col, read after sort, compact resets offset,
copy with compact, persistence round-trip, backward compat (no offset file)

---

## Acceptance criteria

- [ ] `sort_by` on a table with a `list` column does not rewrite the BatchArray
- [ ] Reading list values after sort returns values in the new sorted order
- [ ] `copy(compact=True)` produces a table where the offset is identity and BatchArray
is physically in the correct order
- [ ] Existing `.b2z` files without an offset file open correctly (identity fallback)
- [ ] All existing ctable tests pass

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.