Apparatus and method for determining clustering factor in a database using block level sampling

An apparatus comprising:

• at least one processor;
• a memory coupled to the at least one processor;
• a database residing in the memory, the database including a plurality of indexes that each have at least one key and a reference to at least one corresponding record in the database that satisfies the key, the database further including a database manager that manages queries to the database;
• a clustering factor computation mechanism residing in the memory and executed by the at least one processor, wherein the clustering factor computation mechanism performs block sampling of a plurality of random physical data pages from a selected index in the database, generates an ordered list of keys from the block sampling with pages corresponding to the keys, generates a two-dimensional bitmap from the ordered list, processes the two-dimensional bitmap to generate at least one matrix, reduces the size of the at least one matrix using at least one digital image compression technique, and processes the reduced matrix to determine clustering factor for a specified range of the selected index, the clustering factor computation mechanism determining the clustering factor for a first range in a first index for the database and determining the clustering factor for a second range in a second index for the database;
• wherein the database manager determines relative efficiencies of the first index compared to the second index by comparing the clustering factor of the first index with the clustering factor of the second index, the database manager selecting one of the first and second indexes for a query of the database based on relative efficiencies indicated by the respective clustering factors.

A method for determining clustering factor for a specified range in a database, the method comprising the steps of:

• (A) block sampling a plurality of random physical data pages from the specified range;
• (B) generating at least one matrix from the information in the block sampling;
• and
• (C) processing the at least one matrix to determine clustering factor for the specified range of the database.

A method for determining clustering factor distribution for a plurality of ranges in a database, the method comprising the steps of:

• (A) block sampling a plurality of random physical data pages from the database;
• (B) generating an ordered list of keys from the block sampling with pages corresponding to the keys;
• (C) generating a two-dimensional bitmap from the order list;
• (D) processing the two-dimensional bitmap to generate at least one matrix;
• (E) reducing the size of the at least one matrix using at least one digital image compression technique;
• (F) processing the at least one matrix to determine clustering factor for a specified range in the database;
• and
• (G) repeating steps (A) through (F) to determine clustering factor for each of the plurality of ranges in the database.

A program product comprising:

• (A) a database comprising:
• (A1) a clustering factor computation mechanism that performs block sampling of a plurality of random physical data pages from a selected index in a database, generates an ordered list of keys from the block sampling with pages corresponding to the keys, generates a two-dimensional bitmap from the ordered list, processes the two-dimensional bitmap to generate at least one matrix, reduces the size of the at least one matrix using at least one digital image compression technique, and processes the reduced matrix to determine clustering factor for a specified range of the selected index, the clustering factor computation mechanism determining the clustering factor for a first range in a first index for the database and determining the clustering factor for a second range in a second index for the database;
• (A2) a database manager that determines relative efficiencies of the first index compared to the second index by comparing the clustering factor of the first index with the clustering factor of the second index, the database manager selecting one of the first and second indexes for a query of the database based on the relative efficiencies indicated by the respective clustering factors;
• and
• (B) computer-readable signal bearing media bearing the database.