Innovative Database Engine Tiresias for Advanced Queries and Optimization
"Explore Tiresias, a cutting-edge database oracle that facilitates how-to queries, hypothetical scenarios, KPI analysis, and constraint optimization. Powered by TiQL and MathProg, it offers a seamless interface for efficient data processing and problem-solving in modern DBMS environments."
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Tiresias The Database Oracle for How-To Queries Alexandra Meliou Dan Suciu University of Massachusetts Amherst University of Washington University of Washington Database Group
Hypothetical (What-if) Queries Key Performance Indicators (KPI) Brokerage company DB Example from [Balmin et al. VLDB 00]: An analyst of a brokerage company wants to know what would be the effect on the return of customers portfolios if during the last 3 years they had suggested Intel stocks instead of Motorola. change something in the source (hypothesis) forward observe the effect in the target
How-To Queries Key Performance Indicators (KPI) Brokerage company DB Modified example: An analyst wants to ask how to achieve a 10% return in customer portfolios, with the least number of trades. find changes to the source that achieve the desired effect reverse declare a desired effect in the target
TPC-H example A manufacturing company keeps records of inventory orders in a LineItem table. KPI: Cannot order more than 7% of the inventory from any single country (variables) Can reassign orders to new suppliers as long as the supplier can supply the part (constraints) Minimize the number of changes (optimization objective)constraint optimization
Constraint Optimization on Big Data this is for a set of 10 lineitems and 40 suppliers MathProg DB construct optimization model Impractical! extract data Mixed Integer Programming (MIP) solver transform into data updates
Demo: Tiresias a tool that makes how-to queries practical
Tiresias: How-To Query Engine TiQL (Tiresias Query Language) MIP solver Tiresias Declarative interface, extension to Datalog DBMS
Overview Visualizations TiQL MathProg or AMPL
Overview Visualizations Demo TiQL MathProg or AMPL
Overview Visualizations Demo TiQL Language semantics Evaluation of a TiQL program: Translation from TiQL to linear constraints MathProg or AMPL Performance optimizations
Tiresias Query Language Datalog-like notation: head body: conjunction of predicates TiQL semantics: Mapping from EDBs (Extensional Database) to possible worlds over HDBs (Hypothetical Database) HDB
TiQL Rules Deduction Rule Semantics: Similar to repair-key semantics [Antonova et al. SIGMOD 07], [Koch ICDT 09] Reduction Rule Semantics: Takes a subset of tuples Constraint Rule Semantics: The head predicate needs to hold for all tuples
Overview Visualizations Demo TiQL Language semantics Evaluation of a TiQL program: Translation from TiQL to linear constraints MathProg or AMPL Performance optimizations
Evaluating a TiQL Program TiQL DB Mixed Integer Program (MIP)
Evaluating a TiQL Program possible worlds
Key Constraints NOT a possible world
Provenance Constraints A TiQL rule specifies transformations Transformations define provenance Boolean semantics for queries without aggregates Semi-module provenance for queries with aggregates [Amsterdamer et al. PODS 11] Disjunction: Conjunction:
Overview Visualizations Demo TiQL Language semantics Evaluation of a TiQL program: Translation from TiQL to linear constraints MathProg or AMPL Performance optimizations
Optimizing Performance Model optimizer eliminates variables, constraints, and parameters uses key constraints, functional dependencies, and provenance Significantly faster than letting the MIP solver do it Partitioning optimizer
Evaluation of the Model Optimizer 10000 without model optimization with model optimization 1000 Runtime (sec) baseline 100 10 with optimization 1 100 1000 10000 Data size (# of tuples)
Evaluation of Tiresias Partitioning complex dependency on the granularity of partitioning 1M tuples 10k tuples 80 25000 TiQL to MIP translation TiQL to MIP translation 70 MIP solver MIP solver 20000 total Tiresias query time total Tiresias query time 60 Runtime (sec) Runtime (sec) 50 15000 40 10000 30 20 5000 10 0 0 0 100 200 300 400 500 600 0 100 200 300 400 500 600 Group size (# of partitions per group) Group size (# of partitions per group) granularity of partitioning
Scalability 8 MIP solver / per partition (avg) MIP constructor / per partition (avg) 7 6 Constructor time depends on DB query execution time Runtime (sec) 5 The MIP solver runtime (per partition) does not increase with data size 4 3 2 1 0 5k 10k Data size (# of tuples) 50k 100k 500k 1M
Related Work Provenance [Amsterdamer et al. PODS 11], [Cui et al. TODS 00], [Green et al. PODS 07] Incomplete databases [Antonova et al. SIGMOD 07], [Imielinski et al. JACM 84], [Koch ICDT 09] Other RDM problems [Arasu et al. SIGMOD 11], [Binnig et al. ICDE 07], [Bohannon et al. PODS 06], [Fagin et al. JACM 10]
Next Steps with Tiresias Handling non-partitionable problems Tiresias Approximations Parallelization and handling of skew Result analysis and feedback-based problem generation
SIGMOD Demo Group C Location: Vaquero A Time: 13:30-15:00
Contributions How-To queries Using MIP solvers to answer How-To queries Tiresias prototype implementation http://db.cs.washington.edu/tiresias
