The physical model includes the kind of indices (access paths) that are potentially available for each relation. This corresponds to the types of indices available from the DBMS. Since Model D is not modeling an actual commercial DBMS, the choice of access methods was somewhat arbitrary -- defined to some extent to test the extensibility of the framework. The catalog (discussed in section 6.5) will include a mechanism to describe the actual indices defined for a particular database.
Model D index types include B-tree indices, hash indices and bit-indices. Stored relations are modeled as being clustered on either a B-tree or hash index. B-tree indices are used for range predicates. (with the physical operator, INDEXED-FILTER). A clustered hash or B-tree index on join condition attributes could support the LOOPS_INDEX_JOIN physical operator. The hash, B-tree and clustering aspects of this model are standard approaches and will not be described further.
Bit-indices [Graefe 94] are less standard. Model D has two types of bit indices, bit attribute indices and bit predicate indices. Both could be used to implement the SELECT logical operator. In Model D, however, they are used, only in conjunction with a join, by the BIT_SEMIJOIN physical operator.
Both types of bit-index depend on a dense indexing attribute which is a candidate key of the relation. 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. The length (number of bits) of each bit vector is the maximum value of the indexing attribute.
| 6.2 Physical Model: |
<Access Methods>
<Physical Operators>
<Cost Model>
6.1: Bit Vector 6.2: Operators |
|---|
| 
Page 2
|