Merge lp:~mmcm/akiban-server/sql-nested-map-folder into lp:~akiban-technologies/akiban-server/trunk

[Mike McMahon]

Correctly place operators added to implement non-group outer- and semi- joins.

These (NullIfEmpty, OnlyIfEmpty, Limit(1)) need to stay in the inside of the loop they are put in. They should not migrate down to faster loops the way ordinary single-row operators can.

As a consequence of this, outer joins (NullIfEmpty) need more often to materialize the join via Project. For instance, given t1 LEFT t2 LEFT t3, inside the t2 ⟕ t3 loop, If_Empty to supply a NULL t3, then Project(t2,t3) to implement that join, then outside that loop, but still inside the outer loop, If_Empty to supply the NULL of that join, then another Project to combine t1 and t2,t3 fields.

The code changes are relatively straightforward: the basic mechanisms were already in place, including adding Projects. This branch adds some more tests, so reviewers should convince themselves that the generated plans for those tests are correct for their queries. Also, several existing tests that would have duplicated rows from a semi-join are affected in similar ways.

[Thomas Jones-Low (tjoneslo)]

As described.

review: Approve

=== modified file 'src/main/java/com/akiban/sql/optimizer/rule/MapFolder.java'
--- src/main/java/com/akiban/sql/optimizer/rule/MapFolder.java	2013-03-22 20:05:57 +0000
+++ src/main/java/com/akiban/sql/optimizer/rule/MapFolder.java	2013-07-30 18:29:34 +0000
@@ -149,18 +149,7 @@
             map.setInner(new NullIfEmpty(map.getInner()));
             break;
         case SEMI:
-            {
-                PlanNode inner = map.getInner();
-                if ((inner instanceof Select) && 
-                    ((Select)inner).getConditions().isEmpty())
-                    inner = ((Select)inner).getInput();
-                // Right-nested semi-joins only need one Limit, since
-                // all the effects happen inside the fastest loop.
-                if (!((inner instanceof MapJoin) && 
-                      ((MapJoin)inner).getJoinType() == JoinNode.JoinType.SEMI))
-                    inner = new Limit(map.getInner(), 1);
-                map.setInner(inner);
-            }
+            map.setInner(new Limit(map.getInner(), 1));
             break;
         case ANTI:
             map.setInner(new OnlyIfEmpty(map.getInner()));
@@ -204,11 +193,21 @@
                    (parent instanceof ResultSet) ||
                    (parent instanceof AggregateSource) ||
                    (parent instanceof Sort) ||
+                   (parent instanceof NullIfEmpty) ||
+                   (parent instanceof OnlyIfEmpty) ||
+                   (parent instanceof Limit) ||
                    // Captures enough at the edge of the inside.
                    (child instanceof Project) ||
                    (child instanceof UpdateInput)));
         if (child != map) {
             PlanNode inner = map.getInner();
+            // Add a Project to capture fields within the loop before
+            // leaving the scope of its outer binding, that is,
+            // materialize the join as a projected row. 
+            // The cases where this is needed are:
+            // (1) This loop is itself on the outer side of another loop.
+            // (2) It implements the nullable side of an outer join.
+            // (3) Nested inside and so feeding another instance of (2) or (3).
             if (parent instanceof MapJoin) {
                 MapJoinProject nested = findAddedProject((MapJoin)parent, 
                                                          mapJoinProjects);
@@ -226,12 +225,31 @@
                                        nested, mapJoinProjects);
                 }
             }
+            else if (parent instanceof NullIfEmpty) {
+                // Even though we stop at the outer join, we still
+                // need to find the map that it's contained in.
+                PlanNode ancestor = parent;
+                do {
+                    ancestor = ancestor.getOutput();
+                } while ((ancestor instanceof Select) ||
+                         (ancestor instanceof Project));
+                if (ancestor instanceof MapJoin) {
+                    MapJoinProject nested = findAddedProject((MapJoin)ancestor, 
+                                                             mapJoinProjects);
+                    inner = addProject((MapJoin)ancestor, map, inner,
+                                       nested, mapJoinProjects);
+                }
+            }
             map.getOutput().replaceInput(map, inner);
             parent.replaceInput(child, map);
             map.setInner(child);
         }
     }
 
+    // A pending Project used to capture bindings inside the loop.
+    // When complete, we will walk the tree to determine which fields,
+    // if any, from its scope are used downstream and capture them or
+    // else throw the Project away.
     static class MapJoinProject implements PlanVisitor, ExpressionVisitor {
         MapJoin parentMap, childMap;
         MapJoinProject nested;
@@ -269,6 +287,7 @@
             this.innerSources = innerSources;
         }
         
+        // Are any of the inner bindings used outer?
         public boolean find() {
             columns = new ArrayList<>();
             for (MapJoinProject loop = this; loop != null; loop = loop.nested) {
@@ -280,6 +299,7 @@
             return foundOuter;
         }
 
+        // Actually install field expressions for this Project.
         public void install() {
             Set<ColumnExpression> seen = new HashSet<>();
             for (ColumnExpression column : columns) {
@@ -289,6 +309,7 @@
             }
         }
 
+        // Splice this unneeded Project out.
         public void remove() {
             project.getOutput().replaceInput(project, project.getInput());
             project = null;

=== modified file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/README.txt'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/README.txt	2012-09-05 21:30:52 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/README.txt	2013-07-30 18:29:34 +0000
@@ -1,5 +1,23 @@
 aggregate: Aggregation with nested loops
 
+nested-inner-inner: Nested joins: inner then inner
+
+nested-inner-left: Nested joins: inner then left
+
+nested-inner-right: Nested joins: inner then right
+
+nested-left-inner: Nested joins: left then inner
+
+nested-left-left: Nested joins: left then left
+
+nested-left-right: Nested joins: left then right
+
+nested-right-inner: Nested joins: right then inner
+
+nested-right-left: Nested joins: right then left
+
+nested-right-right: Nested joins: right then right
+
 outer: Outer join across groups.
 
 outer-join-condition: Outer join with another condition.

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-inner.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-inner.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-inner.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,18 @@
+SelectQuery@6f8affe
+  ResultSet@30ea5045[id, s, id, s, id, s]
+    MapJoin@ca7bd3d()
+      Flatten@6fe01bb8(t1)
+        GroupScan@5878f648(Group(test.t1), rows = 1, cost = 0.00000)
+          TableSource@1c26ffc6(t1 - TableGroup@44622e9a(t1))
+      MapJoin@6d711e58()
+        Flatten@623c0669(t2)
+          Select@1d7f5b8a[t2.id == t1.id]
+            GroupScan@1452d027(Group(test.t2), rows = 1, cost = 0.00000)
+              TableSource@58fc4d0e(t2 - TableGroup@9e1a389(t2))
+        Project@673bfb19[t1.id, t1.s, t2.id, t2.s, t3.id, t3.s]
+          Select@12e25b42[]
+            Select@48dfbadd[]
+              Flatten@52c909e1(t3)
+                AncestorLookup@5865288b(t3 -> [t3])
+                  SingleIndexScan@5948eb03(Index(test.t3.PRIMARY[IndexColumn(id)]), NONE, =t2.id, rows = 1, cost = 11.9848)
+                  TableSource@2d3c68ad(t3 - TableGroup@3cb77c70(t3))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-inner.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-inner.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-inner.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,1 @@
+SELECT * FROM t1 INNER JOIN t2 ON t1.id = t2.id INNER JOIN t3 ON t2.id = t3.id
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-left.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-left.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-left.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,19 @@
+SelectQuery@34a7c644
+  ResultSet@72c9b55d[id, s, id, s, id, s]
+    MapJoin@35f9de2()
+      Flatten@7b020cf2(t1)
+        GroupScan@7a766228(Group(test.t1), rows = 1, cost = 0.00000)
+          TableSource@5e1f9277(t1 - TableGroup@72266ee7(t1))
+      MapJoin@393b3a3d()
+        Flatten@43a022f5(t2)
+          Select@5f6c9825[t2.id == t1.id]
+            GroupScan@5278d614(Group(test.t2), rows = 1, cost = 0.00000)
+              TableSource@42dd975(t2 - TableGroup@7b2ee558(t2))
+        Project@18a2278b[t1.id, t1.s, t2.id, t2.s, t3.id, t3.s]
+          Select@3dd2234f[]
+            Select@43d33396[]
+              NullIfEmpty@5edfdfa3
+                Flatten@46572582(t3)
+                  AncestorLookup@3bd376fe(t3 -> [t3])
+                    SingleIndexScan@38293c61(Index(test.t3.PRIMARY[IndexColumn(id)]), NONE, =t2.id, rows = 1, cost = 11.9848)
+                    TableSource@6ac8f2e7(t3 - TableGroup@1b3b2115(t3))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-left.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-left.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-left.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,1 @@
+SELECT * FROM t1 INNER JOIN t2 ON t1.id = t2.id LEFT JOIN t3 ON t2.id = t3.id
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-right.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-right.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-right.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,20 @@
+SelectQuery@6dd64b31
+  ResultSet@fe2b64d[id, s, id, s, id, s]
+    MapJoin@788f8d68()
+      Flatten@6a8d819(t3)
+        GroupScan@188ce4ae(Group(test.t3), rows = 1, cost = 0.00000)
+          TableSource@4252736f(t3 - TableGroup@49f96819(t3))
+      Project@6d2e8160[t1.id, t1.s, t2.id, t2.s, t3.id, t3.s]
+        Select@82ffda0[]
+          NullIfEmpty@3966e4fa
+            MapJoin@15216740()
+              Flatten@370354b9(t1)
+                GroupScan@4401a596(Group(test.t1), rows = 1, cost = 0.00000)
+                  TableSource@15492050(t1 - TableGroup@481e3dbb(t1))
+              Select@3baf59e6[]
+                Project@406793be[t1.id, t2.id, t1.s, t2.s]
+                  Flatten@753729a6(t2)
+                    AncestorLookup@1242f687(t2 -> [t2])
+                      Select@6a47226e[t3.id == t2.id]
+                        SingleIndexScan@64259a44(Index(test.t2.PRIMARY[IndexColumn(id)]), NONE, =t1.id, rows = 1, cost = 11.9848)
+                      TableSource@33189e6d(t2 - TableGroup@60b319b9(t2))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-right.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-right.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-inner-right.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,1 @@
+SELECT * FROM t1 INNER JOIN t2 ON t1.id = t2.id RIGHT JOIN t3 ON t2.id = t3.id
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-inner.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-inner.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-inner.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,20 @@
+SelectQuery@773bf444
+  ResultSet@121d984[id, s, id, s, id, s]
+    MapJoin@14336855()
+      Flatten@12d86228(t1)
+        GroupScan@3b06aecf(Group(test.t1), rows = 1, cost = 0.00000)
+          TableSource@765bf858(t1 - TableGroup@33beb64f(t1))
+      Project@554f69b0[t1.id, t1.s, t2.id, t2.s, t3.id, t3.s]
+        Select@50a3cd91[]
+          NullIfEmpty@17db7729
+            MapJoin@2db31713()
+              Flatten@3c1439c2(t2)
+                Select@48aff7d5[t2.id == t1.id]
+                  GroupScan@18b7e63b(Group(test.t2), rows = 1, cost = 0.00000)
+                    TableSource@2b72af70(t2 - TableGroup@516c382a(t2))
+              Select@496c30fb[]
+                Project@781ffa5a[t2.id, t2.s, t3.id, t3.s]
+                  Flatten@53dc0e5e(t3)
+                    AncestorLookup@5e03d465(t3 -> [t3])
+                      SingleIndexScan@4d6d631b(Index(test.t3.PRIMARY[IndexColumn(id)]), NONE, =t2.id, rows = 1, cost = 11.9848)
+                      TableSource@4ec2506(t3 - TableGroup@4885a953(t3))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-inner.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-inner.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-inner.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,1 @@
+SELECT * FROM t1 LEFT JOIN t2 ON t1.id = t2.id INNER JOIN t3 ON t2.id = t3.id
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-left.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-left.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-left.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,21 @@
+SelectQuery@5b3a7993
+  ResultSet@5c03d0af[id, s, id, s, id, s]
+    MapJoin@1b85f4a1()
+      Flatten@72b85245(t1)
+        GroupScan@777f8424(Group(test.t1), rows = 1, cost = 0.00000)
+          TableSource@7dc52fe(t1 - TableGroup@54bc94c6(t1))
+      Project@7e79c05a[t1.id, t1.s, t2.id, t2.s, t3.id, t3.s]
+        Select@6b439594[]
+          NullIfEmpty@15282f42
+            MapJoin@28cb7ea0()
+              Flatten@23216ada(t2)
+                Select@47e64f4c[t2.id == t1.id]
+                  GroupScan@61602b74(Group(test.t2), rows = 1, cost = 0.00000)
+                    TableSource@154587e3(t2 - TableGroup@70c4fe9d(t2))
+              Select@136a0e8[]
+                Project@7d558b0e[t2.id, t2.s, t3.id, t3.s]
+                  NullIfEmpty@297ddff7
+                    Flatten@66ee203a(t3)
+                      AncestorLookup@6fae669(t3 -> [t3])
+                        SingleIndexScan@422cfb13(Index(test.t3.PRIMARY[IndexColumn(id)]), NONE, =t2.id, rows = 1, cost = 11.9848)
+                        TableSource@36d7da6e(t3 - TableGroup@1717be56(t3))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-left.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-left.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-left.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,1 @@
+SELECT * FROM t1 LEFT JOIN t2 ON t1.id = t2.id LEFT JOIN t3 ON t2.id = t3.id
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-right.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-right.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-right.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,20 @@
+SelectQuery@47d13cd
+  ResultSet@2f9efa08[id, s, id, s, id, s]
+    MapJoin@41cc788f()
+      Flatten@7138ebd2(t3)
+        GroupScan@56ff1608(Group(test.t3), rows = 1, cost = 0.00000)
+          TableSource@492c032(t3 - TableGroup@4ff93d7(t3))
+      Project@6e313ba4[t1.id, t1.s, t2.id, t2.s, t3.id, t3.s]
+        Select@6242c480[]
+          NullIfEmpty@c2a3624
+            MapJoin@27430ad1()
+              Flatten@50026210(t1)
+                GroupScan@227b337a(Group(test.t1), rows = 1, cost = 0.00000)
+                  TableSource@5818428c(t1 - TableGroup@4670a045(t1))
+              Select@4c743179[t3.id == t2.id]
+                Project@7e1c0bf9[t1.id, t2.id, t1.s, t2.s]
+                  NullIfEmpty@27487bb9
+                    Flatten@605c2625(t2)
+                      AncestorLookup@7b2c2d5(t2 -> [t2])
+                        SingleIndexScan@691531e5(Index(test.t2.PRIMARY[IndexColumn(id)]), NONE, =t1.id, rows = 1, cost = 11.9848)
+                        TableSource@3e8814f6(t2 - TableGroup@6e7ee748(t2))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-right.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-right.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-left-right.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,1 @@
+SELECT * FROM t1 LEFT JOIN t2 ON t1.id = t2.id RIGHT JOIN t3 ON t2.id = t3.id
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-inner.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-inner.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-inner.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,19 @@
+SelectQuery@70a66e76
+  ResultSet@3e9e3ec1[id, s, id, s, id, s]
+    MapJoin@73bf3f3f()
+      Flatten@5f0b23d8(t3)
+        GroupScan@10d17c77(Group(test.t3), rows = 1, cost = 0.00000)
+          TableSource@3fbd8be(t3 - TableGroup@29427141(t3))
+      MapJoin@49197790()
+        Flatten@545e6aa7(t2)
+          Select@26f8b46e[t3.id == t2.id]
+            GroupScan@120db5bf(Group(test.t2), rows = 1, cost = 0.00000)
+              TableSource@b52a3fd(t2 - TableGroup@421717db(t2))
+        Project@72a1105[t1.id, t1.s, t2.id, t2.s, t3.id, t3.s]
+          Select@5ac362ef[]
+            Select@7a1f4cc2[]
+              NullIfEmpty@1ce89331
+                Flatten@2ac2537(t1)
+                  AncestorLookup@691784ca(t1 -> [t1])
+                    SingleIndexScan@70f1fad(Index(test.t1.PRIMARY[IndexColumn(id)]), NONE, =t2.id, rows = 1, cost = 11.9848)
+                    TableSource@5e8c3cd9(t1 - TableGroup@71e89a79(t1))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-inner.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-inner.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-inner.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,1 @@
+SELECT * FROM t1 RIGHT JOIN t2 ON t1.id = t2.id INNER JOIN t3 ON t2.id = t3.id
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-left.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-left.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-left.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,19 @@
+SelectQuery@7eba8a14
+  ResultSet@8bf680c[id, s, id, s, id, s]
+    MapJoin@630fa3df()
+      Flatten@5ddbcc3d(t2)
+        GroupScan@17cfb848(Group(test.t2), rows = 1, cost = 0.00000)
+          TableSource@6f6ce13f(t2 - TableGroup@464b8b2e(t2))
+      MapJoin@99e9d10()
+        NullIfEmpty@c598a5f
+          Flatten@93de8ef(t1)
+            AncestorLookup@4a8b694e(t1 -> [t1])
+              SingleIndexScan@6aea61e(Index(test.t1.PRIMARY[IndexColumn(id)]), NONE, =t2.id, rows = 1, cost = 11.9848)
+              TableSource@5538283f(t1 - TableGroup@341bfeff(t1))
+        Project@4e47f050[t1.id, t1.s, t2.id, t2.s, t3.id, t3.s]
+          Select@54f23c56[]
+            NullIfEmpty@1a023213
+              Flatten@3f87a7a6(t3)
+                AncestorLookup@6258abc(t3 -> [t3])
+                  SingleIndexScan@ab73fcb(Index(test.t3.PRIMARY[IndexColumn(id)]), NONE, =t2.id, rows = 1, cost = 11.9848)
+                  TableSource@48d07bc1(t3 - TableGroup@4bd2dec(t3))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-left.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-left.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-left.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,1 @@
+SELECT * FROM t1 RIGHT JOIN t2 ON t1.id = t2.id LEFT JOIN t3 ON t2.id = t3.id
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-right.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-right.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-right.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,21 @@
+SelectQuery@5f42920f
+  ResultSet@b8347a5[id, s, id, s, id, s]
+    MapJoin@2711edd3()
+      Flatten@4d45a08d(t3)
+        GroupScan@a14cbaf(Group(test.t3), rows = 1, cost = 0.00000)
+          TableSource@577ab9(t3 - TableGroup@5b485354(t3))
+      Project@57d4a78a[t1.id, t1.s, t2.id, t2.s, t3.id, t3.s]
+        Select@4a438212[]
+          NullIfEmpty@2013d7b
+            MapJoin@6956de9d()
+              Flatten@162fb09d(t2)
+                Select@46314b72[t3.id == t2.id]
+                  GroupScan@4e504d5e(Group(test.t2), rows = 1, cost = 0.00000)
+                    TableSource@6f3a07db(t2 - TableGroup@7a077e7c(t2))
+              Select@1f6b5744[]
+                Project@3548a494[t2.id, t1.id, t1.s, t2.s]
+                  NullIfEmpty@402e4179
+                    Flatten@14f41ecc(t1)
+                      AncestorLookup@1ccc8fda(t1 -> [t1])
+                        SingleIndexScan@39f83ffb(Index(test.t1.PRIMARY[IndexColumn(id)]), NONE, =t2.id, rows = 1, cost = 11.9848)
+                        TableSource@4ad9f3e9(t1 - TableGroup@59309578(t1))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-right.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-right.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/nested-right-right.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,1 @@
+SELECT * FROM t1 RIGHT JOIN t2 ON t1.id = t2.id RIGHT JOIN t3 ON t2.id = t3.id
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/schema.ddl'
--- src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/schema.ddl	2012-02-26 19:35:32 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/fold-maps/schema.ddl	2013-07-30 18:29:34 +0000
@@ -41,3 +41,7 @@
   GROUPING FOREIGN KEY (cid) REFERENCES customers(cid)
 );
 CREATE INDEX state ON addresses(state);
+
+CREATE TABLE t1(id INT PRIMARY KEY NOT NULL, s VARCHAR(10));
+CREATE TABLE t2(id INT PRIMARY KEY NOT NULL, s VARCHAR(10));
+CREATE TABLE t3(id INT PRIMARY KEY NOT NULL, s VARCHAR(10));

=== modified file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/README.txt'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/README.txt	2013-01-08 23:18:56 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/README.txt	2013-07-30 18:29:34 +0000
@@ -33,3 +33,9 @@
 map-join-project: Need both sides of outer loop.
 
 map-join-project-nested: Needed in inner loop because outer loop is like that.
+
+nested-in: nested semi-joins
+
+nested-not-in: nested anti-joins
+
+nested-in-not: nested semi inside anti

=== modified file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/map-join-project-nested.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/map-join-project-nested.expected	2013-01-08 22:14:51 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/map-join-project-nested.expected	2013-07-30 18:29:34 +0000
@@ -3,10 +3,10 @@
     MapJoin@6dca323d()
       SingleIndexScan@75a87b1a(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
       MapJoin@82a244f()
-        MapJoin@6b5c2b9()
-          Select@7030320[c3.name == c2.name]
-            SingleIndexScan@56c22d78(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
-          NullIfEmpty@66374dc7
+        NullIfEmpty@66374dc7
+          MapJoin@6b5c2b9()
+            Select@7030320[c3.name == c2.name]
+              SingleIndexScan@56c22d78(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
             Select@4663a6c1[]
               MapJoin@38d3783e()
                 SingleIndexScan@437b4b97(Index(test.customers.name[IndexColumn(name)]), covering/NONE, =c2.name, rows = 1, cost = 6.04220)

=== modified file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/map-join-project.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/map-join-project.expected	2013-01-08 22:14:51 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/map-join-project.expected	2013-07-30 18:29:34 +0000
@@ -3,9 +3,9 @@
     MapJoin@273d638c()
       SingleIndexScan@2f529074(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
       MapJoin@24ebb33()
-        MapJoin@7ee41273()
-          SingleIndexScan@2f777d1a(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
-          NullIfEmpty@4db64e4e
+        NullIfEmpty@4db64e4e
+          MapJoin@7ee41273()
+            SingleIndexScan@2f777d1a(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
             Select@2ec72eb4[]
               Project@7bcf0abd[c1.name, c1.cid]
                 Select@55ca3dcb[c3.name == c2.name]

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in-not.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in-not.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in-not.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,14 @@
+SelectQuery@338c94e3
+  ResultSet@5282dd85[name]
+    MapJoin@52a6490c()
+      SingleIndexScan@2305dd38(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
+      Project@d9d7115[customers.name]
+        Select@5b6b20ae[]
+          OnlyIfEmpty@2dfd1d0c
+            MapJoin@55fe997e()
+              Select@3e0f4b4d[customers.cid == orders.cid]
+                SingleIndexScan@5e18cc0f(Index(test.orders.__akiban_fk_0[IndexColumn(cid)]), covering/NONE, rows = 1000, cost = 688.942)
+              Select@66261964[]
+                Limit@447e166a(LIMIT 1)
+                  Select@4f4d28a0[orders.oid == items.oid]
+                    SingleIndexScan@31f1ac47(Index(test.items.sku[IndexColumn(sku)]), covering/NONE, =1234, rows = 97, cost = 158.981)
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in-not.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in-not.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in-not.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,3 @@
+SELECT name FROM customers
+ WHERE cid NOT IN (SELECT cid FROM orders
+                    WHERE oid IN (SELECT oid FROM items WHERE sku = '1234'))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,18 @@
+SelectQuery@270cd144
+  ResultSet@3a7edb63[name]
+    MapJoin@30944cb9()
+      SingleIndexScan@58391e99(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
+      Project@5e755e95[customers.name]
+        Select@6b94b8a5[]
+          Limit@2f7708ec(LIMIT 1)
+            MapJoin@e07fc0f()
+              Select@2e3543fb[customers.cid == orders.cid]
+                SingleIndexScan@2b022b70(Index(test.orders.__akiban_fk_0[IndexColumn(cid)]), covering/NONE, rows = 1000, cost = 688.942)
+              Select@9a6f6ca[]
+                Limit@1b71dc1f(LIMIT 1)
+                  Select@b80fa71[]
+                    Flatten@457514c6(items)
+                      Select@502a854c[items.sku == 1234]
+                        AncestorLookup@179569b2(items -> [items])
+                          SingleIndexScan@524e3136(Index(test.items.__akiban_fk_1[IndexColumn(oid)]), NONE, =orders.oid, rows = 1, cost = 188.762)
+                          TableSource@b849d5c(items - TableGroup@b80fa71(customers))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-in.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,3 @@
+SELECT name FROM customers
+ WHERE cid IN (SELECT cid FROM orders
+                WHERE oid IN (SELECT oid FROM items WHERE sku = '1234'))
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-not-in.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-not-in.expected	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-not-in.expected	2013-07-30 18:29:34 +0000
@@ -0,0 +1,14 @@
+SelectQuery@173d3c4c
+  ResultSet@3541ad7f[name]
+    MapJoin@6a58f699()
+      SingleIndexScan@76a5ed5a(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
+      Project@6ae58829[customers.name]
+        Select@34e7293[]
+          OnlyIfEmpty@29662a39
+            MapJoin@781ec91()
+              Select@62d22770[customers.cid == orders.cid]
+                SingleIndexScan@531b5cbf(Index(test.orders.__akiban_fk_0[IndexColumn(cid)]), covering/NONE, rows = 1000, cost = 688.942)
+              Select@7cc50827[]
+                OnlyIfEmpty@725e196a
+                  Select@6b9a786f[orders.oid == items.oid]
+                    SingleIndexScan@7fd6b8ce(Index(test.items.sku[IndexColumn(sku)]), covering/NONE, =1234, rows = 97, cost = 158.981)
\ No newline at end of file

=== added file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-not-in.sql'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-not-in.sql	1970-01-01 00:00:00 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/nested-not-in.sql	2013-07-30 18:29:34 +0000
@@ -0,0 +1,3 @@
+SELECT name FROM customers
+ WHERE cid NOT IN (SELECT cid FROM orders
+                    WHERE oid NOT IN (SELECT oid FROM items WHERE sku = '1234'))
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/not-in-inner.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/not-in-inner.expected	2012-11-19 16:24:59 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/reverse-ins/not-in-inner.expected	2013-07-30 18:29:34 +0000
@@ -2,11 +2,11 @@
   ResultSet@55de5cd2[cid]
     MapJoin@5208873f()
       SingleIndexScan@2de7632c(Index(test.customers.name[IndexColumn(name)]), covering/NONE, rows = 100, cost = 74.1740)
-      MapJoin@321ff53f()
-        SingleIndexScan@501e14ce(Index(test.parent.PRIMARY[IndexColumn(id)]), covering/NONE, rows = 100, cost = 69.9260)
-        Project@79a00b08[customers.cid]
-          Select@7a347899[]
-            OnlyIfEmpty@66e80979
+      Project@79a00b08[customers.cid]
+        Select@7a347899[]
+          OnlyIfEmpty@66e80979
+            MapJoin@321ff53f()
+              SingleIndexScan@501e14ce(Index(test.parent.PRIMARY[IndexColumn(id)]), covering/NONE, rows = 100, cost = 69.9260)
               Select@287c958f[]
                 Flatten@b3ef40d(items)
                   Select@bc61bb7[customers.name == items.sku]