Databases Reference
In-Depth Information
Figure 1: Index partition and parallel retrieval
Each PE acts as follows. If the PE receives a key value from an upstream neighbor
PE (i.e., right-hand side PE in Fig.1), it searches the corresponding data values
(OID) using the sub-index that it maintains. For each object in the result set
of OIDs thus obtained, the PE sends the OID as a key value to one of the
downstream neighbor PEs that maintains the related sub-index. If the PE maintains
a portion of
V
1
(i.e., ), the set of OIDs searched in the PE is a portion of the
required result OIDs. The PE transfers the results to the
result collecting PE,
which
will be abbreviated as RCPE in the following.
Note that the above retrieval action is performed in parallel on each PE.
Termination Detection
When a retrieval request is issued, the retrieval will be performed in parallel along
the horizontal paths of PEs. Such parallel retrieval in each PE does not require any
synchronization mechanism with other PEs. Therefore, even if the resultant OIDs
are reported from one of the PEs that stores a portion of
V
1
, these OIDs are only
a portion of the final result, and other portions may be reported from other PEs
subsequently. We will now describe the two termination detection schemes for
such parallel index retrieval.
•
Object-level detection
A retrieval
termination detection
scheme is outlined roughly for the simple example
illustrated in Fig. 2. This scheme is simple enough that the basic concept should be
easily understood. First, we describe the construction of the
branch history
attached
to an object.
