NDLI: Efficiently adapting graphical models for selectivity estimation

Please wait, while we are loading the content...

Efficiently adapting graphical models for selectivity estimation

Content Provider	Springer Nature Link
Author	Tzoumas, Kostas Deshpande, Amol Jensen, Christian S.
Copyright Year	2012
Abstract	Query optimizers rely on statistical models that succinctly describe the underlying data. Models are used to derive cardinality estimates for intermediate relations, which in turn guide the optimizer to choose the best query execution plan. The quality of the resulting plan is highly dependent on the accuracy of the statistical model that represents the data. It is well known that small errors in the model estimates propagate exponentially through joins, and may result in the choice of a highly sub-optimal query execution plan. Most commercial query optimizers make the attribute value independence assumption: all attributes are assumed to be statistically independent. This reduces the statistical model of the data to a collection of one-dimensional synopses (typically in the form of histograms), and it permits the optimizer to estimate the selectivity of a predicate conjunction as the product of the selectivities of the constituent predicates. However, this independence assumption is more often than not wrong, and is considered to be the most common cause of sub-optimal query execution plans chosen by modern query optimizers. We take a step towards a principled and practical approach to performing cardinality estimation without making the independence assumption. By carefully using concepts from the field of graphical models, we are able to factor the joint probability distribution over all the attributes in the database into small, usually two-dimensional distributions, without a significant loss in estimation accuracy. We show how to efficiently construct such a graphical model from the database using only two-way join queries, and we show how to perform selectivity estimation in a highly efficient manner. We integrate our algorithms into the PostgreSQL DBMS. Experimental results indicate that estimation errors can be greatly reduced, leading to orders of magnitude more efficient query execution plans in many cases. Optimization time is kept in the range of tens of milliseconds, making this a practical approach for industrial-strength query optimizers.
Starting Page	3
Ending Page	27
Page Count	25
File Format	PDF
ISSN	10668888
Journal	The VLDB Journal
Volume Number	22
Issue Number	1
e-ISSN	0949877X
Language	English
Publisher	Springer-Verlag
Publisher Date	2012-11-07
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Graphical models Selectivity estimation Query optimization Database Management
Content Type	Text
Resource Type	Article
Subject	Information Systems Hardware and Architecture

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

Depth estimation for ranking query optimization

Improved selectivity estimator for XML queries based on structural synopsis

SNEE: a query processor for wireless sensor networks

Query optimization in XML structured-document databases

Consistent selectivity estimation via maximum entropy

In-database batch and query-time inference over probabilistic graphical models using UDA–GIST

Query evaluation over probabilistic XML

The RDF-3X engine for scalable management of RDF data

PrDB: managing and exploiting rich correlations in probabilistic databases

Efficiently adapting graphical models for selectivity estimation

Similar Documents

Depth estimation for ranking query optimization

Improved selectivity estimator for XML queries based on structural synopsis

SNEE: a query processor for wireless sensor networks

Query optimization in XML structured-document databases

Consistent selectivity estimation via maximum entropy

In-database batch and query-time inference over probabilistic graphical models using UDA–GIST

Query evaluation over probabilistic XML

The RDF-3X engine for scalable management of RDF data

PrDB: managing and exploiting rich correlations in probabilistic databases

Efficiently adapting graphical models for selectivity estimation