Query plan for `Q(a, b, c) <- R(a, b), S(b, c), T(a, b)`

triangle-query.dot

# From https://arxiv.org/abs/1210.0481

digraph G {
    rankdir=LR;
    
    subgraph cluster_relations {
        R [group="R"];
        S [group="S"];
        T [group="T"];
        label = "relations";
    }

    subgraph joins {
        #rankdir = TB;
    	subgraph cluster_a {
    	    R_a [label="R(a,_)",group="R"];
            T_a [label="T(a,_)",group="T"];
            join_a[label="⨝a"];
    
            R -> R_a -> join_a;
    		T -> T_a -> join_a;
    		label = "var a";
    	}
    
    	subgraph cluster_b {
    	    S_b [label="S(b,_)",group="S"];
            Ra_b [label="Ra(b)",group="R"];
            join_b[label="⨝b"];
        	join_a -> Ra_b;
    
    		S -> S_b -> join_b;
    		R -> Ra_b -> join_b;
    		label = "var b";
    	}
    	
    	subgraph cluster_c {
            Sb_c [label="Sb(c)",group="S"];
            Ta_c [label="Ta(c)",group="T"];
            join_c[label="⨝c"];
    	    join_a -> Ta_c;
    	    join_b -> Sb_c;
    
    		S -> Sb_c -> join_c;
    		T -> Ta_c -> join_c;
    		label = "var c";
    	}
    	
        join_a -> result;
        join_b -> result;
        join_c -> result;
    }

}

triangle-query.svg

<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="376pt" height="433pt" viewBox="0.00 0.00 375.85 433.00">
<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 429)">
<title>G</title>
<polygon fill="white" stroke="none" points="-4,4 -4,-429 371.85,-429 371.85,4 -4,4"></polygon>
<g id="clust1" class="cluster"><title>cluster_relations</title>
<polygon fill="none" stroke="black" points="8,-120 8,-305 78,-305 78,-120 8,-120"></polygon>
<text text-anchor="middle" x="43" y="-288.4" font-family="Times,serif" font-size="14.00">relations</text>
</g>
<g id="clust3" class="cluster"><title>cluster_a</title>
<polygon fill="none" stroke="black" points="98,-286 98,-417 274.871,-417 274.871,-286 98,-286"></polygon>
<text text-anchor="middle" x="186.436" y="-400.4" font-family="Times,serif" font-size="14.00">var a</text>
</g>
<g id="clust4" class="cluster"><title>cluster_b</title>
<polygon fill="none" stroke="black" points="98.5302,-147 98.5302,-278 274.871,-278 274.871,-147 98.5302,-147"></polygon>
<text text-anchor="middle" x="186.701" y="-261.4" font-family="Times,serif" font-size="14.00">var b</text>
</g>
<g id="clust5" class="cluster"><title>cluster_c</title>
<polygon fill="none" stroke="black" points="101.486,-8 101.486,-139 274.871,-139 274.871,-8 101.486,-8"></polygon>
<text text-anchor="middle" x="188.179" y="-122.4" font-family="Times,serif" font-size="14.00">var c</text>
</g>
<!-- R -->
<g id="node1" class="node"><title>R</title>
<ellipse fill="none" stroke="black" cx="43" cy="-254" rx="27" ry="18"></ellipse>
<text text-anchor="middle" x="43" y="-249.8" font-family="Times,serif" font-size="14.00">R</text>
</g>
<!-- R_a -->
<g id="node4" class="node"><title>R_a</title>
<ellipse fill="none" stroke="black" cx="141.436" cy="-366" rx="35.3716" ry="18"></ellipse>
<text text-anchor="middle" x="141.436" y="-361.8" font-family="Times,serif" font-size="14.00">R(a,_)</text>
</g>
<!-- R&#45;&gt;R_a -->
<g id="edge1" class="edge"><title>R-&gt;R_a</title>
<path fill="none" stroke="black" d="M52.0571,-271.185C61.2712,-289.539 77.7326,-318.719 98,-339 100.986,-341.988 104.359,-344.811 107.865,-347.424"></path>
<polygon fill="black" stroke="black" points="105.946,-350.352 116.172,-353.121 109.905,-344.579 105.946,-350.352"></polygon>
</g>
<!-- Ra_b -->
<g id="node8" class="node"><title>Ra_b</title>
<ellipse fill="none" stroke="black" cx="141.436" cy="-227" rx="33.043" ry="18"></ellipse>
<text text-anchor="middle" x="141.436" y="-222.8" font-family="Times,serif" font-size="14.00">Ra(b)</text>
</g>
<!-- R&#45;&gt;Ra_b -->
<g id="edge8" class="edge"><title>R-&gt;Ra_b</title>
<path fill="none" stroke="black" d="M68.3348,-247.187C78.5196,-244.335 90.6063,-240.951 101.944,-237.777"></path>
<polygon fill="black" stroke="black" points="102.963,-241.126 111.649,-235.06 101.075,-234.386 102.963,-241.126"></polygon>
</g>
<!-- S -->
<g id="node2" class="node"><title>S</title>
<ellipse fill="none" stroke="black" cx="43" cy="-146" rx="27" ry="18"></ellipse>
<text text-anchor="middle" x="43" y="-141.8" font-family="Times,serif" font-size="14.00">S</text>
</g>
<!-- S_b -->
<g id="node7" class="node"><title>S_b</title>
<ellipse fill="none" stroke="black" cx="141.436" cy="-173" rx="34.8114" ry="18"></ellipse>
<text text-anchor="middle" x="141.436" y="-168.8" font-family="Times,serif" font-size="14.00">S(b,_)</text>
</g>
<!-- S&#45;&gt;S_b -->
<g id="edge6" class="edge"><title>S-&gt;S_b</title>
<path fill="none" stroke="black" d="M68.3348,-152.813C78.075,-155.54 89.5546,-158.754 100.455,-161.806"></path>
<polygon fill="black" stroke="black" points="99.6637,-165.219 110.237,-164.545 101.551,-158.478 99.6637,-165.219"></polygon>
</g>
<!-- Sb_c -->
<g id="node10" class="node"><title>Sb_c</title>
<ellipse fill="none" stroke="black" cx="141.436" cy="-34" rx="31.8993" ry="18"></ellipse>
<text text-anchor="middle" x="141.436" y="-29.8" font-family="Times,serif" font-size="14.00">Sb(c)</text>
</g>
<!-- S&#45;&gt;Sb_c -->
<g id="edge12" class="edge"><title>S-&gt;Sb_c</title>
<path fill="none" stroke="black" d="M52.0571,-128.815C61.2712,-110.461 77.7326,-81.2813 98,-61 101.283,-57.7148 105.034,-54.6292 108.916,-51.8021"></path>
<polygon fill="black" stroke="black" points="111.138,-54.5256 117.494,-46.0488 107.239,-48.712 111.138,-54.5256"></polygon>
</g>
<!-- T -->
<g id="node3" class="node"><title>T</title>
<ellipse fill="none" stroke="black" cx="43" cy="-200" rx="27" ry="18"></ellipse>
<text text-anchor="middle" x="43" y="-195.8" font-family="Times,serif" font-size="14.00">T</text>
</g>
<!-- T_a -->
<g id="node5" class="node"><title>T_a</title>
<ellipse fill="none" stroke="black" cx="141.436" cy="-312" rx="34.7902" ry="18"></ellipse>
<text text-anchor="middle" x="141.436" y="-307.8" font-family="Times,serif" font-size="14.00">T(a,_)</text>
</g>
<!-- T&#45;&gt;T_a -->
<g id="edge3" class="edge"><title>T-&gt;T_a</title>
<path fill="none" stroke="black" d="M62.9927,-212.117C68.416,-216.303 73.947,-221.373 78,-227 93.202,-248.106 82.2155,-261.327 98,-282 100.991,-285.917 104.637,-289.529 108.524,-292.786"></path>
<polygon fill="black" stroke="black" points="106.614,-295.73 116.704,-298.962 110.832,-290.143 106.614,-295.73"></polygon>
</g>
<!-- Ta_c -->
<g id="node11" class="node"><title>Ta_c</title>
<ellipse fill="none" stroke="black" cx="141.436" cy="-88" rx="31.878" ry="18"></ellipse>
<text text-anchor="middle" x="141.436" y="-83.8" font-family="Times,serif" font-size="14.00">Ta(c)</text>
</g>
<!-- T&#45;&gt;Ta_c -->
<g id="edge14" class="edge"><title>T-&gt;Ta_c</title>
<path fill="none" stroke="black" d="M62.2017,-187.238C67.5928,-183.025 73.3045,-178.103 78,-173 88.8505,-161.208 88.6555,-156.018 98,-143 105.215,-132.948 113.463,-122.12 120.756,-112.752"></path>
<polygon fill="black" stroke="black" points="123.714,-114.652 127.13,-104.623 118.205,-110.333 123.714,-114.652"></polygon>
</g>
<!-- join_a -->
<g id="node6" class="node"><title>join_a</title>
<ellipse fill="none" stroke="black" cx="239.871" cy="-312" rx="27" ry="18"></ellipse>
<text text-anchor="middle" x="239.871" y="-307.8" font-family="Times,serif" font-size="14.00">⨝a</text>
</g>
<!-- R_a&#45;&gt;join_a -->
<g id="edge2" class="edge"><title>R_a-&gt;join_a</title>
<path fill="none" stroke="black" d="M166.274,-352.652C179.325,-345.343 195.611,-336.224 209.448,-328.476"></path>
<polygon fill="black" stroke="black" points="211.552,-331.309 218.567,-323.37 208.132,-325.202 211.552,-331.309"></polygon>
</g>
<!-- T_a&#45;&gt;join_a -->
<g id="edge4" class="edge"><title>T_a-&gt;join_a</title>
<path fill="none" stroke="black" d="M176.435,-312C184.917,-312 194.043,-312 202.628,-312"></path>
<polygon fill="black" stroke="black" points="202.753,-315.5 212.753,-312 202.753,-308.5 202.753,-315.5"></polygon>
</g>
<!-- join_a&#45;&gt;Ra_b -->
<g id="edge5" class="edge"><title>join_a-&gt;Ra_b</title>
<path fill="none" stroke="black" d="M222.742,-297.783C207.604,-284.441 184.74,-264.287 167.274,-248.893"></path>
<polygon fill="black" stroke="black" points="169.493,-246.183 159.677,-242.196 164.864,-251.434 169.493,-246.183"></polygon>
</g>
<!-- join_a&#45;&gt;Ta_c -->
<g id="edge10" class="edge"><title>join_a-&gt;Ta_c</title>
<path fill="none" stroke="black" d="M223.892,-297.443C219.827,-292.829 215.757,-287.491 212.871,-282 183.19,-225.507 202.099,-201.618 176.871,-143 172.463,-132.755 166.314,-122.209 160.43,-113.126"></path>
<polygon fill="black" stroke="black" points="163.186,-110.952 154.709,-104.597 157.373,-114.852 163.186,-110.952"></polygon>
</g>
<!-- result -->
<g id="node13" class="node"><title>result</title>
<ellipse fill="none" stroke="black" cx="335.361" cy="-173" rx="32.4788" ry="18"></ellipse>
<text text-anchor="middle" x="335.361" y="-168.8" font-family="Times,serif" font-size="14.00">result</text>
</g>
<!-- join_a&#45;&gt;result -->
<g id="edge16" class="edge"><title>join_a-&gt;result</title>
<path fill="none" stroke="black" d="M258.238,-298.713C263.948,-293.839 270.058,-288.029 274.871,-282 295.232,-256.496 312.314,-223.042 322.876,-199.957"></path>
<polygon fill="black" stroke="black" points="326.105,-201.31 326.993,-190.752 319.715,-198.451 326.105,-201.31"></polygon>
</g>
<!-- join_b -->
<g id="node9" class="node"><title>join_b</title>
<ellipse fill="none" stroke="black" cx="239.871" cy="-173" rx="27" ry="18"></ellipse>
<text text-anchor="middle" x="239.871" y="-168.8" font-family="Times,serif" font-size="14.00">⨝b</text>
</g>
<!-- S_b&#45;&gt;join_b -->
<g id="edge7" class="edge"><title>S_b-&gt;join_b</title>
<path fill="none" stroke="black" d="M176.435,-173C184.917,-173 194.043,-173 202.628,-173"></path>
<polygon fill="black" stroke="black" points="202.753,-176.5 212.753,-173 202.753,-169.5 202.753,-176.5"></polygon>
</g>
<!-- Ra_b&#45;&gt;join_b -->
<g id="edge9" class="edge"><title>Ra_b-&gt;join_b</title>
<path fill="none" stroke="black" d="M165.29,-214.203C178.54,-206.783 195.362,-197.364 209.576,-189.404"></path>
<polygon fill="black" stroke="black" points="211.462,-192.36 218.477,-184.42 208.042,-186.252 211.462,-192.36"></polygon>
</g>
<!-- join_b&#45;&gt;Sb_c -->
<g id="edge11" class="edge"><title>join_b-&gt;Sb_c</title>
<path fill="none" stroke="black" d="M224.435,-158.13C220.385,-153.507 216.187,-148.243 212.871,-143 191.598,-109.36 201.267,-92.4489 176.871,-61 175.038,-58.6365 172.954,-56.3612 170.74,-54.2031"></path>
<polygon fill="black" stroke="black" points="172.723,-51.2894 162.885,-47.3583 168.125,-56.5668 172.723,-51.2894"></polygon>
</g>
<!-- join_b&#45;&gt;result -->
<g id="edge17" class="edge"><title>join_b-&gt;result</title>
<path fill="none" stroke="black" d="M266.914,-173C274.913,-173 283.927,-173 292.698,-173"></path>
<polygon fill="black" stroke="black" points="292.809,-176.5 302.809,-173 292.809,-169.5 292.809,-176.5"></polygon>
</g>
<!-- join_c -->
<g id="node12" class="node"><title>join_c</title>
<ellipse fill="none" stroke="black" cx="239.871" cy="-88" rx="27" ry="18"></ellipse>
<text text-anchor="middle" x="239.871" y="-83.8" font-family="Times,serif" font-size="14.00">⨝c</text>
</g>
<!-- Sb_c&#45;&gt;join_c -->
<g id="edge13" class="edge"><title>Sb_c-&gt;join_c</title>
<path fill="none" stroke="black" d="M164.802,-46.5244C178.13,-53.9874 195.199,-63.5452 209.591,-71.6044"></path>
<polygon fill="black" stroke="black" points="208.161,-74.8149 218.597,-76.6469 211.581,-68.7073 208.161,-74.8149"></polygon>
</g>
<!-- Ta_c&#45;&gt;join_c -->
<g id="edge15" class="edge"><title>Ta_c-&gt;join_c</title>
<path fill="none" stroke="black" d="M173.479,-88C182.78,-88 193.06,-88 202.662,-88"></path>
<polygon fill="black" stroke="black" points="202.737,-91.5001 212.737,-88 202.737,-84.5001 202.737,-91.5001"></polygon>
</g>
<!-- join_c&#45;&gt;result -->
<g id="edge18" class="edge"><title>join_c-&gt;result</title>
<path fill="none" stroke="black" d="M256.731,-102.419C271.236,-115.607 292.923,-135.325 309.691,-150.571"></path>
<polygon fill="black" stroke="black" points="307.721,-153.51 317.475,-157.647 312.43,-148.33 307.721,-153.51"></polygon>
</g>
</g>
</svg>