I've been testing the new UUID functionality in 8.3dev and noticed that
UUIDs are sorted using memcmp in their default in-memory layout, which


     struct uuid {

             uint32_t        time_low;

             uint16_t        time_mid;

             uint16_t        time_hi_and_version;

             uint8_t         clock_seq_hi_and_reserved;

             uint8_t         clock_seq_low;

             uint8_t         node[_UUID_NODE_LEN];



When done that way, you're going to see a lot of index B-tree
fragmentation with even DCE 1.1 (ISO/IEC 11578:1996) time based UUIDs,
as described above. With random (version 4) or hashed based (version 3
or 5) UUIDs there's nothing that can be done to improve the situation,


So I went down the path of changing the pgsql sorting order to instead
sort by, from most significant to least:


1)      Node (MAC address),

2)      clock sequence, then

3)      time.


The implementation is as follows:


/* internal uuid compare function */

static int

uuid_internal_cmp(const pg_uuid_t *arg1, const pg_uuid_t *arg2)


  int result;


  /* node */

  if ((result = memcmp(&arg1->data[10], &arg2->data[10], 6)) != 0)

    return result;


  /* clock_seq_hi_and_reserved, clock_seq_low */

  if ((result = memcmp(&arg1->data[8], &arg2->data[8], 2)) != 0)

    return result;


  /* time_hi_and_version */

  if ((result = memcmp(&arg1->data[6], &arg2->data[6], 2)) != 0)

    return result;


  /* time_mid */

  if ((result = memcmp(&arg1->data[4], &arg2->data[4], 2)) != 0)

    return result;


  /* time_low */

  return memcmp(&arg1->data[0], &arg2->data[0], 4);



This results in much less fragmentation and reduced page hits when
indexing a UUID column. When multiple UUID generators with different
node values contribute to a single table concurrently, it should also
result in better performance than if they sorted the way they do now or
by time first.


Sorting UUIDs when they are random/hashed with memcmp seems pretty darn
useless in all scenarios and performs poorly on indexes. This method is
equally poor with random/hashed UUIDs, but much better with version 1
time based UUIDs.


What do you guys think about changing the default behavior of pgsql to
compare UUIDs this way?


-- Robert

Reply via email to