Motivation

SQL query may scan arbitrary set of cache values. In general case interested values may reside on every cluster node, so broadcast is needed. What is worse, when distributed joins are enabled, another broadcast for every broadcasted message may be needed. One of the most important optimization techniques is so-called "partition pruning", allowing to calculate a set of partitions and nodes which will return empty result without actual query execution. Query parts are not executed on these nodes, increasing overall system throughput and providing nearly linear scaling. 

Recent researches in distributed query processing assume that CPU is relatively cheap resource, while network IO and disk IO are equally costly operations. Partition pruning not only saves network requests, but also avoids unnecessary executionы of local query parts, preventing page cache trashing and additional disk reads (mostly random). 

Thus, partition pruning is a critical optimization technique for both distributed and local queries and should be treated as high priority task for Ignite SQL engine.

Partition pruning is already implemented in Apache Ignite in very simplified form [1]. Only WHERE condition with equality is considered and only for SQL queries without joins. We should expand it further.

[1] https://issues.apache.org/jira/browse/IGNITE-4509

Theory

This technique is used excessively by both distributed databases and classical RDBMS vendors (as a part of their partitioning/sharding solutions). First, query is analyzed and optionally re-written to allow for better partition pruning. Second, information of interesting partitions are extracted from query for every table (cache) and subquery (for complex multi-stage distributed queries). 

Query Rewrite

WHERE conditions and JOIN-s are relatively simple targets for extract partition extraction. The main difficulty is subqueries, as they potentially introduce unlimited nesting what complicates analysis a lot. So the main goal of query rewrite is to minimize number of subqueries. Main techniques are JOIN conversion, correlation and materialization. Interestingly, all these techniques not only simplify partition extraction, but also allow optimizer to choose better execution plan for local execution, as JOINs are much easier to be analyzed and reordered than subqueries. As we shall see below, efforts are usually focused on non-correlated subqueries as they are the most costly for straightforward execution.

JOIN conversion

The goal is to convert a subquery to join if possible. Important prerequisite is that number of resulting rows is not changed. Outer(FK) → inner(PK) joins are possible. E.g. subqueries in SELECT (aka "derived table") and FROM clauses.

Example 1: JOIN conversion for derived table

SELECT emp.name, (SELECT dept.name FROM dept WHERE emp.dept_id=dept.id)
FROM emp
WHERE emp.salary>1000

SELECT emp.name, dept.name
FROM emp, dept
WHERE emp.salary>1000 AND emp.dept_id=dept.id

Example 2: JOIN conversion for FROM clause

SELECT emp.name, dept_subquery.name
FROM emp, (SELECT * FROM dept WHERE state='CA') dept_subquery
WHERE emp.salary>1000 AND emp.dept_id=dept_subquery.id

SELECT emp.name, dept.name
FROM emp, dept
WHERE emp.salary>1000 AND emp.dept_id=dept.id AND dept.state='CA'

Also, it is possible for some IN-clauses. MariaDB calls it "table pullout optimization" [1]

Example 3: Table pullout optimization

SELECT emp.name
FROM emp
WHERE emp.salary>1000 AND emp.dept_id IN (SELECT id FROM dept WHERE state='CA')

SELECT emp.name
FROM emp, dept
WHERE emp.salary>1000 AND emp.dept_id=dept.id AND dept.state='CA'

Another example where inner subquery return at most one row is outer(PK) → inner(FK GROUP BY PK) case. Subquery is not eliminated in this case, but IN expression is replaced with more comfortable JOIN.

Example 4: Replacing IN with JOIN

SELECT dept.name
FROM dept
WHERE dept.id IN (SELECT emp.dept_id FROM emp GROUP BY emp.dept_id HAVING COUNT(*) > 10)

SELECT dept.name
FROM dept JOIN (SELECT emp.dept_id FROM emp GROUP BY emp.dept_id HAVING COUNT(*) > 10) emp_subquery ON dept.id=emp_subquery.dept_id

[1] https://mariadb.com/kb/en/library/table-pullout-optimization/

Correlation

TODO

Materialization

TODO

Partition Extraction

TOOD

Proposed Changes

TODO

Tickets