1. A computer-implemented method for creating an approximate index for a database, the method comprising: providing a database table, the database table including a plurality of column tuples; selecting a column in the database table; partitioning the column tuples of the selected column into a plurality of bins, wherein each bin includes a range of tuples and associated metadata, the associated metadata including: a minimum tuple value for the tuples in the bin, a maximum tuple value for the tuples in the bin, a minimum tuple identifier for the bin and a maximum tuple identifier for the bin; and sorting the bins based on tuple values to generate an approximate index for the database, the approximate index providing a query optimizer for the database with information regarding what subset of tables need to be scanned, to allow accurate cost estimation and query planning by the query optimizer.