[MDEV-26664] Store UUIDs in a more efficient manner - Jira

Details

Type: Bug
Status: Closed (View Workflow)
Priority: Critical
Resolution: Fixed
Affects Version/s: None
Fix Version/s: 10.7.1
Component/s: Data types
Labels:
- uuid

Description

UUIDs are stored in a binary form, but not byte-swapped like in MySQL's uuid_to_bin https://dev.mysql.com/doc/refman/8.0/en/miscellaneous-functions.html#function_uuid-to-bin

The order provided by UUID_TO_BIN() is not really friendly to index prefix compression:
it only reorders the timestamp segments, while the clock-seq and the node-ID segments are still at the end. This ruins the whole idea of prefix compression.

Let's sort UUID in a really index-friendly order, by moving the constant part to the left and the variable part to the right.

So for comparison purposes we'll reorder segments, but keep the byte order inside the segments (i.e. in big endian order):

MariaDB binary UUIDv1 representation, as returned by the UUID() function:

  llllllll-mmmm-Vhhh-vsss-nnnnnnnnnnnn

Binary sortable representation:

   nnnnnnnnnnnn-vsss-Vhhh-mmmm-llllllll

Sign           Section               Bits   Bytes  Pos   PosBinSortable

-------------  -------               ----   -----  ---   --------------

llllllll       time low              32     4        0   12

mmmm           time mid              16     2        4   10

Vhhh           version and time hi   16     2        6   8

vsss           variant and clock seq 16     2        8   6

nnnnnnnnnnnn   node ID               48     6       10   0

Attachments

Issue Links

causes

MDEV-29959 UUID Sorting

Closed

is caused by

MDEV-4958 Adding datatype UUID

Closed

relates to

MDEV-20477 Merge binlog extended metadata support from the upstream

Closed

MDEV-27588 MyISAM/Aria descending index compression is not as efficient as ascending

Closed

links to

How are GUIDs compared in SQL Server 2005?

SQL Server GUID sort algorithm. Why?

The uniqueidentifier data type in SQL server

(2 links to)

Activity

Ascending order - Click to sort in descending order

View 11 older comments

Alexander Barkov added a comment - 2021-10-20 08:40 - edited

danblack, I agree, for externally generated UUIDs, it's better to place "vsss" at the end.

Just tested this script:

SET default_storage_engine=MyISAM;

CREATE OR REPLACE TABLE t1 (a UUID, INDEX(a));

SHOW CREATE TABLE t1;

BEGIN;

DELIMITER $$

FOR i IN 0..0xFFFF

DO

  INSERT INTO t1 VALUES (UUID());

END FOR

$$

DELIMITER ;

COMMIT;

show table status like 't1'\G

nnnnnnnnnnnn-vsss-Vhhh-mmmm-llllllll gives the ratio of 0.56:

     Data_length: 1114112

    Index_length: 624640

nnnnnnnnnnnn-Vhhh-mmmm-llllllll-vsss gives the ratio of 0.68:

     Data_length: 1114112

    Index_length: 764928

It's probably still good enough.

Note, the "user visible" order llllllll-mmmm-Vhhh-vsss-nnnnnnnnnnnn, which is now in the preview branch, gives the ratio of 1.44. This one is really bad.

     Data_length: 1114112

    Index_length: 1611776

Alexander Barkov added a comment - 2021-10-20 08:40 - edited danblack , I agree, for externally generated UUIDs, it's better to place "vsss" at the end. Just tested this script: SET default_storage_engine=MyISAM; CREATE OR REPLACE TABLE t1 (a UUID, INDEX (a)); SHOW CREATE TABLE t1; BEGIN ; DELIMITER $$ FOR i IN 0..0xFFFF DO INSERT INTO t1 VALUES (UUID()); END FOR $$ DELIMITER ; COMMIT ; show table status like 't1' \G nnnnnnnnnnnn-vsss-Vhhh-mmmm-llllllll gives the ratio of 0.56: Data_length: 1114112 Index_length: 624640 nnnnnnnnnnnn-Vhhh-mmmm-llllllll-vsss gives the ratio of 0.68: Data_length: 1114112 Index_length: 764928 It's probably still good enough. Note, the "user visible" order llllllll-mmmm-Vhhh-vsss-nnnnnnnnnnnn , which is now in the preview branch, gives the ratio of 1.44. This one is really bad. Data_length: 1114112 Index_length: 1611776

Sergei Golubchik added a comment - 2021-10-21 16:04

The UUIDv1 standard specifies that

sss is initialized to a random value
every time the system clock (hhh-mmmm-llllllll) goes backward (a new generated value is less than the previous one), sss is incremented.

So clearly sss should go before the system clock value, as in sss-hhh-mmmm-llllllll

Sergei Golubchik added a comment - 2021-10-21 16:04 The UUIDv1 standard specifies that sss is initialized to a random value every time the system clock ( hhh-mmmm-llllllll ) goes backward (a new generated value is less than the previous one), sss is incremented. So clearly sss should go before the system clock value, as in sss-hhh-mmmm-llllllll

Sergei Golubchik added a comment - 2021-10-23 18:59 - edited

ok to push (into a preview branch)

Sergei Golubchik added a comment - 2021-10-23 18:59 - edited ok to push (into a preview branch)

Alexander Barkov added a comment - 2021-10-25 10:10

Pushed into preview-10.7-~~MDEV-4958~~-uuid.

Alexander Barkov added a comment - 2021-10-25 10:10 Pushed into preview-10.7- MDEV-4958 -uuid.

Illia Somov added a comment - 2023-04-27 12:50

This should have been only applied to UUIDv1...

Illia Somov added a comment - 2023-04-27 12:50 This should have been only applied to UUIDv1...

People

Assignee:: Alexander Barkov

Reporter:: Ian Gilfillan

Votes:: 2 Vote for this issue

Watchers:: 7 Start watching this issue

Dates

Created:: 2021-09-22 11:35

Updated:: 2023-04-27 12:50

Resolved:: 2021-10-25 10:10

Git Integration

Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.

MariaDB Server