The optimize module provides a way to perform various optimizations on queries. It assumes that the query is correct.

:!: Warning: It is not 100% granted that the optimized query will work. If you find a non working query please submit a bug.


Performing general optimizations

This code will perform all the available general optimizations on the expression, and will return the optimized expression.


Advanced usage

Working with the tree

The expression tree allows to manipulate the expressions.

To obtain the expression just call this:


To generate the tree, just call: (expression is a valid string representing a relational expression)


Each node will have a name, that corresponds to its string representation. Also a kind variable, that specifies if the node is a relation or an operator.

Constants for kind.


Unary operator

  • name: string representation
  • child: child expression
  • props: parameters of the operation

Binary operator

  • name: string representation
  • left: left expression
  • right: right expression


  • name: string representation

General optimizations

This class of optimizations do not need to have informations on the relations.

The functions are implemented in the module.

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

Yes the name is crazy.

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 isn't nice.

Selection inside projection

Original Optimized
σ jk (R)) π kj (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
σ kj(R)) ρ jk(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 is an improvement and 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.

Subsequent renames

Original Optimized
ρ k(R)(ρ j(R)) ρ j,k(R)

hence 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.
So this optimization tries to locate unions and intersections 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(n²), so we're 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
π kj(R)) ρ jk(R))

This will let rename work on a hopefully smaller set and more important, will hopefully allow further optimizations.
Will also eliminate fields in the rename that are cutted in the projection. So the memory needed to perform the task will be reduced.

Select union intersect subtract

Original Optimized
σi(a) ᑌ σq(a) σi ∨ q(a)

This will allow the removal of an O(n²) 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).

Selection and product

Original Optimized
σ k (R*Q) σ lj (R) * σ i (Q))

Where j contains only attributes belonging to R, i contains attributes belonging to Q and l contains attributes belonging to both.

optimizer.txt · Last modified: 2012/05/09 14:48 by LtWorf
Except where otherwise noted, content on this wiki is licensed under the following license: GNU Free Documentation License 1.2
Recent changes RSS feed Valid XHTML 1.0 Valid CSS Driven by DokuWiki