# VAR autoincrement with constant space consumption for super large tables

Assume there was a database system that had a data type called VARINT or some variant that allowed instead of fixed-length INTs regardless of value, a 1 would only take 1 BIT (1), 2 would take 2 BITs (10), etc.

In this perfect world, a VARINT could be used to autoincrement a PRIMARY column. However, there's still the issue of the field growing in size, so the "older" parts of this TABLE would be very fast, but the "younger" parts would get slower and slower.

What counting system could be used to hold the space consumed constant and small or at least grow at a much slower rate?

• Are you searching for a kind of ID that uses constant or sublogarithmic space in the number of elements to be stored? – frafl Apr 5 '13 at 19:51
• @frafl I think so. Like if a FLOAT had accuracy. It never grows in size, but it can be used from the very small to the very large. – user7386 Apr 5 '13 at 19:55

## 1 Answer

If you want an ID (i.e. unique label, whether number or not) which is stored as a binary (or $k$-ary) string you will have at least logarithmic growth, because with $o(\log n)$ bits you can't identify more than $k^{o(\log n)}=o(n)$ objects. So you can't do much better.

You could however map the old IDs to new IDs every time the size of the table doubles. If the entry #$2^m$ is inserted, the old IDs become $\mathrm{id}'=2^{m+1}+\mathrm{id}$ and the younger elements get shorter IDs. This only works if you don't use the IDs elsewhere (major drawback for a PRIMARY) and you have a reason to believe that newer entries get requested more often than older ones.

Finally one may ask whether you really need big integers for some kind of ID. According to this there are $\approx 10^{80}\leq 2^{267}$ atoms in the observable universe, so a kilobit sized ID will do for most purposes.