1. 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 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 the database, generates at least one matrix from the information in the block sampling, and processes the at least one matrix to determine clustering factor for a specified range in the database; wherein the database manager estimates performance of a query to the database based on the clustering factor.