Fix issue849.

Change-Id: I4d2933c94c4139a6c8e2cf15e3cd1f6a52335f6b
Reviewed-on: http://fulliautomatix.ics.uci.edu:8443/217
Tested-by: Jenkins <jenkins@fulliautomatix.ics.uci.edu>
Reviewed-by: Young-Seok Kim <kisskys@gmail.com>
Reviewed-by: Steven Jacobs <sjaco002@ucr.edu>
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java
index 4e880585..eff40e3 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java
@@ -51,6 +51,7 @@
 import edu.uci.ics.asterix.optimizer.rules.PushProperJoinThroughProduct;
 import edu.uci.ics.asterix.optimizer.rules.PushSimilarityFunctionsBelowJoin;
 import edu.uci.ics.asterix.optimizer.rules.RemoveRedundantListifyRule;
+import edu.uci.ics.asterix.optimizer.rules.RemoveRedundantSelectRule;
 import edu.uci.ics.asterix.optimizer.rules.RemoveSortInFeedIngestionRule;
 import edu.uci.ics.asterix.optimizer.rules.RemoveUnusedOneToOneEquiJoinRule;
 import edu.uci.ics.asterix.optimizer.rules.ReplaceSinkOpWithCommitOpRule;
@@ -90,7 +91,6 @@
 import edu.uci.ics.hyracks.algebricks.rewriter.rules.IntroduceGroupByForSubplanRule;
 import edu.uci.ics.hyracks.algebricks.rewriter.rules.IntroduceProjectsRule;
 import edu.uci.ics.hyracks.algebricks.rewriter.rules.IsolateHyracksOperatorsRule;
-import edu.uci.ics.hyracks.algebricks.rewriter.rules.LeftOuterJoinToInnerJoinRule;
 import edu.uci.ics.hyracks.algebricks.rewriter.rules.MoveFreeVariableOperatorOutOfSubplanRule;
 import edu.uci.ics.hyracks.algebricks.rewriter.rules.NestedSubplanToJoinRule;
 import edu.uci.ics.hyracks.algebricks.rewriter.rules.PullSelectOutOfEqJoin;
@@ -148,6 +148,7 @@
         normalization.add(new IntroduceEnforcedListTypeRule());
         normalization.add(new ExtractCommonExpressionsRule());
         normalization.add(new ConstantFoldingRule());
+        normalization.add(new RemoveRedundantSelectRule());
         normalization.add(new UnnestToDataScanRule());
         normalization.add(new IfElseToSwitchCaseFunctionRule());
         normalization.add(new FuzzyEqRule());
@@ -185,7 +186,6 @@
         condPushDownAndJoinInference.add(new PushGroupByThroughProduct());
         condPushDownAndJoinInference.add(new NestGroupByRule());
         condPushDownAndJoinInference.add(new EliminateGroupByEmptyKeyRule());
-        condPushDownAndJoinInference.add(new LeftOuterJoinToInnerJoinRule());
         condPushDownAndJoinInference.add(new PushSubplanIntoGroupByRule());
         condPushDownAndJoinInference.add(new NestedSubplanToJoinRule());
         condPushDownAndJoinInference.add(new EliminateSubplanWithInputCardinalityOneRule());
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/CancelUnnestWithNestedListifyRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/CancelUnnestWithNestedListifyRule.java
index 7474e61..0f45605 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/CancelUnnestWithNestedListifyRule.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/CancelUnnestWithNestedListifyRule.java
@@ -25,7 +25,6 @@
 import edu.uci.ics.asterix.aql.util.FunctionUtils;
 import edu.uci.ics.asterix.om.functions.AsterixBuiltinFunctions;
 import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
-import edu.uci.ics.hyracks.algebricks.common.utils.Pair;
 import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
 import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
 import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalPlan;
@@ -42,8 +41,6 @@
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AggregateOperator;
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.OrderOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.OrderOperator.IOrder;
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.RunningAggregateOperator;
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnnestOperator;
 import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
@@ -187,6 +184,7 @@
             return false;
         }
         AggregateOperator agg = (AggregateOperator) nestedPlanRoot;
+        Mutable<ILogicalOperator> aggInputOpRef = agg.getInputs().get(0);
 
         if (agg.getVariables().size() > 1) {
             return false;
@@ -219,13 +217,7 @@
 
         LogicalVariable posVar = unnest1.getPositionalVariable();
         if (posVar == null) {
-            ArrayList<ILogicalOperator> neededAssigns = new ArrayList<ILogicalOperator>();
-
-            if (agg.getInputs().get(0).getValue().getOperatorTag() == LogicalOperatorTag.ASSIGN) {
-                getNeededAssigns(agg.getInputs().get(0).getValue(), neededAssigns);
-            }
-
-            // create assignment for group-by keys
+            // Creates assignment for group-by keys.
             ArrayList<LogicalVariable> gbyKeyAssgnVars = new ArrayList<LogicalVariable>();
             ArrayList<Mutable<ILogicalExpression>> gbyKeyAssgnExprs = new ArrayList<Mutable<ILogicalExpression>>();
             for (int i = 0; i < gby.getGroupByList().size(); i++) {
@@ -235,33 +227,23 @@
                 }
             }
 
+            // Moves the nested pipeline before aggregation out of the group-by op.
+            Mutable<ILogicalOperator> bottomOpRef = aggInputOpRef;
+            AbstractLogicalOperator bottomOp = (AbstractLogicalOperator) bottomOpRef.getValue();
+            while (bottomOp.getOperatorTag() != LogicalOperatorTag.NESTEDTUPLESOURCE) {
+                bottomOpRef = bottomOp.getInputs().get(0);
+                bottomOp = (AbstractLogicalOperator) bottomOpRef.getValue();
+            }
+
+            // Removes the group-by operator.
+            opRef.setValue(assign);
+            assign.getInputs().add(aggInputOpRef);
             AssignOperator gbyKeyAssign = new AssignOperator(gbyKeyAssgnVars, gbyKeyAssgnExprs);
             gbyKeyAssign.getInputs().add(gby.getInputs().get(0));
-
-            // add sort to replace group-by
-            List<Pair<IOrder, Mutable<ILogicalExpression>>> orderExprs = new ArrayList<Pair<IOrder, Mutable<ILogicalExpression>>>();
-            for (Pair<LogicalVariable, Mutable<ILogicalExpression>> k : gby.getGroupByList()) {
-                orderExprs.add(new Pair<IOrder, Mutable<ILogicalExpression>>(OrderOperator.ASC_ORDER, k.second));
-            }
-
-            OrderOperator order = new OrderOperator(orderExprs);
-
-            if (neededAssigns.size() < 1) {
-                order.getInputs().add(new MutableObject<ILogicalOperator>(gbyKeyAssign));
-            } else {
-                order.getInputs().add(new MutableObject<ILogicalOperator>(neededAssigns.get(0)));
-                neededAssigns.get(neededAssigns.size() - 1).getInputs().clear();
-                neededAssigns.get(neededAssigns.size() - 1).getInputs()
-                        .add(new MutableObject<ILogicalOperator>(gbyKeyAssign));
-            }
-
-            opRef.setValue(assign);
-            assign.getInputs().add(new MutableObject<ILogicalOperator>(order));
+            bottomOpRef.setValue(gbyKeyAssign);
 
             context.computeAndSetTypeEnvironmentForOperator(gbyKeyAssign);
-            context.computeAndSetTypeEnvironmentForOperator(order);
             context.computeAndSetTypeEnvironmentForOperator(assign);
-
         } else {
             // if positional variable is used in unnest, the unnest will be pushed into the group-by as a running-aggregate
 
@@ -297,11 +279,4 @@
 
         return true;
     }
-
-    private void getNeededAssigns(ILogicalOperator assign, ArrayList<ILogicalOperator> assigns) {
-        assigns.add(assign);
-        if (assign.getInputs().get(0).getValue().getOperatorTag() == LogicalOperatorTag.ASSIGN) {
-            getNeededAssigns(assign.getInputs().get(0).getValue(), assigns);
-        }
-    }
 }
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/RemoveRedundantSelectRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/RemoveRedundantSelectRule.java
new file mode 100644
index 0000000..94109dd
--- /dev/null
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/RemoveRedundantSelectRule.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.asterix.optimizer.rules;
+
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.asterix.om.base.ABoolean;
+import edu.uci.ics.asterix.om.constants.AsterixConstantValue;
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+/**
+ * This rule removes redundant select operator, e.g., select operators
+ * in which the condition is TRUE.
+ * Note that the ConstantFoldingRule will evaluate the condition expression
+ * during compile time if it is possible.
+ * 
+ * @author yingyib
+ */
+public class RemoveRedundantSelectRule implements IAlgebraicRewriteRule {
+
+    @Override
+    public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+        return false;
+    }
+
+    @Override
+    public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+            throws AlgebricksException {
+        AbstractLogicalOperator op = (AbstractLogicalOperator) opRef.getValue();
+        if (op.getOperatorTag() != LogicalOperatorTag.SELECT) {
+            return false;
+        }
+        SelectOperator select = (SelectOperator) op;
+        ILogicalExpression cond = select.getCondition().getValue();
+        if (alwaysHold(cond)) {
+            opRef.setValue(select.getInputs().get(0).getValue());
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * Whether the condition expression always returns true.
+     * 
+     * @param cond
+     * @return true if the condition always holds; false otherwise.
+     */
+    private boolean alwaysHold(ILogicalExpression cond) {
+        if (cond.equals(ConstantExpression.TRUE)) {
+            return true;
+        }
+        if (cond.equals(new ConstantExpression(new AsterixConstantValue(ABoolean.TRUE)))) {
+            return true;
+        }
+        return false;
+    }
+}
diff --git a/asterix-app/src/test/resources/optimizerts/queries/query_issue849-2.aql b/asterix-app/src/test/resources/optimizerts/queries/query_issue849-2.aql
new file mode 100644
index 0000000..929c5f1
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/query_issue849-2.aql
@@ -0,0 +1,24 @@
+/*
+ * Description  : This test case is to verify the fix for issue827
+ * https://code.google.com/p/asterixdb/issues/detail?id=849
+ * Expected Res : SUCCESS
+ * Date         : 2nd Feb. 2015
+ */
+
+drop dataverse test if exists;
+create dataverse test;
+
+use dataverse test;
+
+create type sType as closed{b : int32};
+create dataset s(sType) primary key b;
+
+insert into dataset s ({ "b" : 1});
+insert into dataset s ({ "b" : 3});
+
+for $x in dataset s
+for $y in (
+ for $z in {{ {"a":1, "c":1},{"a":2, "c":2},{"a":1, "c":null} }} where $x.b=$z.a
+    return $z.c
+)
+return {"x":$x,"y":$y}
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/optimizerts/queries/query_issue849.aql b/asterix-app/src/test/resources/optimizerts/queries/query_issue849.aql
new file mode 100644
index 0000000..5e45938
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/query_issue849.aql
@@ -0,0 +1,24 @@
+/*
+ * Description  : This test case is to verify the fix for issue827
+ * https://code.google.com/p/asterixdb/issues/detail?id=849
+ * Expected Res : SUCCESS
+ * Date         : 2nd Feb. 2015
+ */
+
+drop dataverse test if exists;
+create dataverse test;
+
+use dataverse test;
+
+create type sType as closed{b : int32};
+create dataset s(sType) primary key b;
+
+insert into dataset s ({ "b" : 1});
+insert into dataset s ({ "b" : 3});
+
+for $x in {{ {"a":1},{"a":2} }}
+for $y in (
+ for $z in dataset s where $x.a=$z.b
+    return $z.b
+)
+return {"x":$x,"y":$y}
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/optimizerts/results/query_issue849-2.plan b/asterix-app/src/test/resources/optimizerts/results/query_issue849-2.plan
new file mode 100644
index 0000000..df5d477
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/query_issue849-2.plan
@@ -0,0 +1,33 @@
+-- COMMIT  |PARTITIONED|
+  -- STREAM_PROJECT  |PARTITIONED|
+    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+      -- INSERT_DELETE  |PARTITIONED|
+        -- HASH_PARTITION_EXCHANGE [$$3]  |PARTITIONED|
+          -- ASSIGN  |UNPARTITIONED|
+            -- ASSIGN  |UNPARTITIONED|
+              -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+-- COMMIT  |PARTITIONED|
+  -- STREAM_PROJECT  |PARTITIONED|
+    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+      -- INSERT_DELETE  |PARTITIONED|
+        -- HASH_PARTITION_EXCHANGE [$$3]  |PARTITIONED|
+          -- ASSIGN  |UNPARTITIONED|
+            -- ASSIGN  |UNPARTITIONED|
+              -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+-- DISTRIBUTE_RESULT  |PARTITIONED|
+  -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+    -- STREAM_PROJECT  |PARTITIONED|
+      -- ASSIGN  |PARTITIONED|
+        -- STREAM_PROJECT  |PARTITIONED|
+          -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+            -- HYBRID_HASH_JOIN [$$15][$$17]  |PARTITIONED|
+              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                -- DATASOURCE_SCAN  |PARTITIONED|
+                  -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                    -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+              -- HASH_PARTITION_EXCHANGE [$$17]  |PARTITIONED|
+                -- STREAM_PROJECT  |UNPARTITIONED|
+                  -- ASSIGN  |UNPARTITIONED|
+                    -- STREAM_SELECT  |UNPARTITIONED|
+                      -- UNNEST  |UNPARTITIONED|
+                        -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/query_issue849.plan b/asterix-app/src/test/resources/optimizerts/results/query_issue849.plan
new file mode 100644
index 0000000..db12ea3
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/query_issue849.plan
@@ -0,0 +1,33 @@
+-- COMMIT  |PARTITIONED|
+  -- STREAM_PROJECT  |PARTITIONED|
+    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+      -- INSERT_DELETE  |PARTITIONED|
+        -- HASH_PARTITION_EXCHANGE [$$3]  |PARTITIONED|
+          -- ASSIGN  |UNPARTITIONED|
+            -- ASSIGN  |UNPARTITIONED|
+              -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+-- COMMIT  |PARTITIONED|
+  -- STREAM_PROJECT  |PARTITIONED|
+    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+      -- INSERT_DELETE  |PARTITIONED|
+        -- HASH_PARTITION_EXCHANGE [$$3]  |PARTITIONED|
+          -- ASSIGN  |UNPARTITIONED|
+            -- ASSIGN  |UNPARTITIONED|
+              -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+-- DISTRIBUTE_RESULT  |PARTITIONED|
+  -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+    -- STREAM_PROJECT  |PARTITIONED|
+      -- ASSIGN  |PARTITIONED|
+        -- STREAM_PROJECT  |PARTITIONED|
+          -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+            -- HYBRID_HASH_JOIN [$$17][$$14]  |PARTITIONED|
+              -- HASH_PARTITION_EXCHANGE [$$17]  |PARTITIONED|
+                -- ASSIGN  |UNPARTITIONED|
+                  -- UNNEST  |UNPARTITIONED|
+                    -- EMPTY_TUPLE_SOURCE  |UNPARTITIONED|
+              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                -- STREAM_PROJECT  |PARTITIONED|
+                  -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                    -- DATASOURCE_SCAN  |PARTITIONED|
+                      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                        -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/rtree-index-join/query-issue838.plan b/asterix-app/src/test/resources/optimizerts/results/rtree-index-join/query-issue838.plan
index 34c71b9..56f292c 100644
--- a/asterix-app/src/test/resources/optimizerts/results/rtree-index-join/query-issue838.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/rtree-index-join/query-issue838.plan
@@ -2,25 +2,22 @@
   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
     -- STREAM_PROJECT  |PARTITIONED|
       -- ASSIGN  |PARTITIONED|
-        -- SORT_MERGE_EXCHANGE [$$18(ASC) ]  |PARTITIONED|
-          -- STABLE_SORT [$$18(ASC)]  |PARTITIONED|
-            -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-              -- STREAM_PROJECT  |PARTITIONED|
-                -- STREAM_SELECT  |PARTITIONED|
-                  -- STREAM_PROJECT  |PARTITIONED|
-                    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                      -- BTREE_SEARCH  |PARTITIONED|
-                        -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                          -- STABLE_SORT [$$29(ASC)]  |PARTITIONED|
-                            -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                              -- STREAM_PROJECT  |PARTITIONED|
-                                -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                  -- RTREE_SEARCH  |PARTITIONED|
-                                    -- BROADCAST_EXCHANGE  |PARTITIONED|
-                                      -- ASSIGN  |PARTITIONED|
-                                        -- STREAM_PROJECT  |PARTITIONED|
-                                          -- ASSIGN  |PARTITIONED|
-                                            -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                              -- DATASOURCE_SCAN  |PARTITIONED|
-                                                -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                  -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
\ No newline at end of file
+        -- STREAM_PROJECT  |PARTITIONED|
+          -- STREAM_SELECT  |PARTITIONED|
+            -- STREAM_PROJECT  |PARTITIONED|
+              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                -- BTREE_SEARCH  |PARTITIONED|
+                  -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                    -- STABLE_SORT [$$29(ASC)]  |PARTITIONED|
+                      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                        -- STREAM_PROJECT  |PARTITIONED|
+                          -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                            -- RTREE_SEARCH  |PARTITIONED|
+                              -- BROADCAST_EXCHANGE  |PARTITIONED|
+                                -- ASSIGN  |PARTITIONED|
+                                  -- STREAM_PROJECT  |PARTITIONED|
+                                    -- ASSIGN  |PARTITIONED|
+                                      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                        -- DATASOURCE_SCAN  |PARTITIONED|
+                                          -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                                            -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849-2/query_issue849-2.1.ddl.aql b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849-2/query_issue849-2.1.ddl.aql
new file mode 100644
index 0000000..3dfda04
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849-2/query_issue849-2.1.ddl.aql
@@ -0,0 +1,14 @@
+/*
+ * Description  : This test case is to verify the fix for issue827
+ * https://code.google.com/p/asterixdb/issues/detail?id=849
+ * Expected Res : SUCCESS
+ * Date         : 2nd Feb. 2015
+ */
+
+drop dataverse test if exists;
+create dataverse test;
+
+use dataverse test;
+
+create type sType as closed{b : int32};
+create dataset s(sType) primary key b;
diff --git a/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849-2/query_issue849-2.2.update.aql b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849-2/query_issue849-2.2.update.aql
new file mode 100644
index 0000000..94bcec2
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849-2/query_issue849-2.2.update.aql
@@ -0,0 +1,12 @@
+/*
+ * Description  : This test case is to verify the fix for issue827
+ * https://code.google.com/p/asterixdb/issues/detail?id=849
+ * Expected Res : SUCCESS
+ * Date         : 2nd Feb. 2015
+ */
+
+use dataverse test;
+
+insert into dataset s ({ "b" : 1});
+insert into dataset s ({ "b" : 3});
+
diff --git a/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849-2/query_issue849-2.3.query.aql b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849-2/query_issue849-2.3.query.aql
new file mode 100644
index 0000000..6a56624
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849-2/query_issue849-2.3.query.aql
@@ -0,0 +1,15 @@
+/*
+ * Description  : This test case is to verify the fix for issue827
+ * https://code.google.com/p/asterixdb/issues/detail?id=849
+ * Expected Res : SUCCESS
+ * Date         : 2nd Feb. 2015
+ */
+
+use dataverse test;
+
+for $x in dataset s
+for $y in (
+ for $z in {{ {"a":1, "c":1},{"a":2, "c":2},{"a":1, "c":null} }} where $x.b=$z.a
+    return $z.c
+)
+return {"x":$x,"y":$y}
diff --git a/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849/query_issue849.1.ddl.aql b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849/query_issue849.1.ddl.aql
new file mode 100644
index 0000000..3dfda04
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849/query_issue849.1.ddl.aql
@@ -0,0 +1,14 @@
+/*
+ * Description  : This test case is to verify the fix for issue827
+ * https://code.google.com/p/asterixdb/issues/detail?id=849
+ * Expected Res : SUCCESS
+ * Date         : 2nd Feb. 2015
+ */
+
+drop dataverse test if exists;
+create dataverse test;
+
+use dataverse test;
+
+create type sType as closed{b : int32};
+create dataset s(sType) primary key b;
diff --git a/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849/query_issue849.2.update.aql b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849/query_issue849.2.update.aql
new file mode 100644
index 0000000..94bcec2
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849/query_issue849.2.update.aql
@@ -0,0 +1,12 @@
+/*
+ * Description  : This test case is to verify the fix for issue827
+ * https://code.google.com/p/asterixdb/issues/detail?id=849
+ * Expected Res : SUCCESS
+ * Date         : 2nd Feb. 2015
+ */
+
+use dataverse test;
+
+insert into dataset s ({ "b" : 1});
+insert into dataset s ({ "b" : 3});
+
diff --git a/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849/query_issue849.3.query.aql b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849/query_issue849.3.query.aql
new file mode 100644
index 0000000..19fb6ca
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/leftouterjoin/query_issue849/query_issue849.3.query.aql
@@ -0,0 +1,15 @@
+/*
+ * Description  : This test case is to verify the fix for issue827
+ * https://code.google.com/p/asterixdb/issues/detail?id=849
+ * Expected Res : SUCCESS
+ * Date         : 2nd Feb. 2015
+ */
+
+use dataverse test;
+
+for $x in {{ {"a":1},{"a":2} }}
+for $y in (
+ for $z in dataset s where $x.a=$z.b
+    return $z.b
+)
+return {"x":$x,"y":$y}
diff --git a/asterix-app/src/test/resources/runtimets/results/leftouterjoin/query_issue849-2/query_issue849-2.1.adm b/asterix-app/src/test/resources/runtimets/results/leftouterjoin/query_issue849-2/query_issue849-2.1.adm
new file mode 100644
index 0000000..1a5a7c0
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/results/leftouterjoin/query_issue849-2/query_issue849-2.1.adm
@@ -0,0 +1,3 @@
+[ { "x": { "b": 1 }, "y": 1 }
+, { "x": { "b": 1 }, "y": null }
+ ]
diff --git a/asterix-app/src/test/resources/runtimets/results/leftouterjoin/query_issue849/query_issue849.1.adm b/asterix-app/src/test/resources/runtimets/results/leftouterjoin/query_issue849/query_issue849.1.adm
new file mode 100644
index 0000000..ba46ac2
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/results/leftouterjoin/query_issue849/query_issue849.1.adm
@@ -0,0 +1,2 @@
+[ { "x": { "a": 1 }, "y": 1 }
+ ]
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/runtimets/testsuite.xml b/asterix-app/src/test/resources/runtimets/testsuite.xml
index 06829ad..e5ea4d3 100644
--- a/asterix-app/src/test/resources/runtimets/testsuite.xml
+++ b/asterix-app/src/test/resources/runtimets/testsuite.xml
@@ -5403,6 +5403,16 @@
                 <output-dir compare="Text">query_issue285-2</output-dir>
             </compilation-unit>
         </test-case>
+        <test-case FilePath="leftouterjoin">
+            <compilation-unit name="query_issue849">
+                <output-dir compare="Text">query_issue849</output-dir>
+            </compilation-unit>
+        </test-case>
+        <test-case FilePath="leftouterjoin">
+            <compilation-unit name="query_issue849-2">
+                <output-dir compare="Text">query_issue849-2</output-dir>
+            </compilation-unit>
+        </test-case>
     </test-group>
     <test-group name="index-leftouterjoin">
         <test-case FilePath="index-leftouterjoin">