Fusion: An Analytics Object Store Optimized for Query Pushdown

Cloud data warehouses store huge data files split across many machines for durability, and to answer a query that needs only a tiny slice they try to run it down at the storage layer — but the durability scheme chops each file into fixed pieces blind to its structure, so the slice a query wants is scattered across several machines and must be gathered back together first, wasting the network; this work from Princeton and Columbia builds Fusion, a storage system that lays out the durability pieces to match the file's own structure so each queryable chunk stays whole on one machine, cutting tail query latency by up to 81 percent while adding barely 1 percent storage overhead.

The argument in one glance

Problem

Answering a selective query over disaggregated storage is slow

Cloud analytics keeps raw data in a shared object store, separate from the machines that compute on it. Most stored objects are large, but most queries need only a tiny slice, so fetching a whole object to use a sliver of it wastes network bandwidth and time.
What people did

Push the query down to the storage layer

To avoid moving so much data, systems use computation pushdown: run the query's filters and aggregates near the storage, and send back only the small result. Cloud services like S3 Select do exactly this.
Why it fell short

Erasure coding scatters the piece the query needs

For durability, storage uses erasure coding, which splits each object into fixed-sized blocks spread across many machines, blind to the object's internal structure. But analytics files are structured into small units that can each answer part of a query on their own. Because coding ignores that structure, each such unit ends up split across several machines, so the storage layer must reassemble it before running anything — burning the very bandwidth pushdown was meant to save.
This paper's idea

Lay out the durability pieces to match the file structure

Fusion co-designs erasure coding with the analytics file format. Its file-format-aware coding uses variable block and stripe sizes so each queryable unit stays whole on one machine, needing no reassembly. A bin-packing algorithm keeps the storage overhead near optimal, and a cost model decides per unit whether pushing down actually helps. Fusion cuts tail query latency by up to 81 percent with only 1.2 percent storage overhead.

Why this problem is worth solving

The setup that makes cloud analytics scalable also makes it slow to query.

Modern clouds separate storage from compute: raw data lives in a shared object store like Amazon S3, and when a job runs, the data is fetched over the network into a separate compute cluster. This disaggregation is great for using resources efficiently and scaling each side independently, but it hurts interactive analytical queries. Two facts collide. First, stored objects are large — in one production trace over sixty percent of objects exceed a gigabyte. Second, analytical queries are highly selective — one report finds about half of queries return less than one percent of their data. So the common case is fetching a gigabyte-scale object across the network only to use a sliver of it, which wastes bandwidth and drags out the query. The standard remedy is computation pushdown: instead of moving all the data to the query, move the query to the data. The storage layer runs the selective parts — filters, projections, aggregates — near where the bytes live, and returns only the small result. Cloud providers offer this as features like S3 Select and Azure Storage query acceleration. Pushdown can dramatically cut the data crossing the network, which is why it has been widely adopted. The catch is that it does not compose well with how cloud storage actually stores data.

The two layers that must cooperate were designed in ignorance of each other.

Cloud object stores keep data durable with erasure coding, which is far cheaper than keeping full replicas. Erasure coding takes an object, splits it into a set of fixed-sized data blocks, computes extra parity blocks, and spreads all of them across different machines, so the object survives even if some machines fail. Crucially, erasure coding treats the object as a featureless blob of bytes; it knows nothing about what is inside. Meanwhile, analytics file formats like Apache Parquet are highly structured. Parquet groups rows into row groups, and within each row group stores each column separately as a column chunk. A column chunk holds all the values of one attribute and can, by itself, answer part of a query — a filter on that column, say. This is the smallest computable unit: the smallest piece of the file that can run a query fragment on its own. The problem is that these units have variable sizes, depending on the data type and how well it compresses, while erasure coding cuts the object into fixed-sized blocks blind to unit boundaries. So a single column chunk routinely ends up split across several machines — in existing systems, about five on average. Before the storage layer can push down a filter on that column, it must first gather the chunk’s pieces back onto one machine. That reassembly burns network bandwidth and adds latency, undermining the whole point of pushdown. The root cause is that erasure coding and pushdown live in separate, isolated layers of the storage stack.

What people did before, and where it broke

Push down without changing storage (S3 Select and similar). Run query filters near the storage over normally erasure-coded objects. Where it broke. The queried unit is split across machines, so the store must reassemble it first, wasting network bandwidth and adding latency — exactly what pushdown was supposed to avoid.
Pad objects to align units with blocks. Insert padding so each computable unit lines up with a fixed-sized erasure block and is not split. Where it broke. Padding wastes space, and enough of it to align every variable-sized unit incurs a large storage overhead, negating the cost advantage that made erasure coding attractive in the first place.
Use replication instead of erasure coding. Keep full copies so any machine has whole units. Where it broke. Replication is much more expensive in storage than erasure coding, so clouds avoid it for the large analytics objects where the cost matters most.
The gap. No object store kept each computable unit intact on one machine — so queries push down without reassembly — while keeping the storage overhead near erasure coding’s optimal. Achieving both by co-designing the coding layout with the file format, and then choosing pushdowns with a cost model, is what Fusion does.

How Fusion works

From a scattered column chunk to a whole, locally-queried unit

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Co-design the two layers that used to ignore each other. The whole problem is that erasure coding and computation pushdown sit in separate layers of the storage stack and neither knows what the other needs — coding sees a blob, pushdown wants structure. Fusion’s core move is to make the durability layer aware of the file format, laying out the erasure blocks to respect the object’s own boundaries so a query fragment can run without fighting the storage layout. Breaking a silo between two layers that were built in isolation, and letting each account for the other so they cooperate, is the same move the cooperative-scheduling work covered elsewhere on this site makes, sharing the hypervisor’s hidden layout with the guest so the two scheduling layers stop working blindly against each other.

Keep each computable unit whole so no reassembly is needed. Once a column chunk is split across five machines, every query on it must first pay to gather the pieces back together, which is pure overhead. Fusion sizes its erasure blocks and stripes to each chunk’s boundaries so the chunk stays intact on one machine, and the reassembly step simply disappears — the query reads the whole unit where it lands. Arranging the data so that the thing you need is already in one place, eliminating an expensive multi-step gather, is the same shortcut the direct page-table indexing work covered elsewhere on this site takes, laying out the mapping so the answer can be read directly instead of walking a chain to reconstruct it.

Pack variable pieces tightly so durability stays cheap. Aligning to variable-sized units threatens to blow up storage, because in an erasure code a stripe’s parity block must be as big as its largest data block, so mixing a tiny chunk with a huge one wastes parity space. Fusion treats this as a bin-packing problem, grouping similar-sized chunks into the same stripe and tuning stripe sizes so the parity is almost fully used, holding the overhead to about one percent above optimal. Casting a layout task as bin-packing to squeeze out wasted space is the same formulation the accelerator-buffer-placement work covered elsewhere on this site uses, searching packings of variable-sized items to fit them with minimal waste.

Following a filter query onto one machine

Filtering a salary column, whole on one node

Tracing one query shows why keeping the unit intact wins.

Step 1 of 5

A selective filter on one column

A query asks for employees whose salary is above a threshold. In a Parquet file, the salary values live in a single column chunk — the smallest unit that can run this filter on its own.

The query touches only the salary column, not the whole table.

Why it works

Selective queries waste huge bandwidth. Because most stored objects are large while most queries return a tiny fraction → shipping a whole object to use one percent of it wastes bandwidth and time → so pushing the query down to the storage layer is the natural fix.
Blind erasure coding splits the computable unit. Because erasure coding cuts the object into fixed blocks with no knowledge of its structure → each column chunk ends up split across several machines → so the store must reassemble it before any query runs, defeating pushdown.
Format-aware coding keeps each unit whole. Because Fusion sizes its erasure blocks and stripes to the chunk boundaries → every column chunk stays intact on one machine → so the filter runs locally with no cross-machine reassembly.
Bin-packing keeps the parity cheap. Because a stripe’s parity block is as large as its biggest data block → packing similar-sized chunks together into a stripe → so almost no parity space is wasted, holding the storage overhead to about one percent above optimal.
A cost model avoids a losing pushdown. Because a heavily compressed chunk decoded at storage can send more data than the compressed chunk itself → the model pushes down only when selectivity and compressibility make it pay → so pushdown never backfires into extra network traffic.

What it costs (trade-offs and scope)

It requires control of the storage layout. Fusion co-designs the erasure coding with the file format, so it is a new object store, not a change one can drop onto an existing S3-style service without controlling how objects are encoded and placed.
It is tuned to structured analytics formats. The gains come from aligning to the computable units of columnar formats like Parquet. Unstructured objects, or formats without such units, have nothing to align to and would not benefit.
Encoding does extra work up front. The stripe-construction and bin-packing algorithm runs when an object is written, computing a layout rather than cutting fixed blocks, so ingesting an object costs more than in a structure-blind store, a cost paid once and amortized over many queries.
A small storage overhead remains. Keeping units intact with variable-sized blocks is not free: Fusion adds about 1.2 percent over the theoretical optimal, far less than padding, but not zero.
The cost model needs the right inputs. Choosing pushdown well depends on estimating query selectivity and chunk compressibility; when those estimates are off, the decision can be suboptimal, though the fallback of shipping the compressed chunk bounds the damage.
Gains depend on the workload. The largest wins are for ad-hoc, highly-selective queries on large objects. Queries that read most of an object, or that are not selective, have less reassembly to avoid and see smaller improvements.

The evaluation

Three ways to store analytics objects for pushdown

Property	Standard erasure store	Padding to align
Keeps each column chunk intact		Yes
Reassembly before a query		No
Storage overhead
Chooses pushdown wisely	Not applicable	No
TPC-H tail latency	Baseline	Better but costly

Three ways to store analytics objects so selective queries can be pushed down, evaluated on the TPC-H benchmark and real-world SQL queries over Parquet data, using systematic Reed-Solomon erasure coding. A standard erasure-coded store like the ones behind MinIO or Ceph splits each column chunk across about five machines, so every pushed-down query must first reassemble it over the network. Padding to align units avoids the split but wastes so much space it negates erasure coding's cost advantage. Fusion co-designs the coding with the file format: file-format-aware coding uses variable block and stripe sizes to keep each column chunk whole on one machine, a bin-packing algorithm keeps parity almost fully used, and a cost model pushes down only where it pays. Fusion improves median and tail query latency by 64 and 81 percent on TPC-H, and up to 40 and 48 percent on real-world SQL, while adding only about 1.2 percent storage overhead compared to the optimal.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Fusion is a tidy systems result: it identifies a concrete mismatch between two layers of the cloud storage stack — durability via erasure coding and query pushdown — and fixes it by making them co-designed instead of oblivious. The central insight is that a query’s smallest computable unit, a column chunk in Parquet, should never be split across machines, because then it must be reassembled before any pushed-down query can touch it. Fusion keeps each unit whole with variable-sized erasure blocks, controls the resulting storage blow-up with a bin-packing algorithm that keeps parity efficient, and adds a cost model so it only pushes down when selectivity and compression make it worthwhile. The measured wins are strong — up to an eighty-one percent cut in tail latency on TPC-H — and the storage cost is small, about 1.2 percent over optimal, far cheaper than padding. Read it with its scope. Fusion is a new object store that must control encoding and placement, not a patch to an existing service, and its gains are specific to structured columnar formats and to ad-hoc, highly-selective queries on large objects. Encoding does extra layout work at write time, a modest overhead remains, and the pushdown decision is only as good as its selectivity and compressibility estimates, though the fallback of shipping the compressed unit bounds the risk. The durable lesson is that when a durability mechanism and an access pattern are designed in separate silos, aligning the storage layout to the unit the workload actually reads can remove a whole class of wasted work.

Background

Why aligning storage to the access unit keeps paying off

It helps to see Fusion as part of a broad theme: a system runs faster when its storage layout matches the granularity at which work actually reads the data. Here the unit is a column chunk, and keeping it whole on one machine removes a costly reassembly step. The same instinct shows up in when to even attempt an optimization: the compatibility-measurement work covered elsewhere on this site teaches that a heavyweight step should be applied only where it genuinely pays, measured rather than assumed — which is exactly what Fusion’s cost model does when it declines to push down a query whose result, once decompressed at storage, would be larger than the compressed chunk itself. The common lesson is that the biggest wins often come not from a faster algorithm but from arranging data and work so that the expensive step is unnecessary or skipped. As systems disaggregate — pulling storage, compute, and memory apart across a network — the cost of moving data between them dominates, and the layouts and decisions that keep the right piece in the right place, and skip work that does not pay, matter more than ever. Fusion is a clean instance of designing the storage layer around what the workload will actually ask of it.

If you remember only three things

1. Cloud analytics separates storage from compute, and answering a selective query means fetching data over the network; since most objects are large (over half exceed a gigabyte) but most queries return under one percent of the data, systems use computation pushdown to run filters near the storage. But pushdown clashes with durability. Erasure coding splits each object into fixed-sized blocks across many machines, blind to structure, while analytics formats like Parquet are made of variable-sized column chunks — the smallest unit that can answer a query fragment. So each chunk gets split across about five machines and must be reassembled before any pushed-down query can run, wasting the bandwidth pushdown was meant to save.
2. Fusion is an analytics object store that co-designs erasure coding with the file format. Its file-format-aware coding uses variable block and stripe sizes aligned to chunk boundaries so every column chunk stays intact on one machine, and queries push down and run locally with no reassembly. Because keeping variable-sized units would waste parity space (a stripe's parity block is as large as its biggest data block), a bin-packing algorithm groups similar-sized chunks into each stripe and tunes stripe sizes, holding storage overhead near optimal. A fine-grained cost model then pushes down only where the query's selectivity and the chunk's compressibility make it pay, otherwise shipping the compressed chunk to compute.
3. On the TPC-H benchmark, Fusion improves median and tail query latency by 64 and 81 percent, and on real-world SQL queries by up to 40 and 48 percent, while adding only about 1.2 percent storage overhead compared to the optimal — far less than the padding approach it replaces. Its limits: it is a new object store that must control encoding and placement rather than a patch to an existing service; it helps structured columnar formats and highly-selective queries on large objects, not unstructured data or full scans; encoding does extra layout work at write time; and the pushdown decision depends on selectivity and compressibility estimates, bounded by the fallback of shipping the compressed unit.

Check yourself

Check your understanding

1. Why does computation pushdown clash with how cloud storage keeps data durable?
2. What is Fusion's file-format-aware coding, and what does it achieve?
3. Keeping variable-sized chunks intact threatens to waste storage. How does Fusion keep the overhead near optimal?
4. Fusion sometimes decides NOT to push a query down to storage. When, and why?

Sources

The paper is “Fusion: An Analytics Object Store Optimized for Query Pushdown” by Jianan Lu, Ashwini Raina, Asaf Cidon, and Michael J. Freedman, published at ASPLOS 2025, DOI 10.1145/3669940.3707234. The authors are at Princeton University and Columbia University.

This explainer is written from the full text of the paper, obtained from the authors’ university copy (hosted on Michael Freedman’s Princeton page and Asaf Cidon’s site), which matches the ASPLOS 2025 proceedings and is distributed under a Creative Commons Attribution license. Everything above comes from the paper’s own sections: the introduction and background on disaggregated cloud storage and computation pushdown (with the statistics that over sixty percent of objects exceed a gigabyte and about half of queries return under one percent of their data, and the pushdown services S3 Select, Azure Storage query acceleration, and AWS AQUA); the explanation of erasure coding (fixed-sized data and parity blocks under systematic Reed-Solomon, distributed across nodes) and of columnar analytics formats (Parquet’s row groups and column chunks, the smallest computable unit, and their variable sizes) and how their mismatch splits a column chunk across about five nodes and forces reassembly in stores like MinIO and Ceph; the design of file-format-aware coding using variable block and stripe sizes to keep each computable unit intact, the bin-packing stripe-construction algorithm based on the observation that a stripe’s parity block size is set by its largest data block; the fine-grained, cost-based pushdown mechanism trading off query selectivity against chunk compressibility (with compression ratios up to sixty-three on TPC-H lineitem chunks); and the evaluation on TPC-H and real-world SQL queries, reporting median and tail latency improvements of 64 and 81 percent on TPC-H and up to 40 and 48 percent on real-world queries, with about 1.2 percent storage overhead compared to the optimal.