An official website of the United States government
Query optimizers rely heavily on selectivity estimates to choose efficient execution plans, but inaccuracies in these estimates often result in poor query performance. We introduceHint-QPT(Hints for RobustQueryPerformanceTuning), an interactive tool designed to help users diagnose and improve query performance. Hint-QPT proactively recommends robust plans that are resilient to uncertainty in selectivity estimates, identifies sensitive subqueries for which selectivity estimation errors greatly affect plan quality, and provides intuitive interfaces for targeted selectivity adjustments. Users can either choose the recommended robust plans for execution, or acquire additional statistics on the identified sensitive subqueries to tune query performance. Moreover, Hint-QPT visualizes the alternative execution plans and their costs under uncertainty, helping users to better understand their robustness.
more »
« less
This content will become publicly available on May 12, 2027
Coresets for Robust Query Optimization
Query optimizers must efficiently choose a query plan using noisy estimates of cardinalities. We study robust query optimization, where the optimizer is made aware of the uncertainty in cardinality estimates and needs to select the most ''robust'' plan. A key empirical observation is that a small set of plans often suffices as robust plan candidates for all queries following a given template. We formalize this phenomenon by introducing coresets of plans and extend this notion to robust coresets, which incorporate uncertainty. We prove positive and negative results on the sizes of such coresets for common cost-function classes. Because our lower bounds suggest that the size of a coreset can be large in the worst case, we exploit the fact that in practice queries arise from workload distributions, rather than being arbitrary. We present algorithms that construct workload-aware coresets whose size and performance closely match those of the optimal workload-specific coresets.
more »
« less
- PAR ID:
- 10690353
- Publisher / Repository:
- ACM
- Date Published:
- Journal Name:
- Proceedings of the ACM on Management of Data
- Volume:
- 4
- Issue:
- 2
- ISSN:
- 2836-6573
- Page Range / eLocation ID:
- 1 to 23
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Parametric Query Optimization (PQO) is an important problem in database systems, yet existing approaches suffer from high training costs, sensitivity to estimation errors, and vulnerability to severe performance regressions. This paper introduces PAR2QO (PARametric Penalty-Aware Robust Query Optimization), a system that integrates robust query optimization into PQO. PAR2QO strategically obtains plans from a well-balanced set of probe locations informed by the workload, and caches them as plan-penalty profiles. At runtime, PAR2QO selects the plan with the lowest expected penalty, explicitly accounting for selectivity uncertainties. Extensive experiments show that PAR2QO delivers significant speedups over existing methods while ensuring robustness against performance degradation. Additionally, we introduceCARVER, a workload generator aimed at covering possible cardinalities of subqueries. Not only does CARVER provide a more comprehensive way to evaluate PQO methods, but when used for training learned methods, it can also enhance their generalizability and stability.more » « less
-
A subgraph query q that finds as output all its subgraph-isomorphic embeddings from a data graph g has been core to modern declarative querying in large graphs. In this paper, we address subgraph queries with the availability of query workload information, W = {w1,...,wn}, where wi ∈ W is a previously issued query with all its subgraph isomorphic embeddings cached beforehand. We introduce a workload-aware subgraph querying framework, WaSQ, that leverages query workload for subgraph query rewriting, search plan refinement, partial results reusing, and false positive filtering towards facilitating the whole subgraph querying process. Experimental studies in real-world graphs demonstrate that WaSQ achieves significant and consistent performance gains in comparison with state-of-the-art, workload-oblivious solutions for large-scale subgraph querying.more » « less
-
Query optimization is critical in relational database management systems (DBMSs) for ensuring efficient query processing. The query optimizer relies on precise selectivity and cost estimates to generate optimal query plans for execution. However, this static query optimization approach falls short for DBMSs handling machine learning (ML) queries. ML-centric DBMSs face distinct challenges in query optimization. First, performance bottlenecks shift to user-defined functions (UDFs), often encapsulating deep learning models, making it difficult to estimate UDF statistics without profiling the query. Second, optimal query plans for ML queries are data-dependent, requiring dynamic plan adjustments during execution. To address these challenges, we introduce Aero, an ML-centric DBMS that utilizes adaptive query processing (AQP) for efficiently processing ML queries. Aero optimizes the evaluation of UDF-based query predicates by dynamically adjusting predicate evaluation order and enhancing UDF execution scalability. By integrating AQP, Aero continuously monitors UDF statistics, routes data to predicates in an optimal order, and dynamically allocates resources for evaluating predicates. Aero achieves up to 6.4x speedup compared to a state-of-the-art ML-centric DBMS across four diverse use cases, with no impact on accuracy.more » « less
-
Recently there has been significant interest in using machine learning to improve the accuracy of cardinality estimation. This work has focused on improving average estimation error, but not all estimates matter equally for downstream tasks like query optimization. Since learned models inevitably make mistakes, the goal should be to improve the estimates that make the biggest difference to an optimizer. We introduce a new loss function, Flow-Loss, for learning cardinality estimation models. Flow-Loss approximates the optimizer's cost model and search algorithm with analytical functions, which it uses to optimize explicitly for better query plans. At the heart of Flow-Loss is a reduction of query optimization to a flow routing problem on a certain "plan graph", in which different paths correspond to different query plans. To evaluate our approach, we introduce the Cardinality Estimation Benchmark (CEB) which contains the ground truth cardinalities for sub-plans of over 16 K queries from 21 templates with up to 15 joins. We show that across different architectures and databases, a model trained with Flow-Loss improves the plan costs and query runtimes despite having worse estimation accuracy than a model trained with Q-Error. When the test set queries closely match the training queries, models trained with both loss functions perform well. However, the Q-Error-trained model degrades significantly when evaluated on slightly different queries (e.g., similar but unseen query templates), while the Flow-Loss-trained model generalizes better to such situations, achieving 4 -- 8× better 99th percentile runtimes on unseen templates with the same model architecture and training data.more » « less
