Thread: Change sort order on UUIDs?
<div class="Section1"><p class="MsoNormal">I’ve been testing the new UUID functionality in 8.3dev and noticed that
UUIDsare sorted using memcmp in their default in-memory layout, which is:<p class="MsoNormal"> <p
class="MsoNormal"> struct uuid {<p class="MsoNormal"> uint32_t time_low;<p
class="MsoNormal"> uint16_t time_mid;<p class="MsoNormal"> uint16_t
time_hi_and_version;<pclass="MsoNormal"> uint8_t clock_seq_hi_and_reserved;<p
class="MsoNormal"> uint8_t clock_seq_low;<p class="MsoNormal"> uint8_t
node[_UUID_NODE_LEN];<pclass="MsoNormal"> };<p class="MsoNormal"> <p class="MsoNormal">When done that way, you’re
goingto 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,obviously.<p class="MsoNormal"> <p class="MsoNormal">So I went down the path of changing the pgsql sorting
orderto instead sort by, from most significant to least:<p class="MsoNormal"> <p class="MsoListParagraph"
style="margin-left:22.5pt;text-indent:-.25in;
mso-list:l0 level1 lfo1"><span style="mso-list:Ignore">1)<span style="font:7.0pt "Times New Roman"">
</span></span>Node(MAC address),<p class="MsoListParagraph" style="margin-left:22.5pt;text-indent:-.25in;
mso-list:l0 level1 lfo1"><span style="mso-list:Ignore">2)<span style="font:7.0pt "Times New Roman"">
</span></span>clocksequence, then<p class="MsoListParagraph" style="margin-left:22.5pt;text-indent:-.25in;
mso-list:l0 level1 lfo1"><span style="mso-list:Ignore">3)<span style="font:7.0pt "Times New Roman"">
</span></span>time.<pclass="MsoNormal"> <p class="MsoNormal">The implementation is as follows:<p class="MsoNormal"> <p
class="MsoNormal">/*internal uuid compare function */<p class="MsoNormal">static int<p
class="MsoNormal">uuid_internal_cmp(constpg_uuid_t *arg1, const pg_uuid_t *arg2)<p class="MsoNormal">{<p
class="MsoNormal"> int result;<p class="MsoNormal"> <p class="MsoNormal"> /* node */<p class="MsoNormal"> if ((result
=memcmp(&arg1->data[10], &arg2->data[10], 6)) != 0)<p class="MsoNormal"> return result;<p
class="MsoNormal"> <pclass="MsoNormal"> /* clock_seq_hi_and_reserved, clock_seq_low */<p class="MsoNormal"> if
((result= memcmp(&arg1->data[8], &arg2->data[8], 2)) != 0)<p class="MsoNormal"> return result;<p
class="MsoNormal"> <pclass="MsoNormal"> /* time_hi_and_version */<p class="MsoNormal"> if ((result =
memcmp(&arg1->data[6],&arg2->data[6], 2)) != 0)<p class="MsoNormal"> return result;<p
class="MsoNormal"> <pclass="MsoNormal"> /* time_mid */<p class="MsoNormal"> if ((result =
memcmp(&arg1->data[4],&arg2->data[4], 2)) != 0)<p class="MsoNormal"> return result;<p
class="MsoNormal"> <pclass="MsoNormal"> /* time_low */<p class="MsoNormal"> return memcmp(&arg1->data[0],
&arg2->data[0],4);<p class="MsoNormal">}<p class="MsoNormal"> <p class="MsoNormal">This results in much less
fragmentationand reduced page hits when indexing a UUID column. When multiple UUID generators with different node
valuescontribute to a single table concurrently, it should also result in better performance than if they sorted the
waythey do now or by time first.<p class="MsoNormal"> <p class="MsoNormal">Sorting UUIDs when they are random/hashed
withmemcmp seems pretty darn useless in all scenarios and performs poorly on indexes. This method is equally poor with
random/hashedUUIDs, but much better with version 1 time based UUIDs.<p class="MsoNormal"> <p class="MsoNormal">What do
youguys think about changing the default behavior of pgsql to compare UUIDs this way?<p class="MsoNormal"> <p
class="MsoNormal">--Robert</div>
"Robert Wojciechowski" <robertw@expressyard.com> writes:
> 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,
> ...
> 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,
This claim seems like nonsense. Btrees don't care about the ordering
details of what they index.
regards, tom lane
Tom Lane wrote: > "Robert Wojciechowski" <robertw@expressyard.com> writes: >> 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, >> ... >> 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, > > This claim seems like nonsense. Btrees don't care about the ordering > details of what they index. I believe he means that with his modified comparison function, when inserting a series of UUIDs with increasing time-fields, the index keys are always inserted to the rightmost page, which gives a more tightly packed index than scattered inserts all-around the index. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com
Heikki Linnakangas <heikki@enterprisedb.com> writes:
> I believe he means that with his modified comparison function, when
> inserting a series of UUIDs with increasing time-fields, the index keys
> are always inserted to the rightmost page, which gives a more tightly
> packed index than scattered inserts all-around the index.
Hm. Still, given that that benefit would only accrue for one version of
uuid generation, it's a pretty weak argument.
The concrete reason for not changing it is that the sort ordering of
uuids would then look quite unnatural compared to the display format.
Which would provoke confusion and bug reports...
regards, tom lane
> >> 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, > >> ... > >> 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, > > > > This claim seems like nonsense. Btrees don't care about the ordering > > details of what they index. > > I believe he means that with his modified comparison function, when > inserting a series of UUIDs with increasing time-fields, the index keys > are always inserted to the rightmost page, which gives a more tightly > packed index than scattered inserts all-around the index. > That was my thinking; that it would speed up (bulk) inserts causing fewer page splits. I'm also using my own contrib module that uses FreeBSD's uuid_create generating DCE 1.1 UUIDs, which keeps the state of the UUID generator in the kernel. The 8.3 contrib module based on uuid-ossp seems to 1) not compile on FreeBSD (conflicts with uuid.h from the OS) and 2) randomizes the clock sequence as there is no state stored between invocations. The other thing this modification does is allow ORDER BY to order by time when possible, which is a nice default behavior as well, yes? -- Robert
> Heikki Linnakangas <heikki@enterprisedb.com> writes: > > I believe he means that with his modified comparison function, when > > inserting a series of UUIDs with increasing time-fields, the index keys > > are always inserted to the rightmost page, which gives a more tightly > > packed index than scattered inserts all-around the index. > > Hm. Still, given that that benefit would only accrue for one version of > uuid generation, it's a pretty weak argument. > > The concrete reason for not changing it is that the sort ordering of > uuids would then look quite unnatural compared to the display format. > Which would provoke confusion and bug reports... > > regards, tom lane If it improves non-user controllable indexing behavior, doesn't negatively affect the indexing of random/hash based UUIDs, and only seems to affect ordering for the display format, it seems worth it to me. A paragraph in the documentation stating how UUIDs are sorted seems to satisfy the visual ordering concern, which is more than what Microsoft is doing (I had to dig for a blog post to find this out.) In addition it would be very odd to sort random/hashed GUIDs and expect anything that in meaningful, anyway. If the user wants to see a UUID lexographically sorted, they could also cast the column to text like so: select uuid_column from uuid_test order by uuid_column::text; ... which produces the desired output for visual analysis if that was desired while still retaining all the other benefits. I'll continue thinking about any other downsides to this tonight, too. -- Robert
"Robert Wojciechowski" <robertw@expressyard.com> writes: > 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, > obviously. Is this based on empirical results or just a theory? I'm asking because it's actually a common technique to reverse the natural index key to construct basically exactly this situation -- for performance reasons. The idea is that low order bits have higher cardinality and that that can *improve* btree performance by avoiding contention. I'm not sure how much I believe in the effectiveness of that strategy myself or for that matter whether it's universally applicable or only useful in certain types of loads. I'm not saying you're wrong, but I'm not sure it's a simple open and shut case either. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com
"Robert Wojciechowski" <robertw@expressyard.com> writes: > That was my thinking; that it would speed up (bulk) inserts causing > fewer page splits. Ah, I understand better now. hm. high data density would be good for reading. But I think the case for inserting is actually quite mixed. If you have lots of processes trying to insert you'll actually get poorer performance because they'll all have to get access to the same page. Worse, you'll probably have a unique index. > The other thing this modification does is allow ORDER BY to order by > time when possible, which is a nice default behavior as well, yes? I think that actually is quite a nice effect. Certainly the loss of it is one of the big practical disadvantages of using UUIDs over a sequence. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com
On Thu, Jun 14, 2007 at 03:38:44PM -0400, Robert Wojciechowski wrote:
> 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
> is:
> 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,
> obviously.
I suggest that treating the UUID as anything other than a unique
random value is a mistake. There should be no assumptions by users
with regard to how the order is displayed. Also, as UUID generation
based on time is always in sequence, it seems to me that sorting by
UUID time would have the effect of inserts always being to the end of
the index. While this might pack tightly, wouldn't this hurt
concurrency? Random access vs sequential performance. For UUID, I
would value random access before sequential performance. Why would
anybody scan UUID through the index in "sequential" order?
Cheers,
mark
--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada
One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness
bindthem...
http://mark.mielke.cc/
On Jun 14, 2007, at 19:04 , mark@mark.mielke.cc wrote: > For UUID, I > would value random access before sequential performance. Why would > anybody scan UUID through the index in "sequential" order? AIUI, to allow UUID columns to be indexed using BTREE, there needs to be some ordering defined. So regardless of what this ordering is, doesn't there need to be some order? And as a (primary?) purpose of UUIDs is to be (universally) unique, and the implementation of uniqueness constraints in PostgreSQL is based on BTREE indexes, this makes the necessity of ordering doubly so. Or have I missed something? Michael Glaesemann grzm seespotcode net
> > 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, > > obviously. > > Is this based on empirical results or just a theory? I'm asking because > it's actually a common technique to reverse the natural index key to > construct basically exactly this situation -- for performance reasons. > The idea is that low order bits have higher cardinality and that that > can *improve* btree performance by avoiding contention. > > I'm not sure how much I believe in the effectiveness of that strategy > myself or for that matter whether it's universally applicable or only > useful in certain types of loads. > > I'm not saying you're wrong, but I'm not sure it's a simple open and shut > case either. > What hinted me off to this was the same problem occurring in SQL Server, where changing the behavior gave them a much lower I/O load with replication (which utilizes UUIDs). A blog post from an MS developer at http://tinyurl.com/2xy5jn talks about how this has allowed a tighter index as well as not requiring random searches on the b-tree, significantly reducing I/O. A performance analysis at http://tinyurl.com/2ysora has a table comparing using an integer, UUID and sequential UUID (when the system orders UUIDs sequentially by time, like SQL Server already does). Obviously this is not SQL Server we're dealing with, but I can see many of the same issues unavoidable and equally impactful as we both use the same index data structure. I'll That being said, I'm going to perform tests today or this weekend on different loads to see how PostgreSQL would be affected by this change. I'll be very interested to see the results of random b-tree searches on every insert vs the contention from sequentially generated UUIDs. -- Robert
> I suggest that treating the UUID as anything other than a unique > random value is a mistake. There should be no assumptions by users > with regard to how the order is displayed. You can always use random UUIDs -- that's a choice in UUID generation. When dealing with random UUIDs you also (by the very nature of them being random) would never order by column as it just doesn't make sense. Nothing changes as long as you generate random UUIDs. Also, treating UUIDs as time based is completely valid -- that is the point of version 1 UUIDs. They have quite a few advantages over random UUIDs. > Also, as UUID generation > based on time is always in sequence, it seems to me that sorting by > UUID time would have the effect of inserts always being to the end of > the index. While this might pack tightly, wouldn't this hurt > concurrency? Random access vs sequential performance. For UUID, I > would value random access before sequential performance. Why would > anybody scan UUID through the index in "sequential" order? > Ordering random UUIDs as if they were time-based will still result in random access on the b-tree, so again luckily this just relies on how you generate the UUIDs not how you order them. So far this ordering method seems to satisfy both needs, but my performance analysis will reveal more. -- Robert
On Fri, Jun 15, 2007 at 09:40:29AM -0500, Michael Glaesemann wrote:
> On Jun 14, 2007, at 19:04 , mark@mark.mielke.cc wrote:
> >For UUID, I
> >would value random access before sequential performance. Why would
> >anybody scan UUID through the index in "sequential" order?
> AIUI, to allow UUID columns to be indexed using BTREE, there needs to
> be some ordering defined. So regardless of what this ordering is,
> doesn't there need to be some order? And as a (primary?) purpose of
> UUIDs is to be (universally) unique, and the implementation of
> uniqueness constraints in PostgreSQL is based on BTREE indexes, this
> makes the necessity of ordering doubly so. Or have I missed something?
The BTREE needs a comparator function, yes. The BTREE comparator
function need not match any expectation of the caller.
For example, if Robert is correct, that indexes on UUID will become
fragmented over time with the current comparator, then he is providing
only a half solution. He will have non fragmented time-based UUID
index, while continuing to allow everybody else to have fragmented
non time-based UUID. The logic does not make sense. Either fragmentation
is an issue, or it is not. Concurrency is either an issue, or it is not.
I do not believe that it has been demonstrated that there is a
fragmentation issue, nor do I believe it has been shown what effect
would occur on concurrency.
Personally, my preference is for the BTREE comparator to be the fastest
comparison possible, to allow the quickest scanning of the index entries.
I don't believe fragmentation is a serious issue, and I believe there are
concurrency benefits to inserting into different index pages, rather than
always adding to the end.
Cheers,
mark
--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada
One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness
bindthem...
http://mark.mielke.cc/
On Fri, Jun 15, 2007 at 11:05:01AM -0400, Robert Wojciechowski wrote:
> Also, treating UUIDs as time based is completely valid -- that is the
> point of version 1 UUIDs. They have quite a few advantages over random UUIDs.
It's a leap from extracting the UUID as time, to sorting by UUID for
results, or an assumption that reduced fragmentation would increase
performance for regular loads.
> Ordering random UUIDs as if they were time-based will still result in
> random access on the b-tree, so again luckily this just relies on how
> you generate the UUIDs not how you order them.
Therefore fragmented by your assertion, therefore a performance
problem. If your premise is correct, the conclusion that it leads to
is that UUIDv1 will perform better under PostgreSQL.
> So far this ordering method seems to satisfy both needs, but my
> performance analysis will reveal more.
The word "satisfy" above is loosely defined. The existing model
"satisfies" both needs. You believe you have a case that would prove
that the existing model is sub-optimal. You would like to make a
change which you believe would optimize your own use, at the minimal
expense of other users. The minimal expense comes from the more
complicated comparator function, and the confusion of any who see
their non-UUIDv1 UUID's sorted by some apparently arbitrary scheme
that seems to have a history of assuming that UUIDv1 will be used.
Cheers,
mark
--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada
One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness
bindthem...
http://mark.mielke.cc/
If index lookup speed or packing truly was the primary concern, people
would use a suitably sized SEQUENCE. They would not use UUID.
I believe the last time I calculated this, the result was that you
could fit 50% more entries in the index if you use a 32-bit sequence
number instead of a 128-bit UUID.
I've been mixed on my personal use of UUID. The main benefits of UUID
for me have been:
1) Different sites can generate UUID values without communicating according to a well known standard formula, and
havean excellent chance of always generating unique values for a particular application that can be later
mergedtogether without conflict.
2) The numbers are difficult to predict by an end user of your application. If exposing your row id to the world,
aUUID is more obscure and difficult to predict than a sequence number.
The rest of the benefits are slim or non-existent. It's not more
efficient to store or access. It's not easier to process, memorize or
type. Any significance of values, such as UUIDv1 embedded a time and
mac address are of only limited value, as it relies on the generator
following the expected algorithm, and the generators having the same
time (with different allowances for error).
For example, if one truly wished to have an efficient lookup key, and
record creation time, why not use two fields? 1 x 32-bit sequence number,
and 1 x 64-bit timestamp. This gives portability and makes the purpose of
the fields clear. It gives flexibility to create the index on either/or.
For read-only data, I've taken to using the SHA1 sum of the data as
the unique id instead of UUID or SEQUENCE. Works pretty good... :-)
Cheers,
mark
--
mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________
. . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder
|\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ |
| | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada
One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness
bindthem...
http://mark.mielke.cc/
This has been saved for the 8.4 release: http://momjian.postgresql.org/cgi-bin/pgpatches_hold --------------------------------------------------------------------------- Michael Glaesemann wrote: > > On Jun 14, 2007, at 19:04 , mark@mark.mielke.cc wrote: > > > For UUID, I > > would value random access before sequential performance. Why would > > anybody scan UUID through the index in "sequential" order? > > AIUI, to allow UUID columns to be indexed using BTREE, there needs to > be some ordering defined. So regardless of what this ordering is, > doesn't there need to be some order? And as a (primary?) purpose of > UUIDs is to be (universally) unique, and the implementation of > uniqueness constraints in PostgreSQL is based on BTREE indexes, this > makes the necessity of ordering doubly so. Or have I missed something? > > Michael Glaesemann > grzm seespotcode net > > > > ---------------------------(end of broadcast)--------------------------- > TIP 7: You can help support the PostgreSQL project by donating at > > http://www.postgresql.org/about/donate -- Bruce Momjian <bruce@momjian.us> http://momjian.us EnterpriseDB http://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. +