Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: PAR2QO: Parametric Penalty-Aware Robust Query Optimization
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
Award ID(s):
2402823
PAR ID:
10690352
Author(s) / Creator(s):
; ; ; ;
Publisher / Repository:
VLDB Endowment
Date Published:
Journal Name:
Proceedings of the VLDB Endowment
Volume:
18
Issue:
11
ISSN:
2150-8097
Page Range / eLocation ID:
4532 to 4545
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Proceedings of the ACM on Management of Data)
    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
  2. ; ; ; ; ; ; ; (, Proceedings of the VLDB Endowment)
    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
  3. ; ; ; ; ; ; ; (, Proceedings of the ACM on Management of Data)
    Log-Structured Merge-tree-based Key-Value Stores (LSM-KVS) have been optimized and redesigned for disaggregated storage via techniques such as compaction offloading to reduce the network I/Os between compute and storage. However, the constrained memory space and slow flush at the compute node severely limit the overall write throughput of existing optimizations. In this paper, we proposeO3-LSM,a fundamental new LSM-KVS architecture, that leverages the shared Disaggregated Memory (DM) to support athree-layeroffloading, i.e., memtableOffloading, flushOffloading, and the existing compactionOffloading. Compared to the existing disaggregated LSM-KVS with compaction offloading only, O3-LSM maximizes the write performance by addressing the above issues. O3-LSM first leverages a novelDM-Optimized Memtableto achievedynamic memtable offloading,which extends the write buffer while enabling fast, asynchronous, and parallel memtable transmission. Second, we proposeCollaborative Flush Offloadingthat decouples the flush control plane from execution and supports memtable flush offloading at any node with dedicated scheduling and global optimizations. Third, O3-LSM is further improved with theShard-Level Optimization,which partitions the memtable into shards based on disjoint key-ranges that can be transferred and flushed independently, unlocking parallelism across shards. Besides, to mitigate slow lookups in the disaggregated setting, O3-LSM also employs an adaptiveCache-Enhanced Read Delegationmechanism to combine a compact local cache with DM-assisted memtable delegated read. Our evaluation shows that O3-LSM achieves up to4.5Xwrite,5.2XXrange query, and1.8Xpoint lookup throughput improvement, and up to76%P99 latency reduction compared with Disaggregated-RocksDB, CaaS-LSM, and Nova-LSM. 
    more » « less
  4. ; ; ; ; ; ; ; (, Proceedings of the VLDB Endowment)
    Query driven cardinality estimation models learn from a historical log of queries. They are lightweight, having low storage requirements, fast inference and training, and are easily adaptable for any kind of query. Unfortunately, such models can suffer unpredictably bad performance under workload drift, i.e., if the query pattern or data changes. This makes them unreliable and hard to deploy. We analyze the reasons why models become unpredictable due to workload drift, and introduce modifications to the query representation and neural network training techniques to make query-driven models robust to the effects of workload drift. First, we emulate workload drift in queries involving some unseen tables or columns by randomly masking out some table or column features during training. This forces the model to make predictions with missing query information, relying more on robust features based on up-to-date DBMS statistics that are useful even when query or data drift happens. Second, we introduce join bitmaps, which extends sampling-based features to be consistent across joins using ideas from sideways information passing. Finally, we show how both of these ideas can be adapted to handle data updates. We show significantly greater generalization than past works across different workloads and databases. For instance, a model trained with our techniques on a simple workload (JOBLight-train), with 40ksynthetically generated queries of at most 3 tables each, is able to generalize to the much more complex Join Order Benchmark, which include queries with up to 16 tables, and improve query runtimes by 2× over PostgreSQL. We show similar robustness results with data updates, and across other workloads. We discuss the situations where we expect, and see, improvements, as well as more challenging workload drift scenarios where these techniques do not improve much over PostgreSQL. However, even in the most challenging scenarios, our models never perform worse than PostgreSQL, while standard query driven models can get much worse than PostgreSQL. 
    more » « less
  5. ; ; (, Frontiers in Robotics and AI)
    Introduction:Human-in-the-loop optimization algorithms have proven useful in optimizing complex interactive problems, such as the interaction between humans and robotic exoskeletons. Specifically, this methodology has been proven valid for reducing metabolic cost while wearing robotic exoskeletons. However, many prostheses and orthoses still consist of passive elements that require manual adjustments of settings. Methods:In the present study, we investigated if human-in-the-loop algorithms could guide faster manual adjustments in a procedure similar to fitting a prosthesis. Eight healthy participants wore a prosthesis simulator and walked on a treadmill at 0.8 ms−1under 16 combinations of shoe heel height and pylon height. A human-in-the-loop optimization algorithm was used to find an optimal combination for reducing the loading rate on the limb contralateral to the prosthesis simulator. To evaluate the performance of the optimization algorithm, we used a convergence criterium. We evaluated the accuracy by comparing it against the optimum from a full sweep of all combinations. Results:In five out of the eight participants, the human-in-the-loop optimization reduced the time taken to find an optimal combination; however, in three participants, the human-in-the-loop optimization either converged by the last iteration or did not converge. Discussion:Findings from this study show that the human-in-the-loop methodology could be helpful in tasks that require manually adjusting an assistive device, such as optimizing an unpowered prosthesis. However, further research is needed to achieve robust performance and evaluate applicability in persons with amputation wearing an actual prosthesis. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Text Encoded Conversion
  • XML
  • Save / Share this Record
  • Send to Email