Royal treasure: an analysis of SQL algebra optimization

1. Algebraic optimization

Algebraic optimization is the equivalent exchange of queries , To reduce execution overhead . The so-called equivalence means that the result of the transformed relational algebra expression is the same as that of the transformed relational algebra expression .

（1） The equivalent change rule

Transform a relational algebraic expression into another equivalent expression that can be executed more efficiently .

Try to select and project first , Then do the connection operation .

When the connection is , First, make connections between small relationships , And then make the connection of big relationship .

1） Multiple choice （σ）

2） choice （σ） Commutative law of

3） Multiple projection （∏）

4） choice （σ） And projection （∏） In exchange for

5） Connection and Cartesian product （x） Commutative law of

6） and （∪） Make friends with others （∩） Commutative law of operations

R ∪ S = S ∪ R

R ∩ S = S ∩ R

7） choice （σ） And connected commutative law

8） Projection （∏） And the distributive law of connection

9） Select merge with set 、 hand over 、 Distributive law of difference operation

10） Projection （∏） Distributive law of union operation

11） Connection and Cartesian product

12） and （∪） Make friends with others （∩） The law of association of

（2） Heuristic rules

1） The selection operation should be done first as far as possible ;

2） Preprocess the relationship appropriately before executing the connection ;

3） Projection operation and selection operation are performed simultaneously ;

4） The binocular operation before or after a projection （ and 、 hand over 、 Bad ） Combine ;

5） Transform some selection operations and Cartesian products performed before them into join operations ;

6） Do the projection operation in advance （ But keep the properties used for the connection ）;

7） Find the common subexpression .

give an example ： Check the elective course 2 The name of the student in course No

1   2 select Sname from Student join SC on Student.Sno=SC.Sno 3 where SC.Cno='2';

The process of optimization ：

（1） Convert to an initial relational algebraic expression （ Not optimized ）：

（2） Optimize with transformation rules

① Use rules 1 Decompose the connection operation part of the selection operation into each selection operation , Make the selection operation as early as possible

② Replace Cartesian product operation with equivalent connection operation

③ Use rules 4 And rules 6 Yes Student Do the projection operation

2. Physical optimization

（1） Select the optimization of the operation

1） For small relationships , There is no need to consider other access paths , Direct sequential scanning ;

2） If no access paths such as indexes or hashes are available , Or it is estimated that the number of tuples selected accounts for a large proportion in the relationship （ For example, greater than 15%）, And there is no clustered index for related attributes , Then reference sequence scanning ;

3） For non primary key equivalent condition query , To estimate the proportion of the number of tuples selected in the relationship . If the proportion is small （ For example, the proportion is less than 15%）, Available nonclustered indexes , Otherwise, only clustered indexes or sequential scans can be used ;

4） For range condition queries , Generally, the boundary of the range is found through the index , Then, the ordered set of the index is collected along the corresponding direction ;

5） For using and Join selection condition of connection , If there is a corresponding multi-attribute index , Multi attribute index should be adopted first ;

6） For using or Disjunctive selection condition of connection , There is no good optimization method , Only one tuple set can be selected according to each condition , Then we calculate the union of these tuples ;

7） Some selection operations can get results just by accessing the index .

（2） Optimization of connection operation

1） If both relationships are sorted by connection properties , Then the sorting and merging method is preferred ;

2） If one of the two relationships has an index in the connection attribute （ Especially clustered indexes ） Or hash , Another relationship can be treated as an external relationship , Sequential scanning , And use the index or hash on the inner relation to find the matching tuple , Instead of polytropic scanning ;

3） If the conditions for applying the above two rules are not met , And both relationships are relatively small , Then the nested loop method can be applied ;

4） If the rules 1、2、3 None of them apply , You can use hash join method .

（3） Optimization of projection operation

Projection operation is generally related to selection 、 Connection and other operations are carried out at the same time , No attachment required I/O expenses . If the projected attribute set does not contain a primary key , Then duplicate tuples may appear in the projection result . Eliminating duplicate tuples is a time-consuming operation , Generally, you need to sort the projection results by all their attributes , Keep repeating tuples in continuous storage , To find duplicate tuples . Hashing is also a feasible way to eliminate duplicate tuples .