Repository: calcite Updated Branches: refs/heads/master d61930407 -> 991784971
[CALCITE-1796] Update materialized views documentation Project: http://git-wip-us.apache.org/repos/asf/calcite/repo Commit: http://git-wip-us.apache.org/repos/asf/calcite/commit/e71157bb Tree: http://git-wip-us.apache.org/repos/asf/calcite/tree/e71157bb Diff: http://git-wip-us.apache.org/repos/asf/calcite/diff/e71157bb Branch: refs/heads/master Commit: e71157bba1ea4eae135d1ddddebe576e72625b3d Parents: d619304 Author: Jesus Camacho Rodriguez <[email protected]> Authored: Mon May 22 14:15:31 2017 +0100 Committer: Jesus Camacho Rodriguez <[email protected]> Committed: Mon May 22 15:16:02 2017 +0100 ---------------------------------------------------------------------- site/_docs/materialized_views.md | 273 ++++++++++++++++++++++++++++++---- 1 file changed, 246 insertions(+), 27 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/calcite/blob/e71157bb/site/_docs/materialized_views.md ---------------------------------------------------------------------- diff --git a/site/_docs/materialized_views.md b/site/_docs/materialized_views.md index b12c057..553bc3d 100644 --- a/site/_docs/materialized_views.md +++ b/site/_docs/materialized_views.md @@ -31,48 +31,267 @@ There are several different ways to exploit materialized views in Calcite. For details, see the [lattices documentation]({{ site.baseurl }}/docs/lattice.html). -## Expose materialized views from adapters +## Expose materialized views to Calcite + +Some Calcite adapters as well as projects that rely on Calcite have their own notion of materialized views. -Some adapters and projects that rely on Calcite have their own notion of materialized views. For example, Apache Cassandra allows the user to define materialized views based on existing tables which are automatically maintained. The Cassandra adapter automatically exposes these materialized views to Calcite. -Another example is Apache Hive, whose integration with Calcite materialized views is ongoing. -By understanding some tables as materialized views, Calcite has the opportunity to automatically rewrite queries to use these views. -## View-based query rewriting +Another example is Apache Hive. When a materialized view is created in Hive, the user can specify whether the view may be used in query optimization. If the user chooses to do so, the materialized view will be registered with Calcite. + +By registering materialized views in Calcite, the optimizer has the opportunity to automatically rewrite queries to use these views. + +### View-based query rewriting View-based query rewriting aims to take an input query which can be answered using a preexisting view and rewrite the query to make use of the view. -Calcite employs two forms of view-based query rewriting. -The first is based on view substitution before the planning phase based on an extension of a {SubstitutionVisitor}. -{MaterializedViewSubstitutionVisitor} aims to substitute part of the relational algebra tree with an equivalent expression which makes use of a materialized view. +Currently Calcite has two implementations of view-based query rewriting. + +#### Substitution via rules transformation -The following example is taken from the documentation of {SubstitutionVisitor}: +The first approach is based on view substitution. +`SubstitutionVisitor` and its extension `MaterializedViewSubstitutionVisitor` aim to substitute part of the relational algebra tree with an equivalent expression which makes use of a materialized view. The scan over the materialized view and the materialized view definition plan are registered with the planner. Afterwards, transformation rules that try to unify expressions in the plan are triggered. Expressions do not need to be equivalent to be replaced: the visitor might add a residual predicate on top of the expression if needed. + +The following example is taken from the documentation of `SubstitutionVisitor`: * Query: `SELECT a, c FROM t WHERE x = 5 AND b = 4` * Target (materialized view definition): `SELECT a, b, c FROM t WHERE x = 5` - * Replacement: `SELECT * FROM mv` * Result: `SELECT a, c FROM mv WHERE b = 4` -Note that {result} uses the materialized view table {mv} and a simplified condition {b = 4}. -This can accomplish a large number of rewritings. -However, this approach is not scalable in the presence of complex -views, e.g., views containing many join operators, since it relies on -the planner rules to create the equivalence between expressions. +Note that `result` uses the materialized view table `mv` and a simplified condition `b = 4`. + +While this approach can accomplish a large number of rewritings, it has some limitations. Since the rule relies on transformation rules to create the equivalence between expressions in the query and the materialized view, it might need to enumerate exhaustively all possible equivalent rewritings for a given expression to find a materialized view substitution. However, this is not scalable in the presence of complex +views, e.g., views with an arbitrary number of join operators. -In turn, an alternative rule that attempts to match queries to views -defined using arbitrary queries has been proposed. +#### Rewriting using plan structural information -{AbstractMaterializedViewRule} builds on the ideas presented [here](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.113). +In turn, an alternative rule that attempts to match queries to views by extracting some structural information about the expression to replace has been proposed. + +`AbstractMaterializedViewRule` builds on the ideas presented in [<a href="#ref-gl01">GL01</a>] and introduces some additional extensions. The rule can rewrite expressions containing arbitrary chains of Join, Filter, and Project operators. -Additionally, the rule can rewrite expressions rooted at an Aggregate operator, rolling aggregations up if necessary. +Additionally, the rule can rewrite expressions rooted at an Aggregate operator, rolling aggregations up if necessary. In turn, it can also produce rewritings using Union operators if the query can be partially answered from a view. + +To produce a larger number of rewritings, the rule relies on information exposed as constraints defined over the database tables, e.g., *foreign keys*, *primary keys*, *unique keys* or *not null*. + +##### Rewriting coverage + +Let us illustrate with some examples the coverage of the view rewriting algorithm implemented in `AbstractMaterializedViewRule`. The examples are based on the following database schema. + +```SQL +CREATE TABLE `depts`( + deptno INT NOT NULL, + deptname VARCHAR(20), + PRIMARY KEY (deptno) +); +CREATE TABLE `locations`( + locationid INT NOT NULL, + state CHAR(2), + PRIMARY KEY (locationid) +); +CREATE TABLE `emps`( + empid INT NOT NULL, + deptno INT NOT NULL, + locationid INT NOT NULL, + empname VARCHAR(20) NOT NULL, + salary DECIMAL (18, 2), + PRIMARY KEY (empid), + FOREIGN KEY (deptno) REFERENCES depts(deptno), + FOREIGN KEY (locationid) REFERENCES locations(locationid) +); +``` + +###### Join rewriting + +The rewriting can handle different join orders in the query and the view definition. In addition, the rule tries to detect when a compensation predicate could be used to produce a rewriting using a view. + +* Query: + +```SQL +SELECT empid +FROM depts +JOIN ( + SELECT empid, deptno + FROM emps + WHERE empid = 1) subq +ON (depts.deptno = subq.deptno) +``` + +* Materialized view definition: + +```SQL +SELECT empid +FROM emps +JOIN depts USING (deptno) +``` + +* Rewriting: + +```SQL +SELECT empid +FROM mv +WHERE empid = 1 +``` + + +###### Aggregate rewriting + +* Query: + +```SQL +SELECT deptno +FROM emps +WHERE deptno > 10 +GROUP BY deptno +``` + +* Materialized view definition: + +```SQL +SELECT empid, deptno +FROM emps +WHERE deptno > 5 +GROUP BY empid, deptno +``` + +* Rewriting: + +```SQL +SELECT deptno +FROM mv +WHERE deptno > 10 +GROUP BY deptno +``` + + +###### Aggregate rewriting (with aggregation rollup) + +* Query: + +```SQL +SELECT deptno, COUNT(*) AS c, SUM(empid) AS s +FROM emps +GROUP BY deptno +``` + +* Materialized view definition: + +```SQL +SELECT empid, deptno, COUNT(*) AS c, SUM(empid) AS s +FROM emps +GROUP BY empid, deptno +``` + +* Rewriting: + +```SQL +SELECT deptno, SUM(c), SUM(s) +FROM mv +GROUP BY deptno +``` + + +###### Query partial rewriting + +Through the declared constraints, the rule can detect joins that only append columns without altering the tuples multiplicity and produce correct rewritings. + +* Query: + +```SQL +SELECT deptno +FROM emps +GROUP BY deptno +``` + +* Materialized view definition: + +```SQL +SELECT empid, depts.deptno, COUNT(*) AS c, SUM(empid) AS s +FROM emps +JOIN depts USING (deptno) +GROUP BY empid, depts.deptno +``` + +* Rewriting: + +```SQL +SELECT deptno +FROM mv +GROUP BY deptno +``` + + +###### View partial rewriting + +* Query: + +```SQL +SELECT deptname, state, SUM(salary) AS s +FROM emps +JOIN depts ON (emps.deptno = depts.deptno) +JOIN locations ON (emps.locationid = locations.locationid) +GROUP BY deptname, state +``` + +* Materialized view definition: + +```SQL +SELECT empid, deptno, state, SUM(salary) AS s +FROM emps +JOIN locations ON (emps.locationid = locations.locationid) +GROUP BY empid, deptno, state +``` + +* Rewriting: + +```SQL +SELECT deptname, state, SUM(s) +FROM mv +JOIN depts ON (mv.deptno = depts.deptno) +GROUP BY deptname, state +``` + + +###### Union rewriting + +* Query: + +```SQL +SELECT empid, deptname +FROM emps +JOIN depts ON (emps.deptno = depts.deptno) +WHERE salary > 10000 +``` + +* Materialized view definition: + +```SQL +SELECT empid, deptname +FROM emps +JOIN depts ON (emps.deptno = depts.deptno) +WHERE salary > 12000 +``` + +* Rewriting: + +```SQL +SELECT empid, deptname +FROM mv +UNION ALL +SELECT empid, deptname +FROM emps +JOIN depts ON (emps.deptno = depts.deptno) +WHERE salary > 10000 AND salary <= 12000 +``` + + +##### Limitations -However, this rule still presents some limitations. In particular, the rule presents the following -shortcomings that we plan to address with follow-up extensions: +This rule still presents some limitations. In particular, the rewriting rule attempts to match all views against each query. We plan to implement more refined filtering techniques such as those described in [<a href="#ref-gl01">GL01</a>]. -* Rewriting is unoptimized and will attempt to match all views against each query. -* The query defining the view must use only inner joins. -* It does not produce rewritings using Union operators, e.g., a given query could be partially answered from the -{mv} (year = 2014) and from the query (not(year=2014)). This can be useful if {mv} is stored in a system such as -Druid. +### References -This rule is currently enabled by default. +<ul> +<li>[<a name="ref-gl01">GL01</a>] Jonathan Goldstein and Per-Ã¥ke Larson. + <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.95.113";>Optimizing queries using materialized views: A practical, scalable solution</a>. + In <i>Proc. ACM SIGMOD Conf.</i>, 2001.</li> +</ul> \ No newline at end of file
