Selectivity estimation by batch-query based histogram and parametric method

Luo, J., Zhou, X., Zhang, Y., Shen, H. T. and Li, J. (2007). Selectivity estimation by batch-query based histogram and parametric method. In: J. Bailey and A. Fekete, Proceedings of the Eighteenth Australasian Database Conference (ADC 2007). Eighteenth Australasian Database Conference, Ballarat , Australia, (93-102). 29 January - 2 February 2007.


Author Luo, J.
Zhou, X.
Zhang, Y.
Shen, H. T.
Li, J.
Title of paper Selectivity estimation by batch-query based histogram and parametric method
Conference name Eighteenth Australasian Database Conference
Conference location Ballarat , Australia
Conference dates 29 January - 2 February 2007
Proceedings title Proceedings of the Eighteenth Australasian Database Conference (ADC 2007)
Place of Publication Sydney, Australia
Publisher Australian Computer Society
Publication Year 2007
Sub-type Fully published paper
ISBN 9781920682446
1920682449
ISSN 1445-1336
Editor J. Bailey
A. Fekete
Volume CRPIT 63
Start page 93
End page 102
Total pages 10
Language eng
Abstract/Summary Histograms are used extensively for selectivity estimation and approximate query processing. Workloadaware dynamic histograms can self-tune itself based on query feedback without scanning or sampling the underlaying datasets in a systematic and comprehensive way. Dynamic histograms allocate more buckets not only for the areas with most skewed data distribution but also according to users' interest. However,it takes long time to 'warm-up' (i.e., a large number of queries need to be processed before the histogram can provide a satisfactory coverage and accuracy). Thus, it is less effective to adapt with workload pattern changes. In this paper, we propose a novel online query scheduling algorithm which can significantly reduce the warm-up time for dynamic histograms. A parametric method is proposed to remedy the problem of inaccurate query selectivity estimation for the areas with poor histogram coverage. Experimental results demonstrate a significant effectiveness and accuracy improvement of our approach.
Subjects 080604 Database Management
0806 Information Systems
Keyword Histograms
Selectivity estimation
Approximate query processing
Online query scheduling algorithm
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status Unknown
Additional Notes ACM International Conference Proceeding Series - Volume 242

 
Versions
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Created: Tue, 31 Mar 2009, 12:05:56 EST by Maryanne Watson on behalf of Faculty Of Engineering, Architecture & Info Tech