5 <meta http-equiv="x-ua-compatible" content="ie=edge">
6 <meta name="viewport" content="width=device-width, initial-scale=1">
7 <title>Project:M36 Blog - 10 Cool Static Relational Algebra Optimizations in Project:M36</title>
8 <link rel="stylesheet" href="../css/brooklyn.css" />
13 <a href="../">Project:M36 Blog</a>
16 <a href="../">Home</a>
17 <a href="../about.html">About</a>
18 <a href="../contact.html">Contact</a>
19 <a href="../archive.html">Archive</a>
25 Posted on November 30, 2017
31<h1 id="cool-static-relational-algebra-optimizations-in-projectm36">10 Cool Static Relational Algebra Optimizations in Project:M36</h1>
32<p>A few months ago, a jooq blog entry was posted called <a href="https://blog.jooq.org/2017/09/28/10-cool-sql-optimisations-that-do-not-depend-on-the-cost-model/#top3">10 Cool SQL Optimisations That do not Depend on the Cost Model</a> which covered some SQL query rewrite optimizations which can unconditionally run faster than the original query. Because these query rewrites do not require inspecting the database state (the “cost model”), the optimizations the rewrites provide are implementation independent. They are often called “static optimizations”.</p>
33<p>In this blog entry, we will cover how the same optimizations apply to the Project:M36 relational algebra engine and why adherence to the mathematical underpinnings of the relational algebra make the optimizations more obvious, easier-to-understand, and ultimately, more performant in execution.</p>
34<p>“Cost-model independent” optimizations are query rewrites which eliminate extraneous processing, implying that doing nothing is unconditionally “cheaper” (in a computation sense) than doing something. For example, in the TutorialD query <code>s where true</code>, it’s obvious that the restriction cannot actually filter out any tuples, so executing the restriction is extraneous.</p>
35<p>Let’s examine the same optimizations that the jooq blog post covered.</p>
36<h2 id="transitive-closure">1. Transitive Closure</h2>
37<p>If the relational restriction predicate <code>A</code> is identical to predicate <code>B</code>, and predicate <code>B</code> is identical to <code>C</code>, then <code>A</code> can be replaced with <code>C</code> (or vice versa). This is called the “transitive property” and can be used to replace obviously more expensive restriction predicates with cheaper versions.</p>
38<p>In general, replacing a predicate with a static value (such as a text or integer value) is cheaper than looking up a value in a tuple or executing a function. For example:</p>
39<pre><code>s where a=@b and b=300</code></pre>
40<p>is optimized to:</p>
41<pre><code>s where a=300 and b=300</code></pre>
42<p>and the Haskell code to implement this is straightforward:</p>
43<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">let</span> attrMap <span class="fu">=</span> findStaticRestrictionPredicates optPred <span class="kw">in</span>
44pure (<span class="dt">Right</span> (replaceStaticAtomExprs optPred attrMap))</code></pre></div>
45<p>The <a href="https://github.com/agentm/project-m36/blob/master/src/lib/ProjectM36/StaticOptimizer.hs#L297">algebraic data type manipulation</a> is elided for brevity, but it is entirely mechanical.</p>
46<h2 id="impossible-predicates">2. Impossible Predicates</h2>
47<p>When predicates are demonstrably and unconditionally false the restriction can be eliminated and replaced with an empty relation. For example, <code>s where false</code> returns the empty relation (no tuples) with the attributes of <code>s</code>.</p>
48<p>Note that this optimization is more effective in the real relational algebra when compared to SQL. In Project:M36, there is no three-valued logic involving NULL, so <code>where true</code> and <code>where false</code> are inverses and the predicate is boolean-valued.</p>
49<p>Project:M36 does not support predicates of the form “0 = 1” because such expression don’t target the relational state, so the examples in the sister blog post cannot be represented.</p>
50<p>The <a href="https://github.com/agentm/project-m36/blob/master/src/lib/ProjectM36/StaticOptimizer.hs#L118">implementation</a> is simple.</p>
51<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"> <span class="fu">|</span> isFalseExpr optimizedPredicate2 <span class="ot">-></span> <span class="kw">do</span> <span class="co">-- replace where false predicate with empty with attributes from relexpr</span>
52 attributesRel <span class="ot"><-</span> typeForRelationalExpr expr
53 <span class="kw">case</span> attributesRel <span class="kw">of</span>
54 <span class="dt">Left</span> err <span class="ot">-></span> pure <span class="fu">$</span> <span class="dt">Left</span> err
55 <span class="dt">Right</span> attributesRelA <span class="ot">-></span> pure <span class="fu">$</span> <span class="dt">Right</span> <span class="fu">$</span> <span class="dt">MakeStaticRelation</span> (attributes attributesRelA) emptyTupleSet
56<span class="fu">...</span></code></pre></div>
57<h2 id="join-elimination">3. Join Elimination</h2>
58<p>If there is a foreign key constraint between a join condition and a projection on the resultant join includes the foreign key and not any attributes from the secondary relation variable, then the join can be elided. For example (from the C.J. Date relation variable examples):</p>
59<pre><code>(s join sp){s#,sname}</code></pre>
60<p>can be rewritten as</p>
61<pre><code>s{s#,sname}</code></pre>
62<p>This rewrite is valid because a foreign key constraint proves that there cannot be <code>s#</code> values in <code>sp</code> which do not already appear in <code>s</code>.</p>
63<p>The <a href="https://github.com/agentm/project-m36/blob/master/src/lib/ProjectM36/StaticOptimizer.hs#L322">implementation</a> is complicated here only because we need to confirm a specific foreign key constraint.</p>
64<h2 id="removing-silly-predicates">4. Removing Silly Predicates</h2>
65<p>In section 2, we covered <code>s where false</code>, but <code>s where true</code> is equally valid to remove. <code>s where true</code> is equivalent to <code>s</code> because the restriction is guaranteed to filter out any tuples.</p>
66<p>The <a href="https://github.com/agentm/project-m36/blob/master/src/lib/ProjectM36/StaticOptimizer.hs#L122">implementation</a> is almost trivial:</p>
67<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="fu">|</span> isTrueExpr optimizedPredicate2 <span class="ot">-></span> applyStaticRelationalOptimization expr <span class="co">-- remove predicate entirely</span></code></pre></div>
68<h2 id="projections-in-exists-subqueries">5. Projections in Exists Subqueries</h2>
69<p>Project:M36 doesn’t really have a notion of “subqueries” because we simply build up an algebraic data type representing the query, so it’s obvious that relational expressions can be nested, but, in the special case of existence, Project:M36 already requires a projection on empty attributes:</p>
70<pre><code>(s rename {s# as sno}) where ((sp where ^gte(@qty,400) and sno=@s#){})</code></pre>
71<p>A projection on empty attributes must either result in <code>true</code> which is the relation with no attributes and one tuple or <code>false</code> which is the relation with no attributes and zero tuples.</p>
72<p>A further optimization here could be to stop the restriction scan as soon as one tuple is found since the existence is then proven.</p>
73<h2 id="predicate-merging">6. Predicate Merging</h2>
74<p>Simple predicate merging such <code>s where true and true</code> is supported, but more complicated merges such as those shown in the sister blog post are not yet supported.</p>
75<p>The implementation is hardly worth mentioning:</p>
76<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">if</span> optPred1 <span class="fu">==</span> optPred2 <span class="kw">then</span>
77 pure (<span class="dt">Right</span> optPred1)
78 <span class="kw">else</span>
79 pure (<span class="dt">Right</span> (<span class="dt">AndPredicate</span> optPred1 optPred2))</code></pre></div>
80<p>A similar boolean short-circuit optimization is offered for <code>or</code> predicates.</p>
81<h2 id="provably-empty-sets">7. Provably Empty Sets</h2>
82<p>This set of optimizations uses constraints to determine if a restriction is universally true or false in order to eliminate the restriction. For example, if a constraint ensures that all values of <code>qty</code> > 3, then <code>sp where @qty = 1</code> must return an empty result relation.</p>
83<p>Project:M36 does not introspect constraints for this type of optimization, but it would be fairly straightforward to implement. There are many forms of this type of optimization, so the implementation would be quite involved to be comprehensive. Project:M36 needs more work in this area.</p>
84<h2 id="check-constraints">8. CHECK constraints</h2>
85<p>Project:M36 supports a comprehensive method of constraints called “inclusion dependencies” which encompass every possible database constraint including cross-relation-variable constraints (GLOBAL constraints in SQL parlance). In addition, Project:M36 supports algebraic data types (ADTs) as values, so simulating enumerations with CHECK constraints is obviated (and antiquated).</p>
86<p>Translating the film rating example from the sister blog entry, we get:</p>
87<pre><code>data FilmRating = G | PG | PG_13 | R | NC_17
88:showexpr relation{tuple{name "The Smurfs", rating G}}
89┌────────────┬──────────────────┐
90│name::Text │rating::FilmRating│
91├────────────┼──────────────────┤
92│"The Smurfs"│G │
93└────────────┴──────────────────┘</code></pre>
94<p>This is an improvement over the SQL’s CHECK constraints example because type safety enforced by the ADT guarantees that a <code>FilmRating</code> not defined by the data type cannot even be represented, much less optimized, so the error is caught sooner.</p>
95<h2 id="unneeded-self-join">9. Unneeded Self Join</h2>
96<p>Unlike in SQL, <code>x join x</code> in Project:M36 is unconditionally <code>x</code> because Project:M36 does not use three-valued logic. More generally, <code>x</code> need not be merely a relation variable’s name but could be an entire relational expression. Thus, <code>join</code> can be used in lieu of the equality operator for relational expressions and we can safely remove it when both sides of the join are identical.</p>
97<p>Furthermore, even when the <code>join</code> conditions are not equal but reference the same relation variable, we can collapse the join plus restriction into a single restriction:</p>
98<pre><code>(x where c1) join (x where c2)</code></pre>
99<p>is equivalent to:</p>
100<pre><code>x where c1 and c2</code></pre>
101<p>Again, the Haskell implementation is completely obvious:</p>
102<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="kw">case</span> (optExprA, optExprB) <span class="kw">of</span>
103 (<span class="dt">Restrict</span> predA (<span class="dt">RelationVariable</span> nameA ()),
104 <span class="dt">Restrict</span> predB (<span class="dt">RelationVariable</span> nameB ())) <span class="fu">|</span> nameA <span class="fu">==</span> nameB <span class="ot">-></span> pure (<span class="dt">Right</span> (<span class="dt">Restrict</span> (<span class="dt">AndPredicate</span> predA predB) (<span class="dt">RelationVariable</span> nameA ())))
105 _ <span class="ot">-></span> <span class="kw">if</span> optExprA <span class="fu">==</span> optExprB <span class="kw">then</span> <span class="co">--A join A == A </span>
106 pure (<span class="dt">Right</span> optExprA)
107 <span class="kw">else</span>
108 pure (<span class="dt">Right</span> (<span class="dt">Join</span> optExprA optExprB))</code></pre></div>
109<h1 id="predicate-pushdown">10. Predicate Pushdown</h1>
110<p>This optimization is a bit more contentious, as the sister blog entry rightfully points out. In a tuple-oriented storage system, slicing tuples horizontally (restriction: <code>s where name</code>) is cheaper than slicing vertically (projection: <code>s{sname}</code>), so it makes sense to push restriction predicates “down” into projections in order to execute the restriction first.</p>
112<pre><code>x{proj} where c1</code></pre>
114<pre><code>(x where c1){proj}</code></pre>
115<p>so that the projection is evaluated potentially on fewer tuples. The pushdown also works on <code>union</code>:</p>
116<pre><code>(x union y) where c</code></pre>
118<pre><code>(x where c) union (y where c)</code></pre>
119<p>so that the union can receive (maybe) fewer tuples.</p>
120<p>The implementation is almost trivial:</p>
121<pre><code>Restrict restrictAttrs (Project projAttrs subexpr) ->
122 Project projAttrs (Restrict restrictAttrs (applyStaticRestrictionPushdown subexpr))</code></pre>
123<h2 id="conclusion">Conclusion</h2>
124<p>This blog post is merely a follow-up to the jooq post and is not meant to be an exhaustive list of Project:M36 static optimizations. Still, this list of optimizations is a fun way of showing how easy it can be to create static optimizations for Project:M36 which throws off the crustiness of SQL (such as three-valued logic) in preference to mathematical coherence (such as set theory). This flies in the face of common database implementations approaches which veer from mathematical correctness in deference to “optimizations”. Haskell makes it easy to match optimization forms using algebraic data types while the strong mathematical underpinnings make the optimizations straightforward. We have demonstrated that the same optimization techniques are of greater benefit when the relational algebra is strictly followed.</p>
125<p>Project:M36 would benefit from many more static optimizations and other exciting features. If you interested in learning more, please <a href="https://github.com/agentm/project-m36#community">join us</a>!</p>
130 Site proudly generated by
131 <a href="http://jaspervdj.be/hakyll">Hakyll</a>
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list