Source-linked AI summary
VerdictDB: Universalizing Approximate Query Processing
Yongjoo Park, Barzan Mozafari, Joseph Sorenson, Junhao Wang
TL;DR
AQP has seen limited industrial adoption because existing systems are platform-specific and difficult to integrate with unchanged databases. VerdictDB addresses this gap with middleware that rewrites SQL and computes approximate answers and error estimates, achieving substantial speedups with low relative error across several engines.
Problem
Existing AQP systems are tied to specific platforms, while database vendors are reluctant to modify established systems, limiting industrial adoption.
Method
VerdictDB uses database-agnostic middleware, SQL rewriting, stratified samples, and variational subsampling to perform AQP without modifying existing databases.
Results
18.45× average speedup and up to 171× speedup were achieved across Impala, Spark SQL, and Amazon Redshift with less than 2.6% relative error.
Takeaways & Limitations
Universal AQP is viable: VerdictDB operates atop existing SQL-based engines and can be comparable to or outperform fully integrated AQP engines.
Takeaways & Limitations
VerdictDB currently requires additional drivers for databases such as Presto, Teradata, Oracle, and HP Vertica, which remain future work.
Abstract
from arXiv · showhide
Despite 25 years of research in academia, approximate query processing (AQP) has had little industrial adoption. One of the major causes of this slow adoption is the reluctance of traditional vendors to make radical changes to their legacy codebases, and the preoccupation of newer vendors (e.g., SQL-on-Hadoop products) with implementing standard features. Additionally, the few AQP engines that are available are each tied to a specific platform and require users to completely abandon their existing databases---an unrealistic expectation given the infancy of the AQP technology. Therefore, we argue that a universal solution is needed: a database-agnostic approximation engine that will widen the reach of this emerging technology across various platforms. Our proposal, called VerdictDB, uses a middleware architecture that requires no changes to the backend database, and thus, can work with all off-the-shelf engines. Operating at the driver-level, VerdictDB intercepts analytical queries issued to the database and rewrites them into another query that, if executed by any standard relational engine, will yield sufficient information for computing an approximate answer. VerdictDB uses the returned result set to compute an approximate answer and error estimates, which are then passed on to the user or application. However, lack of access to the query execution layer introduces significant challenges in terms of generality, correctness, and efficiency. This paper shows how VerdictDB overcomes these challenges and delivers up to 171$\times$ speedup (18.45$\times$ on average) for a variety of existing engines, such as Impala, Spark SQL, and Amazon Redshift, while incurring less than 2.6% relative error. VerdictDB is open-sourced under Apache License.
1 INTRODUCTION
VerdictDB pursues Universal AQP through a database-agnostic middleware that rewrites SQL without modifying backend engines. Its sampling and variational-subsampling techniques target generality, statistical correctness, and efficiency.
- Motivation: A Universal AQP strategy should work across existing platforms without modifying their databases.VerdictDB performs AQP entirely at the driver level.
- Challenges: VerdictDB must address statistical correctness, middleware efficiency, and server efficiency without database-internal access.These constraints prevent changing query evaluation, enforcing foreign-key constraints, or embedding error estimation into relational operators.
- Approach: Variational subsampling replaces repeated aggregation over resamples with one carefully rewritten SQL query that separates resamples using tuple-level resample identifiers.The technique has provably equivalent asymptotic properties to traditional subsampling and extends to nested queries.
- Approach: VerdictDB constructs stratified samples using a probabilistic SQL-implementable strategy based on Bernoulli-process properties.This avoids dynamically adjusting sampling probabilities during scans with procedural logic.
- Approach: VerdictDB can combine multiple prepared samples to minimize error under a specified I/O budget.This differs from systems that use one sample per query or generate samples on demand.
- Results: 57× average speedup and up to 841× speedup were reported across Impala, Redshift, and Spark SQL, with less than 2.6% error.The experiments used benchmark and real-world sales datasets.
2 SYSTEM OVERVIEW
VerdictDB sits between users and off-the-shelf databases, selecting samples and rewriting supported analytical queries into SQL that returns approximate answers and error estimates. Its current support covers common aggregates, joins, comparison subqueries, and selected predicates, while some subqueries remain unsupported.
- Architecture: VerdictDB acts as middleware between users and an underlying off-the-shelf database, returning query results directly to users.Users can issue SQL through interactive tools or applications without directly interacting with the underlying database.
- Architecture: The Query Parser, AQP Rewriter, Syntax Changer, and Answer Rewriter form the core query-processing pipeline.The Syntax Changer isolates database-specific SQL dialects and limitations, simplifying support for new databases.
- Supported Queries: VerdictDB supports common aggregate functions, including count, sum, avg, quantile, var, and stddev, plus qualifying user-defined aggregates.Supported queries are sped up; unsupported queries are passed unchanged to the underlying database.
- Supported Queries: VerdictDB supports equi-joins, comparison subqueries, and predicates such as IN lists, LIKE regexes, and inequalities.Comparison subqueries are flattened into joins with derived tables.
- Supported Queries: IN, EXISTS, and select-list subqueries are not currently approximated.The supported-query boundary excludes these subquery forms.
- Workflow: At runtime, VerdictDB chooses samples under an I/O budget, rewrites the query, and extracts approximate answers with probabilistic error bounds.Sample preparation is offline, while query processing occurs when the user issues a query.
3 SAMPLE PREPARATION
VerdictDB prepares uniform, hashed, and stratified samples using SQL-compatible procedures, then uses those samples for approximate processing. Its stratified-sampling method is parallelizable but requires a staircase probability function to preserve minimum-sample guarantees.
- Sample Types: Uniform samples use independent Bernoulli sampling, while hashed samples retain tuples whose hash values fall below τ.Hashed samples use a chosen column set to determine tuple inclusion.
- Sample Types: VerdictDB constructs uniform, hashed, and stratified samples offline; irregular samples arise only during query processing.The default sampling parameter is τ=1%, targeting a 2% query-time I/O budget.
- Stratified Sampling: VerdictDB creates stratified samples in two passes: it first computes group sizes, then samples using group-size-dependent probabilities.The sampling expression is applied through a SQL join with a temporary table containing stratum sizes.
- Stratified Sampling: The SQL-based stratified-sampling procedure is easy to parallelize because tuples are sampled independently through a Bernoulli process.Its operations can be expressed in SQL and executed in parallel.
- Guarantees: A naïve Bernoulli ratio of 0.1 samples fewer than 10 of 100 tuples with probability approximately 0.45, violating the minimum-sample guarantee.VerdictDB therefore uses a staircase function that upper-bounds the required probability.
- Guarantees: The staircase function is based on fm(n), which gives a sampling probability ensuring at least m of n tuples with probability 1−δ.The default failure probability is δ=0.001.
4 VARIATIONAL SUBSAMPLING: PRINCIPLE
Traditional subsampling is more efficient than bootstrap but remains costly in a middleware setting because SQL implementations repeatedly construct or process subsamples. VerdictDB introduces variational subsampling, which preserves statistical correctness while reducing the time complexity to O(n).
- Subsampling Basics: Bootstrap estimates error by repeatedly recomputing aggregates on resamples, but its repetitive computation has time complexity O(n · b).Analytical bootstrap reduces computational cost but requires modifying relational operators inside the database, making it inapplicable to middleware.
- Subsampling Basics: Subsampling uses smaller samples without replacement, making it more efficient than bootstrap, but SQL implementations can still be expensive for middleware.Traditional SQL subsampling costs O(b · n) to construct subsamples, while the aggregation query costs O(b · ns).
- Variational Subsampling: Variational subsampling avoids repeatedly running the same aggregation query by processing different resamples within one carefully rewritten query.It relaxes the requirement that each subsample contain exactly ns tuples and allows tuples to participate in varying numbers of subsamples.
- Variational Subsampling: O(n) time complexity makes variational subsampling at least O(b) times more efficient than traditional subsampling, whose cost is O(b · n).The overall cost is O(n + b · ns)=O(n) because b · ns ≪ n.
- Variational Subsampling: Variational subsampling corrects for varying subsample sizes and can correctly estimate the distribution of a sample estimate when n is large.Its asymptotic error is minimized at ns = n^1/2, which VerdictDB uses by default while allowing users to choose other values.
5 VARIATIONAL SUBSAMPLING ADVANCED
VerdictDB extends variational subsampling to joins and nested queries while preserving statistical correctness. Its key optimization replaces repeated subsample joins or aggregate scans with SQL operations that are more efficient to execute.
- 5.1 Variational Subsampling for Joins: Joining sampled tables creates inter-tuple dependence, which VerdictDB must handle without changing the database’s internal query evaluation.The middleware also cannot rely on foreign-key constraints or non-standard join algorithms.
- 5.1 Variational Subsampling for Joins: A basic join construction pairs corresponding subsamples from two variational tables and repeats the join b times to form the joined variational table.Theorem 3 states correctness when the sampling ratios for the two input tables are equal.
- 5.1 Variational Subsampling for Joins: VerdictDB instead joins two variational tables once and reassigns sid values using a function that partitions subsample-index pairs.This requires only a single join and projection, making the construction suitable for SQL execution.
- 5.1 Variational Subsampling for Joins: The efficient join construction avoids the extremely inefficient SQL plan caused by a union of multiple join expressions.The approach preserves the variational-table representation needed for estimating the distribution of sample-based join approximations.
- 5.2 Variational Subsampling for Nested Queries: For nested queries, Query 7 replaces repeated aggregate computations over subsamples and requires O(b) fewer scans of orders_v than Query 6.The optimization exploits the disjointness of the subsamples in a variational table.
6 EXPERIMENTS
Experiments evaluate VerdictDB across engines, datasets, query types, and error-estimation methods, finding substantial speedups with low error and competitive performance against integrated AQP.
- Overall results: 18.45× average and up to 171× speedups were achieved across Impala, Spark SQL, and Redshift, with less than 2.6% relative error.The experiments targeted platform-independence, efficiency, and statistical correctness.
- Data-size scaling: 1.4× average speedup at 50 GB increased to 7.00× at 200 GB and more than 22.6× at 500 GB with a fixed 5 GB sample.The trend was measured using two Impala queries.
- Integrated AQP comparison: VerdictDB was comparable to SnappyData for most queries and significantly faster for queries joining two samples.SnappyData used the original table for the second relation when it lacked support for joining two samples, while VerdictDB used hashed samples.
- Native approximations: 43.5× faster average performance than native approximate aggregates was achieved for sampling-based count-distinct and median queries.The native aggregates required full data scans because they relied on sketching techniques.
- Error estimation: 99×, 42×, and 63× lower overall latency than consolidated bootstrap was achieved for flat, join, and nested queries, respectively, using variational subsampling.Variational subsampling added only 0.38–0.87 seconds of latency and its error estimates were within 7% of groundtruth.
7 RELATED WORK
Related work covers sampled AQP, online aggregation, middleware query rewriting, and stratified-sample construction, positioning VerdictDB among approaches that improve portability and query coverage.
- Approximate Query Processing: Sampled AQP systems have explored optimal stratified samples, while online aggregation continuously refines answers during query execution.The cited systems include STRAT, AQUA, BlinkDB, and Online Aggregation.
- Middleware-based Query Rewriting: Aqua, IDEA, and Sesame use query rewriting for AQP, whereas VerdictDB supports non-PK-FK joins, nested queries, and modern distributed query engines.VerdictDB’s query-rewriting approach is presented as covering a wider range of practical queries.
- Stratified Sample Construction Techniques: BlinkDB constructs stratified samples through two passes, but implementing per-group reservoir sampling in SQL is highly complex and increasingly costly with more strata.The process separates strata, randomly shuffles tuples, and filters them with a limit clause.
8 CONCLUSION
VerdictDB demonstrates that database-agnostic AQP can operate atop existing SQL engines using standard SQL and no database modifications. It delivers substantial speedups with low relative error, while future work targets broader database support and additional sampling capabilities.
- Universal AQP can operate atop existing SQL-based engines without modifying the databases.The solution relies on standard SQL queries and a driver-level architecture.
- VerdictDB’s driver-level solution was comparable to fully integrated AQP engines and sometimes outperformed them.The paper attributes some of this performance to Variational Subsampling.
- 18.45× average speedup and up to 171× speedup were achieved with less than 2.6% relative errors.The evaluation covered Impala, Spark SQL, and Amazon Redshift.
- Future work includes drivers for additional databases, online middleware sampling, sample physical design, and studying effects on user behavior.Planned database targets include Presto, Teradata, Oracle, and HP Vertica.
B.1 Actual Errors of VerdictDB’s Answers
VerdictDB’s actual relative errors were low and nearly identical across tested engines. Errors varied primarily with the cardinality of grouping attributes.
- 0.03%–2.57% were the observed relative errors across all 33 queries.The reported results here use Impala because errors were nearly identical across engines.
- Errors were nearly identical across different engines, apart from negligible differences attributed to random sampling.
- Higher grouping-attribute cardinality increased approximation error by reducing the number of tuples averaged by AQP.A 10× increase in unique grouping values reduces the averaged tuples by 10×.
B.2 Sample Preparation Time
VerdictDB’s sampling preparation time was substantially smaller than common data-transfer overheads for cluster data preparation. The comparison covered remote and within-cluster transfer tasks.
- VerdictDB’s sampling preparation time was much smaller than the other data-preparation tasks.The comparison used a 370 GB dataset and included data-transfer overheads.
- The evaluation compared sampling against remote-cluster transfer and within-cluster transfer overheads.Remote transfer involved copying files to an AWS instance, while within-cluster transfer involved uploads to HDFS.
- Sampling creation workloads were mostly read-only, whereas the comparison tasks involved heavy write loads.The passage connects this workload difference to distributed storage systems’ support for sampling creation.
B.3 Further Study of Variational Subsampling
Variational subsampling trades some accuracy against much lower latency than bootstrap and traditional subsampling, while its error behavior depends on sample and resample sizes. The default subsample policy minimized observed errors in one validation.
- Comparison Against Other Techniques: Bootstrap produced more accurate error estimates than traditional and variational subsampling, but the gap narrowed as n increased.Accuracy was measured using relative error with respect to the true mean.
- Comparison Against Other Techniques: Variational subsampling was orders of magnitude faster than bootstrap and traditional subsampling for the same sample size.
- Comparison Against Other Techniques: Given the same time budget, variational subsampling achieved significantly lower relative errors than bootstrap and traditional subsampling.The comparison reflects the prohibitive costs of the other two methods.
- Impact of Subsample Size: Finite resample counts add an O(b^-1/2) error term to resampling-based estimates.The passage motivates this term through the Dvoretzky–Kiefer–Wolfowitz inequality.
- Impact of Subsample Size: n_s = n^1/2 minimized the error expression and was also the lowest-error policy in the empirical validation.The validation fixed n to 50,000 and compared several powers of n.
C PROOFS
The proofs establish that variational subsampling retains the asymptotic distributional guarantees of traditional subsampling while supporting joins between separately sampled tables. They use independence, concentration inequalities, and two-sample asymptotic results to show convergence to the relevant true distributions.
- Theorem 2 states that the empirical distribution from variational subsampling converges in distribution to the true distribution when ns grows while ns/n tends to zero.
- Variational subsampling partitions observations into b non-overlapping sets, making the resulting aggregates mutually independent.This independence permits the use of Hoeffding’s inequality.
- The variational-subsampling proof shows that the relevant error term converges to zero in probability as n grows.The argument uses Hoeffding’s inequality and the vanishing variance of ns,i/n.
- As b grows without bound, the empirical distribution formed by the subsample aggregates converges to the true distribution.
- For two separately sampled tables, the estimator’s distribution converges to the true distribution under the stated equal sampling-ratio condition.The proof uses a two-sample statistic whose variance vanishes asymptotically.
D DATA APPENDS
VerdictDB maintains and plans samples as data changes, selecting sample-table combinations that minimize approximation error within an I/O budget. Its planner enumerates, consolidates, scores, and cost-filters candidate plans, but exhaustive enumeration can grow exponentially with joined tables.
- Incremental Sample Maintenance: VerdictDB updates uniform, hashed, and stratified samples when new data batches are appended.Stratified sampling reuses stored probabilities and generates new probabilities for previously unseen groups.
- Sample Consistency: VerdictDB can update samples after partitioned ingestion and detect stale samples by checking table cardinalities.
- Sample Planning: A sample plan maps aggregate functions to sample tables and seeks the lowest approximation errors within a given I/O budget.
- Plan Selection: The planner generates candidate plans, consolidates aggregates sharing sample tables, and selects the highest-scoring plan within the I/O budget.Candidate plans are scored and assigned I/O costs before selection.
- Plan Selection: The score uses the square root of an effective sampling ratio, reflecting that mean-like errors decrease with the square root of sample size.
- Computational Cost: The number of candidate plans grows exponentially with the number of tables in a query when multiple sample tables are available.
E.2 Heuristic Sample Plans
VerdictDB reduces sample-planning cost with heuristic early pruning and uses rewritten SQL to compute approximate aggregates and error estimates. The heuristic retains the best sample tables at joins, trading efficiency against conservatism through configurable k.
- Heuristic Pruning: VerdictDB prunes sample tables early at joins to avoid the prohibitive cost of exhaustively enumerating candidate plans.
- Heuristic Pruning: Sample tables too large to fit the I/O budget are ignored, while very small samples receive lower scores and are unlikely to be selected.
- Heuristic Pruning: At each join, the planner retains only the k best sample tables; the default value is k = 10.Larger k is more conservative, while smaller k improves efficiency.
- Heuristic Pruning: The same heuristic process is applied separately to multiple aggregate functions and to nested queries when generating candidate plans.
- Default Sample Selection: VerdictDB chooses default sample types from column cardinalities, creating uniform samples and selectively adding hashed or stratified samples.The policy uses a 1% cardinality threshold and limits selections to the top 10 columns in each direction.
- Query Rewriting: Rewritten SQL computes per-subsample estimates, then combines them into a weighted aggregate and an error estimate based on standard deviations.