diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
index 67dab65..5209b3e 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/base/RuleCollections.java
@@ -465,6 +465,7 @@
         prepareForJobGenRewrites.add(new FixReplicateOperatorOutputsRule());
         prepareForJobGenRewrites.add(new PopulateResultMetadataRule());
         prepareForJobGenRewrites.add(new AnnotateOperatorCostCardinalityRule());
+        prepareForJobGenRewrites.add(new EnsureColumnarSupportedTypesRule());
         return prepareForJobGenRewrites;
     }
 }
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceAutogenerateIDRule.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceAutogenerateIDRule.java
index 1fb035f..f51e307 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceAutogenerateIDRule.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/IntroduceAutogenerateIDRule.java
@@ -159,15 +159,14 @@
                 ((InternalDatasetDetails) dds.getDataset().getDatasetDetails()).getPrimaryKey().get(0);
         VariableReferenceExpression rec0 = new VariableReferenceExpression(inputRecord);
         rec0.setSourceLocation(inputRecordSourceLoc);
-        ILogicalExpression rec1 = createPrimaryKeyRecordExpression(pkFieldName, insertOpSourceLoc);
-        ILogicalExpression mergedRec = createRecordMergeFunction(rec0, rec1, insertOpSourceLoc);
+        ILogicalExpression mergedRec = createPutAutogeneratedKeyFunction(rec0, pkFieldName, insertOpSourceLoc);
         ILogicalExpression nonNullMergedRec = createNotNullFunction(mergedRec);
 
         LogicalVariable v = context.newVar();
-        AssignOperator newAssign = new AssignOperator(v, new MutableObject<ILogicalExpression>(nonNullMergedRec));
+        AssignOperator newAssign = new AssignOperator(v, new MutableObject<>(nonNullMergedRec));
         newAssign.setSourceLocation(insertOpSourceLoc);
-        newAssign.getInputs().add(new MutableObject<ILogicalOperator>(newAssignParentOp));
-        newAssignChildOp.getInputs().set(0, new MutableObject<ILogicalOperator>(newAssign));
+        newAssign.getInputs().add(new MutableObject<>(newAssignParentOp));
+        newAssignChildOp.getInputs().set(0, new MutableObject<>(newAssign));
         if (hasFilter) {
             VariableUtilities.substituteVariables(newAssignChildOp, inputRecord, v, context);
         }
@@ -189,52 +188,26 @@
 
     private ILogicalExpression createNotNullFunction(ILogicalExpression mergedRec) {
         List<Mutable<ILogicalExpression>> args = new ArrayList<>();
-        args.add(new MutableObject<ILogicalExpression>(mergedRec));
+        args.add(new MutableObject<>(mergedRec));
         AbstractFunctionCallExpression notNullFn =
                 new ScalarFunctionCallExpression(FunctionUtil.getFunctionInfo(BuiltinFunctions.CHECK_UNKNOWN), args);
         notNullFn.setSourceLocation(mergedRec.getSourceLocation());
         return notNullFn;
     }
 
-    private AbstractFunctionCallExpression createPrimaryKeyRecordExpression(List<String> pkFieldName,
-            SourceLocation sourceLoc) {
-        //Create lowest level of nested uuid
-        AbstractFunctionCallExpression uuidFn =
-                new ScalarFunctionCallExpression(FunctionUtil.getFunctionInfo(BuiltinFunctions.CREATE_UUID));
-        uuidFn.setSourceLocation(sourceLoc);
-        List<Mutable<ILogicalExpression>> openRecordConsArgs = new ArrayList<>();
-        ConstantExpression pkFieldNameExpression =
-                new ConstantExpression(new AsterixConstantValue(new AString(pkFieldName.get(pkFieldName.size() - 1))));
-        pkFieldNameExpression.setSourceLocation(sourceLoc);
-        openRecordConsArgs.add(new MutableObject<>(pkFieldNameExpression));
-        openRecordConsArgs.add(new MutableObject<>(uuidFn));
-        AbstractFunctionCallExpression openRecFn = new ScalarFunctionCallExpression(
-                FunctionUtil.getFunctionInfo(BuiltinFunctions.OPEN_RECORD_CONSTRUCTOR), openRecordConsArgs);
-        openRecFn.setSourceLocation(sourceLoc);
-
-        //Create higher levels
-        for (int i = pkFieldName.size() - 2; i > -1; i--) {
-            AString fieldName = new AString(pkFieldName.get(i));
-            openRecordConsArgs = new ArrayList<>();
-            openRecordConsArgs.add(
-                    new MutableObject<ILogicalExpression>(new ConstantExpression(new AsterixConstantValue(fieldName))));
-            openRecordConsArgs.add(new MutableObject<ILogicalExpression>(openRecFn));
-            openRecFn = new ScalarFunctionCallExpression(
-                    FunctionUtil.getFunctionInfo(BuiltinFunctions.OPEN_RECORD_CONSTRUCTOR), openRecordConsArgs);
-            openRecFn.setSourceLocation(sourceLoc);
+    private AbstractFunctionCallExpression createPutAutogeneratedKeyFunction(ILogicalExpression rec0,
+            List<String> keyName, SourceLocation sourceLoc) {
+        List<Mutable<ILogicalExpression>> putAutogeneratedKeyFnArgs = new ArrayList<>();
+        putAutogeneratedKeyFnArgs.add(new MutableObject<>(rec0));
+        for (String s : keyName) {
+            ConstantExpression pkFieldNameExpression = new ConstantExpression(new AsterixConstantValue(new AString(s)));
+            pkFieldNameExpression.setSourceLocation(sourceLoc);
+            putAutogeneratedKeyFnArgs.add(new MutableObject<>(pkFieldNameExpression));
         }
 
-        return openRecFn;
-    }
-
-    private AbstractFunctionCallExpression createRecordMergeFunction(ILogicalExpression rec0, ILogicalExpression rec1,
-            SourceLocation sourceLoc) {
-        List<Mutable<ILogicalExpression>> recordMergeFnArgs = new ArrayList<>();
-        recordMergeFnArgs.add(new MutableObject<>(rec0));
-        recordMergeFnArgs.add(new MutableObject<>(rec1));
-        AbstractFunctionCallExpression recordMergeFn = new ScalarFunctionCallExpression(
-                FunctionUtil.getFunctionInfo(BuiltinFunctions.RECORD_MERGE_IGNORE_DUPLICATES), recordMergeFnArgs);
-        recordMergeFn.setSourceLocation(sourceLoc);
-        return recordMergeFn;
+        AbstractFunctionCallExpression putAutogeneratedKeyFn = new ScalarFunctionCallExpression(
+                FunctionUtil.getFunctionInfo(BuiltinFunctions.PUT_AUTOGENERATED_KEY), putAutogeneratedKeyFnArgs);
+        putAutogeneratedKeyFn.setSourceLocation(sourceLoc);
+        return putAutogeneratedKeyFn;
     }
 }
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.1.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.1.ddl.sqlpp
new file mode 100644
index 0000000..3ae1d7e
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.1.ddl.sqlpp
@@ -0,0 +1,25 @@
+/*
+ * 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 COLLECTION c PRIMARY KEY (a.id: uuid) AUTOGENERATED;
+UPSERT INTO c ([{"name":"j", "a":{"id": uuid()}}, {"a":{"id":uuid()}}]);
+UPSERT INTO c ([{"name":"j", "a":{"id": uuid()}}, {"a":{"id":"a"}}]);
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.2.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.2.ddl.sqlpp
new file mode 100644
index 0000000..124746b
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.2.ddl.sqlpp
@@ -0,0 +1,26 @@
+/*
+ * 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;
+
+CREATE TYPE openType AS {id: int};
+CREATE TYPE openType2 AS {id: int, myKey: uuid};
+CREATE DATASET ds(openType) PRIMARY KEY id;
+CREATE DATASET ds2(openType2) PRIMARY KEY myKey AUTOGENERATED;
+UPSERT INTO ds ([{"id": 1, "myKey": "xxxx"}, {"id": 2, "myKey": "yyyy"}]);
+UPSERT INTO ds2 SELECT VALUE v FROM ds v;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.3.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.3.query.sqlpp
new file mode 100644
index 0000000..f9e0334
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.3.query.sqlpp
@@ -0,0 +1,21 @@
+/*
+ * 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 COUNT(*) AS cnt FROM c;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.4.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.4.query.sqlpp
new file mode 100644
index 0000000..7a5b1e0
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.4.query.sqlpp
@@ -0,0 +1,21 @@
+/*
+ * 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 COUNT(*) AS cnt FROM ds;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.5.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.5.query.sqlpp
new file mode 100644
index 0000000..812f2c5
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.5.query.sqlpp
@@ -0,0 +1,21 @@
+/*
+ * 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 COUNT(*) AS cnt FROM ds2;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.9.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.9.ddl.sqlpp
new file mode 100644
index 0000000..36b2bab
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/nested-type/nested-type.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 IF EXISTS;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.1.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.1.ddl.sqlpp
new file mode 100644
index 0000000..2e3cbcb
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.1.ddl.sqlpp
@@ -0,0 +1,27 @@
+/*
+ * 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 COLLECTION pk_auto PRIMARY KEY (myKey: uuid) AUTOGENERATED;
+CREATE COLLECTION pk_auto2 PRIMARY KEY (myKey: uuid) AUTOGENERATED;
+UPSERT INTO pk_auto ([ {"x": "a"}] );
+UPSERT INTO pk_auto ([{"myKey" :uuid()} , {"x": 5}] );
+UPSERT INTO pk_auto ([{"myKey" :"x"} , {"x": "abc"}] );
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.2.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.2.ddl.sqlpp
new file mode 100644
index 0000000..81ceb39
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.2.ddl.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;
+
+UPSERT INTO pk_auto ([{"x": "abc","myKey": uuid(),"emp":{"age":23,"myKey":345 }},{"myKey":uuid()}]);
+UPSERT INTO pk_auto ([{"x": "abc","myKey": 566,"emp":{"age":23,"myKey":345 }},{"myKey":uuid()}]);
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.3.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.3.ddl.sqlpp
new file mode 100644
index 0000000..b710bb6
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.3.ddl.sqlpp
@@ -0,0 +1,21 @@
+/*
+ * 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;
+
+UPSERT INTO pk_auto ([{"x": "abc","myKey": uuid(),"emp":{"age":23,"myKey":345 }},{"myKey":"abc"}]);
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.4.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.4.ddl.sqlpp
new file mode 100644
index 0000000..3084025
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.4.ddl.sqlpp
@@ -0,0 +1,124 @@
+/*
+ * 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;
+
+UPSERT INTO pk_auto2 (
+[
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b6355d",
+    "callsign": "AIRLINAIR",
+    "country": "France",
+    "iata": "A5",
+    "icao": "RLA",
+    "id": 1203,
+    "name": "Airlinair",
+    "type": "airline"
+  },
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b63555",
+    "callsign": "TXW",
+    "country": "United States",
+    "iata": "TQ",
+    "icao": "TXW",
+    "id": 10123,
+    "name": "Texas Wings",
+    "type": "airline"
+  },
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b63556",
+    "callsign": "atifly",
+    "country": "United States",
+    "iata": "A1",
+    "icao": "A1F",
+    "id": 10226,
+    "name": "Atifly",
+    "type": "airline"
+  },
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b6355a",
+    "callsign": "ACE AIR",
+    "country": "United States",
+    "iata": "KO",
+    "icao": "AER",
+    "id": 109,
+    "name": "Alaska Central Express",
+    "type": "airline"
+  },
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b63559",
+    "callsign": "SASQUATCH",
+    "country": "United States",
+    "iata": "K5",
+    "icao": "SQH",
+    "id": 10765,
+    "name": "SeaPort Airlines",
+    "type": "airline"
+  },
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b6355b",
+    "callsign": "FLYSTAR",
+    "country": "United Kingdom",
+    "iata": "5W",
+    "icao": "AEU",
+    "id": 112,
+    "name": "Astraeus",
+    "type": "airline"
+  },
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b63558",
+    "callsign": "LOCAIR",
+    "country": "United States",
+    "iata": "ZQ",
+    "icao": "LOC",
+    "id": 10748,
+    "name": "Locair",
+    "type": "airline"
+  },
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b63554",
+    "callsign": "MILE-AIR",
+    "country": "United States",
+    "iata": "Q5",
+    "icao": "MLA",
+    "id": 10,
+    "name": "40-Mile Air",
+    "type": "airline"
+  },
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b63557",
+    "callsign": null,
+    "country": "United Kingdom",
+    "iata": null,
+    "icao": "JRB",
+    "id": 10642,
+    "name": "Jc royal.britannica",
+    "type": "airline"
+  },
+  {
+    "myKey": "2be3fcf4-f86b-09d0-4bf2-eac9d1b6355c",
+    "callsign": "REUNION",
+    "country": "France",
+    "iata": "UU",
+    "icao": "REU",
+    "id": 1191,
+    "name": "Air Austral",
+    "type": "airline"
+  }
+]
+);
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.5.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.5.query.sqlpp
new file mode 100644
index 0000000..43e184b
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.5.query.sqlpp
@@ -0,0 +1,21 @@
+/*
+ * 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 COUNT(*) AS cnt FROM pk_auto;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.6.query.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.6.query.sqlpp
new file mode 100644
index 0000000..2dc2e9c
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.6.query.sqlpp
@@ -0,0 +1,21 @@
+/*
+ * 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 COUNT(*) AS cnt FROM pk_auto2;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.9.ddl.sqlpp b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.9.ddl.sqlpp
new file mode 100644
index 0000000..36b2bab
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/queries_sqlpp/auto_key/simple-type/simple-type.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 IF EXISTS;
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/nested-type/nested-type.3.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/nested-type/nested-type.3.adm
new file mode 100644
index 0000000..3591912
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/nested-type/nested-type.3.adm
@@ -0,0 +1 @@
+{ "cnt": 2 }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/nested-type/nested-type.4.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/nested-type/nested-type.4.adm
new file mode 100644
index 0000000..3591912
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/nested-type/nested-type.4.adm
@@ -0,0 +1 @@
+{ "cnt": 2 }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/nested-type/nested-type.5.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/nested-type/nested-type.5.adm
new file mode 100644
index 0000000..bacb60c
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/nested-type/nested-type.5.adm
@@ -0,0 +1 @@
+{ "cnt": 0 }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/simple-type/simple-type.5.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/simple-type/simple-type.5.adm
new file mode 100644
index 0000000..c3bf580
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/simple-type/simple-type.5.adm
@@ -0,0 +1 @@
+{ "cnt": 5 }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/simple-type/simple-type.6.adm b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/simple-type/simple-type.6.adm
new file mode 100644
index 0000000..bacb60c
--- /dev/null
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/results/auto_key/simple-type/simple-type.6.adm
@@ -0,0 +1 @@
+{ "cnt": 0 }
\ No newline at end of file
diff --git a/asterixdb/asterix-app/src/test/resources/runtimets/sqlpp_queries.xml b/asterixdb/asterix-app/src/test/resources/runtimets/sqlpp_queries.xml
index d476c25..040b3ca 100644
--- a/asterixdb/asterix-app/src/test/resources/runtimets/sqlpp_queries.xml
+++ b/asterixdb/asterix-app/src/test/resources/runtimets/sqlpp_queries.xml
@@ -16622,4 +16622,22 @@
       </compilation-unit>
     </test-case>
   </test-group>
+  <test-group name="auto_key">
+    <test-case FilePath="auto_key">
+      <compilation-unit name="simple-type">
+        <output-dir compare="Clean-JSON">simple-type</output-dir>
+        <expected-error>ASX0001: Field type string cannot be promoted to type uuid</expected-error>
+        <expected-error>ASX0001: Field type bigint cannot be promoted to type uuid</expected-error>
+        <expected-error>ASX0001: Field type string cannot be promoted to type uuid</expected-error>
+        <expected-error>ASX0001: Field type string cannot be promoted to type uuid</expected-error>
+      </compilation-unit>
+    </test-case>
+    <test-case FilePath="auto_key">
+      <compilation-unit name="nested-type">
+        <output-dir compare="Clean-JSON">nested-type</output-dir>
+        <expected-error>ASX0001: Field type string cannot be promoted to type uuid</expected-error>
+        <expected-error>ASX0001: Field type string cannot be promoted to type uuid</expected-error>
+      </compilation-unit>
+    </test-case>
+  </test-group>
 </test-group>
\ No newline at end of file
diff --git a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java
index c65cf38..d7e9210 100644
--- a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java
+++ b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/functions/BuiltinFunctions.java
@@ -119,6 +119,7 @@
 import org.apache.asterix.om.typecomputer.impl.OrderedListOfAStringTypeComputer;
 import org.apache.asterix.om.typecomputer.impl.OrderedListOfAnyTypeComputer;
 import org.apache.asterix.om.typecomputer.impl.PropagateTypeComputer;
+import org.apache.asterix.om.typecomputer.impl.PutAutogeneratedKeyTypeComputer;
 import org.apache.asterix.om.typecomputer.impl.RecordAddFieldsTypeComputer;
 import org.apache.asterix.om.typecomputer.impl.RecordAddTypeComputer;
 import org.apache.asterix.om.typecomputer.impl.RecordMergeTypeComputer;
@@ -1282,6 +1283,9 @@
 
     public static final FunctionIdentifier SERIALIZED_SIZE = FunctionConstants.newAsterix("serialized-size", 1);
 
+    public static final FunctionIdentifier PUT_AUTOGENERATED_KEY =
+            FunctionConstants.newAsterix("put-autogenerated-key", FunctionIdentifier.VARARGS);
+
     static {
         // first, take care of Algebricks builtin functions
         addFunction(IS_MISSING, BooleanOnlyTypeComputer.INSTANCE, true);
@@ -2136,6 +2140,9 @@
         // unnesting function
         addPrivateFunction(SCAN_COLLECTION, CollectionMemberResultType.INSTANCE, true);
 
+        // used by UPSERT/INSERT for collections with autogenerated uuid
+        addPrivateFunction(PUT_AUTOGENERATED_KEY, PutAutogeneratedKeyTypeComputer.INSTANCE, false);
+
     }
 
     static {
diff --git a/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/typecomputer/impl/PutAutogeneratedKeyTypeComputer.java b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/typecomputer/impl/PutAutogeneratedKeyTypeComputer.java
new file mode 100644
index 0000000..7f3bbdc
--- /dev/null
+++ b/asterixdb/asterix-om/src/main/java/org/apache/asterix/om/typecomputer/impl/PutAutogeneratedKeyTypeComputer.java
@@ -0,0 +1,158 @@
+/*
+ * 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.
+ */
+
+package org.apache.asterix.om.typecomputer.impl;
+
+import java.util.Arrays;
+import java.util.List;
+
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.common.exceptions.ErrorCode;
+import org.apache.asterix.om.exceptions.TypeMismatchException;
+import org.apache.asterix.om.typecomputer.base.IResultTypeComputer;
+import org.apache.asterix.om.types.ARecordType;
+import org.apache.asterix.om.types.ATypeTag;
+import org.apache.asterix.om.types.AUnionType;
+import org.apache.asterix.om.types.BuiltinType;
+import org.apache.asterix.om.types.IAType;
+import org.apache.asterix.om.types.TypeHelper;
+import org.apache.asterix.om.utils.ConstantExpressionUtil;
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+import org.apache.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import org.apache.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+import org.apache.hyracks.algebricks.core.algebra.expressions.IVariableTypeEnvironment;
+import org.apache.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
+import org.apache.hyracks.algebricks.core.algebra.metadata.IMetadataProvider;
+import org.apache.hyracks.api.exceptions.SourceLocation;
+
+public class PutAutogeneratedKeyTypeComputer implements IResultTypeComputer {
+
+    public static final PutAutogeneratedKeyTypeComputer INSTANCE = new PutAutogeneratedKeyTypeComputer();
+
+    private PutAutogeneratedKeyTypeComputer() {
+    }
+
+    @Override
+    public IAType computeType(ILogicalExpression expression, IVariableTypeEnvironment env,
+            IMetadataProvider<?, ?> metadataProvider) throws AlgebricksException {
+        AbstractFunctionCallExpression f = (AbstractFunctionCallExpression) expression;
+        FunctionIdentifier funcId = f.getFunctionIdentifier();
+        List<Mutable<ILogicalExpression>> funArgs = f.getArguments();
+        IAType inRecArg = (IAType) env.getType(funArgs.get(0).getValue());
+        boolean unknownable = TypeHelper.canBeUnknown(inRecArg);
+        ARecordType inRecType = TypeComputeUtils.extractRecordType(inRecArg);
+        if (inRecType == null) {
+            throw new TypeMismatchException(f.getSourceLocation(), funcId, 0, inRecArg.getTypeTag(), ATypeTag.OBJECT);
+        }
+        String[] keyNameParts = getKeyNameParts(funArgs);
+        return computeOutRecType(inRecType, keyNameParts, unknownable, f.getSourceLocation());
+    }
+
+    private static IAType computeOutRecType(ARecordType inRecType, String[] keyNameParts, boolean unknownable,
+            SourceLocation sourceLocation) throws AlgebricksException {
+        String[] inFieldNames = inRecType.getFieldNames();
+        String[] resultFieldNames = Arrays.copyOf(inFieldNames, inFieldNames.length);
+        IAType[] resultFieldTypes = new IAType[resultFieldNames.length];
+        int k = 0;
+        return computeResultType(resultFieldNames, resultFieldTypes, inRecType, keyNameParts, k, unknownable,
+                sourceLocation);
+    }
+
+    private static IAType computeResultType(String[] resultFieldNames, IAType[] resultFieldTypes, ARecordType inRecType,
+            String[] keyNameParts, int k, boolean unknownable, SourceLocation sourceLocation)
+            throws CompilationException {
+        boolean keyFound = false;
+        for (int i = 0; i < resultFieldNames.length; i++) {
+            String fName = resultFieldNames[i];
+            IAType fType = inRecType.getFieldType(fName);
+            if (keyNameParts[k].equals(fName)) {
+                keyFound = true;
+                resultFieldTypes[i] = computeAutoType(fType, keyNameParts, k, sourceLocation);
+            } else {
+                if (fType.getTypeTag() == ATypeTag.OBJECT) {
+                    ARecordType nestedType = (ARecordType) fType;
+                    // deep copy prevents altering of input types
+                    resultFieldTypes[i] = nestedType.deepCopy(nestedType);
+                } else {
+                    resultFieldTypes[i] = fType;
+                }
+            }
+        }
+        boolean isOpen = inRecType.isOpen();
+        IAType resultType;
+        if (!keyFound) {
+            resultType = addAutoKeyType(resultFieldNames, resultFieldTypes, isOpen, keyNameParts, k);
+        } else {
+            resultType = new ARecordType("", resultFieldNames, resultFieldTypes, isOpen);
+        }
+        if (unknownable) {
+            resultType = AUnionType.createUnknownableType(resultType);
+        }
+        return resultType;
+    }
+
+    private static IAType addAutoKeyType(String[] resultFieldNames, IAType[] resultFieldTypes, boolean isOpen,
+            String[] keyNameParts, int k) {
+        IAType computedNestedType = BuiltinType.AUUID;
+        int lastPart = keyNameParts.length - 1;
+        for (int i = lastPart; i > k; i--) {
+            computedNestedType =
+                    new ARecordType("", new String[] { keyNameParts[i] }, new IAType[] { computedNestedType }, isOpen);
+        }
+        String[] finalResultFieldNames = Arrays.copyOf(resultFieldNames, resultFieldNames.length + 1);
+        IAType[] finalResultFieldTypes = Arrays.copyOf(resultFieldTypes, resultFieldTypes.length + 1);
+        finalResultFieldNames[finalResultFieldNames.length - 1] = keyNameParts[k];
+        finalResultFieldTypes[finalResultFieldTypes.length - 1] = computedNestedType;
+        return new ARecordType("", finalResultFieldNames, finalResultFieldTypes, isOpen);
+    }
+
+    private static IAType computeAutoType(IAType keyPartType, String[] keyNameParts, int k,
+            SourceLocation sourceLocation) throws CompilationException {
+        IAType fType = TypeComputeUtils.getActualType(keyPartType);
+        if (k == keyNameParts.length - 1) {
+            // reached the final key name part, check it's UUID
+            if (fType.getTypeTag() != ATypeTag.UUID) {
+                throw new CompilationException(ErrorCode.CASTING_FIELD, sourceLocation, fType.getTypeTag(),
+                        ATypeTag.UUID);
+            }
+            return fType;
+        }
+        // keyPartType should be a record because there is more nesting until reaching the final key part
+        if (fType.getTypeTag() != ATypeTag.OBJECT) {
+            throw new CompilationException(ErrorCode.CASTING_FIELD, sourceLocation, fType.getTypeTag(),
+                    ATypeTag.OBJECT);
+        }
+        boolean unknownable = TypeHelper.canBeUnknown(keyPartType);
+        ARecordType recType = (ARecordType) fType;
+        String[] inFieldNames = recType.getFieldNames();
+        String[] resultFieldNames = Arrays.copyOf(inFieldNames, inFieldNames.length);
+        IAType[] resultFieldTypes = new IAType[resultFieldNames.length];
+        return computeResultType(resultFieldNames, resultFieldTypes, recType, keyNameParts, k + 1, unknownable,
+                sourceLocation);
+    }
+
+    private static String[] getKeyNameParts(List<Mutable<ILogicalExpression>> funArgs) {
+        String[] keyName = new String[funArgs.size() - 1];
+        for (int i = 1, k = 0; i < funArgs.size(); i++, k++) {
+            keyName[k] = ConstantExpressionUtil.getStringConstant(funArgs.get(i).getValue());
+        }
+        return keyName;
+    }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/records/PutAutogeneratedKeyDescriptor.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/records/PutAutogeneratedKeyDescriptor.java
new file mode 100644
index 0000000..8293a26
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/records/PutAutogeneratedKeyDescriptor.java
@@ -0,0 +1,80 @@
+/*
+ * 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.
+ */
+package org.apache.asterix.runtime.evaluators.functions.records;
+
+import org.apache.asterix.common.annotations.MissingNullInOutFunction;
+import org.apache.asterix.om.functions.BuiltinFunctions;
+import org.apache.asterix.om.functions.IFunctionDescriptor;
+import org.apache.asterix.om.functions.IFunctionDescriptorFactory;
+import org.apache.asterix.om.functions.IFunctionTypeInferer;
+import org.apache.asterix.om.typecomputer.impl.TypeComputeUtils;
+import org.apache.asterix.om.types.ARecordType;
+import org.apache.asterix.om.types.IAType;
+import org.apache.asterix.runtime.evaluators.base.AbstractScalarFunctionDynamicDescriptor;
+import org.apache.asterix.runtime.functions.FunctionTypeInferers;
+import org.apache.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
+import org.apache.hyracks.algebricks.runtime.base.IEvaluatorContext;
+import org.apache.hyracks.algebricks.runtime.base.IScalarEvaluator;
+import org.apache.hyracks.algebricks.runtime.base.IScalarEvaluatorFactory;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+
+@MissingNullInOutFunction
+public class PutAutogeneratedKeyDescriptor extends AbstractScalarFunctionDynamicDescriptor {
+
+    private static final long serialVersionUID = 1L;
+
+    public static final IFunctionDescriptorFactory FACTORY = new IFunctionDescriptorFactory() {
+        @Override
+        public IFunctionDescriptor createFunctionDescriptor() {
+            return new PutAutogeneratedKeyDescriptor();
+        }
+
+        @Override
+        public IFunctionTypeInferer createFunctionTypeInferer() {
+            return new FunctionTypeInferers.PutAutogeneratedKeyTypeInferer();
+        }
+    };
+
+    private ARecordType outRecType;
+    private ARecordType inRecType;
+
+    @Override
+    public void setImmutableStates(Object... states) {
+        outRecType = TypeComputeUtils.extractRecordType((IAType) states[0]);
+        inRecType = TypeComputeUtils.extractRecordType((IAType) states[1]);
+    }
+
+    @Override
+    public IScalarEvaluatorFactory createEvaluatorFactory(final IScalarEvaluatorFactory[] args) {
+        return new IScalarEvaluatorFactory() {
+
+            private static final long serialVersionUID = 1L;
+
+            @Override
+            public IScalarEvaluator createScalarEvaluator(final IEvaluatorContext ctx) throws HyracksDataException {
+                return new PutAutogeneratedKeyEvaluator(ctx, args, outRecType, inRecType, sourceLoc, getIdentifier());
+            }
+        };
+    }
+
+    @Override
+    public FunctionIdentifier getIdentifier() {
+        return BuiltinFunctions.PUT_AUTOGENERATED_KEY;
+    }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/records/PutAutogeneratedKeyEvaluator.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/records/PutAutogeneratedKeyEvaluator.java
new file mode 100644
index 0000000..6302c78
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/evaluators/functions/records/PutAutogeneratedKeyEvaluator.java
@@ -0,0 +1,215 @@
+/*
+ * 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.
+ */
+package org.apache.asterix.runtime.evaluators.functions.records;
+
+import java.io.DataOutput;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.asterix.builders.RecordBuilder;
+import org.apache.asterix.common.exceptions.ErrorCode;
+import org.apache.asterix.common.exceptions.RuntimeDataException;
+import org.apache.asterix.formats.nontagged.SerializerDeserializerProvider;
+import org.apache.asterix.om.base.AGeneratedUUID;
+import org.apache.asterix.om.base.AUUID;
+import org.apache.asterix.om.pointables.ARecordVisitablePointable;
+import org.apache.asterix.om.pointables.PointableAllocator;
+import org.apache.asterix.om.pointables.base.IVisitablePointable;
+import org.apache.asterix.om.types.ARecordType;
+import org.apache.asterix.om.types.ATypeTag;
+import org.apache.asterix.om.types.BuiltinType;
+import org.apache.asterix.om.types.runtime.RuntimeRecordTypeInfo;
+import org.apache.asterix.runtime.evaluators.functions.AbstractScalarEval;
+import org.apache.asterix.runtime.evaluators.functions.PointableHelper;
+import org.apache.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
+import org.apache.hyracks.algebricks.runtime.base.IEvaluatorContext;
+import org.apache.hyracks.algebricks.runtime.base.IScalarEvaluator;
+import org.apache.hyracks.algebricks.runtime.base.IScalarEvaluatorFactory;
+import org.apache.hyracks.api.dataflow.value.IBinaryComparator;
+import org.apache.hyracks.api.dataflow.value.ISerializerDeserializer;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.api.exceptions.SourceLocation;
+import org.apache.hyracks.data.std.accessors.UTF8StringBinaryComparatorFactory;
+import org.apache.hyracks.data.std.api.IPointable;
+import org.apache.hyracks.data.std.api.IValueReference;
+import org.apache.hyracks.data.std.primitive.VoidPointable;
+import org.apache.hyracks.data.std.util.ArrayBackedValueStorage;
+import org.apache.hyracks.dataflow.common.data.accessors.IFrameTupleReference;
+
+public class PutAutogeneratedKeyEvaluator extends AbstractScalarEval {
+
+    private final IPointable inRecPointable = new VoidPointable();
+    private final List<RecordBuilder> rbStack = new ArrayList<>();
+    private final ArrayBackedValueStorage tempStorage = new ArrayBackedValueStorage();
+    private final IBinaryComparator stringBinaryComparator =
+            UTF8StringBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+    private final RuntimeRecordTypeInfo runtimeRecordTypeInfo = new RuntimeRecordTypeInfo();
+    private final ArrayBackedValueStorage resultStorage = new ArrayBackedValueStorage();
+    private final DataOutput out = resultStorage.getDataOutput();
+    private final ArrayBackedValueStorage uuidStorage = new ArrayBackedValueStorage();
+    private final DataOutput uuidOut = uuidStorage.getDataOutput();
+    private final AGeneratedUUID uuid = new AGeneratedUUID();
+    @SuppressWarnings("unchecked")
+    private final ISerializerDeserializer<AUUID> uuidSerDe =
+            SerializerDeserializerProvider.INSTANCE.getSerializerDeserializer(BuiltinType.AUUID);
+
+    private final ARecordType outRecType;
+    private final IVisitablePointable inRecVisitable;
+    private final IPointable[] keyNameParts;
+    private final IScalarEvaluator inRecEval;
+    private final IScalarEvaluator[] keyNamePartsEvals;
+
+    PutAutogeneratedKeyEvaluator(IEvaluatorContext ctx, IScalarEvaluatorFactory[] args, ARecordType outRecType,
+            ARecordType inRecType, SourceLocation sourceLocation, FunctionIdentifier identifier)
+            throws HyracksDataException {
+        super(sourceLocation, identifier);
+        this.outRecType = outRecType;
+        inRecEval = args[0].createScalarEvaluator(ctx);
+        keyNamePartsEvals = new IScalarEvaluator[args.length - 1];
+        keyNameParts = new VoidPointable[args.length - 1];
+        for (int i = 1, e = 0; i < args.length; i++, e++) {
+            keyNamePartsEvals[e] = args[i].createScalarEvaluator(ctx);
+            keyNameParts[e] = new VoidPointable();
+        }
+        PointableAllocator pa = new PointableAllocator();
+        inRecVisitable = pa.allocateRecordValue(inRecType);
+    }
+
+    @Override
+    public void evaluate(IFrameTupleReference tuple, IPointable result) throws HyracksDataException {
+        inRecEval.evaluate(tuple, inRecPointable);
+        if (PointableHelper.checkAndSetMissingOrNull(result, inRecPointable)) {
+            // TODO: can probably fail instead of producing NULL/MISSING
+            return;
+        }
+        ATypeTag inputTypeTag = PointableHelper.getTypeTag(inRecPointable);
+        if (inputTypeTag != ATypeTag.OBJECT) {
+            throw new RuntimeDataException(ErrorCode.CASTING_FIELD, srcLoc, inputTypeTag, ATypeTag.OBJECT);
+        }
+        for (int i = 0; i < keyNamePartsEvals.length; i++) {
+            keyNamePartsEvals[i].evaluate(tuple, keyNameParts[i]);
+            if (PointableHelper.checkAndSetMissingOrNull(result, keyNameParts[i])) {
+                // TODO: can probably fail instead of producing NULL/MISSING
+                return;
+            }
+        }
+        resultStorage.reset();
+        processTuple(tuple);
+        result.set(resultStorage);
+    }
+
+    private void processTuple(IFrameTupleReference tuple) throws HyracksDataException {
+        inRecVisitable.set(inRecPointable);
+        try {
+            mergeAutoKeyToRecord(outRecType, (ARecordVisitablePointable) inRecVisitable, 0, tuple, keyNameParts[0]);
+            rbStack.get(0).write(out, true);
+        } catch (IOException e) {
+            throw HyracksDataException.create(e);
+        }
+    }
+
+    private void mergeAutoKeyToRecord(ARecordType outType, ARecordVisitablePointable record, int nestedLevel,
+            IFrameTupleReference tuple, IValueReference keyNamePart) throws IOException {
+        if (rbStack.size() < (nestedLevel + 1)) {
+            rbStack.add(new RecordBuilder());
+        }
+        rbStack.get(nestedLevel).reset(outType);
+        rbStack.get(nestedLevel).init();
+        boolean foundKeyNamePart = false;
+        if (record != null) {
+            for (int i = 0; i < record.getFieldNames().size(); i++) {
+                IVisitablePointable fieldName = record.getFieldNames().get(i);
+                IVisitablePointable fieldVal = record.getFieldValues().get(i);
+                if (PointableHelper.isEqual(fieldName, keyNamePart, stringBinaryComparator)) {
+                    foundKeyNamePart = true;
+                    addKeyPart(outType, nestedLevel, tuple, fieldName, fieldVal);
+                } else {
+                    addField(outType, fieldName, fieldVal, nestedLevel);
+                }
+            }
+        }
+        if (!foundKeyNamePart) {
+            // the input record does not have the key, generate a new key with all the field(s) nesting needed
+            if (lastKeyPartName(nestedLevel, keyNamePartsEvals.length)) {
+                addAutogeneratedKey(outType, keyNamePart, nestedLevel);
+            } else {
+                mergeAutoKeyToRecordField(outType, keyNamePart, null, nestedLevel, tuple);
+            }
+        }
+    }
+
+    private void addKeyPart(ARecordType outType, int nestedLevel, IFrameTupleReference tuple,
+            IVisitablePointable keyPartName, IVisitablePointable keyPartVal) throws IOException {
+        ATypeTag typeTag = PointableHelper.getTypeTag(keyPartVal);
+        if (lastKeyPartName(nestedLevel, keyNamePartsEvals.length)) {
+            switch (typeTag) {
+                case UUID:
+                    addField(outType, keyPartName, keyPartVal, nestedLevel);
+                    break;
+                case MISSING:
+                    addAutogeneratedKey(outType, keyPartName, nestedLevel);
+                    break;
+                default:
+                    throw new RuntimeDataException(ErrorCode.CASTING_FIELD, srcLoc, typeTag, ATypeTag.UUID);
+            }
+        } else {
+            if (typeTag != ATypeTag.OBJECT) {
+                throw new RuntimeDataException(ErrorCode.CASTING_FIELD, srcLoc, typeTag, ATypeTag.OBJECT);
+            }
+            mergeAutoKeyToRecordField(outType, keyPartName, (ARecordVisitablePointable) keyPartVal, nestedLevel, tuple);
+        }
+    }
+
+    private void mergeAutoKeyToRecordField(ARecordType combinedType, IValueReference recFieldName,
+            ARecordVisitablePointable recFieldVal, int nestedLevel, IFrameTupleReference tuple) throws IOException {
+        runtimeRecordTypeInfo.reset(combinedType);
+        int pos = runtimeRecordTypeInfo.getFieldIndex(recFieldName.getByteArray(), recFieldName.getStartOffset() + 1,
+                recFieldName.getLength() - 1);
+        mergeAutoKeyToRecord((ARecordType) combinedType.getFieldTypes()[pos], recFieldVal, nestedLevel + 1, tuple,
+                keyNameParts[nestedLevel + 1]);
+        tempStorage.reset();
+        rbStack.get(nestedLevel + 1).write(tempStorage.getDataOutput(), true);
+        rbStack.get(nestedLevel).addField(pos, tempStorage);
+    }
+
+    private void addAutogeneratedKey(ARecordType outType, IValueReference keyNamePart, int nestedLevel)
+            throws IOException {
+        uuidStorage.reset();
+        uuid.nextUUID();
+        uuidSerDe.serialize(uuid, uuidOut);
+        addField(outType, keyNamePart, uuidStorage, nestedLevel);
+    }
+
+    private void addField(ARecordType outType, IValueReference fieldName, IValueReference fieldValue, int nestedLevel)
+            throws IOException {
+        runtimeRecordTypeInfo.reset(outType);
+        int pos = runtimeRecordTypeInfo.getFieldIndex(fieldName.getByteArray(), fieldName.getStartOffset() + 1,
+                fieldName.getLength() - 1);
+        if (pos >= 0) {
+            rbStack.get(nestedLevel).addField(pos, fieldValue);
+        } else {
+            rbStack.get(nestedLevel).addField(fieldName, fieldValue);
+        }
+    }
+
+    private static boolean lastKeyPartName(int nestedLevel, int keyNameParts) {
+        return nestedLevel == keyNameParts - 1;
+    }
+}
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java
index 7001c25..4149e1c 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionCollection.java
@@ -541,6 +541,7 @@
 import org.apache.asterix.runtime.evaluators.functions.records.GetRecordFieldValueDescriptor;
 import org.apache.asterix.runtime.evaluators.functions.records.GetRecordFieldsDescriptor;
 import org.apache.asterix.runtime.evaluators.functions.records.PairsDescriptor;
+import org.apache.asterix.runtime.evaluators.functions.records.PutAutogeneratedKeyDescriptor;
 import org.apache.asterix.runtime.evaluators.functions.records.RecordAddDescriptor;
 import org.apache.asterix.runtime.evaluators.functions.records.RecordAddFieldsDescriptor;
 import org.apache.asterix.runtime.evaluators.functions.records.RecordConcatDescriptor;
@@ -1337,6 +1338,7 @@
         fc.add(DecodeDataverseNameDescriptor.FACTORY);
         fc.add(RandomWithSeedDescriptor.FACTORY);
         fc.add(SerializedSizeDescriptor.FACTORY);
+        fc.add(PutAutogeneratedKeyDescriptor.FACTORY);
 
         ServiceLoader.load(IFunctionRegistrant.class).iterator().forEachRemaining(c -> c.register(fc));
         return fc;
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionTypeInferers.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionTypeInferers.java
index 9c25f6e..731a880 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionTypeInferers.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/functions/FunctionTypeInferers.java
@@ -372,6 +372,17 @@
         }
     }
 
+    public static final class PutAutogeneratedKeyTypeInferer implements IFunctionTypeInferer {
+        @Override
+        public void infer(ILogicalExpression expr, IFunctionDescriptor fd, IVariableTypeEnvironment context,
+                CompilerProperties compilerProps) throws AlgebricksException {
+            AbstractFunctionCallExpression f = (AbstractFunctionCallExpression) expr;
+            IAType outType = (IAType) context.getType(expr);
+            IAType incRecType = (IAType) context.getType(f.getArguments().get(0).getValue());
+            fd.setImmutableStates(outType, incRecType);
+        }
+    }
+
     private static IAType[] getArgumentsTypes(AbstractFunctionCallExpression funExp, IVariableTypeEnvironment ctx)
             throws AlgebricksException {
         IAType[] argsTypes = new IAType[funExp.getArguments().size()];