Filtered Vector Search in a Disaggregated Lakehouse: Composing Table-Format Pruning with Per-File ANN

Filtered Vector Search in a Disaggregated Lakehouse: Composing Table-Format Pruning with Per-File ANN Rakesh Jain

Thomas Griffin

Syed Zawad

IBM Research San Jose, CA, USA rakeshj@us.ibm.com

IBM Research San Jose, CA, USA tdg@us.ibm.com

IBM Research San Jose, CA, USA szawad@ibm.com

arXiv:2608.05441v1 [cs.DB] 5 Aug 2026

ABSTRACT Approximate nearest-neighbor (ANN) search increasingly runs alongside structured data—“find the 10 nearest documents where tenant=’acme’ AND lang=’en’”—yet similarity and filtering are usually bolted together: a specialized vector index for one, a separate filter step for the other. We ask what happens when both live inside an open lakehouse table (Apache Iceberg over Parquet on object storage), where the engine already owns a mature filepruning stack (partition pruning, zone-maps, a bitmap index). We embed an IVF index in place in each Parquet file’s footer and make filtered vector queries fast not with a new filtering algorithm but by composing the table’s existing file pruning with per-file ANN: the planner prunes data files by the predicate first, then runs IVF only over the survivors. The index is built distributed and nondestructively—a metadata-only Iceberg replace that every other engine still reads—and a rendezvous-hashed per-file cache keeps object-store read latency from swamping the algorithmic win. Because the vectors never leave the table, vector search also inherits the lakehouse catalog’s existing access control unchanged, rather than requiring a second authorization surface in a copied-out vector store. The payoff comes entirely from file pruning. On an 11.5M × 768 table, warm IVF search is ∼32× faster than brute force at recall@10 ≥ 0.90, a selective predicate having pruned 355 of 444 data files before ANN runs; on 5M real IBM Granite embeddings, a filter arriving across a join prunes four of five region partitions and runs nearly two orders of magnitude (∼94×: 14.7 s → 157 ms) faster than the query-time join at identical top-𝑘, once the reduction is materialized into a region-partitioned layout. We characterize when the composition pays off—it requires file-level locality on the filter column, and the residual predicate is only safe to push into the search over a provably pure (partitioned) column, not a merely sorted one—and report the failure modes we hit bolting ANN onto a lakehouse engine.

CCS CONCEPTS • Information systems → Data management systems; Retrieval models and ranking.

KEYWORDS vector search, approximate nearest neighbor, lakehouse, Apache Iceberg, Parquet, data skipping, disaggregated compute

1

INTRODUCTION

Retrieval-augmented generation, semantic search, and recommendation all issue the same query shape: return the 𝑘 vectors nearest a query embedding, restricted by a structured predicate. Two facts about production data make this awkward. First, the vectors do not live alone; they sit next to the columns users filter on—tenant, language, category, timestamp, access-control tags—in tables that already hold terabytes of that structured data. Second, those tables increasingly live in an open lakehouse format [3]: Apache Iceberg [1] over Parquet [2] files on object storage, read by many engines (Spark, Trino, Presto, DuckDB) with compute disaggregated from storage. The prevailing answer is to copy the vectors into a dedicated vector database (Milvus [21], pgvector [14]) or a purpose-built columnar vector format (Lance [15]), and reproduce the predicate there. This duplicates data, diverges from the source of truth, and— critically—forces the filtering problem to be solved again, inside the vector system, with specialized filtered-ANN algorithms. A recent in-depth experimental study [16] surveys a dozen such algorithms (segmented graphs, label-partitioned indexes, joint traversal) and confirms both that filtered ANN is an active open problem and that its central lever is partitioning: the study finds partitioning “effective for low-selectivity queries.” That study is strictly in-memory and single-node: every index it benchmarks lives in RAM on one machine, and its notion of “pruning” is graph-edge pruning inside the index. We take a different position. A lakehouse engine already has a partitioning-and-pruning substrate—the physical machinery it uses to skip data files that cannot satisfy a query: Iceberg partition pruning, per-column zone-maps (min/max), and a scalar bitmap file index. If the vector index lives inside the same table, filtered ANN need not reinvent filtering; it can reuse the table’s file pruning and run similarity search only on the files that survive the predicate. The algorithmic-layer finding of [16]—partitioning helps at low selectivity—becomes, one layer down, a storage-layout statement: filtered vector search is fast exactly when the filter column has file-level locality, so the table’s own pruning can drop most files before the ANN index is consulted. Realizing this on a real disaggregated lakehouse engine is where the systems work lies, and it is the contribution of this paper. We embed an IVF [13] index in each Parquet file’s footer—following an This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s).

2

emerging technique [10, 23]—but the single-file, single-node version of that idea does not survive contact with a distributed, S3backed engine. We had to solve: (i) building the index distributed and non-destructively so the table remains a valid Iceberg table readable by other engines; (ii) a query planner rewrite that composes predicate file-pruning with per-file ANN and a direct top-𝑘 assembly that avoids re-scanning data; and (iii) making warm latency acceptable when compute is separated from storage and the per-query bottleneck is random-access rescore reads over object storage.

RELATED WORK

Filtered ANN algorithms. A large body of work makes similarity search predicate-aware at the index level. Chronis et al. [7] organize the space into three families—pre-filter (restrict the candidate set, then search), post-filter (search, then discard non-matching), and in-filter (evaluate the predicate during index traversal)—and argue the field’s central goals are stable recall (the same recall regardless of the predicate) and declarative recall (the user states a target, not a knob). Concrete designs span graphs [17, 19], invertedfile/quantized indexes [13], predicate-agnostic traversal [18], labelaware graph construction (Filtered-DiskANN [11], NHQ [22]), and partition indexes tuned to the filter (CAPS [12]). The recent experimental study of Li et al. [16] taxonomizes and benchmarks a dozen such algorithms in a uniform in-memory, single-node setting (indexes in 2 TB RAM, up to 10M vectors, selectivity 0.1–100%). Our work is orthogonal and complementary: we do not propose a filtered-ANN algorithm. We take the simplest pre-filtering strategy—restrict the candidate set, then search it—and realize it at the storage layer of a distributed lakehouse, where the “restrict” step is the table format’s own file pruning rather than an in-index mechanism. This is precisely the case Chronis et al. single out as having an exact optimum: for a categorical-equality filter, the ideal is a partitioned index, one partition per value [7]; our locality condition (§6) is that same statement realized in the physical layout of an open table rather than in a bespoke index. Their finding and Li et al.’s (partitioning helps at low selectivity) and ours (file-level locality on the filter column is the precondition) are the same principle at three layers. What we do not yet provide is stable/declarative recall across selectivities—our over-fetch 𝑠 and 𝑛 probe are still explicit knobs—which we return to in §8 and §10.

Contributions • Composition of lakehouse pruning with per-file ANN (§5). A planner rewrite pushes the query predicate through the table’s existing file-pruning tiers (partition / zone-map / bitmap), then runs IVF only over surviving files, assembling the global top-𝑘 from workers’ projected candidate rows with no second data scan. A residual filter over a file-pure column (partition or materialized-cluster) is pushed into the per-file search as a mask, keeping the filtered query on the fast path rather than aborting to a full rescore—sound precisely because sorted is not pure, so SORT/ZORDER columns are excluded from the pushdown. • A locality condition for filtered ANN (§6). We show— and measure—that the composition pays off iff the filter column has file-level locality; a bitmap over a uniformlymixed column prunes nothing. This is the storage-layer analogue of the in-memory “partitioning helps” finding of [16]. • Distributed, non-destructive in-place index build (§4). Stateless compute pods rewrite each file’s footer in parallel; the engine commits a metadata-only Iceberg replace (delete-old + add content-identical-new), preserving timetravel and leaving files readable by any Parquet reader. • Disaggregated warm-set engineering (§7). A per-file cache (index blob + embedding matrix) with rendezvoushashed file→pod placement whose warmth survives autoscaling; we trace the 1.0× → 32× speedup to the specific fixes. • Evaluation and lessons (§8,§10) on an 11.5M × 768 table, including the failure modes of bolting ANN onto a lakehouse engine.

Vector databases and vector formats. Dedicated systems (Milvus [21], pgvector [14]) and vector-native columnar formats (Lance [15]) deliver excellent ANN but require the vectors to be copied out of the lakehouse into a system or format they control. Copying out has a governance cost that is easy to overlook: the copy leaves the perimeter the lakehouse catalog governs, so it needs its own authentication, table- and column-level permissions, row/column masking, and audit trail—a second access-control surface that must be kept in sync with the source table’s policy and can silently drift from it. Our goal is the opposite: keep vectors in the standard Iceberg/Parquet table so they stay the single source of truth, remain readable by every lakehouse engine, and—because the query goes through the same catalog—inherit the table’s existing access control unchanged, with no separate policy to define or reconcile. ANN is added as an in-place, ignorable footer artifact.

One framing point is worth stating up front, because it recurs throughout the paper. The pruning-plus-IVF composition removes an enormous share of the arithmetic—a simple cost model (§9) predicts ∼500× fewer distance computations at 𝜎=0.2—yet the end-toend speedup we measure is only ∼30×. The gap is not a disappointment; it is the systems contribution. On disaggregated hardware the fixed per-query costs (two-phase dispatch, object-store reads, shard merge) dominate warm latency, and the value of the warmset engineering (§7) is precisely that it keeps those fixed costs from swamping the algorithmic win. The reader should therefore read the 32×/94× headline numbers as “how much of a large algorithmic win survives the systems tax,” not as the algorithmic win itself.

Disk- and object-store ANN. Once the index leaves RAM, the design problem becomes minimizing random-access reads. DiskANN [19] keeps a compressed representation in memory and reads full vectors from a local SSD only for rescoring; SPANN [6] is a memory–disk hybrid inverted index that holds centroids in memory and posting lists on disk, the same coarse-quantize-thenfetch shape our per-file IVF uses one level further out (centroids in a cached footer blob, vectors random-read from object storage). Both target a single node’s local disk; the disaggregated, S3-backed setting adds network latency on every fetch, which is what makes 2

Coordinator (stateless) plan + plan_files pruning

our warm-set caching (§7) load-bearing rather than incidental. Embedding an ANN index in a Parquet footer and searching it from a query engine has also appeared in practice [10, 23]; these are single-file or single-node in spirit. We contribute the distributed build, the non-destructive Iceberg commit, the pruningcomposition planner rewrite, and the disaggregated warm-set mechanics that a multi-node, S3-backed deployment requires.

shards

read

read rea d

metadata ...

read-compute (autoscaled, per-file cache)

build

build

rewrite

write-compute

Object store (S3) Parquet + footer IVF

Concurrent work: ANN indexes in Apache Iceberg. Closest to our setting is the concurrent proposal of Borycki [5], which also attaches distributed ANN indexes to Iceberg on a computedisaggregated engine and, like us, inherits atomicity, time travel, and multi-engine readability from the table format. The two designs diverge on three axes that define our contribution. (i) Storage. That work stores a Vamana/DiskANN graph in a Puffin sidecar file bound through the snapshot summary, leaving the Parquet data files untouched; we embed a per-file IVF index in each Parquet footer, copying data pages byte-for-byte so file-local row ordinals stay valid—keeping the index inside the same object the row lives in, at the cost of the rewrite the sidecar avoids. (ii) Filtering. Its query path is similarity search with centroid-distance file elimination and coarse bloom-filter/zone-map pruning “against ordinary columns”; it does not compose a structured predicate with file pruning, push a residual predicate into the per-file search under a purity condition, or reduce a filter arriving across a join—the three mechanisms that are the subject of §5–§5.2. (iii) Evidence. That work is explicitly pre-production and reports projected build and query performance for tables up to 109 vectors; our results are measured on real 11.5M- and 5M-vector corpora. The two are complementary: a sidecar graph and an in-footer IVF are points on the same design space, and the filtered-query composition we contribute is orthogonal to where the index blob physically lives.

Figure 1: Disaggregated topology. The coordinator prunes files from Iceberg metadata and dispatches shards; stateless read/write pools touch S3 directly. Build fans out over the write pool (rewrite files in place); query fans out over the read pool (per-file ANN + rescore). Both pools scale to zero when idle, so per-pod cache state must survive membership churn.

(the search retains 𝑘·𝑠 candidates per shard so a residual filter still leaves ≥ 𝑘); and 𝜎 ∈ (0, 1] is the selectivity of the query predicate (the fraction of files, equivalently rows under file-level locality, that survive pruning). These are introduced again in context below. The engine. Our system is a Flight-SQL query engine over Apache Iceberg tables stored as Parquet on S3-compatible object storage. Compute is disaggregated: a small set of stateless coordinator pods plans queries and holds the catalog/metadata caches; a larger, autoscaled pool of stateless read-compute pods executes scan and search shards; a separate write-compute pool handles ingest, rewrite, and index builds (Figure 1). No worker owns data; every pod reads Parquet from object storage on demand and is scaled to zero when idle. Each compute pod runs the actual scan/search in a co-located worker process addressed over Flight; the coordinator dispatches a shard by sending it the file list and the operation. This is the standard modern lakehouse topology [3, 4, 9] and it shapes every design decision below—most importantly, that (a) reading any file crosses the network to object storage, so random-access reads are expensive and worth caching, and (b) the worker set changes size mid-workload as the autoscaler reacts, so any per-pod state must tolerate membership churn (§7).

Vector search in lakehouse/OLAP engines. Vector indexing is increasingly a feature of columnar analytics engines rather than only of dedicated vector stores: DuckDB’s VSS extension [10] and ClickHouse’s approximate-nearest-neighbor indexes [8] both add in-engine ANN over otherwise-relational tables, and Lance [15] is a columnar format built for it. These co-locate the index with the data as we do, but each owns its own storage format or engine. Our target is the open-table case: the vectors stay in a standard Iceberg/Parquet table readable by every engine, and the index is an ignorable footer artifact rather than a format-specific structure; where the Iceberg community pursues a native vector column, our footer approach is the compatible interim that requires no format change.

The vector column and footer index. A table declares an embedding column as FLOAT[𝑑] (fixed dimension 𝑑), physically an Iceberg list<float>. The writer tunes this column so that each vector occupies its own Parquet data page (page-size limit = 4𝑑 bytes, uncompressed, no dictionary), so a random-access read fetches exactly one vector. All other columns store normally. An IVF index— 𝐶 centroids from mini-batch 𝑘-means plus per-centroid posting lists of file-local row ordinals—is serialized into a blob and appended after the Parquet footer, with a tiny pointer in the footer’s key-value metadata [23]. Standard readers seek to the footer and never see the blob; ANN-aware readers follow the pointer. The index is per file: each file has independent centroids, and recall comes from a per-query candidate over-fetch, not a global index.

Lakehouse engines. Disaggregated cloud query engines [4, 9] established compute-storage separation and metadata-driven file skipping as the performance foundation of the lakehouse. We show that this same file-skipping substrate is exactly what filtered vector search needs, if the vector index is co-located in the table.

3

build tasks

BACKGROUND AND SYSTEM SETTING

Notation. Throughout, 𝑑 is the embedding dimension; a table holds 𝑁 vectors in 𝜙 data files; 𝐶 is the number of IVF centroids per file; 𝑛 probe is the number of centroids probed per query; 𝑘 is the requested neighbor count and 𝑠 ≥ 1 the over-fetch safety factor

The pruning substrate. Independently of vectors, the engine skips data files a query cannot need, in three tiers evaluated at plan time from Iceberg metadata: (1) partition pruning on 3

write pool. Two such doublings took a ∼3M-row seed to 11.5M in ∼90 s, versus the serial ingest stalling at 3M in 25 min.

identity/derived partition columns; (2) per-column zone-maps (min/max per file/row-group); (3) a consolidated scalar bitmap index—a per-file value-presence set for low-cardinality columns— materialized once per snapshot. The planner turns a SQL WHERE into an Iceberg predicate and returns the surviving file set. This substrate exists to speed up ordinary analytic queries; §5 reuses it verbatim for vector queries.

4

5

QUERY: COMPOSING PRUNING WITH ANN

A vector query is ordinary SQL: SELECT id, title FROM docs WHERE category = ’tech’ ORDER BY array_distance(embedding, q) LIMIT 10

DISTRIBUTED, ICEBERG-COMPATIBLE INDEX BUILD

The planner recognizes the ORDER BY array_distance(·, literal) LIMIT 𝑘 shape on a table with a registered vector index and rewrites it into a three-step plan; any unmet precondition falls back to a plain scalar array_distance scan (correct, slower).

Building a per-file footer index for a large table is embarrassingly parallel across files, but doing it inside a live Iceberg table—without breaking readers—is not obvious. Fan-out. CREATE VECTOR INDEX ON Col1 returns immediately and runs asynchronously (a large build takes minutes; a synchronous RPC trips connection timeouts). The coordinator enumerates the current snapshot’s live data files, shards them across the writecompute pool, and dispatches a “build these files” task to each pod. A pod reads each assigned file from S3, trains 𝑘-means on the embedding column, appends the IVF blob after the footer, and uploads a new object (object stores have no atomic rename; a new path also keeps the parent snapshot valid). Crucially, the data pages are copied byte-for-byte, so file-local row ordinals—the identity the posting lists reference—are preserved exactly.

Step 1: prune files by the predicate. The rewrite runs the query’s WHERE through the same file-planning routine ordinary scans use (§3), applying partition, zone-map, and bitmap pruning. The output is the set of data files that can satisfy the predicate. This is the crux: the vector query pays nothing to build filtering machinery—it inherits the table’s. Step 2: distributed IVF over survivors. The surviving files are sharded across read-compute pods; each pod, for each of its files, loads the footer IVF index, finds the 𝑛 probe nearest centroids to 𝑞, gathers their posting lists, random-reads those candidate vectors, and rescores with exact L2, returning a per-file shortlist. The coordinator merges shard results into a global candidate list of size 𝑘 · 𝑠 (a safety factor 𝑠 over-fetches to absorb the residual row predicate).

Non-destructive commit. Each worker returns a new DataFile whose record_count equals the original’s. The coordinator commits a metadata-only replace: one new manifest with add-entries for the new files and delete-entries for the old, published as a Replace-operation snapshot. Old files remain referenced by the parent snapshot (time-travel intact) and are physically removed only by ordinary snapshot expiry. The result is a normal Iceberg table: Spark or DuckDB read the new files as plain Parquet, ignoring the footer blob. Per-file failures are non-fatal (that file stays un-indexed and falls back to brute force at query time); re-running fills gaps.

Step 3: direct top-𝑘, no rescan. Because each worker already read its candidate rows to rescore, it also returns the query’s projected columns for those rows (as an Arrow batch aligned with the candidates). The coordinator merges by distance, applies the residual row predicate, and emits the top 𝑘—with no second pass over the data. This matters concretely: an earlier design re-ran the projection SQL over the candidate files through the engine’s normal scan path, which read those files in full and cost ∼138 s— indistinguishable from brute force—even though the IVF step had already identified the exact candidate rows in ∼seconds. The IVF search already touched those rows to rescore them; carrying their projected columns back with the distances is what collapses the query to sub-second. The lesson generalizes: in a per-file ANN design, the search and the projection must be fused, or the projection re-does the scan the index was meant to avoid.

Making the build CPU-bound, not core-bound. The build’s cost is 𝑘-means, which is compute-bound. Two mistakes we corrected mattered at scale. First, the per-file build must run on a blocking thread pool, not inline on the async executor—otherwise concurrent file builds serialize on one runtime worker and an 8-core pod pins one core. Second, index granularity is per file: 𝐶 should √track rows-per-file, not table size. We start from the common rows/file rule of thumb, scale it up by a small constant so each posting list stays short, and round to a power of √ ⌈log2 (4 rows/file) ⌉ . For our ∼26k–34k-row files this gives two: 𝐶 = 2 √ 4 rows/file ≈ 645–738, which rounds to 𝐶=1024; the rule is a floor rounded up, not an exact target. Over-clustering (we initially used 𝐶=4096) inflates 𝑘-means cost (𝑂 (𝐶 · 𝑑) per point) with no recall benefit; 𝐶=1024 built far faster at comparable recall. With both fixed, the build saturates all cores of every pod.

Correctness details. The query embedding is a SQL array literal cast to FLOAT[𝑑] on both sides of array_distance (the stored column is a variable list and literals infer as decimal); the planner sees through these casts. A dimension mismatch is a loud error, never a silent empty result. Files written after the last build carry no index and are searched by brute force within Step 2, so results stay correct as the table grows. A worked trace. Consider the example query on our 11.5M×768 table, laid out with file-level locality on category (444 data files, ∼26k rows each). Step 1 turns category=’tech’ into an Iceberg predicate; the scalar bitmap index reports tech present in only 89 files, so PlanFiles returns those 89 and drops the other 355 before a single vector is read. Step 2 shards the 89 survivors across the

Building the table itself. Generating a large embedding table by client ingest is a single serial stream (a few thousand rows/s at 𝑑=768). The distributed write path is far faster: seed a modest table, then INSERT . . . SELECT from the table into itself—the SELECT reads the table’s own files, which the coordinator shards across the 4

Algorithm 1 Filtered vector top-𝑘 (planner rewrite)

silently drop valid rows or admit invalid ones. Only identity partitioning, or a materialized clustering whose per-file value set we have recorded, guarantees a file is single-valued in the column. So SORT/ZORDER columns are excluded from file_local_cols: they still drive Step 1 file pruning, but their residual predicate is not pushed. If, after the mask, a file yields fewer than 𝑘 candidates (the overfetch was too thin for a selective residual), the worker falls back to the exact rescore path for that file, so recall is never traded for the shortcut. The net effect is that a partition- or cluster-column filter now gets the same in-memory fast path as an unfiltered query; only genuinely non-local filters pay the rescore.

Require: query embedding 𝑞, predicate 𝑃 , projection Π, limit 𝑘 1: 𝐹 ← PlanFiles(table, 𝑃 ) ⊲ partition/zonemap/bitmap prune 2: if 𝐹 = ∅ or no index on table then return FallbackScan() 3: end if 4: shards ← Rendezvous(𝐹, readPods) ⊲ stable file→pod 5: parfor shard (𝑤, 𝐹 𝑤 ) do 6: for file 𝑓 ∈ 𝐹 𝑤 do 7: (idx, 𝑀 ) ← CacheOrLoad( 𝑓 ) ⊲ footer IVF + matrix 8: 𝑐 ← Probe(idx, 𝑞, 𝑛 probe ) ⊲ posting rows 9: emit ⟨ 𝑓 , 𝑟, ∥𝑀 [𝑟 ] − 𝑞 ∥, Π (𝑀, 𝑓 , 𝑟 ) ⟩ for top 𝑘 ·𝑠 of 𝑐 10: end for 11: end parfor 12: 𝑅 ← merge shard emissions by distance 13: return top-𝑘 of {𝑟 ∈ 𝑅 : 𝑃 (𝑟 ) } ⊲ residual predicate; no rescan

5.2

read pool; each pod probes 𝑛 probe =10 of 𝐶=1024 centroids per file, so it exact-rescores ≈ 1% (𝑛 probe /𝐶) of each surviving file’s rows. The 89 survivors hold ≈ 2.3M rows (the 𝜎=0.2 fraction of the table), of which the IVF probe rescores ≈ 2.3M × 10/1024 ≈ 23k candidate distances—versus 11.5M for brute force, and consistent with the “∼0.2% of the vectors” figure below (0.2% of 11.5M ≈ 23k) and with the §9 cost model. Each pod returns its top 𝑘·𝑠 rows with the projected id, title columns already attached. Step 3 merges 89 short lists, applies the residual category=’tech’ check (a no-op here, since pruning was exact), and emits 10 rows—no file re-read. The two prunings compose multiplicatively: the predicate removes 4/5 of the files and IVF removes ∼ 99% of the rows within each survivor, so the query touches ∼ 0.2% of the vectors the brute-force baseline would.

5.1

Filtered ANN across a join

The filter is rarely a literal on the ANN table itself; more often it lives on a joined dimension—“nearest documents where the customer is in the EU”: SELECT d.id, c.region FROM docs d JOIN customers c ON d.customer_id = c.id WHERE c.region = ’EU’ ORDER BY array_distance(d.embedding, q) LIMIT 10

Vector databases typically handle this by post-filtering (fetch neighbors, then join and discard) or by maintaining a separate metadata index. In a SQL engine over a lakehouse, a better option falls out of the same substrate: semi-join reduction. The planner recognizes that the ANN is on one table (docs) and the join only constrains it, evaluates the dimension predicate to a key set ({customer_id : region=’EU’}), and rewrites the query to the single-table form . . . WHERE d.customer_id IN (𝑘 1, . . . , 𝑘𝑚 ) ORDER BY array_distance. . . . That IN-list is then just another predicate fed to PlanFiles (Step 1): if customer_id has file-level locality, the join predicate prunes files before ANN runs, exactly as a literal WHERE does. The dimension’s own columns (c.region) are reattached in Step 3 by rescoring over the shortlist with the dimension registered alongside the candidate files—a join over a few thousand rows, not the table. This reuses machinery the engine already has for analytic queries (the same dimension-key materialization that turns a starschema filter into a fact-table IN-list), so filtered-across-a-join ANN costs no new index and no new operator. The reduction is exact for an inner equi-join whose predicate is separable by table; other join shapes (post-join ranking, outer joins, predicates spanning both tables) fall back to a full ANN sweep plus a normal join— correct, just without the extra file pruning. When the dimension filter is so broad that its key set is very large, the planner abandons the reduction and runs the ordinary path rather than inline an enormous IN-list; dropping the filter is never an option, as it would admit out-of-filter neighbors.

Predicate pushdown for a residual filter

Step 1 prunes at the granularity of a file: it drops files that cannot match, but a surviving file may still hold non-matching rows. Whenever the predicate is not exactly covered by pruning, a residual row filter remains, and applying it is what forces the projection to materialize—in an early design, a residual filter disabled the direct top-𝑘 return of Step 3 and fell back to rescoring over every surviving file (the 138 s regression above). The fix is to push the residual predicate down into the per-file search: the coordinator serializes the scalar comparisons (=, IN, ranges, and their conjunctions over scalar columns) into the shard request, and each worker applies them as a mask over the IVF candidate rows before rescoring— so the filter rides the fast path instead of aborting it. The worker lazily caches the relevant scalar columns per file alongside the embedding matrix. The pushdown is only sound when a surviving file is pure in the filter column—every row in it satisfies (or the file was pruned). We compute the pure set as file_local_cols = partition columns

Query-time vs. materialized reduction. The rewrite above runs the reduction per query: it re-materializes the key set and prunes on customer_id on every call. This still prunes files, but the join key is a high-cardinality identifier, so its file-locality (a contiguous customer_id range per region) is fragile—an unlucky re-binpacking on ingest scatters a region’s rows across files and pruning collapses. When the join is a fixed, recurring shape, a robustly

∪ materialized cluster-spec columns, and push the predicate only when the filter’s columns lie in that set. The distinction that matters here—and that we did not anticipate— is that sorted is not pure. Iceberg SORT/ZORDER ordering makes a column locally contiguous, so its zone-maps prune well, but a boundary file straddles two values; a mask that assumed purity would 5

Placement that survives autoscaling. The cache is per-pod, so which pod searches which file must be stable—otherwise autoscaling the read pool remaps files to cold pods and every scale event cold-starts the cache. We assign files to pods by rendezvous hashing [20]: a file always lands on the pod that maximizes ℎ(file, pod), so adding a pod moves only ∼ 1/𝑁 of files. Round-robin assignment, by contrast, remaps every file when the pod count changes; we observed a query jump from ∼1.8 s into the 52–73 s range (§8) purely because the read pool grew mid-run and the cache went cold. We also block for the read tier to reach full size before the first shard, so the very first query lands on a stable set.

faster option is to materialize the reduction into the physical layout: denormalize the filtered dimension attribute (region) onto the fact table and partition by it. WHERE region=’EU’ then becomes a partition-column predicate—the strongest form of file locality—so Step 1 prunes to exactly that region’s files and, being a partition column, the residual also takes the pushdown fast path (§5.1). This is the classic analytics trade—a denormalized, purpose-partitioned copy in exchange for prune-time robustness—applied to the vector join, and it is the layout our evaluation (§8.8) measures.

6

WHEN FILTERED ANN PAYS OFF: LOCALITY

Composing pruning with ANN is only a win when Step 1 actually removes files. File pruning drops a file only if the table’s metadata proves the predicate cannot match any row in it. For a bitmap index, that means the filter value is absent from the file. Therefore:

Effect. §8 traces the cumulative effect: the same query goes from 1.0× (no cache) through the matrix cache (4.7×) and rendezvous affinity (15.6×) to the full warm set (∼32× versus brute force on the current deployment), at unchanged recall.

Filtered vector search is fast iff the filter column has file-level locality—each value concentrated in few files—so the table’s pruning can eliminate most files before ANN runs.

8

Setup. A production-representative deployment: 2 coordinator pods and an autoscaled pool of up to 12 compute pods (8 vCPU each), Iceberg tables on S3-compatible object storage, all reads crossing the network. We use two datasets. The synthetic dataset (build and warm-set experiments below) is a table of 11,534,160 rows with a 768-dim embedding column and a low-cardinality category column, generated with latent-cluster structure (so IVF recall is meaningful) via the distributed write path (§4); 𝐶=1024 per file, L2; 200 sampled query embeddings drawn from the same latent structure, 𝑘=10. The distributed write path first materialized the table as ∼336 data files, over which the index build ran (§8.1); the per-value re-layout used for the locality experiment (§8, “Filtered queries”) repopulates the table one category at a time and yields ∼444 files. We state the file count with each experiment: build measures the 336-file table, all query and pruning experiments the 444-file value-local table. The real-corpus dataset (join experiments, §8.8) is 5.02M documents embedded with IBM Granite (granite-embedding-97m-multilingual-r2, 384-dim) over five regions, used to confirm the design holds on genuine embeddings rather than a generator. Methodology. For fairness the result cache is disabled on all paths (x-flight-no-cache); otherwise a repeated query is served from cache and measures nothing. Recall ground truth is exact brute force, obtained by a header that skips the IVF fast path so the engine evaluates array_distance over every row; recall@10 = |IVF10 ∩ brute10 |/10 averaged over the query sample. “Warm” means the per-file cache (§7) is populated (we issue a warm-up query and drop it); “cold” is the first query on a freshly scaled read tier. Unless noted, each reported latency is the median (p50) over the 200-query sample, with three timed runs per query (the perquery value is the median of its three runs); for the headline unfiltered table we additionally report p90/p95/p99 across the sample, since tail latency on object storage is the quantity that matters. The join and filtered-rescore paths cost tens of seconds per query (a candidate-file rescore), so those are reported over smaller samples with the count stated in place; recall is a brute-force spotcheck sample, as a full brute-force ground truth over 11.5M vectors

This is the storage-layer statement of the in-memory result of [16] that “partitioning is effective for low-selectivity queries.” If the filter column is spread uniformly across files, every file contains every value, the bitmap proves nothing, and no file is pruned—the query degrades to full-corpus ANN plus a residual filter. We observe exactly this (§8): on a table where each of five categories is uniformly spread across all files, WHERE category=’tech’ with a bitmap index declared prunes zero files. The lever is data layout, and the lakehouse already provides it: partition the table by the filter column (or write per-value), so files become value-local, then declare a bitmap index on it. With a valuepure layout, the same query prunes to the matching partition’s files. For high-cardinality equality filters a bloom filter is the right index; for ordered/range predicates, zone-maps. The point is not a new index—it is that the filtered-ANN practitioner’s job is a familiar physical design decision (partition on your common filter dimensions), not the choice of a specialized filtered-ANN algorithm.

7

EVALUATION

DISAGGREGATED WARM-SET ENGINEERING

On disaggregated hardware, every file read crosses the network to object storage. For per-file IVF the dominant per-query cost is not the centroid math but the random-access rescore reads and the footer index load—and, done naïvely, both are re-paid on every query. We measured, per file per query at 𝑑=768: ∼1.1 s to load the index blob and ∼3.5 s to fetch candidate embeddings, × tens of files per shard. This is why a first, naïve implementation was no faster than brute force despite correct recall. Per-file cache. Each pod caches, per file it is assigned, the parsed IVF index and the file’s embedding matrix (a bounded LRU by bytes). The first query on a file pays the S3 read; subsequent queries rescore by an in-memory gather and reuse the centroids. Objectstore data files are immutable (new writes go to new paths), so caching is trivially coherent. 6

warm p50 latency (s, log)

is minutes per query. We verified IVF and brute force return setidentical top-𝑘 IDs on spot checks to confirm the index is correct, not merely fast. Scope of the claims. The comparisons below are self-relative: IVF versus this system’s own brute force, and materialized versus this system’s own query-time join. They establish feasibility and the design principle (that the table’s file pruning composes with perfile ANN and pays off under file-level locality). They are deliberately not a claim of raw competitiveness against a dedicated vector database or a whole-table index—and §8.7 measures exactly that gap: a dedicated Milvus HNSW answers a subset version of the filtered query in 5 ms and a whole-table IVF-PQ answers the full-corpus unfiltered query in 175 ms, against this system’s 34 s rescore/projection path (or 157 ms when the predicate is partitionaligned and stays on the fast path). Those baselines quantify the tax of the per-file, in-table choice; the paper’s claim is that the tax buys no data copy, a single source of truth, a table every engine can still read, and—because the vector query runs through the lakehouse catalog like any other scan—the table’s existing access control applied to vector search for free, with no second authorization surface to define or keep in sync.

8.1

101 1.6s

100

IVF (nprobe 10)

brute force

Figure 2: Warm top-10 latency, 11.5M×768, 𝑛 probe =10, result cache off, 200-query sample. Bars are p50; black ticks overlay p95. Latency (𝑦) is log10 seconds. IVF p50/p95 = 668/831 ms; brute-force is bimodal (cached ∼1–2 s vs. cold ∼21 s), p50 21.1 s. Table 1: Warm top-10 latency, 11.5M×768, 𝑛 probe =10, cache off, 200-query sample × 3 timed runs/query (per-query median, then percentiles across the sample). Brute-force is bimodal (cached vs. cold matrix); its full distribution is wide, so we give its p50. Speedup is on the p50s.

Distributed build

The full build over ∼336 initial files completes in ∼10 min across 12 pods with all cores saturated (28 files/pod), 0 failed shards, row count preserved, committed as a single metadata-only replace. The build is CPU-bound in 𝑘-means: aggregate CPU held at ∼95 cores throughout and tailed off as shards finished, confirming nearperfect fan-out. Two levers dominate build wall-clock. Parallelism. Before we moved the per-file build off the async executor onto a blocking pool (§4), each 8-core pod ran at ∼1 core (the synchronous 𝑘-means monopolized one runtime thread and files serialized); the build spent 40+ min without finishing. After the fix, per-pod CPU rose to ∼8 cores and aggregate to ∼95, and the build completed in ∼10 min. Cluster count. 𝐶 enters 𝑘-means cost as 𝑂 (𝐶 · 𝑑) per assigned point, so over-clustering a per-file index is pure waste. At 𝐶=4096 on ∼34k-row files the build√pegged all cores for far longer with no recall gain; 𝐶=1024 (the 4 rows/file ≈ 738 floor rounded up to a power of two, §4) was the single largest build-time lever. Building the 11.5M-row table itself used the distributed INSERT. . . SELECT path (§4): two doublings in ∼90 s, versus serial client ingest stalling at 3M rows in 25 min.

8.2

31.0s

8.3

p50

p90

p95

p99

IVF (nprobe 10) Brute force

668 ms 21.1 s

749 ms —

831 ms —

903 ms —

Speedup (p50)

31.6×

recall@10 ≥ 0.90 (IVF), 1.00 (brute)

Recall vs. latency: 𝑛 probe

Figure 3 sweeps 𝑛 probe . Recall climbs from 0.83 at 𝑛 probe =1 to ≈ 1.0 at 𝑛 probe =10, trading latency monotonically—the standard IVF knob, exposed per query via a call header so applications tune recall without a rebuild. The recall figures we report are means of recall@10 over the 200-query sample. A mean can hide a low-recall tail—the failure mode that filtered-ANN work is most concerned with, and the reason Chronis et al. [7] elevate stable recall (the same recall regardless of the predicate) to a first-class goal. Our per-file design has a specific tail risk: when a selective residual filter leaves fewer than 𝑘 candidates after the mask, the over-fetch 𝑠 was too thin, and the worker falls back to exact rescore for that file (§5.1)— which protects recall at a latency cost, so the tail appears in latency rather than in recall. Reporting the recall distribution rather than a bare mean bears this out: over a brute-force spot-check sample at 𝑛 probe =10, recall@10 has mean ∼0.97 but a floor of 0.90 (no query fell below 0.90), and the low-recall instances coincide with the over-fetch-fallback described above—i.e. the tail surfaces as the occasional rescore in the latency distribution, not as a recall miss. A full recall-vs-selectivity curve—recall@10 swept across predicate selectivities—would substantiate stable recall across predicates directly rather than by the mechanism argument above; we leave it to future work because an exact brute-force ground truth on the deployed layout is cost-prohibitive at this scale (a single unindexed top-𝑘 over the 11.5M×768 corpus costs >700 s of single-pod CPU),

Warm search: IVF vs. brute force

Table 1 reports the unfiltered top-10 latency at 𝑛 probe =10 (result cache off, warm), over a 200-query sample with three timed runs per query (we report the per-query median, then percentiles across the sample). IVF is ∼32× faster than brute force at recall@10 ≥ 0.90. Brute-force latency is bimodal—∼1–2 s when a query’s shards find the embedding matrix already resident, ∼21 s otherwise—so its p50 (21.1 s) reflects the common cold-matrix case; IVF is consistently sub-second (p50 668 ms, p99 903 ms). 7

Table 2: Warm-set ablation (11.5M×768, 𝑛 probe =10, cache off). Endpoints (naïve, all-on) are from the current deployment; the intermediate per-fix rows are the decomposition measured on the original (slower) deployment. “vs. brute” normalizes each row to its own run’s brute-force p50 (so the ratio is meaningful within an epoch). Recall is correct in every row—only latency changes.

1.2

0.95

1.0

0.90

0.8

0.85

relative latency

recall@10

1.00

0.6

0.80

5

10

nprobe

15

20

Figure 3: Recall@10 (mean over the 200-query sample) and relative warm latency vs. 𝑛 probe (11.5M×768, 𝐶=1024, L2). Left 𝑦: recall ∈ [0, 1]; right 𝑦: warm latency relative to 𝑛 probe =1. Monotone trade-off; 𝑛 probe =10 reaches ≈1.0 recall.

speedup vs. brute force (×)

10 0

4.7× 1.0× naïve

+matrix +rendezvous +stable cache placement pod set

Figure 4: Warm-set ablation (11.5M×768, 𝑛 probe =10): each bar adds one fix from §7 to the previous (𝑦-axis: speedup vs. brute force, ×). Correct recall throughout; only the cache and stable placement turn correctness into speed.

≈ brute 6.6 s 1.8 s 668 ms

1.0× 4.7× 15.6× 31.6×

Cold start and cache-affinity stability

8.6

Filtered queries and locality

We validate §6 directly by comparing two physical layouts of the same data. In the uniform layout, categories are interleaved across all files; in the value-local layout, the table is populated per category so each file holds one category, with a bitmap index on category declared and built. Table 3 reports WHERE category=’tech’ ORDER BY array_distance(. . . ) LIMIT 10 on each. With locality, the bitmap prunes 355/444 files (355 of the 444 data files) before ANN runs—down to the 89 tech files, a 5× reduction; without it, zero files prune and the query touches everything. Both return identical, correct results (all tech).

so the curve requires a dedicated smaller-corpus harness with precomputed ground truth.

8.4

Naïve (re-read per query) + per-file cache† + rendezvous placement† + stable pod set (all fixes)

The per-file cache makes the first query on newly-warm data pay a one-time load. The subtle failure is not the cold load itself but cacheaffinity loss under autoscaling: with round-robin file→pod assignment, growing the read pool between queries—as the autoscaler does on the first few queries after idle—remaps every file to a different pod, cold-starting caches that were already warm. Against a warm steady-state of ∼1.8 s, we observed the query jump into the 52–73 s range purely from this remap (the spread reflects how many files a given scale event happened to move). Rendezvous placement plus blocking for the read tier to reach full size before the first shard removes it: with both, the first post-warmup query— the one modest cache fill on a now-stable set—is ∼3 s rather than 52–73 s, and every subsequent query is ∼1.6 s. Because object-store data files are immutable, the cache never invalidates; warmth persists across queries and across scale events.

15.6×

5

vs. brute

endpoint rows are the current deployment).

19.5×

15

IVF p50

† per-fix attribution from the original deployment (absolute latency higher; the

8.5

20

Configuration

The warm-set ablation

Table 2 is the paper’s systems story: the same 11.5M query, each row adding one fix from §7. The naïve per-file implementation— correct recall—is no faster than brute force; the cache and stable placement are what turn correctness into speed. We report the endpoints from the current deployment (naïve ≈ brute force; all fixes on: warm p50 668 ms, so a ∼32× net win over brute force’s 21.1 s p50, cf. Table 1) alongside the per-fix decomposition measured on the original deployment (the intermediate rows), which attributes the win across the three fixes; the two epochs differ in absolute latency because the cluster is faster in the later run, but the shape—no-cache is brute-equivalent, the matrix cache and placement carry the win—is unchanged.

Table 3: Filtered query, same data, two layouts. Pruning happens before ANN. Layout Uniform (interleaved) Value-local (per-category)

files after prune

pruned by bitmap

444/444 89/444

0 355

On the constructed locality. Both layouts above are ones we built: the value-local layout concentrates each category by 8

data files

400

WHERE category='tech' (bitmap prune) 444

Table 4: Query cost, 𝑘=10. External systems require a copy of the vectors out of the lakehouse; the whole-table global index is a separate object versioned against the table’s snapshots. This system keeps the vectors in-table and pays a per-query over-fetch instead. The global IVF-PQ and thissystem rows are measured on the full 11.5M×768 corpus; the Milvus row is a measured 300K-subset stand-in (footnotes).

total files files ANN touches

300 200 89

100 0

uniform (interleaved)

value-local (per-category)

Figure 5: Files ANN must touch for WHERE category=’tech’ (11.5M×768), same data, two physical layouts (𝑦-axis: data files scanned, of 444). With value-local files the bitmap prunes 355/444 before ANN runs (89 files remain); uniform layout prunes none. Identical, correct results.

copy

p50 recall@10

Milvus (HNSW, 300K subset) [21] pgvector (HNSW) [14] Global IVF-PQ (whole table) Global HNSW (whole table)

full full sep.† sep.†

5 ms†† high†† n/r ¶ 175 ms‡ ≈0.88§ n/r ¶

This system (per-file IVF)

none

34 s ∥

≥ 0.90

† separate index object, not readable by a plain Parquet reader; rebuilt per commit. ‡

our own decoupled posting-list implementation of a whole-table IVF-PQ (𝑛𝑐 =7141 clusters, PQ 𝑀=96, 𝑘=10, nprobe=8, unfiltered, result cache off): 30 queries, p50 175/p90 262/p95 301 ms over the same 11.5M × 768 corpus laid out across 28,714 files. The posting index range-reads a single index object, so latency is independent of the file count; contrast the per-file path, whose cost scales with surviving files. § recall@10 of the PQ (𝑀=96) codes, measured on matched-encoder deployments where an exact brute-force ground truth is affordable (0.877 on both a 5M and a 50M single-index build with the identical 𝑀=96 codebook); a matched brute-force GT directly on the 28,714-file layout was cost-prohibitive (> 700 s of single-pod CPU per query), and PQ recall is a property of the codebook and 𝑀 , not of the file layout the codes are attached to. ¶ n/r = not run. Global HNSW would give the strongest recall of the whole-table options but at a markedly higher build/memory cost; the IVF-PQ row already establishes the whole-table datapoint the Discussion needs, so we do not separately build HNSW. pgvector was attempted but its standalone image had been retired from the registry (§8.7); Milvus is the external stand-in. ∥ this system, filtered 𝜎=0.2 (category=’tech’): the bitmap index prunes 355/444 files, then the surviving 89 files take the projection/rescore path (§5) rather than the fused direct top-𝑘 path. This row prices a different failure mode from missing locality: even when file pruning succeeds, carrying the query through the rescore/projection path can dominate latency. The fast filtered result on this system is the layout-local, fast-path case (§8.8): a partition-aligned predicate answers in 157 ms. †† Milvus standalone (v2.4, HNSW 𝑀=16, efSearch=64, 𝐿2), category filter applied natively during graph traversal, 20 warm queries, result cache off: p50 5/p90 6/p95 6 ms. This is the price the baseline exists to expose—an in-memory graph index with native attribute filtering answers the subset filtered query orders of magnitude faster than this system’s full-corpus rescore path (and ∼30× faster than the layout-local 157 ms). The costs it hides are exactly the “copy” column: the vectors were copied wholesale out of the lakehouse (138 s for the subset alone) into a separate always-on service, are no longer readable by any Parquet/Iceberg client, and must be re-copied on every write. Measured on a 300K-row subset (the copy is bounded by the loader pod’s 6 GiB, not by Milvus); recall is left qualitative (high: exact-precision HNSW) rather than compared head-to-head, since this is not the same full-corpus measurement as the other rows.

construction, which is exactly the precondition §6 predicts will make pruning happen. This experiment therefore demonstrates the mechanism (when locality is present, the table’s own bitmap prunes and the ANN cost drops proportionally), not that arbitrary real tables enjoy it for free. A non-local counter-example. The distinction is not hypothetical. On the real 5.02M docs table, customer_id carries both a declared bitmap index and a write.cluster.columns clustering directive, yet a single-value predicate WHERE customer_id=𝑐 prunes 0 of 17 data files: ordinary ingest scattered each customer across every file, so no file is provably free of the value and the bitmap proves nothing. Declaring an index does not create locality—the physical layout must. The full observed spectrum, same engine, is thus: valuelocal category prunes 355/444; region-partitioned region prunes 4/5 partitions (§8.8); bitmap-indexed-but-scattered customer_id prunes 0/17. Locality is a property of the layout, not of the index declaration—the practitioner’s lever, and the paper’s precondition, is the former.

8.7

System

Baselines: the cost of the in-table, per-file choice

The speedups above are self-relative and establish the design principle (§8, “Scope of the claims”). The question a reader most wants answered is the tax: how much latency/recall does keeping vectors in the open table cost, relative to the two alternatives the introduction defines—copying them into a dedicated vector database, or building a single whole-table index? The value proposition is not raw latency but no data copy, a single source of truth, and a table every engine can still read; a baseline is what lets the reader price that tradeoff, and it strengthens the paper even if this system loses on raw latency. Table 4 scaffolds the two comparisons. The whole-table index row is measured on the same 11.5M×768 corpus; the Milvus row is a bounded external-system stand-in on a 300K-row subset, included to price the order-of-magnitude latency gap a copied-out, in-memory vector service can achieve.

The global-index row is the more important of the two: the Discussion (§9) concedes a whole-table IVF-PQ or HNSW “would likely give better recall at a fixed candidate budget,” and this row is where that concession is measured rather than asserted. We built exactly that whole-table index on the same 11.5M×768 data—a decoupled IVF-PQ posting list (𝑛𝑐 =7141, 𝑀=96)—and its unfiltered p50 of 175 ms (Table 4) at recall ≈0.88 makes the tax concrete: a single global index is roughly 4× faster unfiltered than the per-file path’s filtered 668 ms headline, and its latency does not grow with the 9

Table 5: Filtered ANN across a join on real Granite embeddings (5.02M×384, five regions, 𝑛 probe =10, warm, result cache off, 𝑁 =8 queries). “pruned” is region partitions dropped before ANN (4/5). Both rows return the identical, in-region top10; materializing the reduction into a region-partitioned layout turns the join into a partition-column prune. Speedup is on the p50s (14.7 s/157 ms).

file count. What the per-file design buys back is exactly what the “copy” and “sep.” columns price: no data copy, no separate object to version and rebuild per commit, and a table any Parquet reader can still scan. The global index also has no native way to compose a lakehouse predicate—the posting list is keyed by cluster, not by the table’s partitions or zone maps—so the moment a query adds WHERE region=’EU’ it must either over-fetch and post-filter or fall back to a scan; that gap is the subject of the follow-on filtered-posting design (§9).

8.8

Query form Query-time join (cust_id) Materialized region-partition

Filtered ANN across a join, on real embeddings

pruned

p50

p95

recall@10

none 14.7 s 18.1 s 4/5 157 ms 197 ms

1.00 1.00

Speedup ∼94×, same result set

We validate the join path (§5.2) end-to-end on a real-corpus deployment rather than the synthetic generator: 5.02M documents embedded with IBM Granite (granite-embedding-97mmultilingual-r2, 384-dim) into a docs fact table, joined to a customers dimension of 1,000 customers spread over five regions (NA, EU, APAC, LATAM, MEA), each region owning a contiguous customer_id range. The application query is the natural one:

9

DISCUSSION: THE DESIGN SPACE

Per-file vs. global index. The per-file footer index is what makes the build non-destructive and time-travel-safe: each file is a selfcontained, independently rewritable unit, and an old snapshot’s files carry their own (old) index. A single global index over the whole table—an IVF-PQ codebook or an HNSW graph—would likely give better recall at a fixed candidate budget, because it clusters the full population rather than ∼26k rows at a time. But a global index is a separate object that must be versioned against the table’s snapshots, rebuilt on every commit, and cannot be ignored by a plain Parquet reader. Our choice trades a modest per-query over-fetch (the 𝑘 · 𝑠 safety factor) for these systems properties. The break-even is workload-dependent: tables that are append-mostly and queried with selective filters favor the per-file design; a static table under pure unfiltered ANN would favor a global index. Our evaluation is squarely in the first regime.

SELECT d.id FROM docs d JOIN customers c ON d.customer_id=c.id WHERE c.region=’EU’ ORDER BY array_distance(d.embedding,q) LIMIT 10

We measure the two forms of the reduction from §5.2 over an 8-query warm sample (cache off, 𝑛 probe =10). Run per-query against the raw two-table join, the reduction still materializes the EU keys and prunes on customer_id, but the dimension rescore and the key-column’s fragile locality leave it at 14.7 s warm (p50; p95 18.1 s)—dominated by the multi-table candidate rescore. Run against the materialized layout—region denormalized onto a copied table docs_r PARTITIONED BY region (five regions, 19 data files)—the identical result set is served in 157 ms (p50; p95 197 ms): WHERE region=’EU’ is now a partition-column predicate, so Step 1 prunes to EU’s partition—roughly one region’s fifth of the files—before ANN runs, and the residual takes the pushdown fast path (§5.1) instead of a rescore. That is 14.7 s/157 ms ≈ 94× on the p50s. (An earlier, colder run measured ∼20 s vs. 241 ms ≈ 83×; the ratio is stable across cluster warmth.) The result set is the same and recall@10 = 1.00 against a brute-force reference, with every returned row in-region (Table 5). The win is entirely file pruning plus staying on the fast path: partition-level locality on the filter column drops the four non-EU partitions, and the pushed-down predicate keeps the survivors on the direct top-𝑘 return.

When is file-level locality achievable? The locality precondition (§6) is not free, but it aligns with how lakehouse tables are already organized. Tenanted or time-series data is routinely partitioned by tenant or day; those same partition columns are the natural filter predicates. When a filter column is not a partition column, the engine’s clustering/sort-on-write can induce locality for numeric/temporal keys, and a per-value INSERT. . . SELECT can induce it for categoricals. The design does not require locality to be correct—only to be fast; a query whose filter has no locality degrades to a full ANN sweep, which is still the brute-force-avoiding fast path over the whole table, just without the extra file pruning. A back-of-envelope cost model. For a table of 𝑁 vectors in 𝜙 files with a filter of selectivity 𝜎 and file-level locality, Step 1 leaves ≈ 𝜎𝜙 files; Step 2 exact-rescores ≈ (𝑛 probe /𝐶) of each survivor’s rows. The candidate distances computed are therefore ≈ 𝜎𝑁 · (𝑛 probe /𝐶), versus 𝑁 for brute force—a 𝐶/(𝜎 𝑛 probe ) reduction in distance computations, plus a 1/𝜎 reduction in bytes read. At 𝜎=0.2, 𝐶=1024, 𝑛 probe =10 this predicts ∼ 500× fewer distances; the measured end-to-end speedup is far smaller (∼ 30×) because the two-phase dispatch, cache reads, and merge—not the arithmetic— dominate warm latency. This gap is the systems contribution: the value of the warm-set engineering (§7) is precisely that it keeps those fixed per-query costs from swamping the algorithmic win.

Same-table filtering and the projection trap. On the same real corpus we also confirm the projection lesson of §5 in the wild. A same-table ranking query that projects the document text blob forces a full-file rescore to fetch that wide column—3.5 s warm (p50; p95 3.7 s, 𝑁 =8). Ranking instead on id+category (the direct IVF path) and then doing a keyed id lookup for only the 𝑘 winners’ text collapses this to 371 ms (p50; p95 396 ms)—a ∼9.5× reduction, from the same fuse-search-and-projection principle that gives the unfiltered IVF its win over brute force. Carrying a wide payload column through the candidate path silently reintroduces the scan the index was meant to avoid. 10

10

LESSONS AND LIMITATIONS

table exhibits it remains to be shown. Third, the non-bitmap pruning tiers (zone-maps for ranges, bloom filters for high-cardinality equality) are part of the design but are not separately exercised by the current evaluation.

Bolting ANN onto a lakehouse engine surfaced failure modes worth recording, as they are intrinsic to the setting rather than to our implementation. A CPU-bound build must not run on the async executor. The per-file 𝑘-means build is compute-bound, but our first implementation ran it inline on the same async runtime that serves I/O. Concurrent file builds then serialized on a single runtime worker, and an 8-core pod pinned one core: the build spent 40+ min without finishing while 7 cores idled (§8). Moving the build onto a dedicated blocking thread pool raised per-pod utilization to ∼8 cores and cut the build to ∼10 min. The general lesson: a synchronous, CPU-heavy operator dropped into an async I/O runtime silently loses all intra-pod parallelism, and the symptom (low CPU, not an error) is easy to misread as a scaling problem. Wide vectors overflow 32-bit list offsets. The engine’s clustering/sort path concatenated row batches with 32-bit Parquet list offsets; an embedding list<float> at 𝑑=768 overflows past ∼2.8M rows. Any batch operation that materializes many wide-list rows must use 64-bit offsets (we widen list→large_list before concat and cast back on output). This is a general hazard for carrying embedding columns through analytic operators. Sorted is not pure. Predicate pushdown into the per-file search (§5.1) is only sound over a column each surviving file is singlevalued in. It is tempting to treat any column the layout skips well on—including SORT/ZORDER columns, whose zone-maps prune sharply—as safe to push. But sort order makes a column locally contiguous, not pure: a file at a value boundary holds two values, so a mask that assumed purity would drop or admit rows. Only identity partitioning or a clustering whose per-file value set is materialized is provably pure. We therefore restrict the pushdown to partition ∪ materialized-cluster columns and exclude sort/z-order; the distinction between “prunes well” and “provably single-valued” is easy to miss and silently corrupts results if conflated.

Reproducibility. The engine that produces the in-table index is a production system we cannot open-source; the contribution we can make independently checkable is the data and the measurement, which is what lets a reader re-derive every latency and recall number here against their own ANN system as well as ours. We release, for the camera-ready: (i) the datasets as open Iceberg tables—the 11.5M×768 docs_bycat corpus (and its whole-table-indexed sibling docs_bycat_gc), and the 5.02M Granite docs/docs_r/customers tables used for the join and sametable experiments—published as Parquet/Iceberg snapshots on a public object store, so the exact bytes every result was measured on are downloadable and readable by any Parquet/Iceberg client, no proprietary reader required; (ii) the query workload and ground truth—the SQL for each experiment, the query-vector sets, the 𝑛 probe and selectivity settings, and precomputed exactnearest-neighbour ground-truth files for the recall measurements (these are the expensive artifact: an exact top-𝑘 over the corpus costs >700 s of CPU per query, so shipping the GT is what makes recall reproducible on modest hardware); and (iii) the benchmark drivers—the client-side Python harness that issues the workload, times it, and computes recall against the shipped GT (Flight SQL / pymilvus clients only, no engine internals), including the externalbaseline driver so the Milvus row is re-runnable. The Granite embeddings derive from the public allenai/c4 documents and the public granite-embedding-97m-multilingual-r2 model, so the corpus is also reconstructable from scratch rather than only redistributed. We do not release the index’s internal byte format or the engine source. The availability URL will be set at camera-ready (\vldbavailabilityurl).

11

CONCLUSION

Filtered vector search does not need a new filtering algorithm when the vectors live in a lakehouse table: it needs the table’s existing file-pruning substrate, composed with a per-file ANN index, on a distributed engine. We showed how to build such an index in place and non-destructively across a compute pool, how to compose predicate pruning with IVF in the planner, and what it takes to make it fast on disaggregated object storage—where the honest answer is a stable, rendezvous-hashed per-file cache. The composition is fast exactly when the filter column has file-level locality, the storage-layer form of the partitioning principle established for inmemory filtered ANN. On 11.5M×768 vectors we build distributed in ∼10 min, search ∼32× faster than brute force at ≥ 0.90 recall, and prune 355/444 files before ANN on a locality-bearing filter; on 5M real Granite embeddings a filter arriving across a join prunes four of five region partitions and runs nearly two orders of magnitude (∼94×) faster than the query-time join at identical top-𝑘—all inside a standard Iceberg table that every other engine can still read, and that governs vector search through the same catalog access control as every other query, with no copied-out data to secure separately.

Limitations. The current system supports one embedding column per table, IVF with L2 only (cosine via client-side normalization), literal query vectors (not bound parameters), and manual fill-gaps reindex. Joins are supported for the common shape where ANN is on one table and an inner join only filters it (§5.2); post-join ranking and outer joins fall back to a full ANN sweep plus a normal join. The per-file index model trades a small per-query candidate over-fetch for build simplicity and time-travel compatibility; a global index (e.g., IVF-PQ or graph) could improve recall/latency at the cost of the non-destructive, per-file properties we rely on. The first query on cold data pays a one-time cache-fill; a background warm-on-build (future work (ii) below) would remove it. Three limitations are evaluative rather than architectural, and we call them out because the current paper does not yet close them. First, the external vector-database baseline is not a full apples-toapples measurement: Milvus is measured on a 300K-row subset and reports latency but not matched recall, while the full-corpus comparison is against our own whole-table IVF-PQ implementation (§8.7). Second, the locality on which the composition depends is, in our experiments, constructed (per-category value-local files; region-partitioned region); whether an organically laid-out real

Future work. Three directions extend the design without disturbing its non-destructive core. (i) Richer per-file indexes: the footer 11

blob is opaque to the table format, so swapping IVF for IVF-PQ (to shrink the resident matrix) or a small per-file graph is a builderand-searcher change, not a format change; the interesting question is how a global codebook shared across files interacts with the per-file rewrite unit. (ii) Automatic warm-on-build: since the build already reads every file’s embedding column, emitting the indexplus-matrix into the read pool’s cache as a side effect would erase the cold-start query entirely. (iii) Cost-based fallback: the planner currently commits to the ANN fast path whenever the query shape and an index match; a selectivity estimate from the same scalar index that drives pruning could instead choose between per-file ANN, a full ANN sweep, and brute force per query. Each stays within the paper’s thesis—keep the vectors in the table, add ANN as an ignorable, per-file artifact, and let the lakehouse’s own machinery do the filtering.

[21] Jianguo Wang, Xiaomeng Yi, Rentong Guo, et al. 2021. Milvus: A purpose-built vector data management system. In SIGMOD. [22] Mengzhao Wang, Lingwei Xu, Xiaoliang Guo, et al. 2022. Native hybrid queries via structured labels and near neighbor search over vectors. arXiv preprint arXiv:2203.13601 (2022). [23] Peng Xiang. 2024. Vector search with Parquet and DataFusion. https://blog.xiangpeng.systems/posts/vector-search-with-parquet-datafusion/.

REFERENCES [1] Apache Software Foundation. 2023. Apache Iceberg: An open table format for huge analytic datasets. https://iceberg.apache.org. [2] Apache Software Foundation. 2023. Apache Parquet. (2023). https://parquet.apache.org. [3] Michael Armbrust, Ali Ghodsi, Reynold Xin, and Matei Zaharia. 2021. Lakehouse: A new generation of open platforms that unify data warehousing and advanced analytics. CIDR (2021). [4] Alexander Behm, Shoumik Palkar, Utkarsh Agarwal, et al. 2022. Photon: A fast query engine for lakehouse systems. In SIGMOD. [5] Artur Borycki. 2026. Puffin-Backed Vector Indexes: Attaching Approximate Nearest Neighbor Indexes to Apache Iceberg Snapshots for ComputeDisaggregated Query Engines. arXiv preprint arXiv:2606.04196 (2026). [6] Qi Chen, Bing Zhao, Haidong Wang, et al. 2021. SPANN: Highly-efficient billionscale approximate nearest neighbor search. In NeurIPS. [7] Yannis Chronis, Helena Caminal, Yannis Papakonstantinou, Fatma Özcan, and Anastasia Ailamaki. 2025. Filtered Vector Search: State-of-the-art and Research Opportunities. Proceedings of the VLDB Endowment (PVLDB) 18, 12 (2025), 5488– 5492. https://doi.org/10.14778/3750601.3750700 [8] ClickHouse. 2024. ClickHouse: Approximate nearest neighbor search indexes. https://clickhouse.com/docs/en/engines/table-engines/mergetreefamily/annindexes. [9] Benoit Dageville, Thierry Cruanes, Marcin Zukowski, et al. 2016. The Snowflake elastic data warehouse. In SIGMOD. [10] DuckDB Labs. 2024. DuckDB VSS: Vector Similarity Search extension. https://duckdb.org/docs/extensions/vss. [11] Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yu Zhang, Neelam Mahapatro, Premkumar Srinivasan, et al. 2023. Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters. Proceedings of the ACM Web Conference (WWW) (2023). [12] Gaurav Gupta, Jonah Yu, Tharun Medini, and Anshumali Shrivastava. 2023. CAPS: A practical partition index for filtered similarity search. In arXiv preprint arXiv:2308.15014. [13] Herve Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product quantization for nearest neighbor search. IEEE TPAMI 33, 1 (2011), 117–128. [14] Andrew Kane. 2024. pgvector: Open-source vector similarity search for Postgres. https://github.com/pgvector/pgvector. [15] LanceDB. 2024. Lance: modern columnar data format for ML and LLMs. https://lancedb.github.io/lance/. [16] Mocheng Li, Yue Zhang, Chenhao Ma, Xiao Yan, Baotong Lu, and James Cheng. 2025. Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study. arXiv preprint arXiv:2508.16263 (2025). [17] Yu A. Malkov and Dmitry A. Yashunin. 2020. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE TPAMI 42, 4 (2020), 824–836. [18] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and predicate-agnostic search over vector embeddings and structured data. In SIGMOD. [19] Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. In NeurIPS. [20] David G. Thaler and Chinya V. Ravishankar. 1998. Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking 6, 1, 1–14. 12

Related documents

• Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification#1084948
• Fast Label-Filtering Approximate Nearest Neighbor Search via Progressive Label Set Stratification#919515
• Rank Minimization with Structured Data Patterns#319028
• Per-Query Gating of LLM Rerankers for Multi-Hop Retrieval#1037563
• Compressed Subsequence Checking is PSPACE-complete#1083921