NDLI: Robust Heuristics for Scalable Optimization of Complex SQL Queries

Content Provider	IEEE Xplore Digital Library
Author	Das, G.C. Haritsa, J.R.
Copyright Year	2007
Description	Author affiliation: Database Syst. Lab., Indian Inst. of Sci., Bangalore, India (Das, G.C.; Haritsa, J.R.)
Abstract	Modern database systems incorporate a query optimizer to identify the most efficient "query execution plan" for executing the declarative SQL queries submitted by users. A dynamic-programming-based approach is used to exhaustively enumerate the combinatorially large search space of plan alternatives and, using a cost model, to identify the optimal choice. While dynamic programming (DP) works very well for moderately complex queries with up to around a dozen base relations, it usually fails to scale beyond this stage due to its inherent exponential space and time complexity. Therefore, DP becomes practically infeasible for complex queries with a large number of base relations, such as those found in current decision-support and enterprise management applications. To address the above problem, a variety of approaches have been proposed in the literature. Some completely jettison the DP approach and resort to alternative techniques such as randomized algorithms, whereas others have retained DP by using heuristics to prune the search space to computationally manageable levels. In the latter class, a well-known strategy is "iterative dynamic programming" (IDP) wherein DP is employed bottom-up until it hits its feasibility limit, and then iteratively restarted with a significantly reduced subset of the execution plans currently under consideration. The experimental evaluation of IDP indicated that by appropriate choice of algorithmic parameters, it was possible to almost always obtain "good" (within a factor of twice of the optimal) plans, and in the few remaining cases, mostly "acceptable" (within an order of magnitude of the optimal) plans, and rarely, a "bad" plan. While IDP is certainly an innovative and powerful approach, we have found that there are a variety of common query frameworks wherein it can fail to consistently produce good plans, let alone the optimal choice. This is especially so when star or clique components are present, increasing the complexity of the join graphs. Worse, this shortcoming is exacerbated when the number of relations participating in the query is scaled upwards.
Starting Page	1281
Ending Page	1283
File Size	97821
Page Count	3
File Format	PDF
ISBN	1424408024
DOI	10.1109/ICDE.2007.368993
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-04-15
Publisher Place	Turkey
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Robustness Dynamic programming Cost function Database systems Iterative algorithms Engines Laboratories Genetics Refining
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Robust Heuristics for Scalable Optimization of Complex SQL Queries

Robust Heuristics For Scalable Optimization Of Complex SQL Queries

Robust heuristics for scalable optimization of complex sql queries.

Inequality/equality constrained optimization: an analytical robustness comparison of a feasibility method versus L1 sequential quadratic programming

Improved Query Plans for Unnesting Nested SQL Queries

Iterative integer programming formulation for robust resource allocation in dynamic real-time systems

Use of AI in Query Optimization of Relational Databases

An Effective Differential Dynamic Programming Algorithm for Constrained Optimal Control Problems

Optimal Trajectories for Multidimensional Nonlinear Processes by Iterated Dynamic Programming

Robust Heuristics for Scalable Optimization of Complex SQL Queries

Similar Documents

Robust Heuristics for Scalable Optimization of Complex SQL Queries

Robust Heuristics For Scalable Optimization Of Complex SQL Queries

Robust heuristics for scalable optimization of complex sql queries.

Inequality/equality constrained optimization: an analytical robustness comparison of a feasibility method versus L1 sequential quadratic programming

Improved Query Plans for Unnesting Nested SQL Queries

Iterative integer programming formulation for robust resource allocation in dynamic real-time systems

Use of AI in Query Optimization of Relational Databases

An Effective Differential Dynamic Programming Algorithm for Constrained Optimal Control Problems

Optimal Trajectories for Multidimensional Nonlinear Processes by Iterated Dynamic Programming

Robust Heuristics for Scalable Optimization of Complex SQL Queries