US Patent 8935233 Approximate index in relational databases

A database table is provided. The database table includes several column tuples. A column is selected in the database table. The column tuples of the selected column are partitioned into several bins. Each bin includes a range of tuples and associated metadata. The associated metadata includes at least one of: 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. The bins are sorted based on the tuple values to provide an approximate index for the database.