Optimizations
Relational provides a way to perform various optimizations on queries. It assumes that the query is correct.
An optimized query must return the same result of the original query. If you find a non working query please submit a bug report.
General optimizations
This class of optimizations does not need to have informations on the relations.
They will work on the expression tree and will modify it. The return value is the number of changes performed on the tree.
Duplicated select
| Original | Optimized |
|---|---|
| σ k ( σ k(C)) | σ k (C) |
| σ k ( σ j(C)) | σ k ⋀ j (C) |
The first one will work only if the expression is exactly the same. If the expression is equivalent but different (for example 3+2 is equivalent but different to 2+3) the 2nd kind of optimization will be used.
Down to unions subtractions intersections
| Original | Optimized |
|---|---|
| σ k (a ᑌ b) | σ k(a) ᑌ σ k(b) |
| σ k (a ᑎ b) | σ k(a) ᑎ σ k(b) |
| σ k (a - b) | σ k(a) - σ k(b) |
It is an optimization because the selection is a O(n) operation while unions, subtractions or intersections are O(n2) operations. So pushing down the selection, we hope to reduce the size of the problem that the O(n2) operation will have to solve.
Duplicated projection
| Original | Optimized |
|---|---|
| π i ( π j (R)) | π i (R) |
Doing two projection and in fact ignoring the result of the inner one is useless.
Selection inside projection
| Original | Optimized |
|---|---|
| σ j (π k (R)) | π k (σ j (R)) |
Performing the selection first, gives us hope that the projection operation (more complex) will be performed on a smaller set.
Swap rename select
| Original | Optimized |
|---|---|
| σ k(ρ j(R)) | ρ j(σ k(R)) |
Renaming the attributes used in the selection, so the operation is still valid.
This is not really an heavy optimization, select is O(n) and rename is O(1), but it might make other optimizations possible as well, in the next step.
Futile renames
| Original | Optimized |
|---|---|
| ρ k➡k(R) | completely removes them. If some renames in the list are valid and some are not, the valid ones will be kept. |
This optimization is performed before performing subsequent renames optimization.
| Original | Optimized |
|---|---|
| ρ k(R)(ρ j(R)) | ρ j,k(R) |
Using a single rename operation.
If j,k will contain things like a➡b,b➡c, they will be replaced with a➡c.
If j.k will contain things like a➡b,b➡a, they will be removed. If all the transformations are removed, the rename itself is removed.
Futile union intersection subtraction
A ⋈ A=A ⧑ A=A ⧒ A=A⧓A = A ᑌ A=A ᑎ A=A.
So this optimization tries to locate unions, intersections and joins that share the same left and right operand, and replaces
them with the operand itself.
Also A - A=∅.
So it locates subtractions that share the same left and right operand and replaces them with σ False(A). This is not as fast as replacing with an empty relation, but there is no such operator in relational algebra. Anyway Selection is O(n) and subtraction is O(n2), so we are saving time anyway.
This function locates things like:
| Original | Optimized |
|---|---|
| R ᑌ R | R |
| R ᑎ R | R |
| R - R | σ False (R) |
| σ k (R) ᑌ R | R |
| σ k (R) ᑎ R | σ k (R) |
| σ k (R) - R | σ False (R) |
| R - σ k (R) | σ ¬k (R) |
R doesn't have to be a relation. It can be a subtree too.
Swap union renames
| Original | Optimized |
|---|---|
| ρ a➡b(R) ᑌ ρ a➡b(Q) | ρ a➡b(R ᑌ Q) |
| ρ a➡b(R) ᑎ ρ a➡b(Q) | ρ a➡b(R ᑎ Q) |
| ρ a➡b(R) - ρ a➡b(Q) | ρ a➡b(R - Q) |
This will save the space taken by an extra relation needed to perform the 2nd rename.
Swap rename projection
| Original | Optimized |
|---|---|
| π k(ρ j(R)) | ρ j(π k(R)) |
This will let rename work on a hopefully smaller set and more important, will hopefully allow further optimizations.
Union and product
| Original | Optimized |
|---|---|
| A * B ∪ A * C | A * (B ∪ C) |
Select union intersect subtract
| Original | Optimized |
|---|---|
| σi(a) ᑌ σq(a) | σi ∨ q(a) |
This will allow the removal of an O(n2) operation like the union.
Both select must work on the same expression, the selects will be united into one, according to the following table:
| original query | resulting query |
|---|---|
| σi(a) ᑌ σq(a) | σi ∨ q(a) |
| σi(a) ᑎ σq(a) | σi ∧ q(a) |
| σi(a) - σq(a) | σi ∧ ¬q(a) |
Specific optimizations
This class of optimizations requires to have knowledge of the specific relations used (meaning that it will need to have access to real instances of the relations to work).
Projection and union
| Original | Optimized |
|---|---|
| π a,b,c(A) ∪ π a,b,c(B) | π a,b,c(A ∪ B) |
If A and B are union compatible.
Selection and product
| Original | Optimized |
|---|---|
| σ k (R*Q) | σ l (σ j (R) * σ i (Q)) |
Where j contains only attributes belonging to R, i contains attributes belonging to Q and l contains attributes belonging to both.
Useless projection
If a projection is done on all the attributes, it can be removed.