Here’s how relational algebra fit together (at least in my mind). Relational algebra is the intermediate language for database queries. It has similar expressive power to, say, SQL, but for various reasons it is easier to manipulate expressions in relational algebra than SQL.
Query optimization is one of the main reasons you want to manipulate relational expressions. You transform the expression into another expression that is equivalent (i.e. gives the same result for all possible inputs) and has minimal cost. Manipulations include logical optimizations (e.g. pushing a filter through a project), physical optimizations (choosing to use merge join because the inputs are already sorted) and substitutions of materialized queries. The last kind is especially important for OLAP. A lot of OLAP queries are aggregations of joins, and these results can be pre-computed in summary tables. Rewriting a query to use a summary table rather than the original table(s) is a really powerful optimization technique, because you can answer a query that might read billions of rows by reading a few rows from a summary table. A summary table is a materialized query. (By the way, since I know you are familiar with Kylin, I’ll point out that Kylin cuboids are basically summary tables.) The problem with OLAP is that there are many, many possible summary tables. You can’t create them all - it would use much more disk space than the original database. You could in principle define and populate them by hand, but it is better automated. So, a lattice is a space that allows a “summary table optimizer” to create a good set of summary tables. When a query is being optimized, the lattice isn’t really in play. There are summary tables T1, …, T17 and Calcite will pick the best applicable summary table (or none). (This is a white lie. Actually lattices are in play at query optimization time. If a summary table belongs to a lattice, Calcite can use a more efficient process to figure out whether it will satisfy the query. But the results would be the same as if it just used the list of summary tables.) Julian > On Nov 25, 2015, at 10:42 AM, Sarnath <[email protected]> wrote: > > Hi all, > > Good morning! > > Please bear with my newbie question here. I am still trying to find out > what calcite is all about. > > I went through the latest calcite presentation on relational algebra. I > followed all of it well except the last few slides that talk about lattice, > tiles and materialized views.... I don't see the connection between these > and relational algebra. Can someone explain this to me, please? > > Thanks a ton, > Best, > Sarnath
