diff --git a/asterixdb/asterix-app/data/complex/records1.adm b/asterixdb/asterix-app/data/complex/records1.adm
new file mode 100644
index 0000000..d425baa
--- /dev/null
+++ b/asterixdb/asterix-app/data/complex/records1.adm
@@ -0,0 +1,33 @@
+{"id":1, "name":"Margarita", "address": {"street": "11th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA"} }
+{"id":2, "name":"Isac", "address": {"street": "14th", "apt": 1, "state": "MN", "zipcode": 78812, "country": "USA"} }
+{"id":3, "name":"Emory", "address": {"street": "12th", "apt": 8, "state": "AL", "zipcode": 33212, "country": "USA"} }
+{"id":4, "name":"Nicholas", "address": {"street": "19th", "state": "IN", "zipcode": 88232, "country": "USA"} }
+{"id":5, "name":"Von", "address": {"street": "17th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA"} }
+{"id":6, "name":"Willis", "address": {"street": "10th", "apt": 9, "state": "MO", "country": "USA"} }
+{"id":7, "name":"Suzanna", "address": {"street": "11th", "apt": 2, "state": "CA", "zipcode": 92211, "country": "USA"} }
+{"id":8, "name":"Nicole", "address": {"street": "16th", "apt": 7, "state": "OR", "zipcode": 97403, "country": "USA"} }
+{"id":9, "name":"Woodrow", "address": {"street": "13th", "apt": 6, "state": "CO", "zipcode": 44321, "country": "USA"} }
+{"id":10, "name":"Bram", "address": {"state": "OR", "zipcode": 97444, "country": "USA"} }
+{"id":11, "name":"Nicholas", "address": {"state": "CA", "zipcode": 92212, "country": "USA"} }
+{"id":12, "name":"John", "address": {"street": "11th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA"} }
+{"id":13, "name":"Steve", "address": {"street": "19th", "state": "IN", "zipcode": 88232, "country": "USA"} }
+{"id":14, "name":"Jay", "address": {"street": "10th", "apt": null, "state": "MO", "country": "USA"} }
+{"id":15, "name":"Jim", "address": null }
+{"id":16, "name":"Wail"}
+{"id":17, "name":"Jim"}
+{"id":18, "name":"Kayle", "address": null }
+{"id":20, "name":"Mai", "address": {"street": "10th", "apt": 9, "state": "ON", "country": "Canada"} }
+{"id":21, "name":"Ken", "address": {"street": "15th", "apt": 6, "state": "CO", "zipcode": 44321, "country": "USA"} }
+{"id":22, "name":"Fend", "address": {"street": "16th", "state": "BC", "country": "Canada"} }
+{"id":23, "name":"Adrian", "address": {"street": "14th", "state": "MN", "zipcode": 78812, "country": "USA"} }
+{"id":24, "name":"Trent", "address": null }
+{"id":25, "name":"Willis", "address": {"street": "18th", "apt": 9, "state": "MO", "country": "USA"} }
+{"id":27, "name":"Eric", "address": {"state": "CA", "country": "USA"} }
+{"id":28, "name":"Lory", "address": {"state": "AL", "country": "USA"} }
+{"id":29, "name":"David", "address": {"state": "OR", "country": "USA"} }
+{"id":30, "name":"Rock", "address": {"state": "BC", "country": "Canada"} }
+{"id":31, "name":"Sam", "address": {"state": "BC", "country": "Canada"} }
+{"id":32, "name":"May", "address": {"state": "ON", "country": "Canada"} }
+{"id":33, "name":"Tiger", "address": {"street": null, "apt": null, "state": "CO", "country": "USA"} }
+{"id":34, "name":"Nicole", "address": {"street": null, "apt": 7, "state": "OR", "zipcode": 97402, "country": "USA"} }
+{"id":35, "name":"Adam", "address": {"street": "18th", "apt": 8, "state": "AL", "zipcode": 33212, "country": "USA"} }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/data/complex/records2.adm b/asterixdb/asterix-app/data/complex/records2.adm
new file mode 100644
index 0000000..7ba1308
--- /dev/null
+++ b/asterixdb/asterix-app/data/complex/records2.adm
@@ -0,0 +1,35 @@
+{"id":1, "name":"Margarita", "address": {"street": "11th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA"} }
+{"id":2, "name":"Isac", "address": {"street": "14th", "apt": 1, "state": "MN", "zipcode": 78812, "country": "USA"} }
+{"id":3, "name":"Emory", "address": {"street": "12th", "apt": 8, "state": "AL", "zipcode": 33212, "country": "USA"} }
+{"id":4, "name":"Nicholas", "address": {"street": "19th", "state": "IN", "zipcode": 88232, "country": "USA"} }
+{"id":5, "name":"Von", "address": {"street": "17th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA"} }
+{"id":6, "name":"Willis", "address": {"street": "10th", "apt": 9, "state": "MO", "country": "USA"} }
+{"id":7, "name":"Suzanna", "address": {"street": "11th", "apt": 2, "state": "CA", "zipcode": 92211, "country": "USA"} }
+{"id":8, "name":"Nicole", "address": {"street": "16th", "apt": 7, "state": "OR", "zipcode": 97403, "country": "USA"} }
+{"id":9, "name":"Woodrow", "address": {"street": "13th", "apt": 6, "state": "CO", "zipcode": 44321, "country": "USA"} }
+{"id":10, "name":"Bram", "address": {"state": "OR", "zipcode": 97444, "country": "USA"} }
+{"id":11, "name":"Nicholas", "address": {"state": "CA", "zipcode": 92212, "country": "USA"} }
+{"id":12, "name":"John", "address": {"street": "11th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA"} }
+{"id":13, "name":"Steve", "address": {"street": "19th", "state": "IN", "zipcode": 88232, "country": "USA"} }
+{"id":14, "name":"Jay", "address": {"street": "10th", "apt": null, "state": "MO", "country": "USA"} }
+{"id":15, "name":"Jim", "address": null }
+{"id":16, "name":"Wail"}
+{"id":17, "name":"Jim"}
+{"id":18, "name":"Kayle", "address": null }
+{"id":19, "name":"Mart", "address": { } }
+{"id":20, "name":"Mai", "address": {"street": "10th", "apt": 9, "state": "ON", "country": "Canada"} }
+{"id":21, "name":"Ken", "address": {"street": "15th", "apt": 6, "state": "CO", "zipcode": 44321, "country": "USA"} }
+{"id":22, "name":"Fend", "address": {"street": "16th", "state": "BC", "country": "Canada"} }
+{"id":23, "name":"Adrian", "address": {"street": "14th", "state": "MN", "zipcode": 78812, "country": "USA"} }
+{"id":24, "name":"Trent", "address": null }
+{"id":25, "name":"Willis", "address": {"street": "18th", "apt": 9, "state": "MO", "country": "USA"} }
+{"id":26, "name":"Nancy", "address": { } }
+{"id":27, "name":"Eric", "address": {"state": "CA", "country": "USA"} }
+{"id":28, "name":"Lory", "address": {"state": "AL", "country": "USA"} }
+{"id":29, "name":"David", "address": {"state": "OR", "country": "USA"} }
+{"id":30, "name":"Rock", "address": {"state": "BC", "country": "Canada"} }
+{"id":31, "name":"Sam", "address": {"state": "BC", "country": "Canada"} }
+{"id":32, "name":"May", "address": {"state": "ON", "country": "Canada"} }
+{"id":33, "name":"Tiger", "address": {"street": null, "apt": null, "state": "CO", "country": "USA"} }
+{"id":34, "name":"Nicole", "address": {"street": null, "apt": 7, "state": "OR", "zipcode": 97402, "country": "USA"} }
+{"id":35, "name":"Adam", "address": {"street": "18th", "apt": 8, "state": "AL", "zipcode": 33212, "country": "USA"} }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.1.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.1.ddl.sqlpp
new file mode 100644
index 0000000..6a37f12
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.1.ddl.sqlpp
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *   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.
+ */
+
+drop  dataverse test if exists;
+create  dataverse test;
+use test;
+
+create type addressType1 as {
+state: string,
+country: string,
+apt: int?,
+street: string?,
+zipcode: int?
+};
+
+create type addressType2 as {
+state: string,
+country: string
+};
+
+create type closedType1 as closed {
+id: int,
+name: string,
+address: addressType1?
+};
+
+create type closedType2 as closed {
+id: int,
+name: string,
+address: addressType2?
+};
+
+create type openType as open {
+id: int,
+name: string
+};
+
+create dataset closedDs1(closedType1) primary key id;
+create dataset closedDs2(closedType2) primary key id;
+create dataset openDs(openType) primary key id;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.2.update.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.2.update.sqlpp
new file mode 100644
index 0000000..c89bf16
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.2.update.sqlpp
@@ -0,0 +1,24 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *   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.
+ */
+
+use test;
+
+load dataset closedDs1 using localfs (("path"="asterix_nc1://data/complex/records1.adm"),("format"="adm"));
+load dataset closedDs2 using localfs (("path"="asterix_nc1://data/complex/records1.adm"),("format"="adm"));
+load dataset openDs using localfs (("path"="asterix_nc1://data/complex/records2.adm"),("format"="adm"));
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.3.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.3.query.sqlpp
new file mode 100644
index 0000000..2b97b84
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.3.query.sqlpp
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *   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.
+ */
+
+use test;
+
+select value v from openDs v order by v.address, v.id;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.4.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.4.query.sqlpp
new file mode 100644
index 0000000..d6840e1
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.4.query.sqlpp
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *   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.
+ */
+
+use test;
+
+select value v from closedDs1 v order by v.address, v.id;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.5.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.5.query.sqlpp
new file mode 100644
index 0000000..8de3f70
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.5.query.sqlpp
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *   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.
+ */
+
+use test;
+
+select value v from closedDs2 v order by v.address, v.id;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.6.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.6.query.sqlpp
new file mode 100644
index 0000000..32d592c
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.6.query.sqlpp
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *   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.
+ */
+
+use test;
+
+select value v from openDs v order by v.address desc, v.id;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.7.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.7.query.sqlpp
new file mode 100644
index 0000000..564630c
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.7.query.sqlpp
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *   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.
+ */
+
+use test;
+
+select value v from closedDs1 v order by v.address desc, v.id;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.8.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.8.query.sqlpp
new file mode 100644
index 0000000..2661017
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.8.query.sqlpp
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *   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.
+ */
+
+use test;
+
+select value v from closedDs2 v order by v.address desc, v.id;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.9.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.9.ddl.sqlpp
new file mode 100755
index 0000000..269f673
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/sorting/records/records.9.ddl.sqlpp
@@ -0,0 +1,20 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 at
+ *
+ *   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.
+ */
+
+drop  dataverse test;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.3.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.3.adm
new file mode 100644
index 0000000..2568592
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.3.adm
@@ -0,0 +1,35 @@
+{ "id": 16, "name": "Wail" }
+{ "id": 17, "name": "Jim" }
+{ "id": 15, "name": "Jim", "address": null }
+{ "id": 18, "name": "Kayle", "address": null }
+{ "id": 24, "name": "Trent", "address": null }
+{ "id": 19, "name": "Mart", "address": {  } }
+{ "id": 26, "name": "Nancy", "address": {  } }
+{ "id": 33, "name": "Tiger", "address": { "street": null, "apt": null, "state": "CO", "country": "USA" } }
+{ "id": 14, "name": "Jay", "address": { "street": "10th", "apt": null, "state": "MO", "country": "USA" } }
+{ "id": 2, "name": "Isac", "address": { "street": "14th", "apt": 1, "state": "MN", "zipcode": 78812, "country": "USA" } }
+{ "id": 7, "name": "Suzanna", "address": { "street": "11th", "apt": 2, "state": "CA", "zipcode": 92211, "country": "USA" } }
+{ "id": 1, "name": "Margarita", "address": { "street": "11th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA" } }
+{ "id": 12, "name": "John", "address": { "street": "11th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA" } }
+{ "id": 5, "name": "Von", "address": { "street": "17th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA" } }
+{ "id": 9, "name": "Woodrow", "address": { "street": "13th", "apt": 6, "state": "CO", "zipcode": 44321, "country": "USA" } }
+{ "id": 21, "name": "Ken", "address": { "street": "15th", "apt": 6, "state": "CO", "zipcode": 44321, "country": "USA" } }
+{ "id": 34, "name": "Nicole", "address": { "street": null, "apt": 7, "state": "OR", "zipcode": 97402, "country": "USA" } }
+{ "id": 8, "name": "Nicole", "address": { "street": "16th", "apt": 7, "state": "OR", "zipcode": 97403, "country": "USA" } }
+{ "id": 3, "name": "Emory", "address": { "street": "12th", "apt": 8, "state": "AL", "zipcode": 33212, "country": "USA" } }
+{ "id": 35, "name": "Adam", "address": { "street": "18th", "apt": 8, "state": "AL", "zipcode": 33212, "country": "USA" } }
+{ "id": 20, "name": "Mai", "address": { "street": "10th", "apt": 9, "state": "ON", "country": "Canada" } }
+{ "id": 6, "name": "Willis", "address": { "street": "10th", "apt": 9, "state": "MO", "country": "USA" } }
+{ "id": 25, "name": "Willis", "address": { "street": "18th", "apt": 9, "state": "MO", "country": "USA" } }
+{ "id": 30, "name": "Rock", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 31, "name": "Sam", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 22, "name": "Fend", "address": { "street": "16th", "state": "BC", "country": "Canada" } }
+{ "id": 32, "name": "May", "address": { "state": "ON", "country": "Canada" } }
+{ "id": 28, "name": "Lory", "address": { "state": "AL", "country": "USA" } }
+{ "id": 27, "name": "Eric", "address": { "state": "CA", "country": "USA" } }
+{ "id": 11, "name": "Nicholas", "address": { "state": "CA", "zipcode": 92212, "country": "USA" } }
+{ "id": 4, "name": "Nicholas", "address": { "street": "19th", "state": "IN", "zipcode": 88232, "country": "USA" } }
+{ "id": 13, "name": "Steve", "address": { "street": "19th", "state": "IN", "zipcode": 88232, "country": "USA" } }
+{ "id": 23, "name": "Adrian", "address": { "street": "14th", "state": "MN", "zipcode": 78812, "country": "USA" } }
+{ "id": 29, "name": "David", "address": { "state": "OR", "country": "USA" } }
+{ "id": 10, "name": "Bram", "address": { "state": "OR", "zipcode": 97444, "country": "USA" } }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.4.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.4.adm
new file mode 100644
index 0000000..3627e36
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.4.adm
@@ -0,0 +1,33 @@
+{ "id": 16, "name": "Wail" }
+{ "id": 17, "name": "Jim" }
+{ "id": 15, "name": "Jim", "address": null }
+{ "id": 18, "name": "Kayle", "address": null }
+{ "id": 24, "name": "Trent", "address": null }
+{ "id": 33, "name": "Tiger", "address": { "state": "CO", "country": "USA", "apt": null, "street": null } }
+{ "id": 14, "name": "Jay", "address": { "state": "MO", "country": "USA", "apt": null, "street": "10th" } }
+{ "id": 2, "name": "Isac", "address": { "state": "MN", "country": "USA", "apt": 1, "street": "14th", "zipcode": 78812 } }
+{ "id": 7, "name": "Suzanna", "address": { "state": "CA", "country": "USA", "apt": 2, "street": "11th", "zipcode": 92211 } }
+{ "id": 1, "name": "Margarita", "address": { "state": "CA", "country": "USA", "apt": 2, "street": "11th", "zipcode": 92212 } }
+{ "id": 12, "name": "John", "address": { "state": "CA", "country": "USA", "apt": 2, "street": "11th", "zipcode": 92212 } }
+{ "id": 5, "name": "Von", "address": { "state": "CA", "country": "USA", "apt": 2, "street": "17th", "zipcode": 92212 } }
+{ "id": 9, "name": "Woodrow", "address": { "state": "CO", "country": "USA", "apt": 6, "street": "13th", "zipcode": 44321 } }
+{ "id": 21, "name": "Ken", "address": { "state": "CO", "country": "USA", "apt": 6, "street": "15th", "zipcode": 44321 } }
+{ "id": 34, "name": "Nicole", "address": { "state": "OR", "country": "USA", "apt": 7, "street": null, "zipcode": 97402 } }
+{ "id": 8, "name": "Nicole", "address": { "state": "OR", "country": "USA", "apt": 7, "street": "16th", "zipcode": 97403 } }
+{ "id": 3, "name": "Emory", "address": { "state": "AL", "country": "USA", "apt": 8, "street": "12th", "zipcode": 33212 } }
+{ "id": 35, "name": "Adam", "address": { "state": "AL", "country": "USA", "apt": 8, "street": "18th", "zipcode": 33212 } }
+{ "id": 20, "name": "Mai", "address": { "state": "ON", "country": "Canada", "apt": 9, "street": "10th" } }
+{ "id": 6, "name": "Willis", "address": { "state": "MO", "country": "USA", "apt": 9, "street": "10th" } }
+{ "id": 25, "name": "Willis", "address": { "state": "MO", "country": "USA", "apt": 9, "street": "18th" } }
+{ "id": 30, "name": "Rock", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 31, "name": "Sam", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 22, "name": "Fend", "address": { "state": "BC", "country": "Canada", "street": "16th" } }
+{ "id": 32, "name": "May", "address": { "state": "ON", "country": "Canada" } }
+{ "id": 28, "name": "Lory", "address": { "state": "AL", "country": "USA" } }
+{ "id": 27, "name": "Eric", "address": { "state": "CA", "country": "USA" } }
+{ "id": 11, "name": "Nicholas", "address": { "state": "CA", "country": "USA", "zipcode": 92212 } }
+{ "id": 4, "name": "Nicholas", "address": { "state": "IN", "country": "USA", "street": "19th", "zipcode": 88232 } }
+{ "id": 13, "name": "Steve", "address": { "state": "IN", "country": "USA", "street": "19th", "zipcode": 88232 } }
+{ "id": 23, "name": "Adrian", "address": { "state": "MN", "country": "USA", "street": "14th", "zipcode": 78812 } }
+{ "id": 29, "name": "David", "address": { "state": "OR", "country": "USA" } }
+{ "id": 10, "name": "Bram", "address": { "state": "OR", "country": "USA", "zipcode": 97444 } }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.5.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.5.adm
new file mode 100644
index 0000000..013685c
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.5.adm
@@ -0,0 +1,33 @@
+{ "id": 16, "name": "Wail" }
+{ "id": 17, "name": "Jim" }
+{ "id": 15, "name": "Jim", "address": null }
+{ "id": 18, "name": "Kayle", "address": null }
+{ "id": 24, "name": "Trent", "address": null }
+{ "id": 33, "name": "Tiger", "address": { "state": "CO", "country": "USA", "street": null, "apt": null } }
+{ "id": 14, "name": "Jay", "address": { "state": "MO", "country": "USA", "street": "10th", "apt": null } }
+{ "id": 2, "name": "Isac", "address": { "state": "MN", "country": "USA", "street": "14th", "apt": 1, "zipcode": 78812 } }
+{ "id": 7, "name": "Suzanna", "address": { "state": "CA", "country": "USA", "street": "11th", "apt": 2, "zipcode": 92211 } }
+{ "id": 1, "name": "Margarita", "address": { "state": "CA", "country": "USA", "street": "11th", "apt": 2, "zipcode": 92212 } }
+{ "id": 12, "name": "John", "address": { "state": "CA", "country": "USA", "street": "11th", "apt": 2, "zipcode": 92212 } }
+{ "id": 5, "name": "Von", "address": { "state": "CA", "country": "USA", "street": "17th", "apt": 2, "zipcode": 92212 } }
+{ "id": 9, "name": "Woodrow", "address": { "state": "CO", "country": "USA", "street": "13th", "apt": 6, "zipcode": 44321 } }
+{ "id": 21, "name": "Ken", "address": { "state": "CO", "country": "USA", "street": "15th", "apt": 6, "zipcode": 44321 } }
+{ "id": 34, "name": "Nicole", "address": { "state": "OR", "country": "USA", "street": null, "apt": 7, "zipcode": 97402 } }
+{ "id": 8, "name": "Nicole", "address": { "state": "OR", "country": "USA", "street": "16th", "apt": 7, "zipcode": 97403 } }
+{ "id": 3, "name": "Emory", "address": { "state": "AL", "country": "USA", "street": "12th", "apt": 8, "zipcode": 33212 } }
+{ "id": 35, "name": "Adam", "address": { "state": "AL", "country": "USA", "street": "18th", "apt": 8, "zipcode": 33212 } }
+{ "id": 20, "name": "Mai", "address": { "state": "ON", "country": "Canada", "street": "10th", "apt": 9 } }
+{ "id": 6, "name": "Willis", "address": { "state": "MO", "country": "USA", "street": "10th", "apt": 9 } }
+{ "id": 25, "name": "Willis", "address": { "state": "MO", "country": "USA", "street": "18th", "apt": 9 } }
+{ "id": 30, "name": "Rock", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 31, "name": "Sam", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 22, "name": "Fend", "address": { "state": "BC", "country": "Canada", "street": "16th" } }
+{ "id": 32, "name": "May", "address": { "state": "ON", "country": "Canada" } }
+{ "id": 28, "name": "Lory", "address": { "state": "AL", "country": "USA" } }
+{ "id": 27, "name": "Eric", "address": { "state": "CA", "country": "USA" } }
+{ "id": 11, "name": "Nicholas", "address": { "state": "CA", "country": "USA", "zipcode": 92212 } }
+{ "id": 4, "name": "Nicholas", "address": { "state": "IN", "country": "USA", "street": "19th", "zipcode": 88232 } }
+{ "id": 13, "name": "Steve", "address": { "state": "IN", "country": "USA", "street": "19th", "zipcode": 88232 } }
+{ "id": 23, "name": "Adrian", "address": { "state": "MN", "country": "USA", "street": "14th", "zipcode": 78812 } }
+{ "id": 29, "name": "David", "address": { "state": "OR", "country": "USA" } }
+{ "id": 10, "name": "Bram", "address": { "state": "OR", "country": "USA", "zipcode": 97444 } }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.6.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.6.adm
new file mode 100644
index 0000000..7ef6e19
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.6.adm
@@ -0,0 +1,35 @@
+{ "id": 10, "name": "Bram", "address": { "state": "OR", "zipcode": 97444, "country": "USA" } }
+{ "id": 29, "name": "David", "address": { "state": "OR", "country": "USA" } }
+{ "id": 23, "name": "Adrian", "address": { "street": "14th", "state": "MN", "zipcode": 78812, "country": "USA" } }
+{ "id": 4, "name": "Nicholas", "address": { "street": "19th", "state": "IN", "zipcode": 88232, "country": "USA" } }
+{ "id": 13, "name": "Steve", "address": { "street": "19th", "state": "IN", "zipcode": 88232, "country": "USA" } }
+{ "id": 11, "name": "Nicholas", "address": { "state": "CA", "zipcode": 92212, "country": "USA" } }
+{ "id": 27, "name": "Eric", "address": { "state": "CA", "country": "USA" } }
+{ "id": 28, "name": "Lory", "address": { "state": "AL", "country": "USA" } }
+{ "id": 32, "name": "May", "address": { "state": "ON", "country": "Canada" } }
+{ "id": 22, "name": "Fend", "address": { "street": "16th", "state": "BC", "country": "Canada" } }
+{ "id": 30, "name": "Rock", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 31, "name": "Sam", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 25, "name": "Willis", "address": { "street": "18th", "apt": 9, "state": "MO", "country": "USA" } }
+{ "id": 6, "name": "Willis", "address": { "street": "10th", "apt": 9, "state": "MO", "country": "USA" } }
+{ "id": 20, "name": "Mai", "address": { "street": "10th", "apt": 9, "state": "ON", "country": "Canada" } }
+{ "id": 35, "name": "Adam", "address": { "street": "18th", "apt": 8, "state": "AL", "zipcode": 33212, "country": "USA" } }
+{ "id": 3, "name": "Emory", "address": { "street": "12th", "apt": 8, "state": "AL", "zipcode": 33212, "country": "USA" } }
+{ "id": 8, "name": "Nicole", "address": { "street": "16th", "apt": 7, "state": "OR", "zipcode": 97403, "country": "USA" } }
+{ "id": 34, "name": "Nicole", "address": { "street": null, "apt": 7, "state": "OR", "zipcode": 97402, "country": "USA" } }
+{ "id": 21, "name": "Ken", "address": { "street": "15th", "apt": 6, "state": "CO", "zipcode": 44321, "country": "USA" } }
+{ "id": 9, "name": "Woodrow", "address": { "street": "13th", "apt": 6, "state": "CO", "zipcode": 44321, "country": "USA" } }
+{ "id": 5, "name": "Von", "address": { "street": "17th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA" } }
+{ "id": 1, "name": "Margarita", "address": { "street": "11th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA" } }
+{ "id": 12, "name": "John", "address": { "street": "11th", "apt": 2, "state": "CA", "zipcode": 92212, "country": "USA" } }
+{ "id": 7, "name": "Suzanna", "address": { "street": "11th", "apt": 2, "state": "CA", "zipcode": 92211, "country": "USA" } }
+{ "id": 2, "name": "Isac", "address": { "street": "14th", "apt": 1, "state": "MN", "zipcode": 78812, "country": "USA" } }
+{ "id": 14, "name": "Jay", "address": { "street": "10th", "apt": null, "state": "MO", "country": "USA" } }
+{ "id": 33, "name": "Tiger", "address": { "street": null, "apt": null, "state": "CO", "country": "USA" } }
+{ "id": 19, "name": "Mart", "address": {  } }
+{ "id": 26, "name": "Nancy", "address": {  } }
+{ "id": 15, "name": "Jim", "address": null }
+{ "id": 18, "name": "Kayle", "address": null }
+{ "id": 24, "name": "Trent", "address": null }
+{ "id": 16, "name": "Wail" }
+{ "id": 17, "name": "Jim" }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.7.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.7.adm
new file mode 100644
index 0000000..3e6b39e
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.7.adm
@@ -0,0 +1,33 @@
+{ "id": 10, "name": "Bram", "address": { "state": "OR", "country": "USA", "zipcode": 97444 } }
+{ "id": 29, "name": "David", "address": { "state": "OR", "country": "USA" } }
+{ "id": 23, "name": "Adrian", "address": { "state": "MN", "country": "USA", "street": "14th", "zipcode": 78812 } }
+{ "id": 4, "name": "Nicholas", "address": { "state": "IN", "country": "USA", "street": "19th", "zipcode": 88232 } }
+{ "id": 13, "name": "Steve", "address": { "state": "IN", "country": "USA", "street": "19th", "zipcode": 88232 } }
+{ "id": 11, "name": "Nicholas", "address": { "state": "CA", "country": "USA", "zipcode": 92212 } }
+{ "id": 27, "name": "Eric", "address": { "state": "CA", "country": "USA" } }
+{ "id": 28, "name": "Lory", "address": { "state": "AL", "country": "USA" } }
+{ "id": 32, "name": "May", "address": { "state": "ON", "country": "Canada" } }
+{ "id": 22, "name": "Fend", "address": { "state": "BC", "country": "Canada", "street": "16th" } }
+{ "id": 30, "name": "Rock", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 31, "name": "Sam", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 25, "name": "Willis", "address": { "state": "MO", "country": "USA", "apt": 9, "street": "18th" } }
+{ "id": 6, "name": "Willis", "address": { "state": "MO", "country": "USA", "apt": 9, "street": "10th" } }
+{ "id": 20, "name": "Mai", "address": { "state": "ON", "country": "Canada", "apt": 9, "street": "10th" } }
+{ "id": 35, "name": "Adam", "address": { "state": "AL", "country": "USA", "apt": 8, "street": "18th", "zipcode": 33212 } }
+{ "id": 3, "name": "Emory", "address": { "state": "AL", "country": "USA", "apt": 8, "street": "12th", "zipcode": 33212 } }
+{ "id": 8, "name": "Nicole", "address": { "state": "OR", "country": "USA", "apt": 7, "street": "16th", "zipcode": 97403 } }
+{ "id": 34, "name": "Nicole", "address": { "state": "OR", "country": "USA", "apt": 7, "street": null, "zipcode": 97402 } }
+{ "id": 21, "name": "Ken", "address": { "state": "CO", "country": "USA", "apt": 6, "street": "15th", "zipcode": 44321 } }
+{ "id": 9, "name": "Woodrow", "address": { "state": "CO", "country": "USA", "apt": 6, "street": "13th", "zipcode": 44321 } }
+{ "id": 5, "name": "Von", "address": { "state": "CA", "country": "USA", "apt": 2, "street": "17th", "zipcode": 92212 } }
+{ "id": 1, "name": "Margarita", "address": { "state": "CA", "country": "USA", "apt": 2, "street": "11th", "zipcode": 92212 } }
+{ "id": 12, "name": "John", "address": { "state": "CA", "country": "USA", "apt": 2, "street": "11th", "zipcode": 92212 } }
+{ "id": 7, "name": "Suzanna", "address": { "state": "CA", "country": "USA", "apt": 2, "street": "11th", "zipcode": 92211 } }
+{ "id": 2, "name": "Isac", "address": { "state": "MN", "country": "USA", "apt": 1, "street": "14th", "zipcode": 78812 } }
+{ "id": 14, "name": "Jay", "address": { "state": "MO", "country": "USA", "apt": null, "street": "10th" } }
+{ "id": 33, "name": "Tiger", "address": { "state": "CO", "country": "USA", "apt": null, "street": null } }
+{ "id": 15, "name": "Jim", "address": null }
+{ "id": 18, "name": "Kayle", "address": null }
+{ "id": 24, "name": "Trent", "address": null }
+{ "id": 16, "name": "Wail" }
+{ "id": 17, "name": "Jim" }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.8.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.8.adm
new file mode 100644
index 0000000..847c95c
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/sorting/records/records.8.adm
@@ -0,0 +1,33 @@
+{ "id": 10, "name": "Bram", "address": { "state": "OR", "country": "USA", "zipcode": 97444 } }
+{ "id": 29, "name": "David", "address": { "state": "OR", "country": "USA" } }
+{ "id": 23, "name": "Adrian", "address": { "state": "MN", "country": "USA", "street": "14th", "zipcode": 78812 } }
+{ "id": 4, "name": "Nicholas", "address": { "state": "IN", "country": "USA", "street": "19th", "zipcode": 88232 } }
+{ "id": 13, "name": "Steve", "address": { "state": "IN", "country": "USA", "street": "19th", "zipcode": 88232 } }
+{ "id": 11, "name": "Nicholas", "address": { "state": "CA", "country": "USA", "zipcode": 92212 } }
+{ "id": 27, "name": "Eric", "address": { "state": "CA", "country": "USA" } }
+{ "id": 28, "name": "Lory", "address": { "state": "AL", "country": "USA" } }
+{ "id": 32, "name": "May", "address": { "state": "ON", "country": "Canada" } }
+{ "id": 22, "name": "Fend", "address": { "state": "BC", "country": "Canada", "street": "16th" } }
+{ "id": 30, "name": "Rock", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 31, "name": "Sam", "address": { "state": "BC", "country": "Canada" } }
+{ "id": 25, "name": "Willis", "address": { "state": "MO", "country": "USA", "street": "18th", "apt": 9 } }
+{ "id": 6, "name": "Willis", "address": { "state": "MO", "country": "USA", "street": "10th", "apt": 9 } }
+{ "id": 20, "name": "Mai", "address": { "state": "ON", "country": "Canada", "street": "10th", "apt": 9 } }
+{ "id": 35, "name": "Adam", "address": { "state": "AL", "country": "USA", "street": "18th", "apt": 8, "zipcode": 33212 } }
+{ "id": 3, "name": "Emory", "address": { "state": "AL", "country": "USA", "street": "12th", "apt": 8, "zipcode": 33212 } }
+{ "id": 8, "name": "Nicole", "address": { "state": "OR", "country": "USA", "street": "16th", "apt": 7, "zipcode": 97403 } }
+{ "id": 34, "name": "Nicole", "address": { "state": "OR", "country": "USA", "street": null, "apt": 7, "zipcode": 97402 } }
+{ "id": 21, "name": "Ken", "address": { "state": "CO", "country": "USA", "street": "15th", "apt": 6, "zipcode": 44321 } }
+{ "id": 9, "name": "Woodrow", "address": { "state": "CO", "country": "USA", "street": "13th", "apt": 6, "zipcode": 44321 } }
+{ "id": 5, "name": "Von", "address": { "state": "CA", "country": "USA", "street": "17th", "apt": 2, "zipcode": 92212 } }
+{ "id": 1, "name": "Margarita", "address": { "state": "CA", "country": "USA", "street": "11th", "apt": 2, "zipcode": 92212 } }
+{ "id": 12, "name": "John", "address": { "state": "CA", "country": "USA", "street": "11th", "apt": 2, "zipcode": 92212 } }
+{ "id": 7, "name": "Suzanna", "address": { "state": "CA", "country": "USA", "street": "11th", "apt": 2, "zipcode": 92211 } }
+{ "id": 2, "name": "Isac", "address": { "state": "MN", "country": "USA", "street": "14th", "apt": 1, "zipcode": 78812 } }
+{ "id": 14, "name": "Jay", "address": { "state": "MO", "country": "USA", "street": "10th", "apt": null } }
+{ "id": 33, "name": "Tiger", "address": { "state": "CO", "country": "USA", "street": null, "apt": null } }
+{ "id": 15, "name": "Jim", "address": null }
+{ "id": 18, "name": "Kayle", "address": null }
+{ "id": 24, "name": "Trent", "address": null }
+{ "id": 16, "name": "Wail" }
+{ "id": 17, "name": "Jim" }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml b/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
index 959813b..b39c2f8 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/testsuite_sqlpp.xml
@@ -121,6 +121,11 @@
         <output-dir compare="Text">arrays</output-dir>
       </compilation-unit>
     </test-case>
+    <test-case FilePath="sorting">
+      <compilation-unit name="records">
+        <output-dir compare="Text">records</output-dir>
+      </compilation-unit>
+    </test-case>
   </test-group>
   <test-group name="explain">
     <test-case FilePath="explain">
diff --git a/asterixdb/asterix-om/src/main/java/org/apache/asterix/dataflow/data/nontagged/comparators/AbstractAGenericBinaryComparator.java b/asterixdb/asterix-om/src/main/java/org/apache/asterix/dataflow/data/nontagged/comparators/AbstractAGenericBinaryComparator.java
index ce7d31a..9a5ae1d 100644
--- a/asterixdb/asterix-om/src/main/java/org/apache/asterix/dataflow/data/nontagged/comparators/AbstractAGenericBinaryComparator.java
+++ b/asterixdb/asterix-om/src/main/java/org/apache/asterix/dataflow/data/nontagged/comparators/AbstractAGenericBinaryComparator.java
@@ -18,21 +18,33 @@
  */
 package org.apache.asterix.dataflow.data.nontagged.comparators;
 
+import static org.apache.asterix.om.types.ATypeTag.SERIALIZED_MISSING_TYPE_TAG;
+import static org.apache.asterix.om.types.ATypeTag.VALUE_TYPE_MAPPING;
+
 import java.io.IOException;
+import java.util.Comparator;
+import java.util.List;
+import java.util.PriorityQueue;
 
 import org.apache.asterix.builders.AbvsBuilderFactory;
 import org.apache.asterix.dataflow.data.common.ListAccessorUtil;
+import org.apache.asterix.om.pointables.ARecordVisitablePointable;
+import org.apache.asterix.om.pointables.PointableAllocator;
 import org.apache.asterix.om.pointables.base.DefaultOpenFieldType;
+import org.apache.asterix.om.pointables.base.IVisitablePointable;
 import org.apache.asterix.om.typecomputer.impl.TypeComputeUtils;
+import org.apache.asterix.om.types.ARecordType;
 import org.apache.asterix.om.types.ATypeTag;
 import org.apache.asterix.om.types.AbstractCollectionType;
 import org.apache.asterix.om.types.EnumDeserializer;
 import org.apache.asterix.om.types.IAType;
+import org.apache.asterix.om.types.TypeTagUtil;
 import org.apache.asterix.om.types.hierachy.ATypeHierarchy;
 import org.apache.asterix.om.types.hierachy.ITypeConvertComputer;
 import org.apache.asterix.om.util.container.IObjectFactory;
 import org.apache.asterix.om.util.container.IObjectPool;
 import org.apache.asterix.om.util.container.ListObjectPool;
+import org.apache.asterix.om.utils.NonTaggedFormatUtil;
 import org.apache.hyracks.api.dataflow.value.IBinaryComparator;
 import org.apache.hyracks.api.exceptions.HyracksDataException;
 import org.apache.hyracks.data.std.accessors.PointableBinaryComparatorFactory;
@@ -115,6 +127,10 @@
     protected final IAType rightType;
     private final IObjectPool<IMutableValueStorage, ATypeTag> storageAllocator;
     private final IObjectPool<IPointable, Void> voidPointableAllocator;
+    // used for record comparison, sorting field names
+    private final PointableAllocator recordAllocator;
+    private final IObjectPool<PriorityQueue<IVisitablePointable>, Void> heapAllocator;
+    private final Comparator<IVisitablePointable> fieldNamesComparator;
 
     AbstractAGenericBinaryComparator(IAType leftType, IAType rightType) {
         // factory should have already made sure to get the actual type
@@ -123,6 +139,9 @@
         this.castBuffer = new ArrayBackedValueStorage();
         this.storageAllocator = new ListObjectPool<>(STORAGE_FACTORY);
         this.voidPointableAllocator = new ListObjectPool<>(VOID_FACTORY);
+        this.recordAllocator = new PointableAllocator();
+        this.fieldNamesComparator = createFieldNamesComp(ascStrComp);
+        this.heapAllocator = new ListObjectPool<>((type) -> new PriorityQueue<>(fieldNamesComparator));
     }
 
     protected int compare(IAType leftType, byte[] b1, int s1, int l1, IAType rightType, byte[] b2, int s2, int l2)
@@ -322,6 +341,8 @@
                 return ascByteArrayComp.compare(b1, s1 + 1, l1 - 1, b2, s2 + 1, l2 - 1);
             case ARRAY:
                 return compareArrays(leftType, b1, s1, l1, rightType, b2, s2, l2);
+            case OBJECT:
+                return compareRecords(leftType, b1, s1, l1, rightType, b2, s2, l2);
             default:
                 // we include typeTag in comparison to compare between two type to enforce some ordering
                 return rawComp.compare(b1, s1, l1, b2, s2, l2);
@@ -339,14 +360,8 @@
         }
         int leftNumItems = ListAccessorUtil.numberOfItems(b1, s1);
         int rightNumItems = ListAccessorUtil.numberOfItems(b2, s2);
-        IAType leftArrayType = TypeComputeUtils.getActualType(leftType);
-        if (leftArrayType.getTypeTag() == ATypeTag.ANY) {
-            leftArrayType = DefaultOpenFieldType.getDefaultOpenFieldType(ATypeTag.ARRAY);
-        }
-        IAType rightArrayType = TypeComputeUtils.getActualType(rightType);
-        if (rightArrayType.getTypeTag() == ATypeTag.ANY) {
-            rightArrayType = DefaultOpenFieldType.getDefaultOpenFieldType(ATypeTag.ARRAY);
-        }
+        IAType leftArrayType = getActualTypeOrOpen(leftType, ATypeTag.ARRAY);
+        IAType rightArrayType = getActualTypeOrOpen(rightType, ATypeTag.ARRAY);
         IAType leftItemType = ((AbstractCollectionType) leftArrayType).getItemType();
         IAType rightItemType = ((AbstractCollectionType) rightArrayType).getItemType();
         ATypeTag leftItemTag = leftItemType.getTypeTag();
@@ -378,4 +393,134 @@
             voidPointableAllocator.free(leftItem);
         }
     }
+
+    private int compareRecords(IAType leftType, byte[] b1, int s1, int l1, IAType rightType, byte[] b2, int s2, int l2)
+            throws HyracksDataException {
+        if (leftType == null || rightType == null) {
+            return rawComp.compare(b1, s1, l1, b2, s2, l2);
+        }
+        ARecordType leftRecordType = (ARecordType) getActualTypeOrOpen(leftType, ATypeTag.OBJECT);
+        ARecordType rightRecordType = (ARecordType) getActualTypeOrOpen(rightType, ATypeTag.OBJECT);
+        ARecordVisitablePointable leftRecord = recordAllocator.allocateRecordValue(leftRecordType);
+        ARecordVisitablePointable rightRecord = recordAllocator.allocateRecordValue(rightRecordType);
+        PriorityQueue<IVisitablePointable> leftNamesHeap = null, rightNamesHeap = null;
+        try {
+            leftRecord.set(b1, s1, l1);
+            rightRecord.set(b2, s2, l2);
+            List<IVisitablePointable> leftFieldsNames = leftRecord.getFieldNames();
+            List<IVisitablePointable> rightFieldsNames = rightRecord.getFieldNames();
+            List<IVisitablePointable> leftFieldsValues = leftRecord.getFieldValues();
+            List<IVisitablePointable> rightFieldsValues = rightRecord.getFieldValues();
+            leftNamesHeap = heapAllocator.allocate(null);
+            rightNamesHeap = heapAllocator.allocate(null);
+            leftNamesHeap.clear();
+            rightNamesHeap.clear();
+            int numLeftValuedFields = addToHeap(leftFieldsNames, leftFieldsValues, leftNamesHeap);;
+            int numRightValuedFields = addToHeap(rightFieldsNames, rightFieldsValues, rightNamesHeap);
+            if (numLeftValuedFields == 0 && numRightValuedFields == 0) {
+                return 0;
+            } else if (numLeftValuedFields == 0) {
+                return -1;
+            } else if (numRightValuedFields == 0) {
+                return 1;
+            }
+            int result;
+            int leftFieldIdx, rightFieldIdx;
+            IAType leftFieldType, rightFieldType;
+            IVisitablePointable leftFieldName, leftFieldValue, rightFieldName, rightFieldValue;
+            while (!leftNamesHeap.isEmpty() && !rightNamesHeap.isEmpty()) {
+                leftFieldName = leftNamesHeap.poll();
+                rightFieldName = rightNamesHeap.poll();
+                // compare the names first
+                result = ascStrComp.compare(leftFieldName.getByteArray(), leftFieldName.getStartOffset() + 1,
+                        leftFieldName.getLength() - 1, rightFieldName.getByteArray(),
+                        rightFieldName.getStartOffset() + 1, rightFieldName.getLength() - 1);
+                if (result != 0) {
+                    return result;
+                }
+                // then compare the values if the names are equal
+                leftFieldIdx = getIndex(leftFieldsNames, leftFieldName);
+                rightFieldIdx = getIndex(rightFieldsNames, rightFieldName);
+                leftFieldValue = leftFieldsValues.get(leftFieldIdx);
+                rightFieldValue = rightFieldsValues.get(rightFieldIdx);
+                leftFieldType = getType(leftRecordType, leftFieldIdx, leftFieldValue);
+                rightFieldType = getType(rightRecordType, rightFieldIdx, rightFieldValue);
+
+                result = compare(leftFieldType, leftFieldValue.getByteArray(), leftFieldValue.getStartOffset(),
+                        leftFieldValue.getLength(), rightFieldType, rightFieldValue.getByteArray(),
+                        rightFieldValue.getStartOffset(), rightFieldValue.getLength());
+                if (result != 0) {
+                    return result;
+                }
+            }
+
+            return Integer.compare(numLeftValuedFields, numRightValuedFields);
+        } finally {
+            recordAllocator.freeRecord(rightRecord);
+            recordAllocator.freeRecord(leftRecord);
+            if (rightNamesHeap != null) {
+                heapAllocator.free(rightNamesHeap);
+            }
+            if (leftNamesHeap != null) {
+                heapAllocator.free(leftNamesHeap);
+            }
+        }
+    }
+
+    private static IAType getActualTypeOrOpen(IAType type, ATypeTag tag) {
+        IAType actualType = TypeComputeUtils.getActualType(type);
+        return actualType.getTypeTag() == ATypeTag.ANY ? DefaultOpenFieldType.getDefaultOpenFieldType(tag) : actualType;
+    }
+
+    private static int addToHeap(List<IVisitablePointable> recordFNames, List<IVisitablePointable> recordFValues,
+            PriorityQueue<IVisitablePointable> names) {
+        // do not add fields whose value is missing, they don't exist in reality
+        int length = recordFNames.size();
+        IVisitablePointable fieldValue;
+        int count = 0;
+        for (int i = 0; i < length; i++) {
+            fieldValue = recordFValues.get(i);
+            if (fieldValue.getByteArray()[fieldValue.getStartOffset()] != SERIALIZED_MISSING_TYPE_TAG) {
+                names.add(recordFNames.get(i));
+                count++;
+            }
+        }
+        return count;
+    }
+
+    private static int getIndex(List<IVisitablePointable> names, IVisitablePointable instance) {
+        int size = names.size();
+        for (int i = 0; i < size; i++) {
+            if (instance == names.get(i)) {
+                return i;
+            }
+        }
+        throw new IllegalStateException();
+    }
+
+    private static IAType getType(ARecordType recordType, int fieldIdx, IVisitablePointable fieldValue)
+            throws HyracksDataException {
+        IAType[] fieldTypes = recordType.getFieldTypes();
+        if (fieldIdx >= fieldTypes.length) {
+            byte tag = fieldValue.getByteArray()[fieldValue.getStartOffset()];
+            ATypeTag fieldRuntimeTag = VALUE_TYPE_MAPPING[tag];
+            return fieldRuntimeTag.isDerivedType() ? DefaultOpenFieldType.getDefaultOpenFieldType(fieldRuntimeTag)
+                    : TypeTagUtil.getBuiltinTypeByTag(fieldRuntimeTag);
+        }
+        return fieldTypes[fieldIdx];
+    }
+
+    private static Comparator<IVisitablePointable> createFieldNamesComp(IBinaryComparator stringComp) {
+        return new Comparator<IVisitablePointable>() {
+            @Override
+            public int compare(IVisitablePointable name1, IVisitablePointable name2) {
+                try {
+                    return stringComp.compare(name1.getByteArray(), name1.getStartOffset() + 1, name1.getLength() - 1,
+                            name2.getByteArray(), name2.getStartOffset() + 1, name2.getLength() - 1);
+                } catch (HyracksDataException e) {
+                    throw new RuntimeException(e);
+                }
+            }
+        };
+    }
 }
diff --git a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/types/AUnorderedListType.java b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/types/AUnorderedListType.java
index 0b458dd..9defce0 100644
--- a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/types/AUnorderedListType.java
+++ b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/types/AUnorderedListType.java
@@ -31,6 +31,7 @@
 
     private static final long serialVersionUID = 1L;
 
+    // TODO: why is the item type "null"? why not ANY?
     public static final AUnorderedListType FULLY_OPEN_UNORDEREDLIST_TYPE = new AUnorderedListType(null, "");
 
     /**
diff --git a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/types/TypeTagUtil.java b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/types/TypeTagUtil.java
index 5d97125..e4167ec 100644
--- a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/types/TypeTagUtil.java
+++ b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/types/TypeTagUtil.java
@@ -85,6 +85,7 @@
             case OBJECT:
                 return RecordUtil.FULLY_OPEN_RECORD_TYPE;
             case MULTISET:
+                // TODO: how come the item type in this instance is "null"
                 return AUnorderedListType.FULLY_OPEN_UNORDEREDLIST_TYPE;
             case ARRAY:
                 return AOrderedListType.FULL_OPEN_ORDEREDLIST_TYPE;