[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

Ian Gilfillan created issue - 2021-09-22 11:35

Ian Gilfillan made changes - 2021-09-22 11:35

Field	Original Value	New Value
Link		This issue relates to ~~MDEV-4958~~ [ ~~MDEV-4958~~ ]

Sergei Golubchik made changes - 2021-10-11 16:12

Link

This issue is part of ~~MDEV-4958~~ [ ~~MDEV-4958~~ ]

Sergei Golubchik made changes - 2021-10-11 16:12

Link

This issue relates to ~~MDEV-4958~~ [ ~~MDEV-4958~~ ]

Sergei Golubchik made changes - 2021-10-11 16:12

Issue Type

Task [ 3 ]

Bug [ 1 ]

Sergei Golubchik made changes - 2021-10-11 16:13

Link

This issue is caused by ~~MDEV-4958~~ [ ~~MDEV-4958~~ ]

Sergei Golubchik made changes - 2021-10-11 16:13

Link

This issue is part of ~~MDEV-4958~~ [ ~~MDEV-4958~~ ]

Sergei Golubchik made changes - 2021-10-11 16:13

Assignee

Alexander Barkov [ bar ]

Sergei Golubchik made changes - 2021-10-11 16:13

Fix Version/s

10.7 [ 24805 ]

Sergei Golubchik made changes - 2021-10-11 16:13

Priority

Major [ 3 ]

Critical [ 2 ]

Alexander Barkov made changes - 2021-10-12 10:42

Remote Link

This issue links to "The uniqueidentifier data type in SQL server (Web Link)" [ 32200 ]

Alexander Barkov made changes - 2021-10-12 10:44

Remote Link

This issue links to "SQL Server GUID sort algorithm. Why? (Web Link)" [ 32201 ]

Alexander Barkov made changes - 2021-10-12 10:44

Remote Link

This issue links to "How are GUIDs compared in SQL Server 2005? (Web Link)" [ 32202 ]

Alexander Barkov made changes - 2021-10-15 18:01

Link

This issue relates to ~~MDEV-20477~~ [ ~~MDEV-20477~~ ]

Alexander Barkov made changes - 2021-10-15 18:10

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

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.

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:

{noformat}
    Binary UUIDv1 representation:

      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
{noformat}

Alexander Barkov made changes - 2021-10-15 18:11

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.

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:

{noformat}
    Binary UUIDv1 representation:

      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
{noformat}

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.

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:

{noformat}
Binary UUIDv1 representation:

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
{noformat}

Alexander Barkov made changes - 2021-10-15 18:11

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.

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:

{noformat}
Binary UUIDv1 representation:

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
{noformat}

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.

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:

{noformat}
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
{noformat}

Alexander Barkov made changes - 2021-10-15 18:12

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.

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:

{noformat}
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
{noformat}

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:

{noformat}
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
{noformat}

Alexander Barkov made changes - 2021-10-15 18:13

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:

{noformat}
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
{noformat}

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

{noformat}
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
{noformat}

Alexander Barkov made changes - 2021-10-19 09:48

Status

Open [ 1 ]

In Progress [ 3 ]

Alexander Barkov made changes - 2021-10-19 09:48

Assignee	Alexander Barkov [ bar ]	Sergei Golubchik [ serg ]
Status	In Progress [ 3 ]	In Review [ 10002 ]

Sergei Golubchik made changes - 2021-10-23 18:59

Assignee	Sergei Golubchik [ serg ]	Alexander Barkov [ bar ]
Status	In Review [ 10002 ]	Stalled [ 10000 ]

Alexander Barkov made changes - 2021-10-25 10:10

issue.field.resolutiondate

2021-10-25 10:10:59.0

2021-10-25 10:10:59.4

Alexander Barkov made changes - 2021-10-25 10:10

Fix Version/s		10.7.1 [ 26120 ]
Fix Version/s	10.7 [ 24805 ]
Resolution		Fixed [ 1 ]
Status	Stalled [ 10000 ]	Closed [ 6 ]

Sergei Golubchik made changes - 2021-12-06 21:53

Workflow

MariaDB v3 [ 125248 ]

MariaDB v4 [ 159704 ]

Elena Stepanova made changes - 2022-01-23 17:03

Link

This issue relates to ~~MDEV-27588~~ [ ~~MDEV-27588~~ ]

Rick Strafy made changes - 2022-11-06 19:37

Link

This issue causes ~~MDEV-29959~~ [ ~~MDEV-29959~~ ]

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.