JingsongLi opened a new pull request, #11249:
URL: https://github.com/apache/paimon/pull/11249

   ### Purpose
   
   Add opt-in centroid-based sharding for Spark vector global indexes on Data 
Evolution append tables. Range-based sharding is the default. With centroid 
sharding, a query can open just the files assigned to the nearest global 
centers. 
[PIP-47](https://cwiki.apache.org/confluence/spaces/PAIMON/pages/444334660/PIP-47+Centroid-Based+Sharding+Design+for+IVF-PQ)
   
   Spark pins a snapshot, counts non-null vectors per split and plans a 
deterministic sample with an ordinary IVF-FLAT trainer. Each map task selects 
rows from its own splits. A single task trains the coarse centers from those 
rows in reservoir order. Spark broadcasts the router, shuffles by centroid ID 
and builds an independent IVF or DiskANN index per populated shard. Readers use 
the persisted router to select files and merge the local results by score.
   
   **Native dependency.** This branch uses 
`paimon-vector-index-java:0.7.0-SNAPSHOT` with the router and sample-planning 
APIs from 
[apache/paimon-vector-index#131](https://github.com/apache/paimon-vector-index/pull/131).
 Local tests used a JAR containing those APIs. Readers need centroid support 
before this layout is enabled.
   
   ### Tests
   
   - 67 local Spark/Paimon tests passed, including Spark SQL integration across 
all five index types, split-local sampling, shard pruning and range rebuilds.
   - On SIFT1M with 64 outer centers and a sampling ratio of 1, all five index 
types selected the same 65,536 rows. The serialized router matched streaming 
IVF-FLAT training on all one million rows, including when DiskANN used seed 93 
and a 4 MiB local build budget.
   
   ### Benchmark results
   
   **Each cell shows Range → Centroid at matched Recall@10.** SIFT1M contains 
one million 128-dimensional L2 vectors. Runs used an Apple M4 Pro, Spark 
`local[4]` and four native threads. Build time includes sampling, training, 
shuffle, index writes and commit. Each timed query opened a fresh reader with a 
warm OS page cache. File counts include the router, and MiB measures logical 
reads per query.
   
   | Index | Recall@10 (%) | Build (s) | Query P95 (ms) | Files/query | 
MiB/query |
   | --- | ---: | ---: | ---: | ---: | ---: |
   | IVF-FLAT | 99.000 → 99.220 | 3.32 → 6.87 | 9.22 → 5.41 | 64 → 25 | 67.18 → 
37.16 |
   | IVF-SQ | 98.015 → 97.950 | 3.81 → 4.64 | 7.58 → 3.38 | 64 → 11 | 22.54 → 
11.03 |
   | IVF-PQ | 72.886 → 73.094 | 66.80 → 67.41 | 33.08 → 1.69 | 64 → 5 | 14.98 → 
1.11 |
   | IVF-RQ | 90.075 → 90.550 | 3.44 → 5.89 | 6.20 → 2.09 | 64 → 13 | 13.04 → 
3.46 |
   | DiskANN | 99.460 → 99.355 | 98.13 → 106.25 | 46.75 → 13.26 | 64 → 11 | 
82.49 → 16.98 |
   
   The four IVF results come from earlier runs with independently trained shard 
models. Build time, P95 and reads are medians over three rounds. IVF-PQ used 
32-byte codes in both layouts and 3,500 held-out queries. Each other family 
used 2,000 held-out queries. All five comparisons met the prespecified matching 
rule, which requires an absolute mean recall difference of at most one 
percentage point and a paired 95% bootstrap lower bound above −1 point.
   
   DiskANN was rebuilt once per layout using the unified IVF-FLAT outer 
sampler. Both builds used 64 shards, graph degree 32, build search width 64, 32 
PQ subquantizers and F16 raw vectors. Range searched 64 shards with graph 
search width 16. Centroid searched 10 shards with width 128. The recall 
difference was −0.105 percentage points (paired 95% interval [−0.260, +0.055]). 
Centroid took 8.12 s longer to build and reduced query P95 from 46.75 ms to 
13.26 ms.
   


-- 
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: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to