Merge lp:~mmcm/akiban-server/product-nested into lp:~akiban-technologies/akiban-server/trunk

[Mike McMahon]

Replace Product_NestedLoops with Product_Nested.

The new operator is much simpler: it produces a Product row of its input row and a bound row.

There was some subtlety to Product_NestedLoops:

(1) It maintained a cache by common ancestor hkey and didn't re-run the inner loop sometimes. While it's possible for ancestors to just happen to coincide from any secondary index, the cases where they do so reliably are rare, mostly involving GroupScans. Since maintaining this cache means keeping all the inner rows, I'm not sure it's worth it in balance. Presumably database caches will have the inner rows in memory at least.

(2) The row set in the bindings is not the one used for the product, but the common ancestor. This isn't possible with Map_NestedLoops. But it's just as easy to do the ancestor in BranchLookup_Nested, which is about this kind of navigation anyway. So, give that operator both an input row type and a source row type, to be extracted by subRow().

Some notes on the relevant ITs:

Product_NestedLoopsIT was incorrectly specifying KEEP_PARENT to Flatten. This may have been left over from when Product worked as a single row stream.

Product2WayIT had a comment about run ids, which again was from long ago. Also it was reusing binding slots for each loop, which isn't reliable, even if the Maps nest on the outer side, because the second inner row of the outer loop is allowed to assume that the bound value is still there. This worked okay with nested Product_NestedLoops's because the bound row was copied at open time. Rather than make Product_Nested do that, just use different slots, as the optimizer does.

[lp:~mmcm/akiban-server/product-nested]

2722. By Mike McMahon on 2013-07-18

Merge from trunk.

[Nathan Williams (nwilliams)]

Minor nit: The Overview in the Javadoc for Product_Nested still references _NestedLoops.

Otherwise looks pretty good. Feel free to Big-A after.

review: Approve

[lp:~mmcm/akiban-server/product-nested]

2723. By Mike McMahon on 2013-07-18

Missed one.

=== modified file 'src/main/java/com/akiban/qp/operator/API.java'
--- src/main/java/com/akiban/qp/operator/API.java	2013-07-13 21:17:31 +0000
+++ src/main/java/com/akiban/qp/operator/API.java	2013-07-18 16:47:28 +0000
@@ -210,6 +210,7 @@
                                                int inputBindingPosition)
     {
         return new BranchLookup_Nested(group,
+                                       inputRowType, 
                                        inputRowType,
                                        null,
                                        outputRowType,
@@ -225,6 +226,7 @@
                                                int inputBindingPosition)
     {
         return new BranchLookup_Nested(group,
+                                       inputRowType, 
                                        inputRowType,
                                        ancestorRowType,
                                        outputRowType,
@@ -232,6 +234,23 @@
                                        inputBindingPosition);
     }
 
+    public static Operator branchLookup_Nested(Group group,
+                                               RowType inputRowType,
+                                               RowType sourceRowType,
+                                               UserTableRowType ancestorRowType,
+                                               UserTableRowType outputRowType,
+                                               InputPreservationOption flag,
+                                               int inputBindingPosition)
+    {
+        return new BranchLookup_Nested(group,
+                                       inputRowType, 
+                                       sourceRowType,
+                                       ancestorRowType,
+                                       outputRowType,
+                                       flag,
+                                       inputBindingPosition);
+    }
+
     // Limit
 
     public static Operator limit_Default(Operator inputOperator, int limitRows)
@@ -448,9 +467,10 @@
                                                        RowType innerType,
                                                        int inputBindingPosition)
     {
-        return new Product_NestedLoops(outerInput, innerInput, outerType, null, innerType, inputBindingPosition);
+        return product_NestedLoops(outerInput, innerInput, outerType, null, innerType, inputBindingPosition);
     }
 
+    /** deprecated */
     public static Operator product_NestedLoops(Operator outerInput,
                                                        Operator innerInput,
                                                        RowType outerType,
@@ -458,7 +478,19 @@
                                                        RowType innerType,
                                                        int inputBindingPosition)
     {
-        return new Product_NestedLoops(outerInput, innerInput, outerType, branchType, innerType, inputBindingPosition);
+        return map_NestedLoops(outerInput,
+                               product_Nested(innerInput, outerType, branchType, innerType, inputBindingPosition),
+                               inputBindingPosition,
+                               false, 0);
+    }
+
+    public static Operator product_Nested(Operator input,
+                                          RowType outerType,
+                                          UserTableRowType branchType,
+                                          RowType inputType,
+                                          int bindingPosition)
+    {
+        return new Product_Nested(input, outerType, branchType, inputType, bindingPosition);
     }
 
     // Count

=== modified file 'src/main/java/com/akiban/qp/operator/BranchLookup_Nested.java'
--- src/main/java/com/akiban/qp/operator/BranchLookup_Nested.java	2013-07-17 18:15:10 +0000
+++ src/main/java/com/akiban/qp/operator/BranchLookup_Nested.java	2013-07-18 16:47:28 +0000
@@ -56,7 +56,9 @@
  <li><b>GroupTable groupTable:</b> The group table containing the
  ancestors of interest.
 
- <li><b>RowType inputRowType:</b> Branches will be located for input
+ <li><b>RowType inputRowType:</b> Bound row will be of this type.
+ 
+ <li><b>RowType sourceRowType:</b> Branches will be located for input
  rows of this type.
  
  <li><b>UserTableRowType ancestorRowType:</b> Identifies the table in the group at which branching occurs.
@@ -136,7 +138,7 @@
         return String.format("%s(%s %s -> %s)",
                              getClass().getSimpleName(),
                              group.getRoot().getName(),
-                             inputRowType,
+                             sourceRowType,
                              outputRowType);
     }
 
@@ -163,6 +165,7 @@
 
     public BranchLookup_Nested(Group group,
                                RowType inputRowType,
+                               RowType sourceRowType,
                                UserTableRowType ancestorRowType,
                                UserTableRowType outputRowType,
                                API.InputPreservationOption flag,
@@ -170,21 +173,22 @@
     {
         ArgumentValidation.notNull("group", group);
         ArgumentValidation.notNull("inputRowType", inputRowType);
+        ArgumentValidation.notNull("sourceRowType", sourceRowType);
         ArgumentValidation.notNull("outputRowType", outputRowType);
         ArgumentValidation.notNull("flag", flag);
-        ArgumentValidation.isTrue("inputRowType instanceof UserTableRowType || flag == API.InputPreservationOption.DISCARD_INPUT",
-                                  inputRowType instanceof UserTableRowType || flag == API.InputPreservationOption.DISCARD_INPUT);
+        ArgumentValidation.isTrue("sourceRowType instanceof UserTableRowType || flag == API.InputPreservationOption.DISCARD_INPUT",
+                                  sourceRowType instanceof UserTableRowType || flag == API.InputPreservationOption.DISCARD_INPUT);
         ArgumentValidation.isGTE("hKeyBindingPosition", inputBindingPosition, 0);
         UserTableRowType inputTableType = null;
-        if (inputRowType instanceof UserTableRowType) {
-            inputTableType = (UserTableRowType) inputRowType;
-        } else if (inputRowType instanceof IndexRowType) {
-            inputTableType = ((IndexRowType) inputRowType).tableType();
-        } else if (inputRowType instanceof HKeyRowType) {
+        if (sourceRowType instanceof UserTableRowType) {
+            inputTableType = (UserTableRowType) sourceRowType;
+        } else if (sourceRowType instanceof IndexRowType) {
+            inputTableType = ((IndexRowType) sourceRowType).tableType();
+        } else if (sourceRowType instanceof HKeyRowType) {
             Schema schema = outputRowType.schema();
-            inputTableType = schema.userTableRowType(inputRowType.hKey().userTable());
+            inputTableType = schema.userTableRowType(sourceRowType.hKey().userTable());
         }
-        assert inputTableType != null : inputRowType;
+        assert inputTableType != null : sourceRowType;
         UserTable inputTable = inputTableType.userTable();
         UserTable outputTable = outputRowType.userTable();
         ArgumentValidation.isSame("inputTable.getGroup()",
@@ -193,6 +197,7 @@
                                   outputTable.getGroup());
         this.group = group;
         this.inputRowType = inputRowType;
+        this.sourceRowType = sourceRowType;
         this.outputRowType = outputRowType;
         this.keepInput = flag == API.InputPreservationOption.KEEP_INPUT;
         this.inputBindingPosition = inputBindingPosition;
@@ -262,7 +267,7 @@
     // Object state
 
     private final Group group;
-    private final RowType inputRowType;
+    private final RowType inputRowType, sourceRowType;
     private final UserTableRowType outputRowType;
     private final boolean keepInput;
     // If keepInput is true, inputPrecedesBranch controls whether input row appears before the retrieved branch.
@@ -278,9 +283,9 @@
         atts.put(Label.BINDING_POSITION, PrimitiveExplainer.getInstance(inputBindingPosition));
         atts.put(Label.OUTPUT_TYPE, outputRowType.getExplainer(context));
         UserTableRowType ancestorRowType = outputRowType.schema().userTableRowType(commonAncestor);
-        if ((ancestorRowType != inputRowType) && (ancestorRowType != outputRowType))
+        if ((ancestorRowType != sourceRowType) && (ancestorRowType != outputRowType))
             atts.put(Label.ANCESTOR_TYPE, ancestorRowType.getExplainer(context));
-        return new LookUpOperatorExplainer(getName(), atts, inputRowType, false, null, context);
+        return new LookUpOperatorExplainer(getName(), atts, sourceRowType, false, null, context);
     }
 
     // Inner classes
@@ -296,10 +301,13 @@
             try {
                 CursorLifecycle.checkIdle(this);
                 Row rowFromBindings = bindings.getRow(inputBindingPosition);
+                assert rowFromBindings.rowType() == inputRowType : rowFromBindings;
+                if (inputRowType != sourceRowType) {
+                    rowFromBindings = rowFromBindings.subRow(sourceRowType);
+                }
                 if (LOG_EXECUTION) {
                     LOG.debug("BranchLookup_Nested: open using {}", rowFromBindings);
                 }
-                assert rowFromBindings.rowType() == inputRowType : rowFromBindings;
                 computeLookupRowHKey(rowFromBindings);
                 cursor.rebind(hKey, true);
                 cursor.open();

=== modified file 'src/main/java/com/akiban/qp/operator/Map_NestedLoops.java'
--- src/main/java/com/akiban/qp/operator/Map_NestedLoops.java	2013-07-18 13:05:48 +0000
+++ src/main/java/com/akiban/qp/operator/Map_NestedLoops.java	2013-07-18 16:47:28 +0000
@@ -76,7 +76,7 @@
 
  <h1>Performance</h1>
 
- Product_NestedLoops does no IO.
+ Map_NestedLoops does no IO.
 
  <h1>Memory Requirements</h1>
 
@@ -135,7 +135,8 @@
         ArgumentValidation.notNull("outerInputOperator", outerInputOperator);
         ArgumentValidation.notNull("innerInputOperator", innerInputOperator);
         ArgumentValidation.isGTE("inputBindingPosition", inputBindingPosition, 0);
-        ArgumentValidation.isGT("depth", depth, 0);
+        if (pipeline)
+            ArgumentValidation.isGT("depth", depth, 0);
         this.outerInputOperator = outerInputOperator;
         this.innerInputOperator = innerInputOperator;
         this.inputBindingPosition = inputBindingPosition;

=== renamed file 'src/main/java/com/akiban/qp/operator/Product_NestedLoops.java' => 'src/main/java/com/akiban/qp/operator/Product_Nested.java'
--- src/main/java/com/akiban/qp/operator/Product_NestedLoops.java	2013-07-18 13:05:48 +0000
+++ src/main/java/com/akiban/qp/operator/Product_Nested.java	2013-07-18 16:47:28 +0000
@@ -22,9 +22,7 @@
 import com.akiban.qp.rowtype.ProductRowType;
 import com.akiban.qp.rowtype.RowType;
 import com.akiban.qp.rowtype.UserTableRowType;
-import com.akiban.server.explain.CompoundExplainer;
-import com.akiban.server.explain.ExplainContext;
-import com.akiban.server.explain.std.NestedLoopsExplainer;
+import com.akiban.server.explain.*;
 import com.akiban.util.ArgumentValidation;
 import com.akiban.util.ShareHolder;
 import com.akiban.util.tap.InOutTap;
@@ -39,7 +37,7 @@
 
  <h1>Overview</h1>
 
- Product_NestedLoops computes the cartesian product of child rows owned by the same parent row. For example, if customer c1 has orders o10 and o11, and addresses a10 and a11; and customer c2 has order o20 and address a20, then Product_NestedLoops computes \{o10, o11\} x \{a10, a11\} for c1, and \{o20\} x \{a20\} for c2.
+ Product_Nested computes the cartesian product of child rows owned by the same parent row. For example, if customer c1 has orders o10 and o11, and addresses a10 and a11; and customer c2 has order o20 and address a20, then Product_Nested computes \{o10, o11\} x \{a10, a11\} for c1, and \{o20\} x \{a20\} for c2.
 
  <h1>Arguments</h1>
 
@@ -48,34 +46,32 @@
  <li><b>RowType outerType:</b> Type of one child row. parent rows to be
  flattened.
 
- <li><b>UserTableRowType branchType:</b> Ancestor type of outerType and innerType. Output will consist
- of the cartesian product of outer and inner rows that match when projected to the branch type.
-
- <li><b>RowType innerType:</b> Type of the other child row.
-
- <li><b>int inputBindingPosition:</b> The position in the bindings that
+ <li><b>UserTableRowType branchType:</b> Ancestor type of outerType and inputType. Output will consist
+ of the cartesian product of outer and input rows that match when projected to the branch type.
+
+ <li><b>RowType inputType:</b> Type of the other child row.
+
+ <li><b>int bindingPosition:</b> The position in the bindings that
  will be used to pass rows from the outer loop to the inner loop.
 
  </ul>
 
- The input types must have resulted from Flattens of some common
+ The row types must have resulted from Flattens of some common
  ancestor, e.g. Flatten(customer, order) and Flatten(customer,
  address).
 
  <h1>Behavior</h1>
 
  Suppose we have a COA schema (C is the parent of O and A), and that we
- have flattened C with O, and C with A. Product_NestedLoops has two
+ have flattened C with O, and C with A. Product_Nested has two
  input streams, with CO in one and CA in the other. The branch type is C.
  For this discussion, let's assume that CO is the outer stream, and CA is in the
- inner stream. The terms "outer" and "inner" reflect the relative
- positions of the inputs in the nested loops used to compute the
- product of the inputs.
+ input stream.
 
- For each CO row from the outer input stream, a set of matching CA rows,
+ For each CO row from the outer stream, a set of matching CA rows,
  (i.e., matching in C)
- from the inner input stream are retrieved. The CO row and all of the
- CA rows will have the same customer primary key. Product_NestedLoops
+ from the input stream are retrieved. The CO row and all of the
+ CA rows will have the same customer primary key. Product_Nested
  will write to the output stream product rows for each CO/CA
  combination.
 
@@ -93,31 +89,31 @@
 
  <h1>Performance</h1>
 
- Product_NestedLoops does no IO.
-
- <h1>Memory Requirements</h1>
-
- For each outer row, all matching rows from the inner input are kept in
- memory. This avoids the need to retrieve the inner rows repeatedly in
- situations where consecutive outer rows match the same inner rows,
- e.g. for hkey-ordered outer rows.
+ Product_Nested does no IO.
 
  */
 
-class Product_NestedLoops extends Operator
+class Product_Nested extends Operator
 {
     // Object interface
 
     @Override
     public String toString()
     {
-        return String.format("%s(%s x %s)", getClass().getSimpleName(), outerType, innerType);
+        return String.format("%s(%s x %s)", getClass().getSimpleName(), outerType, inputType);
     }
 
     @Override
     public CompoundExplainer getExplainer(ExplainContext context)
     {
-        return new NestedLoopsExplainer(getName(), innerInputOperator, outerInputOperator, innerType, outerType, context);
+        Attributes atts = new Attributes();
+        
+        atts.put(Label.NAME, PrimitiveExplainer.getInstance(getName()));
+        atts.put(Label.OUTER_TYPE, outerType.getExplainer(context));
+        atts.put(Label.INNER_TYPE, inputType.getExplainer(context));
+        atts.put(Label.INPUT_OPERATOR, inputOperator.getExplainer(context));
+        atts.put(Label.BINDING_POSITION, PrimitiveExplainer.getInstance(bindingPosition));
+        return new CompoundExplainer(Type.PRODUCT_OPERATOR, atts);
     }
     
     // Operator interface
@@ -125,7 +121,7 @@
     @Override
     protected Cursor cursor(QueryContext context, QueryBindingsCursor bindingsCursor)
     {
-        return new Execution(context, bindingsCursor);
+        return new Execution(context, inputOperator.cursor(context, bindingsCursor));
     }
 
     @Override
@@ -137,8 +133,7 @@
     @Override
     public void findDerivedTypes(Set<RowType> derivedTypes)
     {
-        innerInputOperator.findDerivedTypes(derivedTypes);
-        outerInputOperator.findDerivedTypes(derivedTypes);
+        inputOperator.findDerivedTypes(derivedTypes);
         derivedTypes.add(productType);
     }
 
@@ -146,76 +141,58 @@
     public List<Operator> getInputOperators()
     {
         List<Operator> result = new ArrayList<>(2);
-        result.add(outerInputOperator);
-        result.add(innerInputOperator);
+        result.add(inputOperator);
         return result;
     }
 
     @Override
     public String describePlan()
     {
-        return describePlan(outerInputOperator);
+        return describePlan(inputOperator);
     }
 
-    // Product_NestedLoops interface
+    // Product_Nested interface
 
-    public Product_NestedLoops(Operator outerInputOperator,
-                               Operator innerInputOperator,
-                               RowType outerType,
-                               UserTableRowType branchType,
-                               RowType innerType,
-                               int inputBindingPosition)
+    public Product_Nested(Operator inputOperator,
+                          RowType outerType,
+                          UserTableRowType branchType,
+                          RowType inputType,
+                          int bindingPosition)
     {
-        ArgumentValidation.notNull("outerInputOperator", outerInputOperator);
-        ArgumentValidation.notNull("innerInputOperator", innerInputOperator);
+        ArgumentValidation.notNull("inputOperator", inputOperator);
         ArgumentValidation.notNull("outerType", outerType);
-        ArgumentValidation.notNull("innerType", innerType);
-        ArgumentValidation.isGTE("inputBindingPosition", inputBindingPosition, 0);
-        this.outerInputOperator = outerInputOperator;
-        this.innerInputOperator = innerInputOperator;
+        ArgumentValidation.notNull("inputType", inputType);
+        ArgumentValidation.isGTE("bindingPosition", bindingPosition, 0);
+        this.inputOperator = inputOperator;
         this.outerType = outerType;
-        this.innerType = innerType;
-        this.productType = outerType.schema().newProductType(outerType, branchType, innerType);
+        this.inputType = inputType;
+        this.productType = inputType.schema().newProductType(outerType, branchType, inputType);
         this.branchType = productType.branchType();
-        this.inputBindingPosition = inputBindingPosition;
+        this.bindingPosition = bindingPosition;
     }
 
     // Class state
 
-    private static InOutTap TAP_OPEN = OPERATOR_TAP.createSubsidiaryTap("operator: Product_NestedLoops open");
-    private static InOutTap TAP_NEXT = OPERATOR_TAP.createSubsidiaryTap("operator: Product_NestedLoops next");
-    private static final Logger LOG = LoggerFactory.getLogger(Product_NestedLoops.class);
+    private static InOutTap TAP_OPEN = OPERATOR_TAP.createSubsidiaryTap("operator: Product_Nested open");
+    private static InOutTap TAP_NEXT = OPERATOR_TAP.createSubsidiaryTap("operator: Product_Nested next");
+    private static final Logger LOG = LoggerFactory.getLogger(Product_Nested.class);
 
     // Object state
 
-    private final Operator outerInputOperator;
-    private final Operator innerInputOperator;
+    private final Operator inputOperator;
     private final RowType branchType;
     private final RowType outerType;
-    private final RowType innerType;
+    private final RowType inputType;
     private final ProductRowType productType;
-    private final int inputBindingPosition;
+    private final int bindingPosition;
 
     // Inner classes
 
-    private class Execution extends OperatorCursor
+    private class Execution extends ChainedCursor
     {
         // Cursor interface
 
         @Override
-        public void open()
-        {
-            TAP_OPEN.in();
-            try {
-                CursorLifecycle.checkIdle(this);
-                this.outerInput.open();
-                this.closed = false;
-            } finally {
-                TAP_OPEN.out();
-            }
-        }
-
-        @Override
         public Row next()
         {
             if (TAP_NEXT_ENABLED) {
@@ -226,38 +203,14 @@
                     CursorLifecycle.checkIdleOrActive(this);
                 }
                 checkQueryCancelation();
-                Row outputRow = null;
-                while (!closed && outputRow == null) {
-                    outputRow = nextProductRow();
-                    if (outputRow == null) {
-                        Row row = outerInput.next();
-                        if (row == null) {
-                            close();
-                        } else {
-                            RowType rowType = row.rowType();
-                            if (rowType == outerType) {
-                                Row branchRow = row.subRow(branchType);
-                                assert branchRow != null : row;
-                                if (outerBranchRow.isEmpty() || !branchRow.hKey().equals(outerBranchRow.get().hKey())) {
-                                    if (LOG_EXECUTION) {
-                                        LOG.debug("Product_NestedLoops: branch row {}", row);
-                                    }
-                                    outerBranchRow.hold(branchRow);
-                                    innerRows.newBranchRow(branchRow);
-                                }
-                                outerRow.hold(row);
-                                if (LOG_EXECUTION) {
-                                    LOG.debug("Product_NestedLoops: restart inner loop using current branch row");
-                                }
-                                innerRows.resetForCurrentBranchRow();
-                            }
-                        }
-                    }
+                Row row = input.next();
+                if ((row != null) && (row.rowType() == inputType)) {
+                    row = new ProductRow(productType, bindings.getRow(bindingPosition), row);
                 }
                 if (LOG_EXECUTION) {
-                    LOG.debug("Product_NestedLoops: yield {}", outputRow);
+                    LOG.debug("Product_Nested: yield {}", row);
                 }
-                return outputRow;
+                return row;
             } finally {
                 if (TAP_NEXT_ENABLED) {
                     TAP_NEXT.out();
@@ -265,160 +218,11 @@
             }
         }
 
-        @Override
-        public void close()
-        {
-            CursorLifecycle.checkIdleOrActive(this);
-            if (!closed) {
-                closeOuter();
-                closed = true;
-            }
-        }
-
-        @Override
-        public void destroy()
-        {
-            close();
-            outerInput.destroy();
-            innerRows.destroy();
-        }
-
-        @Override
-        public boolean isIdle()
-        {
-            return closed;
-        }
-
-        @Override
-        public boolean isActive()
-        {
-            return !closed;
-        }
-
-        @Override
-        public boolean isDestroyed()
-        {
-            return outerInput.isDestroyed();
-        }
-
-        @Override
-        public void openBindings() {
-            outerInput.openBindings();
-        }
-
-        @Override
-        public QueryBindings nextBindings() {
-            outerBindings = outerInput.nextBindings();
-            return outerBindings;
-        }
-
-        @Override
-        public void closeBindings() {
-            outerInput.closeBindings();
-        }
-
-        @Override
-        public void cancelBindings(QueryBindings bindings) {
-            closeInner();
-            outerInput.cancelBindings(bindings);
-            closed = true;
-        }
-
         // Execution interface
 
-        Execution(QueryContext context, QueryBindingsCursor bindingsCursor)
-        {
-            super(context);
-            this.outerInput = outerInputOperator.cursor(context, bindingsCursor);
-            this.innerRows = new InnerRows(context, bindingsCursor);
-        }
-
-        // For use by this class
-
-        private Row nextProductRow()
-        {
-            Row productRow = null;
-            if (outerRow.isHolding()) {
-                Row innerRow = innerRows.next();
-                if (innerRow == null) {
-                    closeInner();
-                } else {
-                    productRow = new ProductRow(productType, outerRow.get(), innerRow);
-                }
-            }
-            return productRow;
-        }
-
-        private void closeOuter()
-        {
-            closeInner();
-            outerInput.close();
-        }
-
-        private void closeInner()
-        {
-            outerRow.release();
-            innerRows.close();
-        }
-
-        // Object state
-
-        private final Cursor outerInput;
-        private final ShareHolder<Row> outerRow = new ShareHolder<>();
-        private final ShareHolder<Row> outerBranchRow = new ShareHolder<>();
-        private final InnerRows innerRows;
-        private boolean closed = true;
-        private QueryBindings outerBindings;
-
-        // Inner classes
-
-        private class InnerRows
-        {
-            public InnerRows(QueryContext context, QueryBindingsCursor bindingsCursor)
-            {
-                this.innerBindingsCursor = new SingletonQueryBindingsCursor(null);
-                this.innerInput = innerInputOperator.cursor(context, innerBindingsCursor);
-            }
-
-            public Row next()
-            {
-                return scan.next();
-            }
-
-            public void resetForCurrentBranchRow()
-            {
-                scan.reset();
-            }
-
-            public void newBranchRow(Row branchRow)
-            {
-                close();
-                outerBindings.setRow(inputBindingPosition, branchRow);
-                innerBindingsCursor.reset(outerBindings);
-                innerInput.openTopLevel();
-                rows.clear();
-                Row row;
-                while ((row = innerInput.next()) != null) {
-                    rows.add(row);
-                }
-                resetForCurrentBranchRow();
-            }
-
-            public void close()
-            {
-                innerInput.close();
-            }
-
-            public void destroy()
-            {
-                close();
-                innerInput.destroy();
-            }
-
-            private final Cursor innerInput;
-            private final RowList rows = new RowList();
-            private final RowList.Scan scan = rows.scan();
-            private final SingletonQueryBindingsCursor innerBindingsCursor;
+        Execution(QueryContext context, Cursor input)
+        {
+            super(context, input);
         }
     }
 }

=== modified file 'src/main/java/com/akiban/server/explain/Type.java'
--- src/main/java/com/akiban/server/explain/Type.java	2013-03-22 20:05:57 +0000
+++ src/main/java/com/akiban/server/explain/Type.java	2013-07-18 16:47:28 +0000
@@ -51,6 +51,7 @@
     DUI(GeneralType.OPERATOR), // delete/update/insert
     DISTINCT(GeneralType.OPERATOR),
     FLATTEN_OPERATOR(GeneralType.OPERATOR),
+    PRODUCT_OPERATOR(GeneralType.OPERATOR),
     LIMIT_OPERATOR(GeneralType.OPERATOR),
     NESTED_LOOPS(GeneralType.OPERATOR),
     IF_EMPTY(GeneralType.OPERATOR),

=== modified file 'src/main/java/com/akiban/server/explain/format/DefaultFormatter.java'
--- src/main/java/com/akiban/server/explain/format/DefaultFormatter.java	2013-03-22 20:05:57 +0000
+++ src/main/java/com/akiban/server/explain/format/DefaultFormatter.java	2013-07-18 16:47:28 +0000
@@ -233,6 +233,9 @@
         case FLATTEN_OPERATOR:
             appendFlattenOperator(name, atts);
             break;
+        case PRODUCT_OPERATOR:
+            appendProductOperator(name, atts);
+            break;
         case ORDERED:
             appendOrderedOperator(name, atts);
             break;
@@ -530,6 +533,14 @@
         }
     }
 
+    protected void appendProductOperator(String name, Attributes atts) {
+        if (levelOfDetail != LevelOfDetail.BRIEF) {
+            append(atts.getAttribute(Label.OUTER_TYPE));
+            sb.append(" x ");
+            append(atts.getAttribute(Label.INNER_TYPE));
+        }
+    }
+
     protected void appendOrderedOperator(String name, Attributes atts) {
         if (levelOfDetail != LevelOfDetail.BRIEF) {
             if (atts.containsKey(Label.UNION_OPTION) &&
@@ -586,11 +597,6 @@
             if (name.equals("Map_NestedLoops")) {
                 // Label the loop?
             }
-            else if (name.equals("Product_NestedLoops")) {
-                append(atts.getAttribute(Label.OUTER_TYPE));
-                sb.append(" x ");
-                append(atts.getAttribute(Label.INNER_TYPE));
-            }
         }
     }
 

=== modified file 'src/main/java/com/akiban/sql/optimizer/rule/OperatorAssembler.java'
--- src/main/java/com/akiban/sql/optimizer/rule/OperatorAssembler.java	2013-07-13 21:17:31 +0000
+++ src/main/java/com/akiban/sql/optimizer/rule/OperatorAssembler.java	2013-07-18 16:47:28 +0000
@@ -1472,10 +1472,12 @@
             RowStream stream;
             Group group = branchLookup.getSource().getGroup();
             if (branchLookup.getInput() == null) {
-                // Simple version for Product_NestedLoops.
+                // Simple version for Product_Nested.
                 stream = new RowStream();
                 API.InputPreservationOption flag = API.InputPreservationOption.KEEP_INPUT;
+                ColumnExpressionToIndex boundRow = boundRows.get(boundRows.size()-1);
                 stream.operator = API.branchLookup_Nested(group,
+                                                          boundRow.getRowType(),
                                                           tableRowType(branchLookup.getSource()),
                                                           tableRowType(branchLookup.getAncestor()),
                                                           tableRowType(branchLookup.getBranch()), 
@@ -1491,6 +1493,7 @@
                 ColumnExpressionToIndex boundRow = boundRows.get(rowIndex);
                 stream.operator = API.branchLookup_Nested(group,
                                                           boundRow.getRowType(),
+                                                          boundRow.getRowType(),
                                                           tableRowType(branchLookup.getAncestor()),
                                                           tableRowType(branchLookup.getBranch()), 
                                                           flag,
@@ -1546,14 +1549,12 @@
                 ancestorRowType = tableRowType(product.getAncestor());
             RowStream pstream = new RowStream();
             Flattened flattened = new Flattened();
+            pstream.fieldOffsets = flattened;
             int nbound = 0;
             for (PlanNode subplan : product.getSubplans()) {
                 if (pstream.operator != null) {
-                    // The actual bound row is the branch row, which
-                    // we don't access directly. Just give each
-                    // product a separate position; nesting doesn't
-                    // matter.
-                    pushBoundRow(null);
+                    pushBoundRow(flattened);
+                    nestedBindingsDepth++;
                     nbound++;
                 }
                 RowStream stream = assembleStream(subplan);
@@ -1562,13 +1563,18 @@
                     pstream.rowType = stream.rowType;
                 }
                 else {
-                    pstream.operator = API.product_NestedLoops(pstream.operator,
-                                                               stream.operator,
-                                                               pstream.rowType,
-                                                               ancestorRowType,
-                                                               stream.rowType,
-                                                               currentBindingPosition());
-                    pstream.rowType = pstream.operator.rowType();
+                    stream.operator = API.product_Nested(stream.operator,
+                                                         pstream.rowType,
+                                                         ancestorRowType,
+                                                         stream.rowType,
+                                                         currentBindingPosition());
+                    stream.rowType = stream.operator.rowType();
+                    pstream.operator = API.map_NestedLoops(pstream.operator,
+                                                           stream.operator,
+                                                           currentBindingPosition(),
+                                                           rulesContext.getPipelineConfiguration().isMapEnabled(),
+                                                           nestedBindingsDepth);
+                    pstream.rowType = stream.rowType;
                 }
                 if (stream.fieldOffsets instanceof ColumnSourceFieldOffsets) {
                     TableSource table = ((ColumnSourceFieldOffsets)
@@ -1578,13 +1584,13 @@
                 else {
                     flattened.product((Flattened)stream.fieldOffsets);
                 }
+                flattened.setRowType(pstream.rowType);
             }
             while (nbound > 0) {
                 popBoundRow();
+                nestedBindingsDepth--;
                 nbound--;
             }
-            flattened.setRowType(pstream.rowType);
-            pstream.fieldOffsets = flattened;
             return pstream;
         }
 

=== modified file 'src/test/java/com/akiban/server/test/it/qp/Map_NestedLoopsIT.java'
--- src/test/java/com/akiban/server/test/it/qp/Map_NestedLoopsIT.java	2013-07-15 22:46:16 +0000
+++ src/test/java/com/akiban/server/test/it/qp/Map_NestedLoopsIT.java	2013-07-18 16:47:28 +0000
@@ -120,7 +120,7 @@
     @Test(expected = IllegalArgumentException.class)
     public void testNonPositiveDepth()
     {
-        map_NestedLoops(groupScan_Default(coi), groupScan_Default(coi), 0, pipelineMap(),0);
+        map_NestedLoops(groupScan_Default(coi), groupScan_Default(coi), 0, true,0);
     }
 
     // Test operator execution

=== modified file 'src/test/java/com/akiban/server/test/it/qp/Product3WayIT.java'
--- src/test/java/com/akiban/server/test/it/qp/Product3WayIT.java	2013-07-08 20:48:05 +0000
+++ src/test/java/com/akiban/server/test/it/qp/Product3WayIT.java	2013-07-18 16:47:28 +0000
@@ -34,11 +34,6 @@
 import static com.akiban.qp.operator.API.*;
 import static org.junit.Assert.assertTrue;
 
-// Product_ByRun relies on run ids. Here is an explanation of why run ids are needed:
-// http://akibainc.onconfluence.com/display/db/Implementation+of+the+Product+operator.
-// But no other operator relies on runs, and run ids can probably be omitted if we implement
-// a nested-loops form of product. This test uses a 3-way product, the case motivating run ids.
-
 public class Product3WayIT extends OperatorITBase
 {
     @Override
@@ -134,28 +129,35 @@
             flatten_HKeyOrdered(
                 branchLookup_Nested(
                     rabc,
+                    RA.rowType(),
                     rRowType,
+                    null,
                     bRowType,
                     KEEP_INPUT,
                     0),
                 rRowType,
                 bRowType,
                 INNER_JOIN);
+        Operator RAB = product_Nested(RB, RA.rowType(), null, RB.rowType(), 0);
         Operator RC =
             flatten_HKeyOrdered(
                 branchLookup_Nested(
                     rabc,
+                    RAB.rowType(),
                     rRowType,
+                    null,
                     cRowType,
                     KEEP_INPUT,
-                    0),
+                    1),
                 rRowType,
                 cRowType,
                 INNER_JOIN);
-        Operator RAB = product_NestedLoops(RA, RB, RA.rowType(), RB.rowType(), 0);
-        Operator RABC = product_NestedLoops(RAB, RC, RAB.rowType(), RC.rowType(), 0);
-        Cursor cursor = cursor(RABC, queryContext, queryBindings);
+        Operator RABC = product_Nested(RC, RAB.rowType(), null, RC.rowType(), 1);
         RowType rabcRowType = RABC.rowType();
+        Operator plan = map_NestedLoops(
+                            map_NestedLoops(RA, RAB, 0, pipelineMap(), 1),
+                            RABC, 1, pipelineMap(), 1);
+        Cursor cursor = cursor(plan, queryContext, queryBindings);
         RowBase[] expected = new RowBase[]{
             row(rabcRowType, 1L, "r1", 13L, 1L, "a13", 15L, 1L, "b15", 17L, 1L, "c17"),
             row(rabcRowType, 1L, "r1", 13L, 1L, "a13", 15L, 1L, "b15", 18L, 1L, "c18"),
@@ -192,32 +194,39 @@
                 rRowType,
                 aRowType,
                 INNER_JOIN);
+        Operator RC =
+            flatten_HKeyOrdered(
+                branchLookup_Nested(
+                    rabc,
+                    RA.rowType(),
+                    rRowType,
+                    null,
+                    cRowType,
+                    KEEP_INPUT,
+                    0),
+                rRowType,
+                cRowType,
+                INNER_JOIN);
+        Operator RAC = product_Nested(RC, RA.rowType(), null, RC.rowType(), 0);
         Operator RB =
             flatten_HKeyOrdered(
                 branchLookup_Nested(
                     rabc,
+                    RAC.rowType(),
                     rRowType,
+                    null,
                     bRowType,
                     KEEP_INPUT,
-                    0),
+                    1),
                 rRowType,
                 bRowType,
                 INNER_JOIN);
-        Operator RC =
-            flatten_HKeyOrdered(
-                branchLookup_Nested(
-                    rabc,
-                    rRowType,
-                    cRowType,
-                    KEEP_INPUT,
-                    0),
-                rRowType,
-                cRowType,
-                INNER_JOIN);
-        Operator RAC = product_NestedLoops(RA, RC, RA.rowType(), RC.rowType(), 0);
-        Operator RACB = product_NestedLoops(RAC, RB, RAC.rowType(), RB.rowType(), 0);
-        Cursor cursor = cursor(RACB, queryContext, queryBindings);
+        Operator RACB = product_Nested(RB, RAC.rowType(), null, RB.rowType(), 1);
         RowType racbRowType = RACB.rowType();
+        Operator plan = map_NestedLoops(
+                            map_NestedLoops(RA, RAC, 0, pipelineMap(), 1),
+                            RACB, 1, pipelineMap(), 1);
+        Cursor cursor = cursor(plan, queryContext, queryBindings);
         RowBase[] expected = new RowBase[]{
             row(racbRowType, 1L, "r1", 13L, 1L, "a13", 17L, 1L, "c17", 15L, 1L, "b15"),
             row(racbRowType, 1L, "r1", 13L, 1L, "a13", 17L, 1L, "c17", 16L, 1L, "b16"),
@@ -254,39 +263,50 @@
                 branchLookup_Nested(
                     rabc,
                     rRowType,
+                    rRowType,
+                    null,
                     aRowType,
                     KEEP_INPUT,
                     0),
                 rRowType,
                 aRowType,
                 INNER_JOIN);
+        Operator RA = product_Nested(flattenRA, rRowType, null, flattenRA.rowType(), 0);
         Operator flattenRB =
             flatten_HKeyOrdered(
                 branchLookup_Nested(
                     rabc,
+                    RA.rowType(),
                     rRowType,
+                    null,
                     bRowType,
                     KEEP_INPUT,
-                    0),
+                    1),
                 rRowType,
                 bRowType,
                 INNER_JOIN);
+        Operator RAB = product_Nested(flattenRB, RA.rowType(), null, flattenRB.rowType(), 1);
         Operator flattenRC =
             flatten_HKeyOrdered(
                 branchLookup_Nested(
                     rabc,
+                    RAB.rowType(),
                     rRowType,
+                    null,
                     cRowType,
                     KEEP_INPUT,
-                    0),
+                    2),
                 rRowType,
                 cRowType,
                 INNER_JOIN);
-        Operator RA = product_NestedLoops(rScan, flattenRA, rRowType, flattenRA.rowType(), 0);
-        Operator RAB = product_NestedLoops(RA, flattenRB, RA.rowType(), flattenRB.rowType(), 0);
-        Operator RABC = product_NestedLoops(RAB, flattenRC, RAB.rowType(), flattenRC.rowType(), 0);
-        Cursor cursor = cursor(RABC, queryContext, queryBindings);
+        Operator RABC = product_Nested(flattenRC, RAB.rowType(), null, flattenRC.rowType(), 2);
         RowType rabcRowType = RABC.rowType();
+        Operator plan = map_NestedLoops(
+                            map_NestedLoops(
+                                map_NestedLoops(rScan, RA, 0, pipelineMap(), 1),
+                                RAB, 1, pipelineMap(), 1),
+                            RABC, 2, pipelineMap(), 1);
+        Cursor cursor = cursor(plan, queryContext, queryBindings);
         RowBase[] expected = new RowBase[]{
             row(rabcRowType, 1L, "r1", 13L, 1L, "a13", 15L, 1L, "b15", 17L, 1L, "c17"),
             row(rabcRowType, 1L, "r1", 13L, 1L, "a13", 15L, 1L, "b15", 18L, 1L, "c18"),

=== renamed file 'src/test/java/com/akiban/server/test/it/qp/Product_NestedLoopsIT.java' => 'src/test/java/com/akiban/server/test/it/qp/Product_NestedIT.java'
--- src/test/java/com/akiban/server/test/it/qp/Product_NestedLoopsIT.java	2013-07-08 18:16:50 +0000
+++ src/test/java/com/akiban/server/test/it/qp/Product_NestedIT.java	2013-07-18 16:47:28 +0000
@@ -33,14 +33,13 @@
 import java.util.Set;
 
 import static com.akiban.qp.operator.API.*;
-import static com.akiban.qp.operator.API.FlattenOption.KEEP_PARENT;
 import static com.akiban.qp.operator.API.JoinType.INNER_JOIN;
 import static com.akiban.qp.rowtype.RowTypeChecks.checkRowTypeFields;
 import static com.akiban.server.types.AkType.INT;
 import static com.akiban.server.types.AkType.VARCHAR;
 import static org.junit.Assert.assertTrue;
 
-public class Product_NestedLoopsIT extends OperatorITBase
+public class Product_NestedIT extends OperatorITBase
 {
     @Override
     protected void setupPostCreateSchema()
@@ -97,33 +96,27 @@
     // Test argument validation
 
     @Test(expected = IllegalArgumentException.class)
-    public void testLeftInputNull()
-    {
-        product_NestedLoops(null, groupScan_Default(coi), customerRowType, customerRowType, 0);
-    }
-
-    @Test(expected = IllegalArgumentException.class)
-    public void testRightInputNull()
-    {
-        product_NestedLoops(groupScan_Default(coi), null, customerRowType, customerRowType, 0);
+    public void testInputNull()
+    {
+        product_Nested(null, customerRowType, null, customerRowType, 0);
     }
 
     @Test(expected = IllegalArgumentException.class)
     public void testLeftTypeNull()
     {
-        product_NestedLoops(groupScan_Default(coi), groupScan_Default(coi), null, customerRowType, 0);
+        product_Nested(groupScan_Default(coi), null, null, customerRowType, 0);
     }
 
     @Test(expected = IllegalArgumentException.class)
     public void testRightTypeNull()
     {
-        product_NestedLoops(groupScan_Default(coi), groupScan_Default(coi), customerRowType, null, 0);
+        product_Nested(groupScan_Default(coi), customerRowType, null, null, 0);
     }
 
     @Test(expected = IllegalArgumentException.class)
     public void testNegativeInputBindingPosition()
     {
-        product_NestedLoops(groupScan_Default(coi), groupScan_Default(coi), customerRowType, customerRowType, -1);
+        product_Nested(groupScan_Default(coi), customerRowType, null, customerRowType, -1);
     }
 
     // Test operator execution
@@ -150,17 +143,17 @@
                     removeDescendentTypes(orderRowType)),
                 customerRowType,
                 orderRowType,
-                INNER_JOIN,
-                KEEP_PARENT);
+                INNER_JOIN);
         Operator flattenCA =
             flatten_HKeyOrdered(
-                branchLookup_Nested(coi, customerRowType, addressRowType, InputPreservationOption.KEEP_INPUT, 0),
+                branchLookup_Nested(coi, flattenCO.rowType(), customerRowType, null, addressRowType, InputPreservationOption.KEEP_INPUT, 0),
                 customerRowType,
                 addressRowType,
                 INNER_JOIN);
-        Operator plan = product_NestedLoops(flattenCO, flattenCA, flattenCO.rowType(), flattenCA.rowType(), 0);
-        RowType coaRowType = plan.rowType();
+        Operator product = product_Nested(flattenCA, flattenCO.rowType(), null, flattenCA.rowType(), 0);
+        RowType coaRowType = product.rowType();
         checkRowTypeFields(coaRowType, INT, VARCHAR, INT, INT, VARCHAR, INT, INT, VARCHAR);
+        Operator plan = map_NestedLoops(flattenCO, product, 0, pipelineMap(), 1);
         Cursor cursor = cursor(plan, queryContext, queryBindings);
         RowBase[] expected = new RowBase[]{
             row(coaRowType, 2L, "foundation", 200L, 2L, "david", 2000L, 2L, "222 2000 st"),
@@ -191,13 +184,14 @@
                 INNER_JOIN);
         Operator flattenCA =
             flatten_HKeyOrdered(
-                branchLookup_Nested(coi, customerRowType, addressRowType, InputPreservationOption.KEEP_INPUT, 0),
+                branchLookup_Nested(coi, flattenCO.rowType(), customerRowType, null, addressRowType, InputPreservationOption.KEEP_INPUT, 0),
                 customerRowType,
                 addressRowType,
                 INNER_JOIN);
-        Operator plan = product_NestedLoops(flattenCO, flattenCA, flattenCO.rowType(), flattenCA.rowType(), 0);
-        RowType coaRowType = plan.rowType();
+        Operator product = product_Nested(flattenCA, flattenCO.rowType(), null, flattenCA.rowType(), 0);
+        RowType coaRowType = product.rowType();
         checkRowTypeFields(coaRowType, INT, VARCHAR, INT, INT, VARCHAR, INT, INT, VARCHAR);
+        Operator plan = map_NestedLoops(flattenCO, product, 0, pipelineMap(), 1);
         Cursor cursor = cursor(plan, queryContext, queryBindings);
         RowBase[] expected = new RowBase[]{
             row(coaRowType, 2L, "foundation", 200L, 2L, "david", 2000L, 2L, "222 2000 st"),
@@ -222,12 +216,12 @@
                     Arrays.asList(customerRowType, addressRowType)),
                 customerRowType,
                 addressRowType,
-                JoinType.LEFT_JOIN,
-                FlattenOption.KEEP_PARENT);
+                JoinType.LEFT_JOIN);
         Operator flattenCAInner =
             flatten_HKeyOrdered(
                 branchLookup_Nested(
                     coi,
+                    flattenCAOuter.rowType(),
                     customerRowType,
                     customerRowType,
                     addressRowType,
@@ -237,14 +231,14 @@
                 addressRowType,
                 JoinType.LEFT_JOIN);
         Operator product =
-            product_NestedLoops(
-                flattenCAOuter,
+            product_Nested(
                 flattenCAInner,
                 flattenCAOuter.rowType(),
                 customerRowType,
                 flattenCAInner.rowType(),
                 0);
         RowType productRowType = product.rowType();
+        Operator plan = map_NestedLoops(flattenCAOuter, product, 0, pipelineMap(), 1);
         RowBase[] expected = new RowBase[]{
             row(productRowType, 1L, "northbridge", 1000L, 1L, "111 1000 st", 1000L, 1L, "111 1000 st"),
             row(productRowType, 1L, "northbridge", 1000L, 1L, "111 1000 st", 1001L, 1L, "111 1001 st"),
@@ -262,7 +256,7 @@
             row(productRowType, 5L, "highland", 5001L, 5L, "555 5001 st", 5001, 5L, "555 5001 st"),
             row(productRowType, 6L, "flybridge", null, null, null, null, null, null),
         };
-        compareRows(expected, cursor(product, queryContext, queryBindings));
+        compareRows(expected, cursor(plan, queryContext, queryBindings));
     }
 
     @Test
@@ -285,16 +279,16 @@
                     removeDescendentTypes(orderRowType)),
                 customerRowType,
                 orderRowType,
-                INNER_JOIN,
-                KEEP_PARENT);
+                INNER_JOIN);
         Operator flattenCA =
             flatten_HKeyOrdered(
-                branchLookup_Nested(coi, customerRowType, addressRowType, InputPreservationOption.KEEP_INPUT, 0),
+                branchLookup_Nested(coi, flattenCO.rowType(), customerRowType, null, addressRowType, InputPreservationOption.KEEP_INPUT, 0),
                 customerRowType,
                 addressRowType,
                 INNER_JOIN);
-        Operator plan = product_NestedLoops(flattenCO, flattenCA, flattenCO.rowType(), flattenCA.rowType(), 0);
-        final RowType coaRowType = plan.rowType();
+        Operator product = product_Nested(flattenCA, flattenCO.rowType(), null, flattenCA.rowType(), 0);
+        final RowType coaRowType = product.rowType();
+        Operator plan = map_NestedLoops(flattenCO, product, 0, pipelineMap(), 1);
         CursorLifecycleTestCase testCase = new CursorLifecycleTestCase()
         {
             @Override

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiindex-multi-duplicate.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiindex-multi-duplicate.expected	2012-08-29 13:38:58 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiindex-multi-duplicate.expected	2013-07-18 16:47:28 +0000
@@ -1,14 +1,15 @@
 PhysicalSelect[quan:int[INT], quan:int[INT]]
   Project_Default(i1.quan, i2.quan)
-    Product_NestedLoops(customers - orders - items x customers - orders - items)
+    Map_NestedLoops()
       Flatten_HKeyOrdered(customers - orders INNER items)
         Flatten_HKeyOrdered(customers INNER orders)
           AncestorLookup_Default(Index(items.sku) -> customers, orders, items)
             Intersect_Ordered(skip 1 left, skip 1 right, compare 1)
               IndexScan_Default(Index(items.sku), sku = '1234')
               IndexScan_Default(Index(items.sku), sku = '4567')
-      Filter_Default(customers - orders - items)
-        Flatten_HKeyOrdered(customers - orders INNER items)
-          Flatten_HKeyOrdered(customers INNER orders)
-            Select_HKeyOrdered(i2.sku == '4567')
-              BranchLookup_Nested(customers -> orders)
\ No newline at end of file
+      Product_Nested(customers - orders - items x customers - orders - items)
+        Filter_Default(customers - orders - items)
+          Flatten_HKeyOrdered(customers - orders INNER items)
+            Flatten_HKeyOrdered(customers INNER orders)
+              Select_HKeyOrdered(i2.sku == '4567')
+                BranchLookup_Nested(customers -> orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiindex-multi-ordered.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiindex-multi-ordered.expected	2012-08-29 13:38:58 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiindex-multi-ordered.expected	2013-07-18 16:47:28 +0000
@@ -1,14 +1,15 @@
 PhysicalSelect[quan:int[INT], quan:int[INT]]
   Project_Default(i1.quan, i2.quan)
-    Product_NestedLoops(customers - orders - items x customers - orders - items)
+    Map_NestedLoops()
       Flatten_HKeyOrdered(customers - orders INNER items)
         Flatten_HKeyOrdered(customers INNER orders)
           AncestorLookup_Default(Index(items.sku) -> customers, orders, items)
             Intersect_Ordered(skip 1 left, skip 1 right, compare 1)
               IndexScan_Default(Index(items.sku), sku = '1234', orders.cid DESC, oid, iid)
               IndexScan_Default(Index(items.sku), sku = '4567', orders.cid DESC, oid, iid)
-      Filter_Default(customers - orders - items)
-        Flatten_HKeyOrdered(customers - orders INNER items)
-          Flatten_HKeyOrdered(customers INNER orders)
-            Select_HKeyOrdered(i2.sku == '4567')
-              BranchLookup_Nested(customers -> orders)
\ No newline at end of file
+      Product_Nested(customers - orders - items x customers - orders - items)
+        Filter_Default(customers - orders - items)
+          Flatten_HKeyOrdered(customers - orders INNER items)
+            Flatten_HKeyOrdered(customers INNER orders)
+              Select_HKeyOrdered(i2.sku == '4567')
+                BranchLookup_Nested(customers -> orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiple-table-conds-1.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiple-table-conds-1.expected	2012-10-19 19:07:51 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiple-table-conds-1.expected	2013-07-18 16:47:28 +0000
@@ -3,13 +3,14 @@
     AncestorLookup_Default(Index(parent.PRIMARY) -> parent)
       IndexScan_Default(Index(parent.PRIMARY), id > 1)
     Project_Default(customers.cid)
-      Product_NestedLoops(customers - items x customers - addresses)
+      Map_NestedLoops()
         Flatten_HKeyOrdered(customers INNER items)
           Select_HKeyOrdered(items.quan > 100)
             AncestorLookup_Default(Index(customers.cname_and_sku) -> customers, items)
               IndexScan_Default(Index(customers.cname_and_sku), customers.name = parent.name, items.sku = '1234')
-        Select_HKeyOrdered(addresses.city != customers.name)
-          Filter_Default(customers - addresses)
-            Flatten_HKeyOrdered(customers INNER addresses)
-              Select_HKeyOrdered(parent.state == addresses.state)
-                BranchLookup_Nested(customers -> addresses)
+        Product_Nested(customers - items x customers - addresses)
+          Select_HKeyOrdered(addresses.city != customers.name)
+            Filter_Default(customers - addresses)
+              Flatten_HKeyOrdered(customers INNER addresses)
+                Select_HKeyOrdered(parent.state == addresses.state)
+                  BranchLookup_Nested(customers -> addresses)

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiple-table-conds-1.t3expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiple-table-conds-1.t3expected	2012-10-20 04:06:22 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/cbo/multiple-table-conds-1.t3expected	2013-07-18 16:47:28 +0000
@@ -3,13 +3,14 @@
     AncestorLookup_Default(Index(parent.PRIMARY) -> parent)
       IndexScan_Default(Index(parent.PRIMARY), id > 1)
     Project_Default(customers.cid)
-      Product_NestedLoops(customers - items x customers - addresses)
+      Map_NestedLoops()
         Flatten_HKeyOrdered(customers INNER items)
           Select_HKeyOrdered(items.quan > 100)
             AncestorLookup_Default(Index(customers.cname_and_sku) -> customers, items)
               IndexScan_Default(Index(customers.cname_and_sku), customers.name = parent.name, items.sku = '1234')
-        Select_HKeyOrdered(addresses.city != customers.name)
-          Filter_Default(customers - addresses)
-            Flatten_HKeyOrdered(customers INNER addresses)
-              Select_HKeyOrdered(parent.state == addresses.state)
-                BranchLookup_Nested(customers -> addresses)
\ No newline at end of file
+        Product_Nested(customers - items x customers - addresses)
+          Select_HKeyOrdered(addresses.city != customers.name)
+            Filter_Default(customers - addresses)
+              Flatten_HKeyOrdered(customers INNER addresses)
+                Select_HKeyOrdered(parent.state == addresses.state)
+                  BranchLookup_Nested(customers -> addresses)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/coia-group-index/select-17bu.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/coia-group-index/select-17bu.expected	2013-06-06 19:56:32 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/coia-group-index/select-17bu.expected	2013-07-18 16:47:28 +0000
@@ -1,7 +1,7 @@
 PhysicalSelect[name:varchar(32)[VARCHAR], quan:int[INT]]
   Project_Default(customers.name, items.quan)
     Sort_General(items.quan DESC)
-      Product_NestedLoops(customers - addresses x customers - orders - items)
+      Map_NestedLoops()
         Flatten_HKeyOrdered(customers INNER addresses)
           AncestorLookup_Default(Index(addresses.state) -> customers, addresses)
             UnionAll_Default()
@@ -9,7 +9,8 @@
                 IndexScan_Default(Index(addresses.state), state = 'MA', cid ASC, aid)
                 IndexScan_Default(Index(addresses.state), state = 'NY', cid ASC, aid)
               IndexScan_Default(Index(addresses.state), state = 'VT', cid ASC, aid)
-        Filter_Default(customers - orders - items)
-          Flatten_HKeyOrdered(customers - orders INNER items)
-            Flatten_HKeyOrdered(customers INNER orders)
-              BranchLookup_Nested(customers -> orders)
\ No newline at end of file
+        Product_Nested(customers - addresses x customers - orders - items)
+          Filter_Default(customers - orders - items)
+            Flatten_HKeyOrdered(customers - orders INNER items)
+              Flatten_HKeyOrdered(customers INNER orders)
+                BranchLookup_Nested(customers -> orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/coia-text-index/full-text-2.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/coia-text-index/full-text-2.expected	2013-03-06 16:01:20 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/coia-text-index/full-text-2.expected	2013-07-18 16:47:28 +0000
@@ -1,11 +1,12 @@
 PhysicalSelect[cid:int[INT], name:varchar(32)[VARCHAR], oid:int[INT], cid:int[INT], order_date:date[DATE], iid:int[INT], oid:int[INT], sku:varchar(32)[VARCHAR], quan:int[INT], aid:int[INT], cid:int[INT], state:char(2)[VARCHAR], city:varchar(100)[VARCHAR]]
   Project_Default(customers.cid, customers.name, orders.oid, orders.cid, orders.order_date, items.iid, items.oid, items.sku, items.quan, addresses.aid, addresses.cid, addresses.state, addresses.city)
-    Product_NestedLoops(customers - addresses x customers - orders - items)
+    Map_NestedLoops()
       Filter_Default(customers - addresses)
         Flatten_HKeyOrdered(customers INNER addresses)
           BranchLookup_Default(HKey -> customers)
             IndexScan_FullText(test.customers.cust_ft, +state:MA +sku:1234)
-      Filter_Default(customers - orders - items)
-        Flatten_HKeyOrdered(customers - orders INNER items)
-          Flatten_HKeyOrdered(customers INNER orders)
-            BranchLookup_Nested(customers -> orders)
\ No newline at end of file
+      Product_Nested(customers - addresses x customers - orders - items)
+        Filter_Default(customers - orders - items)
+          Flatten_HKeyOrdered(customers - orders INNER items)
+            Flatten_HKeyOrdered(customers INNER orders)
+              BranchLookup_Nested(customers -> orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/coia-text-index/full-text-2n.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/coia-text-index/full-text-2n.expected	2013-03-06 16:01:20 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/coia-text-index/full-text-2n.expected	2013-07-18 16:47:28 +0000
@@ -1,11 +1,12 @@
 PhysicalSelect[cid:int[INT], name:varchar(32)[VARCHAR], oid:int[INT], cid:int[INT], order_date:date[DATE], iid:int[INT], oid:int[INT], sku:varchar(32)[VARCHAR], quan:int[INT], aid:int[INT], cid:int[INT], state:char(2)[VARCHAR], city:varchar(100)[VARCHAR]]
   Project_Default(customers.cid, customers.name, orders.oid, orders.cid, orders.order_date, items.iid, items.oid, items.sku, items.quan, addresses.aid, addresses.cid, addresses.state, addresses.city)
-    Product_NestedLoops(customers - addresses x customers - orders - items)
+    Map_NestedLoops()
       Filter_Default(customers - addresses)
         Flatten_HKeyOrdered(customers INNER addresses)
           BranchLookup_Default(HKey -> customers)
             IndexScan_FullText(test.customers.cust_ft, -state:MA +sku:1234)
-      Filter_Default(customers - orders - items)
-        Flatten_HKeyOrdered(customers - orders INNER items)
-          Flatten_HKeyOrdered(customers INNER orders)
-            BranchLookup_Nested(customers -> orders)
\ No newline at end of file
+      Product_Nested(customers - addresses x customers - orders - items)
+        Filter_Default(customers - orders - items)
+          Flatten_HKeyOrdered(customers - orders INNER items)
+            Flatten_HKeyOrdered(customers INNER orders)
+              BranchLookup_Nested(customers -> orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/coia-text-index/full-text-2v.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/coia-text-index/full-text-2v.expected	2013-03-06 16:01:20 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/coia-text-index/full-text-2v.expected	2013-07-18 16:47:28 +0000
@@ -1,11 +1,12 @@
 PhysicalSelect[CHAR(2) CHARACTER SET utf8 COLLATE utf8_bin, VARCHAR(32) CHARACTER SET utf8 COLLATE utf8_bin][cid:int[INT], name:varchar(32)[VARCHAR], oid:int[INT], cid:int[INT], order_date:date[DATE], iid:int[INT], oid:int[INT], sku:varchar(32)[VARCHAR], quan:int[INT], aid:int[INT], cid:int[INT], state:char(2)[VARCHAR], city:varchar(100)[VARCHAR]]
   Project_Default(customers.cid, customers.name, orders.oid, orders.cid, orders.order_date, items.iid, items.oid, items.sku, items.quan, addresses.aid, addresses.cid, addresses.state, addresses.city)
-    Product_NestedLoops(customers - addresses x customers - orders - items)
+    Map_NestedLoops()
       Filter_Default(customers - addresses)
         Flatten_HKeyOrdered(customers INNER addresses)
           BranchLookup_Default(HKey -> customers)
             IndexScan_FullText(test.customers.cust_ft, TERM($1), TERM($2))
-      Filter_Default(customers - orders - items)
-        Flatten_HKeyOrdered(customers - orders INNER items)
-          Flatten_HKeyOrdered(customers INNER orders)
-            BranchLookup_Nested(customers -> orders)
\ No newline at end of file
+      Product_Nested(customers - addresses x customers - orders - items)
+        Filter_Default(customers - orders - items)
+          Flatten_HKeyOrdered(customers - orders INNER items)
+            Flatten_HKeyOrdered(customers INNER orders)
+              BranchLookup_Nested(customers -> orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/coia/select-2.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/coia/select-2.expected	2012-08-26 04:29:21 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/coia/select-2.expected	2013-07-18 16:47:28 +0000
@@ -1,9 +1,10 @@
 PhysicalSelect[name:varchar(32)[VARCHAR], order_date:date[DATE], city:varchar(100)[VARCHAR]]
   Project_Default(customers.name, orders.order_date, addresses.city)
-    Product_NestedLoops(customers - addresses x customers - orders)
+    Map_NestedLoops()
       Flatten_HKeyOrdered(customers INNER addresses)
         AncestorLookup_Default(Index(addresses.state) -> customers, addresses)
           IndexScan_Default(Index(addresses.state), state = 'MA')
-      Filter_Default(customers - orders)
-        Flatten_HKeyOrdered(customers INNER orders)
-          BranchLookup_Nested(customers -> orders)
\ No newline at end of file
+      Product_Nested(customers - addresses x customers - orders)
+        Filter_Default(customers - orders)
+          Flatten_HKeyOrdered(customers INNER orders)
+            BranchLookup_Nested(customers -> orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/coia/select-5.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/coia/select-5.expected	2012-08-26 04:29:21 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/coia/select-5.expected	2013-07-18 16:47:28 +0000
@@ -1,10 +1,11 @@
 PhysicalSelect[name:varchar(32)[VARCHAR], order_date:date[DATE], state:char(2)[VARCHAR]]
   Project_Default(customers.name, orders.order_date, addresses.state)
-    Product_NestedLoops(customers - addresses x customers - orders)
+    Map_NestedLoops()
       Filter_Default(customers - addresses)
         Flatten_HKeyOrdered(customers INNER addresses)
           BranchLookup_Default(Index(customers.name) -> customers)
             IndexScan_Default(Index(customers.name), name = 'IBM')
-      Filter_Default(customers - orders)
-        Flatten_HKeyOrdered(customers INNER orders)
-          BranchLookup_Nested(customers -> orders)
\ No newline at end of file
+      Product_Nested(customers - addresses x customers - orders)
+        Filter_Default(customers - orders)
+          Flatten_HKeyOrdered(customers INNER orders)
+            BranchLookup_Nested(customers -> orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/coia/select-6.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/coia/select-6.expected	2012-08-26 04:29:21 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/coia/select-6.expected	2013-07-18 16:47:28 +0000
@@ -1,9 +1,10 @@
 PhysicalSelect[name:varchar(32)[VARCHAR], order_date:date[DATE], state:char(2)[VARCHAR]]
   Project_Default(customers.name, orders.order_date, addresses.state)
-    Product_NestedLoops(customers - orders x customers - addresses)
+    Map_NestedLoops()
       Flatten_HKeyOrdered(customers INNER orders)
         AncestorLookup_Default(Index(orders.order_date) -> customers, orders)
           IndexScan_Default(Index(orders.order_date), order_date > DATE '2011-01-01')
-      Filter_Default(customers - addresses)
-        Flatten_HKeyOrdered(customers INNER addresses)
-          BranchLookup_Nested(customers -> addresses)
\ No newline at end of file
+      Product_Nested(customers - orders x customers - addresses)
+        Filter_Default(customers - addresses)
+          Flatten_HKeyOrdered(customers INNER addresses)
+            BranchLookup_Nested(customers -> addresses)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/coia/select-7.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/coia/select-7.expected	2012-08-26 04:29:21 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/coia/select-7.expected	2013-07-18 16:47:28 +0000
@@ -1,12 +1,13 @@
 PhysicalSelect[name:varchar(32)[VARCHAR], order_date:date[DATE], sku:varchar(32)[VARCHAR], state:char(2)[VARCHAR]]
   Project_Default(customers.name, orders.order_date, items.sku, addresses.state)
-    Product_NestedLoops(customers - orders - items x customers - addresses)
+    Map_NestedLoops()
       Filter_Default(customers - orders - items)
         Flatten_HKeyOrdered(customers - orders INNER items)
           Flatten_HKeyOrdered(customers INNER orders)
             AncestorLookup_Default(orders -> customers)
               BranchLookup_Default(Index(orders.order_date) -> orders)
                 IndexScan_Default(Index(orders.order_date), order_date > DATE '2011-01-01')
-      Filter_Default(customers - addresses)
-        Flatten_HKeyOrdered(customers INNER addresses)
-          BranchLookup_Nested(customers -> addresses)
\ No newline at end of file
+      Product_Nested(customers - orders - items x customers - addresses)
+        Filter_Default(customers - addresses)
+          Flatten_HKeyOrdered(customers INNER addresses)
+            BranchLookup_Nested(customers -> addresses)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/operator/coia/select-8.expected'
--- src/test/resources/com/akiban/sql/optimizer/operator/coia/select-8.expected	2012-08-26 04:29:21 +0000
+++ src/test/resources/com/akiban/sql/optimizer/operator/coia/select-8.expected	2013-07-18 16:47:28 +0000
@@ -1,10 +1,11 @@
 PhysicalSelect[name:varchar(32)[VARCHAR], order_date:date[DATE], sku:varchar(32)[VARCHAR], quan:int[INT], state:char(2)[VARCHAR]]
   Project_Default(customers.name, orders.order_date, items.sku, items.quan, addresses.state)
-    Product_NestedLoops(customers - addresses x customers - orders - items)
+    Map_NestedLoops()
       Filter_Default(customers - addresses)
         Flatten_HKeyOrdered(customers INNER addresses)
           GroupScan_Default(customers)
-      Filter_Default(customers - orders - items)
-        Flatten_HKeyOrdered(customers - orders INNER items)
-          Flatten_HKeyOrdered(customers INNER orders)
-            BranchLookup_Nested(customers -> orders)
\ No newline at end of file
+      Product_Nested(customers - addresses x customers - orders - items)
+        Filter_Default(customers - orders - items)
+          Flatten_HKeyOrdered(customers - orders INNER items)
+            Flatten_HKeyOrdered(customers INNER orders)
+              BranchLookup_Nested(customers -> orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/rule/operator/full-text-2.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/operator/full-text-2.expected	2013-03-06 16:01:20 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/operator/full-text-2.expected	2013-07-18 16:47:28 +0000
@@ -1,11 +1,12 @@
 PhysicalSelect@2fc5027d[cid, name, oid, cid, order_date, iid, oid, sku, quan, price, aid, cid, state, city]
   Project_Default(Field(0), Field(1), Field(6), Field(7), Field(8), Field(9), Field(10), Field(11), Field(12), Field(13), Field(2), Field(3), Field(4), Field(5))
-    Product_NestedLoops(test.customers - test.addresses x test.customers - test.orders - test.items)
+    Map_NestedLoops()
       Filter_Default(test.customers - test.addresses)
         Flatten_HKeyOrdered(test.customers INNER test.addresses)
           BranchLookup_Default(HKey -> test.customers)
             IndexScan_FullText(test.customers.cust_ft, +state:MA +sku:1234)
-      Filter_Default(test.customers - test.orders - test.items)
-        Flatten_HKeyOrdered(test.customers - test.orders INNER test.items)
-          Flatten_HKeyOrdered(test.customers INNER test.orders)
-            BranchLookup_Nested(test.customers -> test.orders)
\ No newline at end of file
+      Product_Nested(test.customers - test.addresses x test.customers - test.orders - test.items)
+        Filter_Default(test.customers - test.orders - test.items)
+          Flatten_HKeyOrdered(test.customers - test.orders INNER test.items)
+            Flatten_HKeyOrdered(test.customers INNER test.orders)
+              BranchLookup_Nested(test.customers -> test.orders)
\ No newline at end of file

=== modified file 'src/test/resources/com/akiban/sql/optimizer/rule/operator/select-5.expected'
--- src/test/resources/com/akiban/sql/optimizer/rule/operator/select-5.expected	2012-08-26 04:55:19 +0000
+++ src/test/resources/com/akiban/sql/optimizer/rule/operator/select-5.expected	2013-07-18 16:47:28 +0000
@@ -1,10 +1,11 @@
 PhysicalSelect@bd056de[name, order_date, state]
   Project_Default(Field(1), Field(8), Field(4))
-    Product_NestedLoops(test.customers - test.addresses x test.customers - test.orders)
+    Map_NestedLoops()
       Filter_Default(test.customers - test.addresses)
         Flatten_HKeyOrdered(test.customers INNER test.addresses)
           BranchLookup_Default(Index(test.customers.name) -> test.customers)
             IndexScan_Default(Index(test.customers.name), name = 'IBM', cid ASC)
-      Filter_Default(test.customers - test.orders)
-        Flatten_HKeyOrdered(test.customers INNER test.orders)
-          BranchLookup_Nested(test.customers -> test.orders)
\ No newline at end of file
+      Product_Nested(test.customers - test.addresses x test.customers - test.orders)
+        Filter_Default(test.customers - test.orders)
+          Flatten_HKeyOrdered(test.customers INNER test.orders)
+            BranchLookup_Nested(test.customers -> test.orders)
\ No newline at end of file