2

In MS SQL Server it is possible to cluster an index on a non-primary, non-unique key. For example, if I wanted to create a clustered index on the insert date to prevent page splits and fragmentation upon insert in the middle of a UUID primary key, SQL Server would perform the background work for this.

It appears in MySQL/InnoDB that the clustered index would be created upon the first primary or unique key added to the table. Other than adding a non-UUID primary key, or not building any unique keys, how would the major fragmentation be avoided? Is there another engine that would work better with this?

If unavoidable, are there any steps that can be taken to mitigate the issue outside of periodic rebuilds of the clustered index?

5

Face it, wherever you have the UUID as a KEY, it will be in a fragmented BTree. But, the BTree is kept reasonably clean. That is, when a BTree block is too full to accept another row, it splits into two blocks, each about half full. As time goes on, any new inserts into either of those blocks will simply add to the blocks without immediately splitting. The end result of 'random' inserts is blocks that average about 69% full. This is only slightly worse than 100% full.

InnoDB uses only BTrees. The data is 'clustered' with the PRIMARY KEY. There is always a PRIMARY KEY:

  1. an explicit PK, or
  2. the first UNIQUE key with non-null column(s), or
  3. a fabricated, hidden, 6-byte PK.

If your UUID is the PK, then you are doing splits/fragmentation on the data. If your UUID is a secondary key, then that BTree suffers from splits/fragmentation. There is (almost) no escaping it.

I say 'almost' because if you are using Type-1 UUIDs, you can shuffle the bits to make them approximately time oriented. This makes them much like AUTO_INCREMENT ids. I discuss that in my blog.

Yes, you could rebuild whatever index contains the UUID. This is via the OPTIMIZE TABLE, which rebuilds the table, blocking access during the process. And, as I say, you won't gain much from it. Ordinary blocks splits are not costly; OPTIMIZE is. I often tell people to 'never' use OPTIMIZE.

Is your entire table small enough to be cached in the buffer_pool? If so, UUIDs are not too much of a performance problem. On the other hand, once the table (or the UUID index) gets much bigger than the buffer pool, processing becomes I/O-bound. This is because of the random nature of UUIDs. As the table grows, each INSERT and each SELECT (using UUID) becomes more and more likely to require a disk hit.

If you cannot avoid UUIDs (which would be my first recommendation), you can at least shrink them from taking 110 bytes via a casual implementation (VARCHAR(36) w/utf8) or 36 bytes (CHAR(36) w/ascii) and shrink it down to 16 bytes (BINARY(16)). See my blog for the pair of Stored Functions. Smaller --> More cacheable --> Less I/O --> Faster.

If you would like to discuss further what you are doing, I would be happy to elaborate further.

  • For v4 there are comb uuids, if possible, can you edit your answer with your opinion on them? – JCM Dec 21 '16 at 15:11
  • @JCM - The datetime must be at the beginning of the "locality of reference" to happen based on datetime. I do not see how the Comb in that reference can help. Furthermore, if it is losing part of a Type 4 UUID, it is risking duplicates unnecessarily. Type 1 UUIDs can be rearranged to discover the datetime (if that is a goal). – Rick James Dec 21 '16 at 17:38
  • The goal is to reduce fragmentation of the index by adding a time part to the uuid, and rearranging it. We do lose some bytes of the uuid, but it still keeps really low collision chances. – JCM Dec 21 '16 at 17:49
  • 1
    If you are going to the effort of building a UUID, why not build a Type 1 and rearrange it? It has been vetted (for collisions) better than Comb. – Rick James Dec 21 '16 at 17:53
  • Mostly because the random part is required. But I get your point, I will look further into the available alternatives. – JCM Dec 21 '16 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.