diff --git a/asterix-om/src/main/java/edu/uci/ics/asterix/dataflow/data/nontagged/serde/AUUIDSerializerDeserializer.java b/asterix-om/src/main/java/edu/uci/ics/asterix/dataflow/data/nontagged/serde/AUUIDSerializerDeserializer.java
index 91e1c48..acd0888 100644
--- a/asterix-om/src/main/java/edu/uci/ics/asterix/dataflow/data/nontagged/serde/AUUIDSerializerDeserializer.java
+++ b/asterix-om/src/main/java/edu/uci/ics/asterix/dataflow/data/nontagged/serde/AUUIDSerializerDeserializer.java
@@ -3,7 +3,6 @@
 import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
-import java.util.UUID;
 
 import edu.uci.ics.asterix.om.base.AUUID;
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
@@ -20,16 +19,14 @@
     public AUUID deserialize(DataInput in) throws HyracksDataException {
         long msb = Integer64SerializerDeserializer.INSTANCE.deserialize(in);
         long lsb = Integer64SerializerDeserializer.INSTANCE.deserialize(in);
-        UUID uuid = new UUID(msb, lsb);
-        return new AUUID(uuid);
+        return new AUUID(msb, lsb);
     }
 
     @Override
     public void serialize(AUUID instance, DataOutput out) throws HyracksDataException {
-        UUID uuid = instance.getValue();
         try {
-            Integer64SerializerDeserializer.INSTANCE.serialize(uuid.getMostSignificantBits(), out);
-            Integer64SerializerDeserializer.INSTANCE.serialize(uuid.getLeastSignificantBits(), out);
+            Integer64SerializerDeserializer.INSTANCE.serialize(instance.getMostSignificantBits(), out);
+            Integer64SerializerDeserializer.INSTANCE.serialize(instance.getLeastSignificantBits(), out);
         } catch (IOException e) {
             throw new HyracksDataException(e);
         }
diff --git a/asterix-om/src/main/java/edu/uci/ics/asterix/om/base/AMutableUUID.java b/asterix-om/src/main/java/edu/uci/ics/asterix/om/base/AMutableUUID.java
index ea0024c..88c5875 100644
--- a/asterix-om/src/main/java/edu/uci/ics/asterix/om/base/AMutableUUID.java
+++ b/asterix-om/src/main/java/edu/uci/ics/asterix/om/base/AMutableUUID.java
@@ -1,15 +1,19 @@
 package edu.uci.ics.asterix.om.base;
 
-import java.util.UUID;
-
 public class AMutableUUID extends AUUID {
+    private final long[] uuidBits;
+    private final byte[] randomBytes;
 
-    public AMutableUUID(UUID uuid) {
-        super(uuid);
+    public AMutableUUID(long msb, long lsb) {
+        super(msb, lsb);
+        randomBytes = new byte[16];
+        uuidBits = new long[2];
     }
 
-    public void setValue(UUID uuid) {
-        this.uuid = uuid;
+    public void nextUUID() {
+        Holder.srnd.nextBytes(randomBytes);
+        uuidBitsFromBytes(uuidBits, randomBytes);
+        msb = uuidBits[0];
+        lsb = uuidBits[1];
     }
-
 }
diff --git a/asterix-om/src/main/java/edu/uci/ics/asterix/om/base/AUUID.java b/asterix-om/src/main/java/edu/uci/ics/asterix/om/base/AUUID.java
index 7557869..d8ada69 100644
--- a/asterix-om/src/main/java/edu/uci/ics/asterix/om/base/AUUID.java
+++ b/asterix-om/src/main/java/edu/uci/ics/asterix/om/base/AUUID.java
@@ -1,5 +1,6 @@
 package edu.uci.ics.asterix.om.base;
 
+import java.security.SecureRandom;
 import java.util.UUID;
 
 import org.json.JSONException;
@@ -12,20 +13,58 @@
 
 public class AUUID implements IAObject {
 
-    protected UUID uuid;
-
-    public AUUID(UUID uuid) {
-        this.uuid = uuid;
+    protected static class Holder {
+        static final SecureRandom srnd = new SecureRandom();
     }
 
-    public UUID getValue() {
-        return uuid;
+    protected long msb;
+    protected long lsb;
+
+    public AUUID(UUID uuid) {
+        msb = uuid.getMostSignificantBits();
+        lsb = uuid.getLeastSignificantBits();
+    }
+
+    public AUUID(long msb, long lsb) {
+        this.msb = msb;
+        this.lsb = lsb;
+    }
+
+    public long getMostSignificantBits() {
+        return msb;
+    }
+
+    public long getLeastSignificantBits() {
+        return lsb;
+    }
+
+    public static AUUID randomUUID() {
+        long[] bits = new long[2];
+        byte[] randomBytes = new byte[16];
+        Holder.srnd.nextBytes(randomBytes);
+        uuidBitsFromBytes(bits, randomBytes);
+        return new AUUID(bits[0], bits[1]);
+    }
+
+    protected static void uuidBitsFromBytes(long[] bits, byte[] randomBytes) {
+        bits[0] = 0;
+        bits[1] = 0;
+        randomBytes[6] &= 0x0f; /* clear version        */
+        randomBytes[6] |= 0x40; /* set to version 4     */
+        randomBytes[8] &= 0x3f; /* clear variant        */
+        randomBytes[8] |= 0x80; /* set to IETF variant  */
+        for (int i = 0; i < 8; ++i) {
+            bits[0] = (bits[0] << 8) | (randomBytes[i] & 0xff);
+        }
+        for (int i = 8; i < 16; ++i) {
+            bits[1] = (bits[1] << 8) | (randomBytes[i] & 0xff);
+        }
     }
 
     @Override
     public JSONObject toJSON() throws JSONException {
         JSONObject json = new JSONObject();
-        json.put("AUUID", uuid.toString());
+        json.put("AUUID", toString());
         return json;
     }
 
@@ -45,16 +84,24 @@
             return false;
         }
         AUUID oUUID = (AUUID) obj;
-        return uuid.equals(oUUID.uuid);
+        return oUUID.msb == this.msb && oUUID.lsb == this.lsb;
     }
 
     @Override
     public int hash() {
-        return uuid.hashCode();
+        long hilo = msb ^ lsb;
+        return ((int) (hilo >> 32)) ^ (int) hilo;
     }
 
     @Override
     public String toString() {
-        return "AUUID: {" + uuid + "}";
+        return "AUUID: {"
+                + (digits(msb >> 32, 8) + "-" + digits(msb >> 16, 4) + "-" + digits(msb, 4) + "-"
+                        + digits(lsb >> 48, 4) + "-" + digits(lsb, 12)) + "}";
+    }
+
+    private static String digits(long val, int digits) {
+        long hi = 1L << (digits * 4);
+        return Long.toHexString(hi | (val & (hi - 1))).substring(1);
     }
 }
diff --git a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/evaluators/functions/CreateUUIDDescriptor.java b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/evaluators/functions/CreateUUIDDescriptor.java
index a799a5b..fdb7361 100644
--- a/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/evaluators/functions/CreateUUIDDescriptor.java
+++ b/asterix-runtime/src/main/java/edu/uci/ics/asterix/runtime/evaluators/functions/CreateUUIDDescriptor.java
@@ -1,7 +1,5 @@
 package edu.uci.ics.asterix.runtime.evaluators.functions;
 
-import java.util.UUID;
-
 import edu.uci.ics.asterix.formats.nontagged.AqlSerializerDeserializerProvider;
 import edu.uci.ics.asterix.om.base.AMutableUUID;
 import edu.uci.ics.asterix.om.base.AUUID;
@@ -42,11 +40,11 @@
             @Override
             public ICopyEvaluator createEvaluator(final IDataOutputProvider output) throws AlgebricksException {
                 return new ICopyEvaluator() {
-                    final AMutableUUID uuid = new AMutableUUID(null);
+                    final AMutableUUID uuid = new AMutableUUID(0, 0);
 
                     @Override
                     public void evaluate(IFrameTupleReference tuple) throws AlgebricksException {
-                        uuid.setValue(UUID.randomUUID());
+                        uuid.nextUUID();
                         try {
                             uuidSerDe.serialize(uuid, output.getDataOutput());
                         } catch (HyracksDataException e) {