More Web Proxy on the site http://driver.im/

research-article

An Incremental Anytime Algorithm for Multi-Objective Query Optimization

Authors:

Immanuel Trummer,

Christoph KochAuthors Info & Claims

SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data

Pages 1941 - 1953

https://doi.org/10.1145/2723372.2746484

Published: 27 May 2015 Publication History

Abstract

Query plans offer diverse tradeoffs between conflicting cost metrics such as execution time, energy consumption, or execution fees in a multi-objective scenario. It is convenient for users to choose the desired cost tradeoff in an interactive process, dynamically adding constraints and finally selecting the best plan based on a continuously refined visualization of optimal cost tradeoffs. Multi-objective query optimization (MOQO) algorithms must possess specific properties to support such an interactive process: First, they must be anytime algorithms, generating multiple result plan sets of increasing quality with low latency between consecutive results. Second, they must be incremental, meaning that they avoid regenerating query plans when being invoked several times for the same query but with slightly different user constraints. We present an incremental anytime algorithm for MOQO, analyze its complexity and show that it offers an attractive tradeoff between result update frequency, single invocation time complexity, and amortized time over multiple invocations. Those properties make it suitable to be used within an interactive query optimization process. We evaluate the algorithm in comparison with prior work on TPC-H queries; our implementation is based on the Postgres database management system.

References

[1]

S. Agarwal, A. Iyer, and A. Panda. Blink and it's done: interactive queries on very large data. In VLDB, volume 5, pages 1902--1905, 2012.

Digital Library

[2]

G. Ausiello and G. Italiano. Incremental paths algorithms for minimal length paths. Journal of Algorithms, 12(4):12--21, 1991.

Digital Library

[3]

J. L. Bentley and J. H. Friedman. Data structures for range searching. ACM Computing Surveys, 11(4):397--409, 1979.

Digital Library

[4]

P. Bizarro, N. Bruno, and D. DeWitt. Progressive parametric query optimization. KDE, 21(4):582--594, 2009.

Digital Library

[5]

S. Chatterji and S. Evani. On the complexity of approximate query optimization. In PODS, pages 282--292, 2002.

Digital Library

[6]

S. Chaudhuri. Query optimizers: time to rethink the contract? SIGMOD, pages 961--968, 2009.

Digital Library

[7]

S. Ganguly, W. Hasan, and R. Krishnamurthy. Query optimization for parallel execution. In SIGMOD, pages 9--18, 1992.

Digital Library

[8]

J. M. Hellerstein, P. J. Haas, and H. J. Wang. Online aggregation. In SIGMOD, pages 171--182, 1997.

Digital Library

[9]

P. Klein and N. Young. Approximation algorithms for NP-hard optimization problems. In Algorithms and Theory of Computation Handbook. 2010.

Digital Library

[10]

D. Kossmann and K. Stocker. Iterative dynamic programming: a new class of query optimization algorithms. ACM TODS, 25(1):43--82, 2000.

Digital Library

[11]

C. Papadimitriou and M. Yannakakis. Multiobjective query optimization. In PODS, pages 52--59, 2001.

Digital Library

[12]

P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. In SIGMOD, pages 23--34, 1979.

Digital Library

[13]

M. Stonebraker, P. Aoki, R. Devine, W. Litwin, and M. Olson. Mariposa: a new architecture for distributed data. In ICDE, pages 54--65, 1994.

Digital Library

[14]

I. Trummer and C. Koch. Approximation schemes for many-objective query optimization. In SIGMOD, pages 1299--1310, 2014.

Digital Library

[15]

I. Trummer and C. Koch. Multi-objective parametric query optimization. VLDB, 8(3):221--232, 2015.

Digital Library

[16]

S. V. Vrbsky and Jane W.-S. Liu. APPROXIMATE-a query processor that produces monotonically improving approximate answers. KDE, 5(6):1056--1068, 1993.

Digital Library

[17]

R. Willis, CEWillis, C., & Perlack. Multiple objective decision making: generating techniques or goal programming. Journal of the Northeastern Agr. Econ. Council, 9(1):0--5, 1980.

[18]

Z. Xu, Y. C. Tu, and X. Wang. PET: Reducing Database Energy Cost via Query Optimization. VLDB, 5(12):1954--1957, 2012.

Digital Library

[19]

S. Zilberstein. Using anytime algorithms in intelligent systems. AI Magazine, 17(3):73--83, 1996.

Digital Library

Cited By

Lyu CFan QGuyard PDiao Y(2024)A Spark Optimizer for Adaptive, Fine-Grained Parameter TuningProceedings of the VLDB Endowment10.14778/3681954.368202117:11(3565-3579)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682021
Chen YZheng QYan Z(2023)Efficient Bi-objective SQL Optimization for Enclaved Cloud Databases with Differentially Private PaddingACM Transactions on Database Systems10.1145/359702148:2(1-40)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1145/3597021
Lyu CFan QSong FSinha ADiao YChen WMa LFeng YLi YZeng KZhou J(2022)Fine-grained modeling and optimization for intelligent resource management in big data processingProceedings of the VLDB Endowment10.14778/3551793.355185515:11(3098-3111)Online publication date: 29-Sep-2022
https://dl.acm.org/doi/10.14778/3551793.3551855
Show More Cited By

Index Terms

An Incremental Anytime Algorithm for Multi-Objective Query Optimization
1. Information systems
  1. Data management systems
    1. Database management system engines

Recommendations

A Fast Randomized Algorithm for Multi-Objective Query Optimization
SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

Query plans are compared according to multiple cost metrics in multi-objective query optimization. The goal is to find the set of Pareto plans realizing optimal cost tradeoffs for a given query. So far, only algorithms with exponential complexity in the ...
Approximation schemes for many-objective query optimization
SIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data

The goal of multi-objective query optimization (MOQO) is to find query plans that realize a good compromise between conflicting objectives such as minimizing execution time and minimizing monetary fees in a Cloud scenario. A previously proposed ...
Ordered Incremental Multi-Objective Problem Solving Based on Genetic Algorithms

Many Multiple Objective Genetic Algorithms (MOGAs) have been designed to solve problems with multiple conflicting objectives. Incremental approach can be used to enhance the performance of various MOGAs, which was developed to evolve each objective ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '15: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data

May 2015

2110 pages

ISBN:9781450327589

DOI:10.1145/2723372

General Chair:
Timos Sellis
RMIT University, Australia
,
Program Chairs:
Susan B. Davidson
University of Pennsylvania, USA
,
Zack Ives
University of Pennsylvania, USA

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 May 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'15

Sponsor:

SIGMOD

SIGMOD/PODS'15: International Conference on Management of Data

May 31 - June 4, 2015

Victoria, Melbourne, Australia

Acceptance Rates

SIGMOD '15 Paper Acceptance Rate 106 of 415 submissions, 26%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
510
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)2

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lyu CFan QGuyard PDiao Y(2024)A Spark Optimizer for Adaptive, Fine-Grained Parameter TuningProceedings of the VLDB Endowment10.14778/3681954.368202117:11(3565-3579)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682021
Chen YZheng QYan Z(2023)Efficient Bi-objective SQL Optimization for Enclaved Cloud Databases with Differentially Private PaddingACM Transactions on Database Systems10.1145/359702148:2(1-40)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1145/3597021
Lyu CFan QSong FSinha ADiao YChen WMa LFeng YLi YZeng KZhou J(2022)Fine-grained modeling and optimization for intelligent resource management in big data processingProceedings of the VLDB Endowment10.14778/3551793.355185515:11(3098-3111)Online publication date: 29-Sep-2022
https://dl.acm.org/doi/10.14778/3551793.3551855
Song FZaouk KLyu CSinha AFan QDiao YShenoy P(2021)Spark-based Cloud Data Analytics using Multi-Objective Optimization2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00041(396-407)Online publication date: May-2021
https://doi.org/10.1109/ICDE51399.2021.00041
Gawali RShinde S(2021)Novel Design Approach for Optimal Execution Plan and Strategy for Query ExecutionAdvanced Computing10.1007/978-981-16-0404-1_23(308-319)Online publication date: 11-Feb-2021
https://doi.org/10.1007/978-981-16-0404-1_23
Rituraj RVarkonyi Koczy A(2020)Advantages of Anytime Algorithm for Multi-Objective Query Optimization2020 IEEE 18th World Symposium on Applied Machine Intelligence and Informatics (SAMI)10.1109/SAMI48414.2020.9108713(000141-000144)Online publication date: Jan-2020
https://doi.org/10.1109/SAMI48414.2020.9108713
Zaouk KSong FLyu CSinha ADiao YShenoy P(2019)UDAOProceedings of the VLDB Endowment10.14778/3352063.335210312:12(1934-1937)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.14778/3352063.3352103
Mytilinis ITsoumakos DKoziris N(2019)Scaling the Construction of Wavelet Synopses for Maximum Error MetricsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.286718531:9(1794-1808)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1109/TKDE.2018.2867185
Trummer IKoch C(2017)Multi-objective parametric query optimizationCommunications of the ACM10.1145/306861260:10(81-89)Online publication date: 25-Sep-2017
https://dl.acm.org/doi/10.1145/3068612
Dutt ANarasayya VChaudhuri SChirkova RYang JSuciu D(2017)Leveraging Re-costing for Online Optimization of Parameterized Queries with GuaranteesProceedings of the 2017 ACM International Conference on Management of Data10.1145/3035918.3064040(1539-1554)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3035918.3064040
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten