GUID/UUID Performance Breakthrough

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:

      1026-baba-6ccd780c-9564-0040f4311e29
      11e2-17a2-49ea2de3-8346-001eecac3efa
      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

Again, this code is obviated in MySQL 8.0 by UUID_TO_BIN(str, swap_flag)

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

    DELIMITER //

    CREATE FUNCTION UuidToBin(_uuid BINARY(36))
        RETURNS BINARY(16)
        LANGUAGE SQL  DETERMINISTIC  CONTAINS SQL  SQL SECURITY INVOKER
    RETURN
        UNHEX(CONCAT(
            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)
        LANGUAGE SQL  DETERMINISTIC  CONTAINS SQL  SQL SECURITY INVOKER
    RETURN
        LCASE(CONCAT_WS('-',
            HEX(SUBSTR(_bin,  5, 4)),
            HEX(SUBSTR(_bin,  3, 2)),
            HEX(SUBSTR(_bin,  1, 2)),
            HEX(SUBSTR(_bin,  9, 2)),
            HEX(SUBSTR(_bin, 11))
                 ));

    //
    DELIMITER ;

Then you would do things like the following. (Applies to 8.0, but with function names changed to UUID_TO_BIN(, true) and BIN_TO_UUID().)

    -- 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

InnoDB -- how/when indexes are updated

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). Remember that the PK is unique and the data is stored in the BTree in PK order.
    ⚈  Insert the row, splitting the block if necessary. (Typically a block split occurs 1% of the time.)
    ⚈  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; 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.

UNIQUE secondary keys (in InnoDB) work essentially like the PK: fetch the block (possibly cached); check uniqueness (give error if dup); mark block dirty; eventually write to disk.

Non-unique secondary keys use the "Change Buffer":
    ⚈  Updates to non-unique indexes are stored in the Change Buffer (which is a part of the buffer_pool, defaults to 25%).
    ⚈  These are kept sorted, but the write to disk is delayed.
    ⚈  Eventually changes are batched together and poured into the actual index blocks.
    ⚈  Therefore, both reads and writes are delayed and somewhat cached.
    ⚈  Meanwhile, index lookups look both in the Change buffer and the actually index BTree; so, the CB is totally transparent.
    ⚈  If a crash or rollback occurs, the stuff delayed in the CB is magically reconstructed; so the indexes do not get corrupted.

But... If the index is big and random, the read/write caching may be minimal. That is, the Change Buffer helps some, but only very little for 'huge' indexes or tables.

Changes to indexes for Update and Delete also go through the Change Buffer.

TokuDB

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…

Tokudb, work a bit like the Change Buffer but on disk; it 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.

Wrapup

This shows three thing for speeding up usage of GUIDs/UUIDs:
    ⚈  Shrink footprint (Smaller → more cacheable → less I/o → 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; 8.0.11 GA in Apr. 2018), 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(UUID(), true) - convert from UUID formatted text to VARBINARY(16), optionally shuffling the time parts to the top
    ⚈  BIN_TO_UUID(..., true) - convert from VARBINARY(16) to UUID formatted text, optionally unshuffling the time parts
    ⚈  IS_UUID() - check the validity of an UUID formatted text

The UUID stored as a VARBINARY(16) can be indexed using functional indexes.

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.

MariaDB 10.7

UUID Datatype
UUID discussion

MariaDB is adding a datatype, thereby avoiding the need for conversion functions.

(10.7 is expected to become GA in summer 2022.)

Migration

Now that there are multiple ways to store UUIDs, migration may be an issue

    ⚈  Simple CHAR(36) string (in any MySQL/MariaDB version)
    ⚈  BINARY(16), with code using what is discussed in this blog (any version)
    ⚈  BINARY(16), with code using MySQL 8.0 functions (8.0)
    ⚈  10.7 Datatype UUID (no functions needed)

Migrations:

    ⚈  CHAR(36) -> BINARY(16): change code and datatype
    ⚈  BINARY(16) -> CHAR(36)-> 10.7 datatype UUID: Probably need to get rid of (or simulate) functions (this blog or 8.0), then add 10.7 datatype
    ⚈  10.7 UUID -> CHAR(36) -> 8.0 BINARY(16): Again, a two-step migration

Postlog

Thanks to Oracle for building in functions (in ver 8) similar to what has been described here.

Thanks to Trey for some of the ideas here.

The tips in this document apply to MySQL, MariaDB, and Percona. Although the 8.0 functions have not yet made it into MariaDB or Percona, the Stored Functions described here have similar functionality.

UUID issues in a huge table
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
A StackExchange discussion
NEXTSEQUENTIALID() would be nice
Good analysis of UUID performance

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

Node.js function to do similar thing

[[https://gh.peabody.io/uuidv6/][Version 6, The version RFC 4122 forgot]] (~2020)

Separate lookup table to map UUID to smaller id?

Written: Oct, 2012; Added TokuDB: Jan, 2015; MySQL 8.0: Sep, 2016; Change Buffering: Sep. 2017; MariaDB 10.7: Nov, 2021

-- 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:
Data Warehouse Overview Summary Tables High speed ingestion Bulk Normalization

Schema and code design for large Sensor database

Entity-Attribute-Value (EAV) -- a common, poorly performing, design pattern; plus an alternative

5 methods for 'Find Nearest'

Lat/Lng search to Find the nearest 10 pizza parlors
Lat/Long representation choices

Z-Order 'find nearest'

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

Efficient List of Latest 10 news articles

Build and execute a Pivot SELECT (showing rows as columns)

(Groupwise Max): Efficiently find largest row(s) for each group

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

Rick's RoTs (Rules of Thumb -- lots of tips)

Datatypes and building a good schema

Memory Allocation (caching, etc)

Character Set and Collation problem solver
Trouble with UTF-8 If you want case folding, but accent sensitivity, please file a request at https://bugs.mysql.com .
Python tips, PHP tips, other language tips
utf8 Collations utf8mb4 Collations on 8.0

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 Handler counts wp_postmeta UNION+OFFSET

MySQL Limits -- built-in hard limits
767-byte INDEX limit

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

Analyze MySQL Performance
Analyze VARIABLEs and GLOBAL STATUS Analyze SlowLog

My slides from conferences
MiniFest 2021 - Rick James & Daniel Black - Answering on Stack Overflow(+comments) - MariaDB Frontlines
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

Contact me via LinkedIn; be sure to include a brief teaser in the Invite request:

Did my articles help you out? Like what you see? Consider donating:

☕️ Buy me a Banana Latte and bagel ($10) There is no obligation but it would put a utf8mb4 smiley 🙂 on my face, instead of the Mojibake "ðŸ™‚"

GUID/UUID Performance Breakthrough

Table of Contents

The Problem

Why it is a Problem

Second Problem

Combining the Problems and Crafting a Solution