Subject: Re: Standard uuid vs. custom data type uuid_v1
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: pgsql-performance@lists.postgresql.org
References: <2d21f58d-230b-27b9-e48c-dda23a258066@googlemail.com>
 <20190727134736.xmzqbo2uoigmfkkv@development>
From: Ancoron Luciferis <ancoron.luciferis@googlemail.com>
Openpgp: preference=signencrypt
Autocrypt: addr=ancoron.luciferis@googlemail.com; prefer-encrypt=mutual;
 keydata=
 mQINBE3Z7bUBEAC3ZYDTnxOiu0JWJR+6XzFQmJEVncGMehyuE9GBfyaNYnsNKmFITkubNVB9
 tN/xgn5FJ9eg0WediTaWXigHNDDOPSNHZGaf1nHu0AQNOgpEyJETtX/A56PXQ82+VwoKCNUN
 v8+m5CJ8njWZlZMCVA3AcQ1vR2VRR6O0pzEVPDCDMutPytkRl+XrPoPhxMTVEmwM4jfWwmfI
 NgiOZnsueU78VW8Go1qTN20YdVOdVpbPWfyp8VIGYBNjEEefv5f/l+zt4Z+CQMmvunDUdaKY
 85opNIMLqC3dDY0AQG+FpcDLhHWLcuGLmE+Ghiix0G3kX4QX/fH0/2KtVNdfnZtcpq+5rim0
 E97PVQe4EixVD/DivpwvNMWqQ2GJlOCx52+J13ZSfe/63XpjL7TNqhR3wMnNuMidLMgLoH5z
 RtQ2FH9zeYlKgqMUkmwvEHVI+M4oQRE0rzgqx6xHbkPIFEov9ZziQVwCtct+Ja9ho/BXoe/T
 VIFVOGEp7DG12QSaiLILhzTRUkDXqa+BH9H4V2Hsv77nT2JQ7KO9pM5gb4wq4gtLFo7MMTUq
 jlqjD2vOm3NY3tg1s7HTggVNgGsWhh9JlNR3v9SRGckKVIIvwDxvzo+Z4iji2SLElWb9BWiH
 Xku5IEuWGTmC+nOzSvbSxTaC53JcppC5kKXj11N73uw5eR4s3wARAQABtDRBbmNvcm9uIEx1
 Y2lmZXJpcyA8YW5jb3Jvbi5sdWNpZmVyaXNAZ29vZ2xlbWFpbC5jb20+iQI4BBMBAgAiBQJN
 2e21AhsDBgsJCAcDAgYVCAIJCgsEFgIDAQIeAQIXgAAKCRBzrR1GWXG7SN0DD/9qJR1Bsm52
 W/T+XKQ0DApt3rCVgt9e5gvk4mUgtUIufIVOx3t/s2qw84VcSyNVclfoecLF0JdBWavobyCn
 JAIVkgGt0wGF6Kzsbiq7vlqDHDYiB7prvY4vj6bpmEQGYBBmWPG6/AVvBRJsvvaSGTqqdVth
 4MYl43VxDZD+aVq52o0ROQAWyZC28kevTvRxusLuwZc4Q7HvOuAGNeD4aGLIgbOpyiS4mkC3
 i2B++/cQ+zurzCWqCi1U/0sFXtwV2Qh6gjZK/TvZogTMUxjftZdvP49R5NrEB6AWx5ztp/RO
 7Jy2j+Xm4OAteb5uGegzyoPKzr7B9O76GtfXLgLyZjpBIpuudosx+vJ9g7wuDHWXj7f5QKZQ
 PLqDO5SxI/Yi5tM4byag9/KZ7aHmeCXuAOnRTvKh6xMyB0fq6aPtpRlek4NcHWdT2SaR1y5K
 XxqWM/x7wLUyQo1lvjPTWX2MS70AjPJ5BdZzEjoA3zucT/ibu+CRjbyAOx5XwIBTnutj/+oI
 osslCFbMMj6n9NRoJidmy8q2nMYH+lMP1nTbdLCLesURVlTVLcMxIQhsjRZC/E6tu86C6rHB
 VrNjlUHkXHwJ9qQ3FbFOudqPUatYcfJSI7PmPbxWqNhcnVXlA1yndT7kAfWsmIxaJvDw09p5
 dxkrNZi0LYoyLmMLImCb0yCHibkCDQRN2e21ARAAuQP7cntv+HFvl+3aUMZ68vTcV+0AfFfN
 DqZy6UYNbggIkuTtE5c5O88oBaJ/4idyAwzleb0Ess51xgYExv1zdxj61i+FfTOXEHhXp+uG
 Zk3mYVlp5juZwdEClrNkMTZehP6zvEvem5MkGGe3RBg7v4svg+xiaqaPMeN2Kj7KbObrlKcA
 F9A/4lRr5F0lH/RJaIaIUAgccVbRQdN1Z0JD6CU54sNlOCvkRqq1zNgmDSq/6WPs+WMkd0FT
 yMeyus9sPOmBrld4Wp6jHJSt7cYzq45F87b6oUPPVs4uSa1CN6IZZKk1rmQzuuFclTdw3Ari
 kjBKhFXe0gwsahPUYMOaICc62ivGKhHW/6HXh0JrPP9zqc/hMSY/fXffBXKAab4xnCA7/oUU
 4W8/wD4qvq0w77i5bUJrHg+AhFEGDXWPfMCYjIE0oLTCYK696yhhVpVSFD8c3Uj1tSQERbBN
 7qpDKGSOjRZyPLAH0yOAVgqteLkDhzwhqgwBhCXEOQAWqgvP2JI8cvbQYprG5uQnsS6TkYlq
 1/nmmV+6HfMmitEp7siGaq0UmVZHBrGD+BQjuLkKPZ95YCSwc8xM/Y6viOIxvgisVRNXqo0r
 QW/FYXKnz0i7ZQTYE4Rad487mtd+eAcW1LhwBlM5dJRxx6Ee8dKkhjvQjap4MmghpNltULUF
 yGkAEQEAAYkCHwQYAQIACQUCTdnttQIbDAAKCRBzrR1GWXG7SOmfEACisSp8ZEfX6zVvzLNu
 YVXlvnQcd+w7VtN9+MMB3P9xZUku82/flaZTVvCbQ/kDRT9BrLdNcxM9dgt6Fgih49qN6+TI
 2Atl+nBO9KtKaBc8wFs06VEEYkaIvtiS99KJO2wjQXKE1/Fj/HLKET62BctFFk5fgTdzHpxZ
 2yovkQ+cPhkkyKpW7/UjFYn2Phpvg3KU1kcH/5oyGjRzCFTT0ERlyKWA/X/XxzX7+k2LVEh0
 QzpuZbn/S0ldHDtP+fMoZZAHjVpWUu6A0zLYIHQkX/X4gkBvlWwvVuh27lDULJ8elrECyGOp
 46G14r1t6bSnESm9W9AcvtG1pQQMv7zoHXJNgYew2cbkSxgBSjNNxnkUPIJdvX8Bel/iQzLr
 EXCaZ/myDJ4RNrzkvRBWdOWMvBkIV3yXogp6CyYzq5IaQgSIiv5Hr17ssuNR+FS5aZBocJru
 pCqLD/AdS3MZLBeRGmpDWkuj4uc4/4tLDIHcmCYia47FD2OuGSbLDz4BBeEmR37CkFsxIq6f
 eszCf1awGfZv7i0ddVFT3gtJTBoRE6VPkpcMrYaEjhtbrGI9PwB+7rNd4V9O6qPwV450KldB
 FwlHzOjWNRkfDUc3sgRB3QXlH3bVsHqUVBBTXf5YwqxeQtIRe/A7ICU3kLx8BKiUZXhOoTur
 jG7LftY+nte9Tt8CTQ==
Message-ID: <c870e7d7-9f26-32ff-dc55-c0c994cb6712@googlemail.com>
Date: Mon, 29 Jul 2019 10:13:23 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.8.0
MIME-Version: 1.0
In-Reply-To: <20190727134736.xmzqbo2uoigmfkkv@development>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Precedence: bulk

On 27/07/2019 15:47, Tomas Vondra wrote:
> On Thu, Jul 25, 2019 at 11:26:23AM +0200, Ancoron Luciferis wrote:
>> Hi,
>>
>> I have finally found some time to implement a custom data type optimized
>> for version 1 UUID's (timestamp, clock sequence, node):
>> https://github.com/ancoron/pg-uuid-v1
>>
>> Some tests (using a few millions of rows) have shown the following
>> results (when used as a primary key):
>>
>> COPY ... FROM: ~7.8x faster (from file - SSD)
>> COPY ... TO  : ~1.5x faster (no where clause, sequential output)
>>
>> The best thing is that for INSERT's there is a very high chance of
>> hitting the B-Tree "fastpath" because of the timestamp being the most
>> significant part of the data type, which tends to be increasing.
>>
>> This also results in much lower "bloat", where the standard "uuid" type
>> easily goes beyond 30%, the "uuid_v1" should be between 10 and 20%.
>>
>> Additionally, it also reveals the massive performance degrade I saw in
>> my tests for standard UUID's:
>>
>> Initial 200 million rows: ~ 80k rows / second
>> Additional 17 million rows: ~26k rows / second
>>
>> ...and the new data type:
>> Initial 200 million rows: ~ 623k rows / second
>> Additional 17 million rows: ~618k rows / second
>>
> 
> Presumably, the new data type is sorted in a way that eliminates/reduces
> random I/O against the index. But maybe that's not the case - hard to
> say, because the linked results don't say how the data files were
> generated ...
> 

Yes, by definition, version 1 UUID's contain the timestamp and when used
in applications, that is usually the "current" timestamp when an entry
gets prepared for storage. As a result, for testing I've simulated 9
nodes with increasing timestamps, which then results in very similar
behavior to sequentially increasing values.

The calculation for the above numbers has been based on "\timing" in
logged psql test sessions (so the little client overhead is included in
calculation). Internal behavior has also been tracked with Linux "perf
record" and flamegraph'd.

Test data has been generated by the following Java (Maven) project:
https://github.com/ancoron/java-uuid-serial

...with arguments:

mvn clean test \
	-Duuids=217000000 \ # number of UUID's
	-Duuid.skip.v1=false \ # generate V1 UUID's and serial
	-Dnodes=9 \ # how many nodes to simulate
	-Duuid.historic=true \ # enable historic mode (not "now")
	-Dinterval_days=365 # range of days to generate

...which will generate V1 UUID's into a file
"target/uuids.v1.historic.txt" as follows:

fb2893ae-9265-11e8-90d8-e03f496e733b
fb2c3d2e-9265-11e8-a131-e03f49777cbb
fda90b33-9265-11e8-af1b-e03f4957fa73
fdaba343-9265-11e8-b648-e03f49e7fd77
fdad50f3-9265-11e8-b9be-e03f49de7ab7
fdaf73d3-9265-11e8-bdce-e03f49dff937
fdb25a03-9265-11e8-a0d8-e03f49c67ff3
fdb28113-9265-11e8-9c15-e03f4976fd73
fdb2a823-9265-11e8-8273-e03f49d6f3f7
fdb8c2a3-9265-11e8-90d8-e03f496e733b
fdbc6c23-9265-11e8-a131-e03f49777cbb
00393a28-9266-11e8-af1b-e03f4957fa73
003bd238-9266-11e8-b648-e03f49e7fd77
003d7fe8-9266-11e8-b9be-e03f49de7ab7
003fa2c8-9266-11e8-bdce-e03f49dff937
004288f8-9266-11e8-a0d8-e03f49c67ff3
0042b008-9266-11e8-9c15-e03f4976fd73
0042d718-9266-11e8-8273-e03f49d6f3f7
0048f198-9266-11e8-90d8-e03f496e733b

...so yes, they are ever-increasing from a timestamp-perspective, which
is what I was intending to optimize for in the first iteration.

I'll do some more testing with slight time offsets between the nodes to
simulate behavior when some nodes generate time a few seconds behind others.

I might re-implement the UUID test data generator in Python as that
would be far more usable for others.


Cheers,

	Ancoron