Subject: Re: UUID v1 optimizations...
To: pgsql-performance@lists.postgresql.org
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>
 <CAKqnccg_Wc1HS_+ddS=zPoKEAvtC7ZLdYFrWMDLbjw4c=hxzjQ@mail.gmail.com>
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: <17b9facd-4c3e-1306-afac-98f70011aab1@googlemail.com>
Date: Sun, 26 May 2019 11:38:48 +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: 
 <CAKqnccg_Wc1HS_+ddS=zPoKEAvtC7ZLdYFrWMDLbjw4c=hxzjQ@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Precedence: bulk

On 26/05/2019 06:27, Morris de Oryx wrote:
> I'm not worthy to post here, but a bit of a random thought.
> 
> If I've followed the conversation correctly, the reason for a V1 UUID is
> partly to order and partition rows by a timestamp value, but without the
> cost of a timestamp column. As I was told as a boy, "Smart numbers
> aren't." Is it _absolutely_ the case that you can't afford another
> column? I don't know the ins and outs of the Postgres row format, but my
> impression is that it's a fixed size, so you may be able to add the
> column without splitting rows? Anyway, even if that's not true and the
> extra column costs you disk space, is it the index that concerns you? 
> Have you considered a timestamp column, or a numeric column with an
> epoch offset, and a BRIN index? If you insert data is in pretty much
> chronological order, that might work well for you.

Exactly, we are using the actual information combined within a v1 UUID
in multiple places and would like to avoid redundancy of information in
the database as we strive to keep as much of it in memory and
partitioning as well as timestamp (range) searching and sorting is a
pretty common thing for us.

For us, it's not an absolute "no-go" to have an additional column but
the semantics of the v1 UUID already guarantees us uniqueness across all
partitions, is the internal primary key and has additional information
we are using (creation time, node).

In addition, the extra column would need yet another index which brings
our write performance down again. So, while it would improve reading,
we're currently (still) more concerned about the write performance.

The BRIN index is something I might need to test, though.

> 
> Best of luck, I've enjoyed following the commentary.
> 
> 
> On Sun, May 26, 2019 at 11:09 AM Tomas Vondra
> <tomas.vondra@2ndquadrant.com <mailto:tomas.vondra@2ndquadrant.com>> 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
>     <mailto: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.
> 
>     > 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.
> 
>     >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.
> 
>     >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.
> 
> 
>     regards
> 
>     -- 
>     Tomas Vondra                  http://www.2ndQuadrant.com
>     PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
> 
>