DocumentCode :
2847893
Title :
On the optimal ordering of maps and selections under factorization
Author :
Neumann, Thomas ; Helmer, Sven ; Moerkotte, Guido
Author_Institution :
Mannheim Univ., Germany
fYear :
2005
fDate :
5-8 April 2005
Firstpage :
490
Lastpage :
501
Abstract :
The query optimizer of a database system is confronted with two aspects when handling user-defined functions (UDFs) in query predicates: the vast differences in evaluation costs between UDFs (and other functions) and multiple calls of the same (expensive) UDF The former is dealt with by ordering the evaluation of the predicates optimally, the latter by identifying common subexpressions and thereby avoiding costly recomputation. Current approaches order n predicates optimally (neglecting factorization) in O(nlogn). Their result may deviate significantly from the optimal solution under factorization. We formalize the problem of finding optimal orderings under factorization and prove that it is NP-hard. Furthermore, we show how to improve on the run time of the brute-force algorithm (which computes all possible orderings) by presenting different enhanced algorithms. Although in the worst case these algorithms obviously still behave exponentially, our experiments demonstrate that for real-life examples their performance is much better.
Keywords :
computational complexity; database management systems; query processing; NP-hard problem; database system query optimizer; factorization; optimal orderings; query predicates; user-defined function handling; Content based retrieval; Cost function; Database systems; Feature extraction; Image databases; Image retrieval; Information retrieval; Runtime; Shape; Spatial databases;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Engineering, 2005. ICDE 2005. Proceedings. 21st International Conference on
ISSN :
1084-4627
Print_ISBN :
0-7695-2285-8
Type :
conf
DOI :
10.1109/ICDE.2005.97
Filename :
1410161
Link To Document :
بازگشت