A Backend-Agnostic Compiler for Approximate Query Processing with Probabilistic Tensor Algebra

Despite decades of research, the practical adoption of Approximate Query Processing (AQP) remains limited. Sampling-based systems such as VerdictDB often yield slow or inaccurate results for complex analytical queries, as their effectiveness depends heavily on sample quality. Model-based systems such as DeepDB perform well on simple queries but incur high runtime latency for multiway joins and group-by operations, as each group is evaluated as an independent query with instantiated attribute values, preventing global optimization across groups. Both approaches are tied to fixed hardware backends, limiting flexibility across CPU and GPU platforms. This paper presents BayesAQP, a backend-agnostic AQP framework that compiles Bayesian Network (BN) inference into tensor algebra (TA) programs. During training, BayesAQP models per-table statistics using BNs and integrates join histograms for efficient multi-table queries. At runtime, SQL queries are compiled into TA programs in BTL++, a tensor-centric probabilistic programming language, and optimized into tensor contractions for execution on tensor processing frameworks across CPUs and GPUs. Experimental results show that BayesAQP achieves an average 37× speed-up over existing AQP systems on three real-world datasets while maintaining comparable accuracy and significantly improving performance for complex multiway join and group-by queries.