Smart Checkpointing for the Qbeast OTree Index

Abstract

Qbeast is an open-source extension to Apache Spark and Delta Lake that maintains a multidimensional OTree index over columnar tables, enabling approximate query processing through file pruning. Each time a table is queried, the system constructs an \emph{IndexStatus}, a compact in-memory map from cube metadata. It does so through two sequential steps: replaying the Delta Lake transaction log to enumerate the active file set ($O(D)$ in log depth $D$), then running a distributed \texttt{groupBy} aggregation over all active block metadata ($O(N)$ in active file count $N$). The log replay cost is paid once per relation, the aggregation is rerun on every query against the same relation. Delta Lake's periodic checkpoint compaction caps the log-replay cost at a bounded overhead; the per-query $0(N)$ aggregation is the gap that smart checkpointing fills.

This thesis introduces \emph{smart checkpointing}: a persistent cache for the IndexStatus, saved as a $K$-row Parquet file (where $K$ is the number of OTree cubes, $K \ll N$) and written automatically after each batch of writes. Further queries load the snapshot and replay the $G$ commits that have accumulated since the snapshot. This reduces the per-query reconstruction cost from $O(N)$ to $O(K + \alpha G)$. An incremental merging algorithm handles the common pure-append deltas and is equivalent to the full index rebuild. A closed-form cost model is defined, which gives an optimal snapshot interval $G^* = \sqrt{F_\text{write} \cdot C_\text{dump} / (F_\text{query} \cdot \alpha)}$, providing a workload-based tuning rule.

Experiment~1 establishes the baseline $O(N)$ coefficient $E_\text{shuffle} = 0.353$\,ms/file ($R^2 = 0.950$) over a wide range of active file counts. Experiment~2 validates the smart path with $\alpha \approx 21$\,ms/commit ($R^2 > 0.99$), confirms that $\alpha$ is independent of table size across a range of $N$, and derives $G^* \approx 10$\,commits. Experiment~3 validates the amortized cost model under mixed read/write workloads. For read-heavy workloads, total operational cost is reduced by 45\% at $G=500$. Experiment 4 emulates a deployment on a distributed cluster by adding a per-file latency. With a representative latency of $E_\text{net} = 20$ the emulated speedup is up to $19\times$ , amplifying the advantage of smart checkpointing. The final experiment replicates two experiments on real-world datasets, to confirm values from synthetic experiments.

The central finding of the thesis is the transformation of the index reconstruction cost from a full data history rebuild to a snapshot and delta load. The practical benefit starts with approximately 30 prior commits in cold-start scenarios, and grows with a big table in a distributed deployment.