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 fc9e789..e45eeea 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
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 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.base;
 
 import java.util.LinkedList;
@@ -18,6 +33,7 @@
 import edu.uci.ics.asterix.optimizer.rules.IntroduceDynamicTypeCastRule;
 import edu.uci.ics.asterix.optimizer.rules.IntroduceRTreeIndexSearchRule;
 import edu.uci.ics.asterix.optimizer.rules.IntroduceSecondaryIndexInsertDeleteRule;
+import edu.uci.ics.asterix.optimizer.rules.IntroduceStaticTypeCastRule;
 import edu.uci.ics.asterix.optimizer.rules.LoadRecordFieldsRule;
 import edu.uci.ics.asterix.optimizer.rules.NestGroupByRule;
 import edu.uci.ics.asterix.optimizer.rules.PullPositionalVariableFromUnnestRule;
@@ -28,7 +44,6 @@
 import edu.uci.ics.asterix.optimizer.rules.RemoveRedundantListifyRule;
 import edu.uci.ics.asterix.optimizer.rules.SetAsterixPhysicalOperatorsRule;
 import edu.uci.ics.asterix.optimizer.rules.SetClosedRecordConstructorsRule;
-import edu.uci.ics.asterix.optimizer.rules.IntroduceStaticTypeCastRule;
 import edu.uci.ics.asterix.optimizer.rules.UnnestToDataScanRule;
 import edu.uci.ics.hyracks.algebricks.core.rewriter.base.HeuristicOptimizer;
 import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
@@ -83,8 +98,9 @@
         normalization.add(new ExtractDistinctByExpressionsRule());
         normalization.add(new ExtractOrderExpressionsRule());
 
-        // TopdownTypeInferenceRule should go before IntroduceCastRecordRule to
-        // avoid unnecessary casting
+        // IntroduceStaticTypeCastRule should go before
+        // IntroduceDynamicTypeCastRule to
+        // avoid unnecessary dynamic casting
         normalization.add(new IntroduceStaticTypeCastRule());
         normalization.add(new IntroduceDynamicTypeCastRule());
         normalization.add(new ConstantFoldingRule());
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/ByNameToByIndexFieldAccessRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/ByNameToByIndexFieldAccessRule.java
index 25412d8..704ccb5 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/ByNameToByIndexFieldAccessRule.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/ByNameToByIndexFieldAccessRule.java
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 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 java.util.ArrayList;
@@ -49,11 +64,6 @@
             return false;
         }
         AssignOperator assign = (AssignOperator) op;
-        // if
-        // (assign.getAnnotations().get(AsterixOperatorAnnotations.PUSHED_FIELD_ACCESS)
-        // == null) {
-        // return false;
-        // }
         if (assign.getExpressions().get(0).getValue().getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
             return false;
         }
@@ -123,6 +133,7 @@
         return changed;
     }
 
+    @SuppressWarnings("unchecked")
     private static ILogicalExpression createFieldAccessByIndex(ARecordType recType, AbstractFunctionCallExpression fce) {
         String s = getStringSecondArgument(fce);
         if (s == null) {
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/ConstantFoldingRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/ConstantFoldingRule.java
index 36783ce..a8e6961 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/ConstantFoldingRule.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/ConstantFoldingRule.java
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 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 java.io.DataInputStream;
@@ -106,7 +121,6 @@
         if (context.checkIfInDontApplySet(this, op)) {
             return false;
         }
-        // context.addToDontApplySet(this, op);
         return op.acceptExpressionTransform(cfv);
     }
 
@@ -167,6 +181,8 @@
             resStore.reset();
             eval.evaluate(null);
             Object t = _emptyTypeEnv.getType(expr);
+            
+            @SuppressWarnings("rawtypes")
             ISerializerDeserializer serde = _jobGenCtx.getSerializerDeserializerProvider().getSerializerDeserializer(t);
             bbis.setByteBuffer(ByteBuffer.wrap(resStore.getBytes(), resStore.getStartIndex(), resStore.getLength()), 0);
             IAObject o;
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/IntroduceDynamicTypeCastRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/IntroduceDynamicTypeCastRule.java
index 1bd4127..35a5966 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/IntroduceDynamicTypeCastRule.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/IntroduceDynamicTypeCastRule.java
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 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 java.util.ArrayList;
@@ -73,50 +88,39 @@
         IVariableTypeEnvironment env = oldAssignOperator.computeInputTypeEnvironment(context);
         ARecordType inputRecordType = (ARecordType) env.getVarType(inputRecordVar);
 
-        boolean needCast = needCast(requiredRecordType, inputRecordType);
-        if (needCast) {
-            // insert
-            // project
-            // assign
-            // assign
-            AbstractFunctionCallExpression cast = new ScalarFunctionCallExpression(
-                    FunctionUtils.getFunctionInfo(AsterixBuiltinFunctions.CAST_RECORD));
-            ARecordType[] types = new ARecordType[2];
-            types[0] = requiredRecordType;
-            types[1] = inputRecordType;
-            cast.getArguments().add(
-                    new MutableObject<ILogicalExpression>(new VariableReferenceExpression(inputRecordVar)));
-            cast.setOpaqueParameters(types);
-            LogicalVariable newAssignVar = context.newVar();
-            AssignOperator newAssignOperator = new AssignOperator(newAssignVar, new MutableObject<ILogicalExpression>(
-                    cast));
-            newAssignOperator.getInputs().add(new MutableObject<ILogicalOperator>(op3));
-
-            List<LogicalVariable> projectVariables = new ArrayList<LogicalVariable>();
-            VariableUtilities.getProducedVariables(oldAssignOperator, projectVariables);
-            projectVariables.add(newAssignVar);
-            ProjectOperator projectOperator = new ProjectOperator(projectVariables);
-            projectOperator.getInputs().add(new MutableObject<ILogicalOperator>(newAssignOperator));
-
-            ILogicalExpression payloadExpr = new VariableReferenceExpression(newAssignVar);
-            MutableObject<ILogicalExpression> payloadRef = new MutableObject<ILogicalExpression>(payloadExpr);
-            InsertDeleteOperator newInserDeleteOperator = new InsertDeleteOperator(
-                    insertDeleteOperator.getDataSource(), payloadRef, insertDeleteOperator.getPrimaryKeyExpressions(),
-                    insertDeleteOperator.getOperation());
-            newInserDeleteOperator.getInputs().add(new MutableObject<ILogicalOperator>(projectOperator));
-            insertDeleteOperator.getInputs().clear();
-            op1.getInputs().get(0).setValue(newInserDeleteOperator);
-            return true;
-        }
-        return false;
-
-    }
-
-    private boolean needCast(ARecordType reqType, ARecordType inputType) {
-        if (!reqType.equals(inputType))
-            return true;
-        else
+        boolean needCast = !requiredRecordType.equals(inputRecordType);
+        if (!needCast)
             return false;
+
+        // insert
+        // project
+        // assign
+        // assign
+        AbstractFunctionCallExpression cast = new ScalarFunctionCallExpression(
+                FunctionUtils.getFunctionInfo(AsterixBuiltinFunctions.CAST_RECORD));
+        ARecordType[] types = new ARecordType[2];
+        types[0] = requiredRecordType;
+        types[1] = inputRecordType;
+        cast.getArguments().add(new MutableObject<ILogicalExpression>(new VariableReferenceExpression(inputRecordVar)));
+        cast.setOpaqueParameters(types);
+        LogicalVariable newAssignVar = context.newVar();
+        AssignOperator newAssignOperator = new AssignOperator(newAssignVar, new MutableObject<ILogicalExpression>(cast));
+        newAssignOperator.getInputs().add(new MutableObject<ILogicalOperator>(op3));
+
+        List<LogicalVariable> projectVariables = new ArrayList<LogicalVariable>();
+        VariableUtilities.getProducedVariables(oldAssignOperator, projectVariables);
+        projectVariables.add(newAssignVar);
+        ProjectOperator projectOperator = new ProjectOperator(projectVariables);
+        projectOperator.getInputs().add(new MutableObject<ILogicalOperator>(newAssignOperator));
+
+        ILogicalExpression payloadExpr = new VariableReferenceExpression(newAssignVar);
+        MutableObject<ILogicalExpression> payloadRef = new MutableObject<ILogicalExpression>(payloadExpr);
+        InsertDeleteOperator newInserDeleteOperator = new InsertDeleteOperator(insertDeleteOperator.getDataSource(),
+                payloadRef, insertDeleteOperator.getPrimaryKeyExpressions(), insertDeleteOperator.getOperation());
+        newInserDeleteOperator.getInputs().add(new MutableObject<ILogicalOperator>(projectOperator));
+        insertDeleteOperator.getInputs().clear();
+        op1.getInputs().get(0).setValue(newInserDeleteOperator);
+        return true;
     }
 
 }
diff --git a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-c2o.aql b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-c2o.aql
index ef6cd3a..e29ccdc 100644
--- a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-c2o.aql
+++ b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-c2o.aql
@@ -1,3 +1,10 @@
+/* 
+ * Test case Name  : opentype-c2o.aql
+ * Description     : read data from a closed type dataset into a open type dataset and verify if
+ *					records can be casted to the target open type 
+ * Expected Result : Success
+ */
+
 drop dataverse testdv2 if exists;
 create dataverse testdv2;
 use dataverse testdv2;
@@ -8,6 +15,10 @@
   hobby: string?
 }
 
+/*
+* name and hobby from the closed dataset will
+* become open fields, and hobby can be null
+*/
 create type testtype2 as open {
   id: string
 }
@@ -17,15 +28,15 @@
 create dataset testds2(testtype2) partitioned by key id;
  
 insert into dataset testds (
-{ "id": "001", "name": "Person Three", "hobby": "music"}
+{ "hobby": "music", "id": "001", "name": "Person Three"}
 );
 
 insert into dataset testds (
-{ "id": "002", "name": "Person One", "hobby": "sports"}
+{ "name": "Person One", "id": "002", "hobby": "sports"}
 );
 
 insert into dataset testds (
-{ "id": "003", "name": "Person Two", "hobby": "movie"}
+{ "id": "003", "hobby": "movie", "name": "Person Two"}
 );
 
 insert into dataset testds (
@@ -33,7 +44,7 @@
 );
  
 insert into dataset testds (
-{ "id": "005", "name": "Person Five"}
+{ "name": "Person Five", "id": "005"}
 ); 
  
 insert into dataset testds2 (
diff --git a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-closed-optional.aql b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-closed-optional.aql
index cc3b622..94991be 100644
--- a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-closed-optional.aql
+++ b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-closed-optional.aql
@@ -1,9 +1,15 @@
+/* 
+ * Test case Name  : opentype-closed-optional.aql
+ * Description     : verify that closed type can have optional fields
+ * Expected Result : Success
+ */
+
 drop dataverse testdv2 if exists;
 create dataverse testdv2;
 use dataverse testdv2;
 
 create type testtype as closed {
-  name: string ?,
+  name: string?,
   id: string
 }
 
diff --git a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-insert.aql b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-insert.aql
index 19dd1d6..12248dd 100644
--- a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-insert.aql
+++ b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-insert.aql
@@ -1,3 +1,9 @@
+/* 
+ * Test case Name  : opentype-insert.aql
+ * Description     : verify static type casting
+ * Expected Result : Success
+ */
+
 drop dataverse testdv2 if exists;
 create dataverse testdv2;
 use dataverse testdv2;
diff --git a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-insert2.aql b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-insert2.aql
index db5ee2e..1903bf2 100644
--- a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-insert2.aql
+++ b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-insert2.aql
@@ -1,12 +1,16 @@
-//Test the case where SetClosedRecordRule should not rewrite
-//the plan to use closed-record-descriptor;
+/* 
+ * Test case Name  : opentype-insert2.aql
+ * Description     : verify that the case where SetClosedRecordRule should not rewrite
+ *					the plan to use closed-record-descriptor
+ * Expected Result : Success
+ */
 
 drop dataverse test if exists;
 create dataverse test;
 use dataverse test;
 
 create type TestType as open {
-id:int32
+	id:int32
 }
 
 create dataset testds(TestType) partitioned by key id;
diff --git a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-noexpand.aql b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-noexpand.aql
index f8b4880..c6ff1cd 100644
--- a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-noexpand.aql
+++ b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-noexpand.aql
@@ -1,9 +1,16 @@
+/* 
+ * Test case Name  : opentype-noexpand.aql
+ * Description     : verify that open type dataset can have records without open fields
+ *					 verify the bag-based fields
+ * Expected Result : Success
+ */
+ 
 drop dataverse testdv2 if exists;
 create dataverse testdv2;
 use dataverse testdv2;
 
 create type testtype as open {
-  name: string ?,
+  name: string?,
   id: string
 }
 
diff --git a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-o2c.aql b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-o2c.aql
index d160f40..a6ed9cc 100644
--- a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-o2c.aql
+++ b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-o2c.aql
@@ -1,3 +1,11 @@
+/* 
+ * Test case Name  : opentype-o2c.aql
+ * Description     : verify that open records can be inserted into a closed dataset
+ *					 verify missing optional fields in the closed part of the target closed dataset are allowed
+ * Expected Result : Success
+ */
+
+
 drop dataverse testdv2 if exists;
 create dataverse testdv2;
 use dataverse testdv2;
@@ -8,9 +16,9 @@
 }
 
 create type testtype2 as closed {
+  hobby: string?,
   id: string,
-  name: string,
-  hobby: string?
+  name: string
 }
 
 create dataset testds(testtype) partitioned by key id;
@@ -18,7 +26,7 @@
 create dataset testds2(testtype2) partitioned by key id; 
  
 insert into dataset testds (
-{ "id": "001", "name": "Person Three", "hobby": "music"}
+{ "id": "001",  "hobby": "music", "name": "Person Three"}
 );
 
 insert into dataset testds (
@@ -30,7 +38,7 @@
 );
 
 insert into dataset testds (
-{ "id": "004", "name": "Person Three", "hobby": "swimming"}
+{ "name": "Person Three", "hobby": "swimming", "id": "004"}
 );
 
 insert into dataset testds (
diff --git a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-o2o.aql b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-o2o.aql
index 6793180..545790b 100644
--- a/asterix-app/src/test/resources/runtimets/queries/dml/opentype-o2o.aql
+++ b/asterix-app/src/test/resources/runtimets/queries/dml/opentype-o2o.aql
@@ -1,3 +1,11 @@
+/* 
+ * Test case Name  : opentype-o2o.aql
+ * Description     : verify that the dynamic type cast from one open type to another compatible open type
+ *					 verify the bag-based fields
+ * Expected Result : Success
+ */
+
+
 drop dataverse testdv2 if exists;
 create dataverse testdv2;
 use dataverse testdv2;
@@ -22,7 +30,7 @@
 );
 
 insert into dataset testds (
-{ "name": "Person Two", "id": "002",  "hobby": "football", "city":"irvine"}
+{ "hobby": "football", "city":"irvine", "name": "Person Two", "id": "002"}
 );
 
 insert into dataset testds (
@@ -30,7 +38,7 @@
 );
 
 insert into dataset testds (
-{ "name": "Person Four", "id": "004",  "hobby": "swimming", "phone":"102-304-506"}
+{ "hobby": "swimming", "name": "Person Four", "id": "004", "phone":"102-304-506"}
 );
 
 insert into dataset testds2 (
diff --git a/asterix-app/src/test/resources/runtimets/queries/open-closed/open-closed-02.aql b/asterix-app/src/test/resources/runtimets/queries/open-closed/open-closed-02.aql
index c037cc8..e15577b 100644
--- a/asterix-app/src/test/resources/runtimets/queries/open-closed/open-closed-02.aql
+++ b/asterix-app/src/test/resources/runtimets/queries/open-closed/open-closed-02.aql
@@ -19,7 +19,7 @@
 
 create dataset testds(testType) partitioned by key id;
 
-insert into dataset testds({"id": 123);
+insert into dataset testds({"id": 123});
 
 write output to nc1:"rttest/open-closed_open-closed-02.adm";
 for $l in dataset("testds") return $l
diff --git a/asterix-app/src/test/resources/runtimets/results/dml/opentype-o2c.adm b/asterix-app/src/test/resources/runtimets/results/dml/opentype-o2c.adm
index 34023cd..d9c778b 100644
--- a/asterix-app/src/test/resources/runtimets/results/dml/opentype-o2c.adm
+++ b/asterix-app/src/test/resources/runtimets/results/dml/opentype-o2c.adm
@@ -1,5 +1,5 @@
-{ "id": "001", "name": "Person Three", "hobby": "music" }
-{ "id": "002", "name": "Person Three", "hobby": "football" }
-{ "id": "003", "name": "Person Three", "hobby": "movie" }
-{ "id": "004", "name": "Person Three", "hobby": "swimming" }
-{ "id": "005", "name": "Person Five", "hobby": null }
+{ "hobby": "music", "id": "001", "name": "Person Three" }
+{ "hobby": "football", "id": "002", "name": "Person Three" }
+{ "hobby": "movie", "id": "003", "name": "Person Three" }
+{ "hobby": "swimming", "id": "004", "name": "Person Three" }
+{ "hobby": null, "id": "005", "name": "Person Five" }
diff --git a/asterix-om/src/main/java/edu/uci/ics/asterix/om/functions/AsterixBuiltinFunctions.java b/asterix-om/src/main/java/edu/uci/ics/asterix/om/functions/AsterixBuiltinFunctions.java
index 9aeac2b..a996683 100644
--- a/asterix-om/src/main/java/edu/uci/ics/asterix/om/functions/AsterixBuiltinFunctions.java
+++ b/asterix-om/src/main/java/edu/uci/ics/asterix/om/functions/AsterixBuiltinFunctions.java
@@ -737,8 +737,6 @@
         builtinFunctionsSet.put(functionInfo, functionInfo);
         funTypeComputer.put(functionInfo, typeComputer);
         asterixFunctionIdToInfo.put(fi, functionInfo);
-        // AsterixFunction asterixFunction = new AsterixFunction(fi.getName(),
-        // fi.getArity());
     }
 
     private static void addAgg(FunctionIdentifier fi) {
diff --git a/asterix-om/src/main/java/edu/uci/ics/asterix/om/functions/IFunctionDescriptorFactory.java b/asterix-om/src/main/java/edu/uci/ics/asterix/om/functions/IFunctionDescriptorFactory.java
index dd77193..516bf51 100644
--- a/asterix-om/src/main/java/edu/uci/ics/asterix/om/functions/IFunctionDescriptorFactory.java
+++ b/asterix-om/src/main/java/edu/uci/ics/asterix/om/functions/IFunctionDescriptorFactory.java
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 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.om.functions;
 
 public interface IFunctionDescriptorFactory {
diff --git a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/evaluators/common/FunctionManagerImpl.java b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/evaluators/common/FunctionManagerImpl.java
index 72a2b70..b5b6f29 100644
--- a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/evaluators/common/FunctionManagerImpl.java
+++ b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/evaluators/common/FunctionManagerImpl.java
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 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.runtime.evaluators.common;
 
 import java.util.ArrayList;
diff --git a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ARecordAccessor.java b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ARecordAccessor.java
index 9a048f5..d45b4ac 100644
--- a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ARecordAccessor.java
+++ b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ARecordAccessor.java
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 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.runtime.util;
 
 import java.io.DataOutputStream;
@@ -23,11 +38,11 @@
     private List<SimpleValueReference> fieldValues = new ArrayList<SimpleValueReference>();
 
     private byte[] typeBuffer = new byte[32768];
-    private ResetableByteArrayOutputStream typeBos = new ResetableByteArrayOutputStream();
+    private ResettableByteArrayOutputStream typeBos = new ResettableByteArrayOutputStream();
     private DataOutputStream typeDos = new DataOutputStream(typeBos);
 
     private byte[] dataBuffer = new byte[32768];
-    private ResetableByteArrayOutputStream dataBos = new ResetableByteArrayOutputStream();
+    private ResettableByteArrayOutputStream dataBos = new ResettableByteArrayOutputStream();
     private DataOutputStream dataDos = new DataOutputStream(dataBos);
 
     private int closedPartTypeInfoSize = 0;
diff --git a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ARecordCaster.java b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ARecordCaster.java
index 5ba7a31..505e769 100644
--- a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ARecordCaster.java
+++ b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ARecordCaster.java
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 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.runtime.util;
 
 import java.io.DataOutput;
@@ -13,23 +28,29 @@
 import edu.uci.ics.asterix.om.types.AUnionType;
 import edu.uci.ics.asterix.om.types.IAType;
 import edu.uci.ics.asterix.om.util.NonTaggedFormatUtil;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
 import edu.uci.ics.hyracks.api.dataflow.value.INullWriter;
+import edu.uci.ics.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
+import edu.uci.ics.hyracks.data.std.primitive.UTF8StringPointable;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.IValueReference;
 
 public class ARecordCaster {
 
     // describe closed fields in the required type
     private int[] fieldPermutation;
+    private boolean[] optionalFields;
 
     // describe fields (open or not) in the input records
     private boolean[] openFields;
-    private boolean[] optionalFields;
+    private int[] fieldNamesSortedIndex;
 
     private List<SimpleValueReference> reqFieldNames = new ArrayList<SimpleValueReference>();
+    private int[] reqFieldNamesSortedIndex;
     private List<SimpleValueReference> reqFieldTypeTags = new ArrayList<SimpleValueReference>();
     private ARecordType cachedReqType = null;
 
     private byte[] buffer = new byte[32768];
-    private ResetableByteArrayOutputStream bos = new ResetableByteArrayOutputStream();
+    private ResettableByteArrayOutputStream bos = new ResettableByteArrayOutputStream();
     private DataOutputStream dos = new DataOutputStream(bos);
 
     private RecordBuilder recBuilder = new RecordBuilder();
@@ -37,6 +58,8 @@
     private SimpleValueReference nullTypeTag = new SimpleValueReference();
 
     private int numInputFields = 0;
+    private IBinaryComparator fieldNameComparator = PointableBinaryComparatorFactory.of(UTF8StringPointable.FACTORY)
+            .createBinaryComparator();
 
     public ARecordCaster() {
         try {
@@ -63,6 +86,7 @@
 
         if (openFields == null || numInputFields > openFields.length) {
             openFields = new boolean[numInputFields];
+            fieldNamesSortedIndex = new int[numInputFields];
         }
         if (cachedReqType == null || !reqType.equals(cachedReqType)) {
             loadRequiredType(reqType);
@@ -79,6 +103,8 @@
             openFields[i] = true;
         for (int i = 0; i < fieldPermutation.length; i++)
             fieldPermutation[i] = -1;
+        for (int i = 0; i < numInputFields; i++)
+            fieldNamesSortedIndex[i] = i;
     }
 
     private void loadRequiredType(ARecordType reqType) throws IOException {
@@ -123,62 +149,57 @@
             typeNamePointable.reset(buffer, nameStart, nameEnd - nameStart);
             reqFieldNames.add(typeNamePointable);
         }
+
+        reqFieldNamesSortedIndex = new int[reqFieldNames.size()];
+        for (int i = 0; i < reqFieldNamesSortedIndex.length; i++)
+            reqFieldNamesSortedIndex[i] = i;
+        // sort the field name index
+        quickSort(reqFieldNamesSortedIndex, reqFieldNames, 0, reqFieldNamesSortedIndex.length - 1);
     }
 
     private void matchClosedPart(List<SimpleValueReference> fieldNames, List<SimpleValueReference> fieldTypeTags,
             List<SimpleValueReference> fieldValues) {
-        // forward match: match from actual to required
-        boolean matched = false;
-        for (int i = 0; i < numInputFields; i++) {
-            SimpleValueReference fieldName = fieldNames.get(i);
-            SimpleValueReference fieldTypeTag = fieldTypeTags.get(i);
-            matched = false;
-            for (int j = 0; j < reqFieldNames.size(); j++) {
-                SimpleValueReference reqFieldName = reqFieldNames.get(j);
-                SimpleValueReference reqFieldTypeTag = reqFieldTypeTags.get(j);
-                if (fieldName.equals(reqFieldName) && fieldTypeTag.equals(reqFieldTypeTag)) {
-                    fieldPermutation[j] = i;
-                    openFields[i] = false;
-                    matched = true;
-                    break;
+        // sort-merge based match
+        quickSort(fieldNamesSortedIndex, fieldNames, 0, numInputFields - 1);
+        int fnStart = 0;
+        int reqFnStart = 0;
+        while (fnStart < numInputFields && reqFnStart < reqFieldNames.size()) {
+            int fnPos = fieldNamesSortedIndex[fnStart];
+            int reqFnPos = reqFieldNamesSortedIndex[reqFnStart];
+            int c = compare(fieldNames.get(fnPos), reqFieldNames.get(reqFnPos));
+            if (c == 0) {
+                SimpleValueReference fieldTypeTag = fieldTypeTags.get(fnPos);
+                SimpleValueReference reqFieldTypeTag = reqFieldTypeTags.get(reqFnPos);
+                if (fieldTypeTag.equals(reqFieldTypeTag) || (
+                // match the null type of optional field
+                        optionalFields[reqFnPos] && fieldTypeTag.equals(nullTypeTag))) {
+                    fieldPermutation[reqFnPos] = fnPos;
+                    openFields[fnPos] = false;
                 }
+                fnStart++;
+                reqFnStart++;
             }
-            if (matched)
-                continue;
-            // the input has extra fields
-            if (!cachedReqType.isOpen())
+            if (c > 0)
+                reqFnStart++;
+            if (c < 0)
+                fnStart++;
+        }
+
+        // check unmatched fields in the input type
+        for (int i = 0; i < openFields.length; i++) {
+            if (openFields[i] == true && !cachedReqType.isOpen())
                 throw new IllegalStateException("type mismatch: including extra closed fields");
         }
 
-        // backward match: match from required to actual
-        for (int i = 0; i < reqFieldNames.size(); i++) {
-            SimpleValueReference reqFieldName = reqFieldNames.get(i);
-            SimpleValueReference reqFieldTypeTag = reqFieldTypeTags.get(i);
-            matched = false;
-            for (int j = 0; j < numInputFields; j++) {
-                SimpleValueReference fieldName = fieldNames.get(j);
-                SimpleValueReference fieldTypeTag = fieldTypeTags.get(j);
-                if (fieldName.equals(reqFieldName)) {
-                    if (fieldTypeTag.equals(reqFieldTypeTag)) {
-                        matched = true;
-                        break;
-                    }
-
-                    // match the null type of optional field
-                    if (optionalFields[i] && fieldTypeTag.equals(nullTypeTag)) {
-                        matched = true;
-                        break;
-                    }
+        // check unmatched fields in the required type
+        for (int i = 0; i < fieldPermutation.length; i++) {
+            if (fieldPermutation[i] < 0) {
+                IAType t = cachedReqType.getFieldTypes()[i];
+                if (!(t.getTypeTag() == ATypeTag.UNION && NonTaggedFormatUtil.isOptionalField((AUnionType) t))) {
+                    // no matched field in the input for a required closed field
+                    throw new IllegalStateException("type mismatch: miss a required closed field");
                 }
             }
-            if (matched)
-                continue;
-
-            IAType t = cachedReqType.getFieldTypes()[i];
-            if (!(t.getTypeTag() == ATypeTag.UNION && NonTaggedFormatUtil.isOptionalField((AUnionType) t))) {
-                // no matched field in the input for a required closed field
-                throw new IllegalStateException("type mismatch: miss a required closed field");
-            }
         }
     }
 
@@ -210,4 +231,45 @@
         }
         recBuilder.write(output, true);
     }
+
+    private void quickSort(int[] index, List<SimpleValueReference> names, int start, int end) {
+        if (end <= start)
+            return;
+        int i = partition(index, names, start, end);
+        quickSort(index, names, start, i - 1);
+        quickSort(index, names, i + 1, end);
+    }
+
+    private int partition(int[] index, List<SimpleValueReference> names, int left, int right) {
+        int i = left - 1;
+        int j = right;
+        while (true) {
+            // grow from the left
+            while (compare(names.get(index[++i]), names.get(index[right])) < 0)
+                ;
+            // lower from the right
+            while (compare(names.get(index[right]), names.get(index[--j])) < 0)
+                if (j == left)
+                    break;
+            if (i >= j)
+                break;
+            // swap i and j
+            swap(index, i, j);
+        }
+        // swap i and right
+        swap(index, i, right); // swap with partition element
+        return i;
+    }
+
+    private void swap(int[] array, int i, int j) {
+        int temp = array[i];
+        array[i] = array[j];
+        array[j] = temp;
+    }
+
+    private int compare(IValueReference a, IValueReference b) {
+        // start+1 and len-1 due to the type tag
+        return fieldNameComparator.compare(a.getBytes(), a.getStartIndex() + 1, a.getLength() - 1, b.getBytes(),
+                b.getStartIndex() + 1, b.getLength() - 1);
+    }
 }
diff --git a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResetableByteArrayInputStream.java b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResettableByteArrayInputStream.java
similarity index 88%
rename from asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResetableByteArrayInputStream.java
rename to asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResettableByteArrayInputStream.java
index 7f8f0e9..af18133 100644
--- a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResetableByteArrayInputStream.java
+++ b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResettableByteArrayInputStream.java
@@ -18,13 +18,13 @@
 import java.util.logging.Level;
 import java.util.logging.Logger;
 
-public class ResetableByteArrayInputStream extends ByteArrayInputStream {
-    private static final Logger LOGGER = Logger.getLogger(ResetableByteArrayInputStream.class.getName());
+public class ResettableByteArrayInputStream extends ByteArrayInputStream {
+    private static final Logger LOGGER = Logger.getLogger(ResettableByteArrayInputStream.class.getName());
 
     private byte[] data;
     private int position;
 
-    public ResetableByteArrayInputStream(byte[] data) {
+    public ResettableByteArrayInputStream(byte[] data) {
         super(data);
     }
 
diff --git a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResetableByteArrayOutputStream.java b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResettableByteArrayOutputStream.java
similarity index 89%
rename from asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResetableByteArrayOutputStream.java
rename to asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResettableByteArrayOutputStream.java
index 2958314..62db3a9 100644
--- a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResetableByteArrayOutputStream.java
+++ b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/ResettableByteArrayOutputStream.java
@@ -18,13 +18,13 @@
 import java.util.logging.Level;
 import java.util.logging.Logger;
 
-public class ResetableByteArrayOutputStream extends ByteArrayOutputStream {
-    private static final Logger LOGGER = Logger.getLogger(ResetableByteArrayOutputStream.class.getName());
+public class ResettableByteArrayOutputStream extends ByteArrayOutputStream {
+    private static final Logger LOGGER = Logger.getLogger(ResettableByteArrayOutputStream.class.getName());
 
     private byte[] data;
     private int position;
 
-    public ResetableByteArrayOutputStream() {
+    public ResettableByteArrayOutputStream() {
     }
 
     public void setByteArray(byte[] data, int position) {
diff --git a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/SimpleValueReference.java b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/SimpleValueReference.java
index bb54624..e49218a 100644
--- a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/SimpleValueReference.java
+++ b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/util/SimpleValueReference.java
@@ -1,3 +1,18 @@
+/*
+ * Copyright 2009-2010 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.runtime.util;
 
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.IValueReference;