A cost model for interval intersection queries on RI-trees
Proceedings 14th International Conference on Scientific and Statistical Database Management - Trang 131-141
Tóm tắt
The efficient management of interval data represents a core requirement for many temporal and spatial database applications. With the relational interval tree (RI-tree), an efficient access method has been proposed to process interval intersection queries on top of existing object-relational database systems. The paper complements that approach by effective and efficient models to estimate the selectivity and the I/O cost of interval intersection queries in order to guide the cost-based optimizer whether and how to include the RI-tree into the execution plan. By design, the models immediately fit to common extensible indexing/optimization frameworks, and their implementations exploit the built-in statistics facilities of the database server. According to our experimental evaluation on an Oracle database, the average relative error of the estimated cost to the actual cost of index scans ranges from 0% to 23%, depending on the resolution of the persistent statistics and the size of the query objects.
Từ khóa
#Costs #Databases #Conference managementTài liệu tham khảo
10.1109/69.842247
10.1109/ICDE.1986.7266230
10.1109/ICDE.1994.283041
snodgrass, 2000, Developing Time-Oriented Database Applications in SQL
10.1145/280277.280279
huang, 1997, A Cost Model for Estimating the Performance of Spatial Joins Using R-trees, Proc SSDBM, 30
haas, 1995, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proc VLDB, 311
10.1145/170035.170078
1999, IBM DB2 Universal Database Application Development Guide, Version 6
1998, DataBlade Developers Kit User's Guide, Version 3
10.1145/170088.170403
kriegel, 2000, Managing Intervals Efficiently in Object-Relational Databases, Proc VLDB, 407
10.1007/3-540-47724-1_27
10.1007/3-540-47724-1_25
10.1145/375663.375678
10.1007/BFb0054512
10.1145/582095.582099
böhm, 1999, XZ-Ordering: A Space-Filling Curve for Objects with Spatial Extension, Proc of SSD99 (LNCS 1651), 75
10.1109/ICDE.1999.754947
10.1109/ICDE.2000.839396
10.1145/333607.333610
edelsbrunner, 1980, Dynamic Rectangle Intersection Searching, Inst for Information Processing Report 47
chen, 1999, High Level Indexing of User-Defined Types, Proc VLDB, 554
belussi, 1995, Estimating the Selectivity of Spatial Queries Using the ‘Correlation’ Fractal Dimension, Proc VLDB, 299
10.1145/73721.73746
10.1145/304182.304184
10.1109/ICDE.1998.655772
10.1145/290593.290598
10.1145/93597.93611
proietti, 1998, Selectivity Estimation of Window Queries for Line Segment Datasets Proc ACM CIKM, 340
1999, Oracle8i Data Cartridge Developer's Guide, Release 2 (8 1 6)
10.1007/3-540-62222-5_61
10.1109/ICDE.1999.754979