Algebraic Optimization

1 - About

3 - Example

<MATH> N = ((Z*2)+((Z*3)+0))/1 </MATH>

Algebraic Laws:

  1. (+) identity: x+0 = x
  2. (/) identity: x/1 = x
  3. (*) distributes: (n*x+n*y) = n*(x+y)
  4. (*) commutes: x*y = y*x

Apply rules 1,3,4,2 and we get <MATH> N = (2+3)*z </MATH>

Two operations instead of five, no division operator

Same idea works with the Relational Algebra

4 - Filter Early

Filter Early is an algebraic optimization:

5 - Others

  • Predicate push Down
  • Column pruning

6 - No Sort

Example from CALCITE-873

Given the following table:

CREATE TABLE T (
  K1 VARCHAR,
  K2 VARCHAR,
  K3 VARCHAR,
  CONSTRAINT pk PRIMARY KEY (K1, K2, K3));

In the following queries, no sort is necessary:

SELECT * FROM T WHERE K1='A' ORDER BY K2,K3;
SELECT * FROM T WHERE K2='B' ORDER BY K1,K3;
SELECT * FROM T WHERE K1='A' AND K2='B' ORDER BY K3;

7 - Documentation / Reference

data/type/relation/algebraic_optimization.txt ยท Last modified: 2018/05/30 11:49 by gerardnico