[Proposal] feat(table): compute and write table statistics (NDV) as Puffin StatisticsFile

[tanmayrauth]

Feature Request / Improvement

Proposal: Table statistics computation (NDV via Theta sketches)

Motivation

iceberg-go can read and track StatisticsFile metadata, but it cannot compute or write it. Tables created or maintained by iceberg-go therefore carry no NDV (number-of-distinct-values) statistics, so query engines that use them for cost-based planning (join ordering, cardinality estimation) get nothing from Go-managed tables. This proposes the missing producer, closing a parity gap with the Java implementation.

Current state (what already exists)

Modeling and lifecycle are in place — only the producer is missing:

• StatisticsFile / BlobMetadata types and the apache-datasketches-theta-v1 blob-type constant — table/statistics.go, puffin/puffin.go
• Metadata registration — SetStatisticsUpdate / RemoveStatisticsUpdate (table/updates.go), builder support in table/metadata.go
• Lifecycle — statistics pruned on RemoveSnapshots, deleted on ExpireSnapshots, included in orphan-file cleanup

What is missing: nothing computes a Theta sketch, and the only Puffin write path that emits a blob today is the deletion-vector writer (table/dv/dv_writer.go). There is no "analyze this snapshot → produce a StatisticsFile" entry point.

Goals

• Compute per-column NDV for a snapshot as Theta sketches.
• Serialize sketches in a form byte-compatible with Apache DataSketches, so blobs written by iceberg-go are readable by Java/Spark and vice versa.
• Write a valid Puffin StatisticsFile (correct snapshot-id / sequence-number footer) and register it via the existing SetStatistics update.
• Expose a CLI entry point to compute statistics for a table/snapshot.

Design sketch

1. Theta sketch core — pure-Go sketch (Update / Union / Estimate), no Iceberg dependencies.
2. DataSketches-compatible serialization — compact serialized form with Java-produced fixtures as the parity oracle (the correctness-critical piece).
3. NDV compute pass — scan a snapshot's data files, feed values into per-field-ID sketches, emit theta blob bytes keyed by field ID.
4. Puffin StatisticsFile writer + registration — assemble blobs into a Puffin file and commit through SetStatistics.
5. CLI + docs — a compute-stats-style command and reference docs.

Proposed PR breakdown (6 PRs )

1. feat(table): add Theta sketch core (update/union/estimate) — pure algorithm + error-bound tests.
2. feat(table): DataSketches-compatible Theta sketch serialization — compact encode/decode + Java-fixture byte cross-check.
3. feat(table): compute per-column NDV over a snapshot — scan → per-field sketches → blob bytes.
4. feat(table): write StatisticsFile and register via SetStatistics — Puffin write + commit (end-to-end).
5. feat(cli): add compute-stats command — CLI wired to (4), text/JSON output.
6. docs(website): document table statistics + read-side surface — docs and a compute→reload→verify integration test.

Open questions

Theta sketch serialization: The blob must be byte-compatible with Apache DataSketches so Java/Spark can read it. I don't see a maintained Go port of the compact Theta format, so my lean is to implement the compact serialization in-tree (bounded, and spec'd by DataSketches) and validate byte-for-byte against Java-produced fixtures — the same approach the DV code uses against Java. Flagging in case there's a preferred dependency I should use instead.

[tanmayrauth]

I'll work on this issue

[derekperkins]

Very interested in this!

[laskoviymishka]

Thanks for driving this!

Direction looks right to me, and the PR breakdown is a sane dependency order (could be executed as a stack PR imo). One thing I'd settle before code: the test strategy around Java compatibility.

I'd bake the Java-authored bytes into the repo and keep the tests Java-less, rather than standing up a JVM on the test path. That's already the pattern the DV code uses, and I think it's worth cloning that approach exactly: the Puffin fixtures live under table/dv/testdata, and the x-client tests read those bytes back through the reader with no Java at test time.

I read the "same as DV approach" line to mean this already, but worth being explicit so nobody wires a Gradle build into go-CI :D.

Separately, cc @nssalian: this is exactly the x-client byte parity that apache/iceberg-verification is for (see: VOTE). I think the Theta/NDV parity vectors are a strong early candidate to live in the verification repo.

[zeroshade]

Theta sketch serialization: The blob must be byte-compatible with Apache DataSketches so Java/Spark can read it. I don't see a maintained Go port of the compact Theta format, so my lean is to implement the compact serialization in-tree (bounded, and spec'd by DataSketches) and validate byte-for-byte against Java-produced fixtures — the same approach the DV code uses against Java. Flagging in case there's a preferred dependency I should use instead.

What about https://pkg.go.dev/github.com/apache/datasketches-go@v0.2.0/theta#CompactSketch?

The plan looks good and I agree with @laskoviymishka that the PR breakown looks good.

I'd bake the Java-authored bytes into the repo and keep the tests Java-less, rather than standing up a JVM on the test path. That's already the pattern the DV code uses, and I think it's worth cloning that approach exactly: the Puffin fixtures live under table/dv/testdata, and the x-client tests read those bytes back through the reader with no Java at test time.

I think we should do both. We have the integration tag for integration tests where we stand up a spark image and run queries hitting iceberg-java. We should have Java-authored bytes as testdata and keep the unit-tests Java-less, but we should also add to the integration tests.

Separately, cc @nssalian: this is exactly the x-client byte parity that apache/iceberg-verification is for (see: VOTE). I think the Theta/NDV parity vectors are a strong early candidate to live in the verification repo.

Precisely! I agree completely here. My preference would actually be to add the Java-authored bytes and integration test strategy into apache/iceberg-verification and then just add it as a submodule here to use (similar to how github.com/apache/arrow-go uses github.com/apache/arrow-testing and github.com/apache/parquet-testing submodules with test files)

[tanmayrauth]

Thanks @zeroshade @laskoviymishka, this is great feedback.

Good call on datasketches-go, I'd missed it, and it saves me hand-porting the serialization, which was the scary part. Had a look and it has everything: the update sketch for the compute pass, Union for merging across files, and CompactSketch/Encoder/Decode for the bytes. Reassuringly it defaults to seed 9001, same as Java's DEFAULT_UPDATE_SEED, so cross-reads should Just Work. That folds the first two PRs into one ("adopt the lib + prove parity")

The thing I want to nail down in that first PR is exactly which serialization the theta-v1 blob uses. I'm assuming the plain uncompressed v3 form (Java's CompactSketch.toByteArray()), but I'll confirm it by round-tripping against a blob Java actually wrote rather than guessing.

On testing: yep, cloning the DV setup: Java-authored bytes checked in as testdata, unit tests with no JVM in CI. And agreed we should do both, so I'll add an integration-tagged test against the Spark image too, so we catch anything the static fixtures miss.

On where the vectors live: totally agree they belong in iceberg-verification as a submodule down the line (the arrow-testing / parquet-testing setup is a nice model). Since that repo isn't up yet I'll start them under table/testdata so this isn't blocked, and move them over once it exists. One thing I'll make sure of: I'll generate those vectors straight from iceberg-java's own write path, so they're the same canonical bytes the verification repo would end up hosting, not a separate set that could drift. Happy to seed the Theta/NDV vectors there and line up the recipe (dataset, lgK, seed, serial version) whenever it's ready, @nssalian, tell me if I can help get it going.

Going to start on PR 1. Thanks again for the quick turnaround!

[nssalian]

Thanks for starting this @tanmayrauth.

Precisely! I agree completely here. My preference would actually be to add the Java-authored bytes and integration test strategy into apache/iceberg-verification and then just add it as a submodule here to use (similar to how github.com/apache/arrow-go uses github.com/apache/arrow-testing and github.com/apache/parquet-testing submodules with test files)

Agreed. Long term this would be great to have in the iceberg-verification. That repo is just getting kicked off and we are putting the initial artifacts in as we speak. To unblock your work here, Tanmay, you could follow the integration + test data setup like we have for geo and variant in this repo. Feel free to refer to this: #1238. If you are able to get a roundtrip verification here with integration tests, that would be a great place to start and then port over as needed into the verification repo.

On testing: yep, cloning the DV setup: Java-authored bytes checked in as testdata, unit tests with no JVM in CI

Let's be careful to not add a lot of files but a qualitative sample would suffice. I added only a handful of shredded variant cases from a bunch in parquet testing so we cover the cases while being compact.