lance-format / lance-format/lance

parallelize zone statistics computation in scalar index training

Open
#8,468 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
7.1k
Forks
852
Avg merge
3d 18h
Merged PRs (30d)
272

Description

Problem

ZoneTrainer::train computed every zone's statistics on a single task. chunk_concat_stream first copied the input stream into zone-sized batches, then one processor walked the zones sequentially, calling reset() between them. Zone statistics are independent of one another, so this pinned the whole computation to a single core regardless of machine size. The cost scales with per-zone work — a bloom filter has to hash every value into that zone's SBBF, which made it the dominant part of index build time.

Approach

Separate zone splitting from zone computation:

  • ZoneAssembler (serial) scans _rowaddr in a single pass and cuts at fragment boundaries and zone capacity, emitting each zone as zero-copy RecordBatch slices. This also removes the chunk_concat_stream copy.
  • process_zone (pure CPU) computes one zone's statistics and null row addresses, dispatched via spawn_cpu.
  • ZoneTrainer::new now takes a processor factory instead of a single processor, so each zone gets its own processor.
  • Results are collected through FuturesOrdered, with in-flight tasks capped at get_num_compute_intensive_cpus() for backpressure.

Zone order and contents are unchanged, so the on-disk index is byte-identical; no format change.

Results

Benchmarks added in this PR, comparing training performance only (default parameters). This is not an end-to-end measurement: it times builder.train(...) alone, excluding write_index and the dataset scan.

8M rows / 64 fragments:

Benchmark Before After Speedup
bloomfilter_train_string (Utf8, 64 frags) 395.5 ms 15.5 ms 25.5×
zonemap_train_string (Utf8, 64 frags) 65.9 ms 11.3 ms 5.8×
zonemap_train (Int32, batch = 8192) 30.2 ms 9.15 ms 3.3×

The bloom filter gains the most, as expected: it has the largest per-zone workload (e SBBF), and the serial version spent nearly all of its time there.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reading ZoneTrainer::train and ZoneTrainer::new, then trace how builder.train invokes scalar index training. Use the mentioned bloomfilter_train_string, zonemap_train_string, and zonemap_train benchmarks to compare training behavior. Done means zones are processed independently without changing their order or contents, and the on-disk index remains byte-identical.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, performance
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.