Database learning notes (Chapter 15)

Chapter 15 Query processing

1. The basic steps of query processing
Grammar analysis and Translation （ Syntax check 、 Semantic check ）+ Optimize + perform

① Analysis and Translation
parsers Check grammar , Verify the relationship
Translate the query statement into The internal representation of the system , That is translated into Relational algebra
② perform
Query execution engine Receive a query execution plan , Execute the plan and return the results to the query

2. An important step in query processing : Optimize
A relational algebraic expression may have many equivalent expressions
Each relational algebra operation can be performed with a variety of different algorithms , Accordingly , A relational algebraic expression can be evaluated in many ways

Used to execute a query Primitive operation sequence be called Query execution plan

Query optimization ： Select the plan with the minimum query execution cost among all the equivalent execution plans

3. Measurement of query cost
The cost of query processing can be used to measure the usage of various resources , These resources include disk access , Used to execute a query CPU Time , Even the cost of network communication

stay disk The cost of accessing data on is usually the main cost . It is measured by the following indicators ：
Only Number of disk blocks transferred as well as Number of disk searches To measure the cost of querying the calculation plan

Ignore CPU Time , Practical application CPU Time should be taken into account
Cost estimation Do not include The cost of writing the final result of the operation back to disk

4. Select operation —— File scanning （ I don't understand ）

4.1 Algorithm A1 ( Linear search )

4.2 An index scan – Search algorithm using index
The selection criteria must be the search code of the index

5. Nested loop connection

Block nested loop connection

It is a variant of nested loop join , Each piece of the inner relationship corresponds to each piece of the outer relationship , Forming block pairs , In each block pair , Each tuple of one block is paired with each tuple of another block , So we can get all the group pairs
It is applicable to the case that the memory cannot fully accommodate any relationship , If we deal with relationships in blocks rather than tuples , You can reduce the number of block reads and writes .

6. Index loop nested join

7. Merge and connect

Sort all relationships on the connection properties ( If it wasn't orderly before )

To connect them , Merge ordered relations ：

The join step is similar to the merge phase in the merge sort algorithm
The main difference is to deal with duplicate values on connection properties — Tuples of each pair of connection attributes with the same value must be matched

8. Hash connection

9. Expression evaluation

Physicochemical : Enter a relationship or completed calculation , Produce the result of an expression , Materialize it on disk , Repeat the process
Assembly line : Part of the result of an ongoing operation is transferred to the next operation of the pipeline , So that the two operations can be carried out at the same time

9.1 Physicochemical
Physicochemical calculation : from At the bottom Start , Perform operations in the tree , Create... For each intermediate result of the operation ( Physicochemical , Create a temporary relationship ), Then it is used for the upper level operation

9.2 Assembly line

I think this chapter is too difficult , I don't quite understand
END