Algebraic Optimization

Data System Architecture

About

Same as: SQL Engine - Query Optimizer (Query Optimization)

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

Filter

Filter early

Filter Early is an algebraic optimization:

Filter Early Algebraic Optimization

Predicate push Down

Predicate push Down is the same that filter early.

It is valid to push a filter into an input of an inner join if the filter does not reference columns from the other input.

Others

  • Column pruning

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;

Documentation / Reference





Discover More
Card Puncher Data Processing
Calcite - Optimizer (RelOptCluster)

The optimizer is a program that takes a relational expression (query plan) and rewrites it with optimization rules. The output is still a relational expression and is generally called the physical plan....
Data System Architecture
Data Partition - Partition Pruning (Elimination)

Partition Pruning is access paths methods that occurs when a table is partitioned by the column in the predicate. In this case, the database will read only the partitions involved and not the full table....
Relational Algebra Between Sql And Query Plan
Relational Algebra - Expression and Operators

Relational algebra is based upon the fact that you can pass tabular data through a set of data operators (select, filter, join, sort, union, etc.) in a algebraic structure. It means that: the output...
Query Optimizer Process
SQL Engine - Query Optimizer (Query Optimization)

in a SQL Engine. A SQL statement can be executed in many different ways, such as: full table scans, index scans, nested loops, hash joins. The query optimizer determines the most efficient...



Share this page:
Follow us:
Task Runner