Patent ID: 6421664
Filing Date: 2002-07-16
Classification: G06F,Y10S

Abstract:
A computer-implemented method of performing database operations utilizing an estimation of the number of keys within a key range over an index wherein the index includes page pointers to pages in the index, the method comprising(a) defining a left endpoint and a right endpoint of the key range and finding the point in the index at which the paths to the left and right endpoints diverge; (b) starting at the divergence point, scanning the index until a page pointer is found; (c) incrementing a counter for each page pointer that is found; (d) determining if the page pointer points to a leaf page or a non-leaf page in the index; (e) if the page pointer points to a leaf page in the index, continuing scanning to find the next page pointer without going to the corresponding leaf page, otherwise continuing scanning to find the next page pointer; (f) repeating steps (c), (d) and (e) above until the index is scanned for the entire key range; (g) after scanning is complete, determining an estimate of the number of keys utilizing the counter and performing a database operation using the estimate.