Database learning notes (Chapter 16)

Chapter 16 ： Query optimization

1. Overview of query optimization
Query optimization is from a number of possible strategies , A process for finding the most efficient query execution plan .

On the one hand, optimization can occur at the relational algebra level
The other is to select a detailed strategy for processing queries , For example, executing algorithms 、 Select index, etc

Select an execution method for a given query

Equivalent expressions
Each operation has a different algorithm

Example ： Inquire about music The name of the faculty member and the course name of the professor

The expression tree on the left will produce a large intermediate relationship ,instructor ⋈ (teaches ⋈ (course), But we are only right music college Teachers interested in , therefore , After optimization, the expression tree becomes the one on the right .

An execution plan defines exactly what should be used for each operation Algorithm , And the execution between operations should How to coordinate .
Given a relational algebraic expression , The task of the query optimizer is to generate a Query execution plan , The plan can get the same result as the original relational expression , And get the result set The cost of execution is minimal .

Cost based optimization step

Use equivalence rules to generate logically equivalent expressions
Annotate the result expression to get an alternative query plan
Choose the plan with the least cost based on cost estimation

2. Transformation of relational expression

• If two relational algebraic expressions are generated in all valid database instances Same tuple set , They are equivalent
  Be careful : The order of tuples is irrelevant
• stay SQL In language , Both input and output are tuples Multiple sets
  If for all valid databases , Two expressions produce the same tuple multiset , It is said that the two relational algebraic expressions of the multiple set version are equivalent
• The equivalence rule states that two different forms of expressions are equivalent
  You can replace the first with the second form of expression , vice versa

3. Equivalence rules （ important ）

A few examples ：

For relationships r1 , r2 and r3
(r1 ⋈r2) ⋈r3 = r1 ⋈(r2 ⋈r3 )
( Associative law of connection )
If r2 ⋈ r3 It's bigger , r1 ⋈ r2 It's small , choice
(r1 ⋈r2) ⋈r3
This makes it possible to compute and store a small temporary relationship

3. Cost estimate

• The cost of an operation depends on the size of its input and other statistics
• Let's start by listing some statistics about database relationships stored in the database directory , Then it points out how to use these statistics to estimate the statistics of the results of different relational operations

4. An estimate of the statistical size of the expression result set

• Statistics about indexes , such as B+ The height of the tree and the number of pages of nodes in the index , Also saved in the directory .
• Every time you modify data in the database , Statistics must also be updated .

5. Histogram

A histogram takes up very little space , Therefore, histograms on different attributes can be stored in the system directory
Constant width histogram ： Divide the value range into equal size intervals
Contour histogram ： Adjust interval decomposition , So that the number of values falling into each interval is equal

6. Select an estimate of the size of the operation result

END