PERFORMANCE-RELATED ESTIMATION USING PSEUDO-RANKED TREES

A method and system for estimating a cost of using a tree index to process a query that includes at least one interval restriction is provided. The cost of using an index to process a select query is estimated by (1) classifying intervals covered by the index as either true, false, or mixed intervals, based on the selection criteria, (2) estimating the cost of using the index based on the size of the true and mixed intervals, and (3) improving the cost estimate based on the average ratio of the parent and child node cardinalities taken down one or more sampling paths of the index. Use of a pseudo-ranked B-tree is generally preferred over a fully ranked tree due to the relatively low update costs of a pseudo-ranked B-tree. The index cost estimations are used to pick a select query execution plan that has the smallest cost, in terms of disk I/O operations, from numerous possible execution plans.