Subject: Re: UUID v1 optimizations...
References: <8d5f4b67-d540-8d3d-9979-808b9c1e1ca7@googlemail.com>
 <20635.1558796270@sss.pgh.pa.us>
 <19faa3aa-a103-b991-ff20-b73852085f30@googlemail.com>
 <14074.1558821255@sss.pgh.pa.us>
 <20190525221428.3yc6hhvj7aawjpjv@development>
 <fbe47bd7-d1a3-16bd-4c0f-90378022eeb1@googlemail.com>
 <20190526010918.lrww6cw76halyu4w@development>
To: pgsql-performance@lists.postgresql.org
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: <6043492f-f372-2887-c686-0995da409427@googlemail.com>
Date: Sun, 26 May 2019 11:01:36 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.6.1
MIME-Version: 1.0
In-Reply-To: <20190526010918.lrww6cw76halyu4w@development>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Precedence: bulk

On 26/05/2019 03:09, Tomas Vondra wrote:
> On Sun, May 26, 2019 at 01:49:30AM +0200, Ancoron Luciferis wrote:
>> On 26/05/2019 00:14, Tomas Vondra wrote:
>>> On Sat, May 25, 2019 at 05:54:15PM -0400, Tom Lane wrote:
>>>> Ancoron Luciferis <ancoron.luciferis@googlemail.com> writes:
>>>>> On 25/05/2019 16:57, Tom Lane wrote:
>>>>>> (4) it in fact *wouldn't* do anything useful, because we'd still have
>>>>>> to sort UUIDs in the same order as today, meaning that btree index
>>>>>> behavior
>>>>>> would remain the same as before.  Plus UUID comparison would get a
>>>>>> lot
>>>>>> more complicated and slower than it is now.
>>>>
>>>>> I get your first sentence, but not your second. I know that when
>>>>> changing the internal byte order we'd have to completed re-compute
>>>>> everything on-disk (from table to index data), but why would the
>>>>> sorting
>>>>> in the index have to be the same?
>>>>
>>>> Because we aren't going to change the existing sort order of UUIDs.
>>>> We have no idea what applications might be dependent on that.
>>>>
>>>> As Vitalii correctly pointed out, your beef is not with the physical
>>>> storage of UUIDs anyway: you just wish they'd sort differently, since
>>>> that is what determines the behavior of a btree index.  But we aren't
>>>> going to change the sort ordering because that's an even bigger
>>>> compatibility break than changing the physical storage; it'd affect
>>>> application-visible semantics.
>>>>
>>>> What you might want to think about is creating a function that maps
>>>> UUIDs into an ordering that makes sense to you, and then creating
>>>> a unique index over that function instead of the raw UUIDs.  That
>>>> would give the results you want without having to negotiate with the
>>>> rest of the world about whether it's okay to change the semantics
>>>> of type uuid.
>>>>
>>>
>>> FWIW that's essentially what I implemented as an extension some time
>>> ago. See [1] for a more detailed explanation and some benchmarks.
>>
>> Yes, I've seen that before. Pretty nice work you but together there and
>> I'll surely have a look at it but we certainly need the node id in
>> compliance with v1 UUID's so that's why we've been generating UUID's at
>> the application side from day 1.
>>
>>>
>>> The thing is - it's not really desirable to get perfectly ordered
>>> ordering, because that would mean we never get back to older parts of
>>> the index (so if you delete data, we'd never fill that space).
>>
>> Wouldn't this apply also to any sequential-looking index (e.g. on
>> serial)?
> 
> Yes, it does apply to any index on sequential (ordered) data. If you
> delete data from the "old" part (but not all, so the pages don't get
> completely empty), that space is lost. It's available for new data, but
> if we only insert to "new" part of the index, that's useless.

OK, thanks for clearing that up for me.

> 
>> The main issue with the UUID's is that it almost instantly
>> consumes a big part of the total value space (e.g. first value is
>> '01...' and second is coming as 'f3...') which I would assume not being
>> very efficient with btrees (space reclaim? - bloat).
>>
> 
> I don't understand what you mean here. Perhaps you misunderstand how
> btree indexes grow? It's not like we allocate separate pages for
> different values/prefixes - we insert the data until a page gets full,
> then it's split in half. There is some dependency on the order in which
> the values are inserted, but AFAIK random order is generally fine.

OK, I might not understand the basics of the btree implementation. Sorry
for that.

However, one of our issues with standard v1 UUID's was bloat of the
indexes, although we kept only a few months of data in it. I think, this
was due to the pages still containing at least one value and not
reclaimed by vacuum. It just continued to grow.

Now, as we have this different ever-increasing prefix, we still have
some constant growing but we see that whenever historic data get's
deleted (in a separate process), space get's reclaimed.


> 
>> One of our major concerns is to keep index size small (VACUUM can't be
>> run every minute) to fit into memory next to a lot of others.
>>
> 
> I don't think this has much to do with vacuum - I don't see how it's
> related to the ordering of generated UUID values. And I don't see where
> the "can't run vacuum every minute" comes from.

OK, numbers (after VACUUM) which I really found strange using the query
from pgexperts [1]:

     index_name      | bloat_pct | bloat_mb | index_mb | table_mb
---------------------+-----------+----------+----------+----------
 uuid_v1_pkey        |        38 |      363 |  965.742 |  950.172
 uuid_serial_pkey    |        11 |       74 |  676.844 |  950.172
 uuid_serial_8_pkey  |        46 |      519 | 1122.031 |  950.172
 uuid_serial_16_pkey |        39 |      389 |  991.195 |  950.172

...where the "8" and "16" is a "shift" of the timestamp value,
implemented with:

timestamp = (timestamp >>> (60 - shift)) | (timestamp << (shift + 4))

If someone could shed some light on why that is (the huge difference in
index sizes) I'd be happy.

> 
>> I've experimented with the rollover "prefix" myself but found that it
>> makes the index too big (same or larger index size than standard v1
>> UUIDs) and VACUUM too slow (almost as slow as a standard V1 UUID),
>> although INSERT performance wasn't that bad, our sequential UUID's where
>> way faster (at least pre-generated and imported with COPY to eliminate
>> any value generation impact).
>>
> 
> I very much doubt that has anything to do with the prefix. You'll need
> to share more details about how you did your tests.

OK, I'll see if I can prepare something and publish it.

> 
> 
> regards
> 


Refs:
[1]
https://github.com/pgexperts/pgx_scripts/blob/master/bloat/index_bloat_check.sql