Techniques for database table look-up are provided. The techniques include storing one or more column attributes of a database table in a data structure, wherein the data structure also comprises a record identification (RID) column of a table, one or more predicate columns corresponding to the RID column, and a sequence number column that is associated with one or more updated records, generating a key using one or more portions from one or more of the one or more predicate columns, using the key to partition the data structure, wherein partitioning the data structure comprises partitioning the one or more predicate columns for evaluation, and evaluating the one or more predicate columns against the data structure for each matching predicate column-data structure partition.