Source-linked AI summary
WaRP: Workload-Aware Request Planning for Vector Retrieval on Object Storage
Ruipeng Wan, Xinyu Zeng, Yiming Qiao, Huanchen Zhang
TL;DR
Object-store-backed vector search must group payload reads despite fixed per-request overhead, GET charges, and workload-sensitive coalescing thresholds. WaRP optimizes those groups under a request budget and expected concurrency, alongside offline payload reordering. Across seven AWS S3 datasets, WaRP + Reorder improves QPS and reduces GETs relative to Lance while preserving recall.
Problem
Object-store Range-GET overhead and charges make fragmented reads costly, while existing fixed-threshold coalescing heuristics do not transfer reliably across datasets and workloads.
Source: §1 · p. 1Method
WaRP globally plans merged payload ranges using a request-time surrogate, a per-query request budget, and expected request parallelism, paired with offline payload reordering.
Source: §1 · p. 2Results
1.09–3.48× QPS and 2.12–5.19× fewer GETs than Lance across seven AWS S3 datasets, while preserving Lance’s recall.
Source: §1 · p. 2Takeaways & Limitations
The request budget directly bounds a query’s GET charge and provides a knob for balancing that charge against latency.
Source: §1 · p. 2The formulation assumes a nondecreasing request-time surrogate and preserves candidates and recall only under a fixed probe set and evaluation procedure.
Source: §3 · p. 3
Abstract
from arXiv · showhide
Modern vector search systems keep payload vectors in cloud object storage and only a compact routing index on fast local storage, typically using cluster-based ANN indexes. This design inherits a problem existing systems do not address. On object storage, small Range-GETs have latency dominated by fixed per-request overhead and are billed per request. Existing readers either issue one request per probed cluster, or coalesce adjacent ranges with hand-tuned gap or span thresholds that do not transfer across datasets or query workloads. We formulate the grouping of probed-cluster byte intervals into object-store requests as a global per-query optimization problem and present WaRP, a workload-aware request planner that solves it efficiently. Given the sorted byte intervals, a limit on the number of requests per query, and an estimate of how many object-store requests from one query can proceed concurrently under the target serving configuration, WaRP searches for a merge plan that minimizes a concurrency-aware latency surrogate while satisfying the request limit. Using an optimized dynamic program and adaptive frontier search, WaRP returns a plan within $(1{+}\epsilon)$ of the optimum, with per-query planning overhead under $10$ms even in the most demanding tested settings. A lightweight offline reordering pass further improves request mergeability without changing the semantics of ANN search. We implement WaRP inside Lance's I/O scheduler and evaluate it on AWS S3. We build IVFPQ indexes on seven datasets, including SIFT100M and DEEP100M at the 100M-vector scale. WaRP + Reorder improves QPS by $1.09--3.48\times$ and reduces GETs by $2.12--5.19\times$ relative to Lance, while preserving Lance's recall.
1 Introduction
Object-store request planning must balance fixed per-request latency and GET charges against overfetch, but local coalescing thresholds do not transfer reliably across datasets and workloads. WaRP treats merging as a global per-query optimization, pairs it with offline payload reordering, and improves throughput while preserving recall.
1 Introduction
- Small Range-GETs are dominated by fixed request overhead, while merging them trades fewer requests against overfetch and GET charges.A 1 KB request takes roughly 25 ms versus about 30 ms for a 1 MB request; merging all three example ranges overfetches 2.7 MiB.Source: §1 · p. 1
- Fixed gap-threshold coalescing heuristics are unreliable across datasets and workloads, motivating global optimization over ordered payload intervals.Parameters that work well on one dataset can perform sharply worse on another.Source: §1 · p. 2
- Coarser clustering is not a substitute: at matched recall it cuts requests by 58% but enlarges the candidate set by nearly 50%, raising compute.Larger clusters also weaken pruning, increase update and rewrite costs, and limit flexibility under filters or mixed workloads.Source: §1 · p. 2, Table 1 · p. 2
- WaRP uses a request budget, expected request parallelism, and an offline-calibrated request-time surrogate to find a near-optimal merge plan; offline reordering brings likely co-accessed clusters closer.The planner’s per-query overhead is under 10 ms in the most demanding tested settings, and the methods preserve probe selection and recall.Source: §1 · p. 2
- 1.09–3.48× QPS and 2.12–5.19× fewer GETs than Lance: WaRP + Reorder preserves Lance’s recall across seven AWS S3 datasets.The implementation is integrated into Lance’s I/O scheduler.Source: §1 · p. 2
- The paper contributes a practical dynamic-programming planner, adaptive frontier search, offline IVF payload reordering, and an end-to-end evaluation in Lance.The optimization runs on the query critical path and reordering creates merge opportunities with less overfetch.Source: §1 · p. 2
2 Background and Motivation
Cluster-based ANN systems select clusters using a local routing structure and fetch their payloads from object storage. WaRP targets the intervening request-planning step, where object-store latency and charges make the grouping of payload reads consequential.
2 Background and Motivation
- The background frames cloud-based ANN as a setting where payloads reside in object storage while query execution uses a local routing structure.This arrangement separates storage from compute and is used with cluster-based index families.Source: §2 · p. 2, §2.1 · p. 2
2.1 Cluster-Based ANN Indexes
- Cluster-based ANN indexes select a probe set using cluster centroids, then fetch those clusters’ payloads for candidate evaluation.The scope includes IVF variants and designs that use auxiliary graphs or trees to accelerate probe selection.Source: §2.1 · p. 2
2.2 Cloud Object-Store I/O Characteristics
- Cloud object stores offer low-cost elastic payload storage, but Range-GETs have substantial fixed overhead and variable latency with a long tail.Request count affects GET charges; where transferred bytes are billed, overfetch can also incur transfer charges.Source: §2.2 · p. 2
- WaRP calibrates a request-time surrogate from measured object-store latency; the convex fit approximates single-request latency in the primary same-region setting.Figure 4a compares convex and monotone fits and reports MAPE on request sizes excluded from fitting.Source: §2.2 · p. 3
2.3 Execution Pipeline and Planning Challenge
- The query pipeline selects clusters locally, fetches cache-missing payloads remotely, then evaluates or reranks candidates; request planning groups the required reads between selection and retrieval.WaRP focuses on this step rather than changing the probe set.Source: §2.3 · p. 3, Figure 3 · p. 3
3 Problem Formulation
The formulation groups sorted required byte intervals into contiguous merged ranges under a per-query request budget. It evaluates plans using a request-time surrogate and a concurrency-aware objective, while retaining every required payload.
3 Problem Formulation
- The input is a sorted interval set, a request budget, and an estimate of per-query request parallelism; the budget directly bounds GET charge.The formulation assumes a nondecreasing request-time surrogate mapping range length to estimated completion time.Source: §3 · pp. 3–4
- A feasible plan partitions the intervals into contiguous groups, each fetched as one range that may include gaps between required intervals.Every required payload is preserved, so a fixed probe set and evaluation procedure leave the candidate set and recall unchanged.Source: §3 · p. 3
- W(π) sums estimated request times for serial execution, while B(π) is the largest request-time estimate for ideal parallel execution.The planner uses a calibrated surrogate for each planned range’s completion time.Source: §3 · pp. 3–4
- The feasible plans form a frontier in (B,W) space, whose lowest-T_P vertex is optimal for finite P.The objectives depend on a plan through (W(π), B(π)) and do not increase when either quantity decreases.Source: Figure 5 · p. 4, §3 · p. 4
- For finite request parallelism P, T_P is a planning objective rather than an exact latency predictor and interpolates between W(π) and B(π).The estimate of P reflects expected request parallelism under the target serving configuration.Source: §3 · p. 4
4 Request Planning
WaRP formulates grouping sorted payload intervals into object-store requests as a per-query optimization balancing estimated request time under a request budget and serving parallelism. It combines exact dynamic programs with adaptive frontier search and accounts for the resulting GET and transfer costs.
4 Request Planning
- WaRP searches feasible merge plans to minimize a concurrency-aware objective while respecting the per-query request budget.For finite parallelism, it searches between plans minimizing total request-time estimates and plans minimizing the slowest request estimate.Source: §4 · p. 4, §4.1 · p. 4, §4.3 · p. 6
4.1.1 Basic Dynamic Program.
- The Sum-Minimizing DP partitions sorted intervals into at most Kmax contiguous groups and minimizes the sum of their predicted request times.Its basic form takes O(n^2 Kmax) time; recording minimizing splits allows plan recovery by backtracking.Source: §4.1.1 · p. 4
4.1.2 Divide-and-Conquer DP Optimization.
- Convex request-time surrogates enable divide-and-conquer optimization, reducing the Sum-Minimizing DP to O(n Kmax log n) time and O(n Kmax) space.Monotone optimal split points support the acceleration; a nondecreasing but nonconvex surrogate leaves the basic DP exact but unaccelerated.Source: §4.1.2 · pp. 4–5
4.2 Minimizing 𝑩
- The min-B endpoint minimizes the maximum merged span under Kmax, using binary search and a greedy feasibility scan.A span cap is feasible when the scan partitions the intervals into at most Kmax groups.Source: §4.2 · p. 5
4.3 Finite 𝑷: Searching the Frontier
- For finite parallelism, Adaptive Frontier Search explores plans trading off maximum request time B and summed request time W.It expands the segment with the smallest lower bound and evaluates a midpoint cap using the thresholded DP.Source: §4.3.1 · p. 6, §4.3 · p. 6
4.3.2 Complexity and Guarantees.
- The adaptive search returns a plan within 1+epsilon of the optimum and, in tested cases with a few hundred intervals, finishes in single-digit milliseconds per query.The exact approach of enumerating all candidate caps is too expensive online; early-stopped Lagrangian relaxation is an optional fast path when Kmax is large.Source: §4.1.2 · p. 5, §4.3.2 · p. 6, §4.3 · p. 6
4.4 Cost Accounting
- A merge plan determines both payload GET count and bytes read, so same-region charges depend on GETs while cross-region charges also depend on bytes.The paper focuses on the common same-region setting.Source: §4.4 · pp. 6–7
5 Cluster Payload Reordering
WaRP reorders IVF payloads offline to place frequently co-accessed clusters closer together, improving opportunities to merge requests. It measures locality using a weighted co-access gap and compares practical ordering methods.
5 Cluster Payload Reordering
- Reordering places frequently co-accessed clusters closer, reducing required-interval gaps and enabling one request instead of three with one extra cluster payload overfetched.Figure 6 depicts each box as one cluster in contiguous layout.Source: §5 · p. 7
5.1 Layout Materialization and Maintenance
- The permutation is materialized during the existing payload-writing phase, and updated during rebuilds or segment merges without a separate rewrite pass.Each payload is written once; the added work is computing the permutation.Source: §5.1 · p. 7
5.2 Measuring Co-Access Locality
- The weighted co-access gap combines how often cluster pairs are selected together with their byte separation; lower values mean better co-access locality.Direct minimization is an instance of minimum linear arrangement, which is NP-hard.Source: §5.2 · p. 7
5.3 Reordering Methods
- The evaluated methods order clusters using centroid geometry or query-log co-access counts; the default PCA n-D plus Z-order needs no query log and avoids spectral methods’ cubic cost.Spectral (log) can incorporate workload information when reliable query logs and higher offline cost are acceptable.Source: §5.3 · pp. 7–8
- Figure 7 normalizes end-to-end results to Lance, with cache-on SIFT100M referenced to cache-off SIFT100M Lance; Figure 8 varies I/O or query concurrency.Figure 7 error bars show propagated sample standard deviations across three runs.Source: Figure 7 · p. 8, Figure 8 · p. 8
6 End-to-End Evaluation
WaRP is integrated into Lance’s I/O scheduler and evaluated end-to-end on AWS S3, with cached and concurrency-scaled settings also tested. The evaluation compares throughput, GET counts, latency, and cost across seven datasets.
6.1 Experimental Setup
- WaRP was integrated into Lance’s I/O scheduler (v2.1.0beta.0) and evaluated end-to-end on AWS S3 across both 100M-scale datasets and five real 1M-scale datasets; Table 3 lists nine datasets.Each dataset and method was run three times in counterbalanced order, with 200 warm-up queries followed by 10,000 measured queries per run.Source: §6 · p. 8, §6.1 · pp. 8–9
6.2 Overall Performance
- 1.09–3.48× Lance’s QPS and 2.12–5.19× fewer GETs are achieved by WaRP + Reorder across seven datasets; p95 and p99 latency also fall on six.GIST1M is the latency exception because its larger, 960-dimensional vectors already amortize more fixed request overhead.Source: §6.2 · p. 9
- Both WaRP variants lower same-region cost on all seven datasets, but increase payload bandwidth and have higher cross-region cost than Lance.The evaluation applies Tokyo’s S3 GET price; cross-region transfer adds a data-transfer charge.Source: §6.2 · p. 9, Table 4 · p. 9
6.3 Effect of Caching
- At 50% cache capacity, remote GETs fall by 27–43% and all three methods improve throughput and p95 latency; WaRP variants still outperform Lance at both cache sizes.A 10% cache reduces remote GETs by 4–8% while changing throughput and p95 latency little; caching and request planning are complementary.Source: §6.3 · p. 9
6.4 Concurrency Scaling
- At Q=128, WaRP + Reorder delivers 1.47× Lance’s QPS and reduces p95 latency by 1.46×, with its advantage persisting across tested query concurrency levels.Lance peaks at about 99 QPS at Q=64, while WaRP + Reorder reaches about 150 QPS at Q=96.Source: §6.4 · p. 9
7 Microbenchmarks
The microbenchmarks isolate I/O completion using shared cluster intervals and compare WaRP with separate reads and fixed-threshold merging policies. They test throughput, parameter robustness, planner overhead, reordering choices, and sensitivity to probe count and cluster granularity.
7.1 Throughput and Planned Range Reduction
- WaRP + Reorder achieves the highest peak QPS across all six datasets, while too few or too many planned ranges hurt performance.Too few ranges overfetch through large requests; too many create small requests that add overhead and consume I/O slots.Source: §7.1 · p. 10, Figure 9 · p. 10
- About 3× the QPS of Separate is reached on SIFT1M and DEEP1M, while gains are smaller on Random1M without co-access locality and on high-dimensional OpenImage and MSong.OpenImage and MSong reach 1.6–1.7× Separate; larger cluster payloads already amortize more fixed request overhead.Source: §7.1 · p. 10
7.2 Parameter Robustness
- The default P, set to the I/O concurrency limit divided by Q, achieves on average 97% of the best tested QPS across 18 panels without per-workload tuning.P estimates how many requests from one query can progress concurrently.Source: §7.2 · p. 10
- SIFT-tuned Greedy matches WaRP on its validation workload but falls behind after workload or dataset shifts.The tested shifts change locality, probe count, both together, or transfer the setting from SIFT1M to MSong.Source: §7.2 · p. 10
7.3 Planner Overhead
- At common settings with n_probe≤256, the planner runs in 0.5–2.2 ms; where the unoptimized planner finishes within 120 seconds, no optimized plan is more than 3.5% from exact, with average error below 1.2%.At n_probe=256 and K_max=128, adaptive frontier search drops overhead to roughly 6 ms, and the Lagrangian fast path reduces it to about 1.7 ms.Source: §7.3 · p. 11
7.4 Reordering Method Comparison
- At C=8192, projection methods take 1.4–30 ms versus 112–143 ms for spectral methods, which do not consistently produce better locality.PCA n-D + Hilbert performs best on SIFT1M, while Spectral (log) performs best on GloVe; the paper deploys PCA n-D + Z-order.Source: §7.4 · p. 11, Figure 13 · p. 12
7.5 Probe Count and Cluster Granularity
- With K_max=n_probe/2, WaRP + Reorder stays above Separate as n_probe rises from 32 to 512; at fixed probe fraction, QPS falls 3.3× for Separate versus 1.2× for WaRP + Reorder as clusters shrink.With the tighter K_max=n_probe/4 budget, WaRP + Reorder trails Separate at small probe counts.Source: §7.5 · p. 12
8 Related Work
Related work spans ANN indexing, object-storage retrieval, and data reordering. WaRP differs by optimizing the retrieval of selected IVF cluster payloads and arranging variable-size payloads for object-store request planning.
ANN Indexes
- WaRP operates after IVF probe selection to optimize retrieval of selected clusters from object storage, unlike ANN methods focused on index structures or local-SSD I/O.The paper includes IVF variants and auxiliary graph or tree structures used to accelerate probe-set selection.Source: §8 · p. 12, Figure 14 · p. 12
Object Storage, Remote I/O, and Vector Retrieval
- For cache-missing IVF payloads, WaRP coalesces byte intervals into fewer Range-GETs and replaces fixed gap or span thresholds with global request optimization.The related-work discussion notes that WaRP + Reorder achieves the highest peak QPS across six datasets in the microbenchmarks.Source: §8 · p. 12
Data Reordering and Locality Optimization
- Unlike fixed-size page reordering for disk-based ANN, WaRP reorders variable-size IVF payloads to reduce gaps among clusters likely to be probed together.The online planner can then select variable-length Range-GETs for each query.Source: §8 · p. 12
9 Conclusion
The paper presents WaRP as an object-storage request planner and pairs it with offline payload reordering. Across seven datasets, WaRP + Reorder improves QPS and reduces GETs relative to Lance.
9 Conclusion
- Across seven datasets, WaRP + Reorder delivers 1.09–3.48× Lance’s QPS and reduces GETs by 2.12–5.19×.The reported results establish request planning as an optimization layer between ANN probe selection and object-store reads.Source: §9 · p. 12
- WaRP uses a request-time surrogate and an optimized planner fast enough for the query path, while offline payload reordering improves co-access locality and merge opportunities.The conclusion characterizes the planning layer as practical between probe selection and object-store reads.Source: §9 · p. 12
- The conclusion frames request planning as a practical optimization layer between ANN probe selection and object-store reads.Source: §9 · p. 12