Adaptive access path selection for relational database systems

Query optimization is crucial to relational database performance. Traditional approaches select the access plan with the minimum projected cost based on estimated selectivity. Since estimates can deviate substantial from true values, the access plan chosen can be far from optimal. We propose an adaptive approach which utilizes the information embedded in indexes to identify the tuples satisfying a select predicate or having a match in a join operation. Then, access path (index or table scan) and join method (index join, nested loop, sort-merge) are chosen to construct the results progressively. This leads to the optimal evaluation of queries and substantial performance improvement. With an efficient implementation, the decision process becomes a part of query evaluation procedure and imposes a minimal overhead.