Re: A varint implementation for PG? - Mailing list pgsql-hackers

On 8/4/21 9:01 PM, Andres Freund wrote:
> Hi,
> 
> On 2021-08-03 14:26:16 -0400, Robert Haas wrote:
>> [ resurrecting this 2-year-old thread ]
>>
>> On Fri, Dec 13, 2019 at 12:45 AM Andres Freund <andres@anarazel.de> wrote:
>>>> If baking a new variant integer format now, I think limiting it to 64 bits
>>>> is probably a mistake given how long-lived PostgreSQL is, and how hard it
>>>> can be to change things in the protocol, on disk, etc.
>>>
>>> I don't think it's ever going to be sensible to transport 64bit quanta
>>> of data. Also, uh, it'd be larger than the data a postgres instance
>>> could really contain, given LSNs are 64 bit.
>>
>> We already use 128-bit integers in some places in the source code, and
>> it seems more likely than not that use of 128-bit integer data types
>> will continue to expand over time. If we want to represent 64 bit
>> integers in a variable number of bits today, it does seem pretty
>> likely that some day we will want to do the same thing with 128 bit
>> integers, and maybe eventually larger. And I think that all of that is
>> true even though exhausting a 64-bit LSN space looks difficult today
>> and will likely remain difficult for the foreseeable future.
> 
> I was thinking a bit about how to encode arbitrary length values for the cases
> where that's interesting.
> 
> Currently what I proposed for 8 byte unsigned integers is that we encode the
> length in unary unset bits, followed by a set bit. As a special case, a prefix
> of 8 bits indicates a length of 9, without needing the separator bit - we
> don't need a separator bit at that point.
> 

How is that better than the two varint flavors that are already out 
there, i.e. the bitcoin [1] and protocol buffers [2]?

The first one seems quite efficient in how it encodes the length into 
very few bits (which matters especially for small values). It's designed 
for integers with 1B, 2B, 4B or 8B, but it can be extended to arbitrary 
lengths fairly easily, I think:

Look at the first byte, and

0 - 243 - encoded as is
244 - 1 byte
245 - 2 bytes
246 - 3 bytes
247 - 4 bytes
248 - 5 bytes
249 - 6 bytes
250 - 7 bytes
251 - 8 bytes
252 - next 1 byte is length
253 - next 2 bytes are length
254 - next 3 bytes are length
255 - next 4 bytes are length

If we want to support longer lengths, we'd have to reserve an extra 
value (which reduces the number of values that require a single byte).

The [2] is a bit more problematic, as it's tailored for very short 
values (essentially wasting 1/8 of bits) and you have to parse the whole 
value to determine the length.

[1] https://wiki.bitcoinsv.io/index.php/VarInt
[2] https://developers.google.com/protocol-buffers/docs/encoding

> Extending that to arbitrary lengths obviously at some point makes the encoding
> in unary wasteful, and the benefit of few branches vanishes. So what I was
> thinking is that for variable length pieces of data that are not limited to 8
> bytes, we could replace the '8 0 bits' special case with a new special case:
> The length in bytes follows as a max-8-byte varint.
> 
> That'd leave us with the following overheads:
> - 0 - 127: 0 bytes (i.e. 0 to 7 bits)
> - 128 - 2^56 - 1: 1 byte (i.e. 7 bits - 7 bytes)
> - 7 bytes - 127 bytes: 2 bytes
> - 128 bytes - 16383 bytes: 3 bytes
> - 16384 bytes - 2097151 bytes: 4 bytes
> - 2097152 bytes - 268435455 bytes: 5 bytes
> - 268435456 bytes - 34359738367 bytes: 6 bytes
> - ...
> 
> The obvious alternative would of course be to just always store the length
> prefix separately:
> - 0 - 127 bytes: 1 byte
> - 128 - 16383 bytes: 2 bytes
> - 16384 - 2097151 bytes: 3 bytes
> - ...
> 
> I do suspect that for a fair number of cases the "0 byte overhead" for very
> small values would be worth the increase in overhead later. Particularly
> because the decoding for values up to 7 bytes would be cheaper cpu-wise as
> well.
> 

Yeah. Especially if the long values can be compressed, which probably 
applies to most real-world data sets. IMHO the efficiency for short 
values is the more important thing.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company