For bit attribute indices
there is a particular attribute
called the value attribute.
The number of possible values
(i.e. the number of values in the domain)
for the value attribute
must be small,
and cannot change.
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.
This results in a single bit vector which
can then be used in physical operators
set up to use bit vectors --
in Model D this is just the BIT_SEMIJOIN
physical operator.
Figure 6.1: Bit Vector of Bit Attribute Index
Figure 6.1 shows a bit vector for
the attribute C_Mktsegment (CM) of the relation CUSTOMER
for the value "Building".
For bit predicate indices
a bit vector
exists for every predicate
in a list of predicates.
Bit predicate
bit vectors
are the same length as bit attribute bit vectors.
Predicates are arbitrary
sargable predicates.
The nth bit
of the predicate's bit vector
is one,
if for the tuple
with key value n ,
the predicate evaluates to TRUE.
Page 3