18.1. General request processing

18.1. General request processing

It can be imagined that the processing of a request received by the system consists of the phases shown below.

In the first phase, the query specified in the query language is subjected to lexical and syntactic analysis. At the same time, its internal representation is generated, reflecting the structure of the query and containing information that characterizes the database objects mentioned in the query (relations, fields and constants). Information about objects stored in the database is selected from the database directories. The internal representation of the request is used and converted in the next stages of processing the request. The form of the internal representation should be sufficiently convenient for subsequent optimization transformations.

In the second phase, the query in the internal representation is subjected to logical optimization. Various transformations may be applied that "improve" the initial presentation of the query. Transformations may be equivalent, after which an internal representation is obtained that is semantically equivalent to the initial one (for example, casting a query to a certain canonical form). Transformations may be semantic: the resulting representation is not semantically equivalent to the initial one, but it is guaranteed that the result of the converted query matches with the result of the query in the initial form, subject to the integrity constraints that exist in the database. After the second phase of processing the request, its internal representation remains nonprocedural, although it is in some sense more effective than the initial one.

The third stage of query processing is to select, based on the information that the optimizer has, a set of alternative procedural plans for the execution of this query in accordance with its internal representation obtained in the second phase. For each plan, the estimated cost of the request is estimated. The estimates use statistical information about the state of the database, which is available to the optimizer. From the obtained alternative plans, the cheapest one is chosen, and its internal representation now corresponds to the request being processed.

At the fourth stage, according to the internal representation of the most optimal plan for the execution of the request, an executable representation of the plan is formed. The executed presentation of the plan can be a program in machine codes, if, as in the case of System R, the system is focused on compiling queries into machine codes, or to be machine-independent, but more convenient for interpretation, if, as in the case of INGRES, the system is oriented on interpretation requests. In our case, this is unprincipled, since the fourth phase of processing the request is no longer associated with optimization.

Finally, at the fifth stage of processing the request, its actual execution takes place. This is either the execution of the corresponding subroutine, or the call of the interpreter with the transfer to it to interpret the executed plan.