| 摘要 |
A database system comprises a database storing a number of records of different types. The system handles database queries, involving joins between a number of different record types. Each query is first preprocessed to identify optimal starting points for accessing the records. The system then generates a data structure comprising a number of nodes, each node representing one of the record types in the query and indicating an access method for that record type. The nodes are organized into a number of chains, each having a head node representing one of the optimal starting points, and each successive node in each chain representing a record type that can be accessed from the record type represented by a preceding node in the chain by an index mechanism, a hashed access mechanism or an ownership mechanism. A virtual row of the join is constructed by accessing each of the nodes and reading a corresponding record using the specified access method. Further virtual rows are constructed by tracing a backward path through the nodes, starting from the last node in the last chain until a node is encountered for which at least one further record is available for reading from the database. Then, a forward path is traced, starting from this node, reading from the database one record of each record type represented by each node in the forward path, using the access method indicated by each node, until the last node in the last chain is reached.
|
