GUID/UUID Performance Breakthrough

Table of Contents

The Problem
Why it is a Problem
Second Problem
Combining the Problems and Crafting a Solution
Code to do it
MySQL 8.0
Brought to you by Rick James

The Problem

GUIDs/UUIDs are very random. Therefore, INSERTing into an index means jumping around a lot. Once the index is too big to be cached, most INSERTs involve a disk hit. Even on a beefy system, this limits you to a few hundred INSERTs per second.

MySQL's UUID function

This blog is mostly eliminated in MySQL 8.0 with the advent of the following functions: UUID_TO_BIN(str, swap_flag)

Why it is a Problem

A 'standard' GUID/UUID is composed of the time, machine identification and some other stuff. The combination should be unique, even without coordination between different computers that could be generating UUIDs simultaneously.

The top part of the GUID/UUID is the bottom part of the current time. The top part is the primary part of what would be used for placing the value in an ordered list (INDEX). This cycles in about 7.16 minutes.

Some math... If the index is small enough to be cached in RAM, each insert into the index is CPU only, with the writes being delayed and batched. If the index is 20 times as big as can be cached, then 19 out of 20 inserts will be a cache miss. (This math applies to any "random" index.)

Second Problem

36 characters is bulky. If you are using that as a PRIMARY KEY in InnoDB and you have secondary keys, remember that each secondary key has an implicit copy of the PK, thereby making it bulky.

It is tempting to declare the UUID VARCHAR(36). And, since you probably are thinking globally, so you have CHARACTER SET utf8 (or utf8mb4). For utf8:
    ⚈  2 - Overhead for VAR
    ⚈  36 - chars
    ⚈  3 (or 4) bytes per character for utf8 (or utf8mb4)
So, max length = 2+3*36 = 110 (or 146) bytes. For temp tables 108 (or 144) is actually used if a MEMORY table is used.

To compress
    ⚈  utf8 is unnecessary (ascii would do); but this is obviated by the next two steps
    ⚈  Toss dashes
    ⚈  UNHEX
Now it will fit in 16 bytes: BINARY(16)

Combining the Problems and Crafting a Solution

But first, a caveat. This solution only works for
"Time based" / "Version 1" UUIDs
They are recognizable by the "1" at the beginning of the third clump.

The manual's sample: 6ccd780c-baba-1026-9564-0040f4311e29 . A more current value (after a few years): 49ea2de3-17a2-11e2-8346-001eecac3efa . Notice how the 3rd part has slowly changed over time? Let's data is rearranged, thus:
      11e2-17ac-106762a5-8346-001eecac3efa -- after a few more minutes

Now we have a number that increases nicely over time. Multiple sources won't be quite in time order, but they will be close. The "hot" spot for inserting into an INDEX(uuid) will be rather narrow, thereby making it quite cacheable and efficient.

If your SELECTs tend to be for "recent" uuids, then they, too, will be easily cached. If, on the other hand, your SELECTs often reach for old uuids, they will be random and not well cached. Still, improving the INSERTs will help the system overall.

Code to do it

Let's make Stored Functions to do the messy work of the two actions:
    ⚈  Rearrange fields
    ⚈  Convert to/from BINARY(16)

    CREATE FUNCTION UuidToBin(_uuid BINARY(36))
        RETURNS BINARY(16)
            SUBSTR(_uuid, 15, 4),
            SUBSTR(_uuid, 10, 4),
            SUBSTR(_uuid,  1, 8),
            SUBSTR(_uuid, 20, 4),
            SUBSTR(_uuid, 25) ));

    CREATE FUNCTION UuidFromBin(_bin BINARY(16))
        RETURNS BINARY(36)
            HEX(SUBSTR(_bin,  5, 4)),
            HEX(SUBSTR(_bin,  3, 2)),
            HEX(SUBSTR(_bin,  1, 2)),
            HEX(SUBSTR(_bin,  9, 2)),
            HEX(SUBSTR(_bin, 11))


Then you would do things like
    -- Letting MySQL create the UUID:
    INSERT INTO t (uuid, ...) VALUES (UuidToBin(UUID()), ...);

    -- Creating the UUID elsewhere:
    INSERT INTO t (uuid, ...) VALUES (UuidToBin(?), ...);

    -- Retrieving (point query using uuid):
    SELECT ... FROM t WHERE uuid = UuidToBin(?);

    -- Retrieving (other):
    SELECT UuidFromBin(uuid), ... FROM t ...;
Do not flip the WHERE; this will be inefficent because it won't use INDEX(uuid):
    WHERE UuidFromBin(uuid) = '1026-baba-6ccd780c-9564-0040f4311e29' -- NO


TokuDB is a viable engine if you must have UUIDs (even non-type-1) in a huge table. TokuDB is available in MariaDB as a 'standard' engine, making the barrier to entry very low. There are a small number of differences between InnoDB and TokuDB; I will not go into them here.

Tokudb, with its “fractal” indexing strategy builds the indexes in stages. In contrast, InnoDB inserts index entries “immediately” — actually that indexing is buffered by most of the size of the buffer_pool. To elaborate…

When adding a record to an InnoDB table, here are (roughly) the steps performed to write the data (and PK) and secondary indexes to disk. (I leave out logging, provision for rollback, etc.) First the PRIMARY KEY and data:
    ⚈  Check for UNIQUEness constraints
    ⚈  Fetch the BTree block (normally 16KB) that should contain the row (based on the PRIMARY KEY).
    ⚈  Insert the row (overflow typically occurs 1% of the time; this leads to a block split).
    ⚈  Leave the page “dirty” in the buffer_pool, hoping that more rows are added before it is bumped out of cache (buffer_pool).. Note that for AUTO_INCREMENT and TIMESTAMP-based PKs, the “last” block in the data will be updated repeatedly before splitting; hence, this delayed write adds greatly to the efficiency. OTOH, a UUID will be very random; when the table is big enough, the block will almost always be flushed before a second insert occurs in that block. <– This is the inefficiency in UUIDs.
Now for any secondary keys:
    ⚈  All the steps are the same, since an index is essentially a "table" except that the "data" is a copy of the PRIMARY KEY.
    ⚈  UNIQUEness must be checked immediately — cannot delay the read.
    ⚈  There are (I think) some other "delays" that avoid some I/O.

Tokudb, on the other hand, does something like
    ⚈  Write data/index partially sorted records to disk before finding out exactly where it belongs.
    ⚈  In the background, combine these partially digested blocks. Repeat as needed.
    ⚈  Eventually move the info into the real table/indexes.

If you are familiar with how sort-merge works, consider the parallels to Tokudb. Each "sort" does some work of ordering things; each "merge" is quite efficient.

To summarize:
    ⚈  In the extreme (data/index much larger than buffer_pool), InnoDB must read-modify-write one 16KB disk block for each UUID entry.
    ⚈  Tokudb makes each I/O "count" by merging several UUIDs for each disk block. (Yeah, Toku rereads blocks, but it comes out ahead in the long run.)
    ⚈  Tokudb excels when the table is really big, which implies high ingestion rate.


This shows three thing for speeding up usage of GUIDs/UUIDs:
    ⚈  Shrink footprint (Smaller -> more cacheable -> faster).
    ⚈  Rearrange uuid to make a "hot spot" to improve cachability.
    ⚈  Use TokuDB

Note that the benefit of the "hot spot" is only partial:
    ⚈  Chronologically ordered (or approximately ordered) INSERTs benefit; random ones don't.
    ⚈  SELECTs/UPDATEs by "recent" uuids benefit; old ones don't benefit.

MySQL 8.0

With these new features in MySQL 8.0.0 (Sep. 2016; GA will be later), this blog is rendered mostly useless.

MySQL 8.0.0 improves the usability of UUID manipulations (WL#8920) by implementing three new SQL functions: UUID_TO_BIN(), BIN_TO_UUID(), and IS_UUID(). The first one converts from UUID formatted text to VARBINARY(16), the second one from VARBINARY(16) to UUID formatted text, and the last one checks the validity of an UUID formatted text. The UUID stored as a VARBINARY(16) can be indexed using functional indexes. The functions UUID_TO_BIN() and UUID_TO_BIN() can also shuffle the time-related bits and move them at the beginning making it index friendly and avoiding the random inserts in the B-tree, this way reducing the insert time. The lack of such functionality has been mentioned as one of the drawbacks of using UUID’s.

To summarize, MySQL does not have special data types for IPv6 addresses or UUIDs but instead encourages the use of VARBINARY(16). MySQL provides functions to convert from textual IPv6/UUID representations to and from the more compact VARBINARY(16) datatype. MySQL now offers bit-wise operations on VARBINARY(16) datatype. IPv6/UUID functions combined with bit-wise operations can be used to test, extract, or combine on parts (sub-structure) of the IPv6/UUID, i.e. defining a function over IPv6/UUID content. This function can be used to define the content in a virtual generated column which then can be indexed.


Thanks to Trey for some of the ideas here.

The tips in this document apply to MySQL, MariaDB, and Percona.

Detailed discussion of UUID indexing
Graphical display of the random nature of UUID on PRIMARY KEY
Benchmarks, etc, by Karthik Appigatla
More details on the clock
Percona benchmarks

NHibernate can generate sequential GUIDs
but it seems to be backwards.

Written Oct, 2012. Added TokuDB, Jan, 2015. 8.0 Sep, 2016

Contact me by posting a question at MySQL Forums :: Performance
-- Rick James

MySQL Documents by Rick James

HowTo Techniques for Optimizing Tough Tasks:

Partition Maintenance (DROP+REORG) for time series (includes list of PARTITION uses)
Big DELETEs - how to optimize -- and other chunking advice, plus a use for PARTITIONing
    Chunking lengthy DELETE/UPDATE/etc.
Data Warehouse techniques:
    Overview   Summary Tables   High speed ingestion  
Entity-Attribute-Value -- a common, poorly performing, design pattern (EAV); plus an alternative
Find the nearest 10 pizza parlors -- efficient searching on Latitude + Longitude (another PARITION use)
Pagination, not with OFFSET, LIMIT
Techniques on efficiently finding a random row (On beyond ORDER BY RAND())
GUID/UUID Performance (type 1 only)
IP Range Table Performance -- or other disjoint ranges
Rollup Unique User Counts
Alter of a Huge table -- Mostly obviated by 5.6
Latest 10 news articles -- how to optimize the schema and code for such
Build and execute a "Pivot" SELECT (showing rows as columns)
Find largest row for each group ("groupwise max")

Other Tips, Tuning, Debugging, Optimizations, etc...

Rick's RoTs (Rules of Thumb -- lots of tips)
Memory Allocation (caching, etc)
Character Set and Collation problem solver
    Trouble with UTF-8
Converting from MyISAM to InnoDB -- includes differences between them
Compound INDEXes plus other insights into the mysteries of INDEXing
Cookbook for Creating Indexes
    Many-to-many mapping table
MySQL Limits -- built-in hard limits
Galera, tips on converting to (Percona XtraDB Cluster, MariaDB 10, or manually installed)
5.7's Query Rewrite -- perhaps 5.7's best perf gain, at least for this forum's users
Best of MySQL Forum -- index of lots of tips, discussions, etc

My slides from conferences
Percona Live 4/2017 - Rick's RoTs (Rules of Thumb) - MySQL/MariaDB
Percona Live 4/2017 - Index Cookbook - MySQL/MariaDB
Percona Live 9/2015 - PARTITIONing - MySQL/MariaDB
(older ones upon request)

View Rick James's profile on LinkedIn