Model D has two types of bit indices, bit attribute indices and bit predicate indices. A dense attribute is one where all of the values are packed within a range with few absent values. For simplicity, it is further assumed that the minimum value of the attribute is zero. For example, an index would be considered dense if the minimum key value was 0, the maximum was 10000 and 9000 unique keys were contained in the relation. An example of a dense attribute would be a serial column.
Bit vectors store a single bit for every tuple in the relation.
For bit attribute indices there is a particular attribute called the value attribute. For each value v of the value attribute, a bit vector is stored. The nth bit of this bit vector is one if the tuple with key value n has the value v for the value attribute. Boolean expressions on attributes which have these bit vectors translate easily to boolean expressions on the bit vectors. For bit predicate indices a bit vector exists for every predicate in a list of predicates.