Numeric patch to add special-case representations for < 8 bytes

I've uploaded a quick hack to store numerics in < 8 bytes when possible.

http://community.enterprisedb.com/numeric-hack-1.patch

This is a bit of a kludge since it doesn't actually provide any interface for
external clients of the numeric module to parse the resulting data. Ie, the
macros in numeric.h will return garbage.

But I'm not entirely convinced that matters. It's not like those macros were
really useful to any other modules anyways since there was no way to extract
the actual digits.

The patch is also slightly unsatisfactory because as I discovered numbers like
1.1 are stored as two digits currently. But it does work and it does save a
substantial amount of space for integers.

postgres=# select n,pg_column_size(n) from n;
n | pg_column_size
----------+----------------
1 | 2
11 | 2
101 | 2
1001 | 3
10001 | 9
100001 | 9
1.1 | 9
10.1 | 9
100.1 | 9
1000.1 | 9
10000.1 | 11
100000.1 | 11

I had hoped to get the second batch to be 3-4 bytes. But even now note how
much space is saved for integers <10000.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Gregory Stark schrieb am 27.02.2007 01:39:
> I've uploaded a quick hack to store numerics in < 8 bytes when possible.
>
> http://community.enterprisedb.com/numeric-hack-1.patch
>
> This is a bit of a kludge since it doesn't actually provide any interface for
> external clients of the numeric module to parse the resulting data. Ie, the
> macros in numeric.h will return garbage.
>
> But I'm not entirely convinced that matters. It's not like those macros were
> really useful to any other modules anyways since there was no way to extract
> the actual digits.
>
> The patch is also slightly unsatisfactory because as I discovered numbers like
> 1.1 are stored as two digits currently. But it does work and it does save a
> substantial amount of space for integers.
>
> postgres=# select n,pg_column_size(n) from n;
> n | pg_column_size
> ----------+----------------
> 1 | 2
> 11 | 2
> 101 | 2
> 1001 | 3
> 10001 | 9
> 100001 | 9
> 1.1 | 9
> 10.1 | 9
> 100.1 | 9
> 1000.1 | 9
> 10000.1 | 11
> 100000.1 | 11
>
> I had hoped to get the second batch to be 3-4 bytes. But even now note how
> much space is saved for integers <10000.
>
>
Very nice :-) I'm looking forward to something like that. We store huge
quantities of numerics in our DB's (I strongly discourage using ANSI754
floats anywhere).
Maybe you want to have a look here:
http://www2.hursley.ibm.com/decimal/DPDecimal.html

just my 0.02$... ;-)

Patric

"Patric Bechtel" <bechtel(at)ipcon(dot)de> writes:

> Maybe you want to have a look here:
> http://www2.hursley.ibm.com/decimal/DPDecimal.html

Well we're not really looking for the optimal packing in general. All the
problems here have to do with convenience in the implementation rather than
the problems with the approach. It's easier in the code to have fixed size
scale and weight and to have them at the beginning of the data type, which is
fine for larger values but for small values they dominate and waste space.

But as far as the approach goes, I admit I find it a bit hard to believe that
we're still doing BCD in the 21st century at all.

If we stored the digits in base 2 with a base 10 exponent would it really be
too hard to output the digits? Even long multiplication and then reversing the
results doesn't seem like it would be too bad and surely there must exist
reasonable algorithms to do better.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Gregory Stark schrieb am 01.03.2007 10:23:
> "Patric Bechtel" <bechtel(at)ipcon(dot)de> writes:
>
>> Maybe you want to have a look here:
>> http://www2.hursley.ibm.com/decimal/DPDecimal.html
>
> Well we're not really looking for the optimal packing in general. All the
> problems here have to do with convenience in the implementation rather than
> the problems with the approach. It's easier in the code to have fixed size
> scale and weight and to have them at the beginning of the data type,
which is
> fine for larger values but for small values they dominate and waste space.
>
> But as far as the approach goes, I admit I find it a bit hard to
believe that
> we're still doing BCD in the 21st century at all.
:D That's true in the first glance. But fact is, that, if the numbers
get bigger, it get's hard to implement certain algorithms properly while
on arbitrary format (read: decimal) these are tested and available. Not
mentioning that you would have to provide different algos for 4 byte/8
byte or weird 31bit machines.
Another reason to use bcd still is that errors (I don't mean real
errors, but imprecisions, overflow etc) occur where you expect them,
because humans in the Real World (tm) tend to use basis 10 for their
everyday numbers. And, after all, the ANSI754 imprecisions come exactly
from the unexpected occurence of roundings and internal number format
behaviour.
> If we stored the digits in base 2 with a base 10 exponent would it
really be
> too hard to output the digits? Even long multiplication and then
reversing the
> results doesn't seem like it would be too bad and surely there must exist
> reasonable algorithms to do better.
You should go with this, as it's just on-disk representation. Sorry if I
got you wrong on that, the focus of the decimal project goes more for
in-memory representation of arbitrary numbers and really calculate with
them, even implement this in hardware.
I would really welcome the above mentioned, also for big numbers, as it
would greatly decrease the amount of storage needed for huge amounts of
numerics (12 bytes for "10530" *is* somewhat unreasonable imho).

Anyway, your patch called my attention to this matter, so many thanks
already to that. Any improvement there would be really great :-) (tell
me if I can lend a hand)

Patric
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)
Comment: GnuPT 2.5.2

iD4DBQFF5klnfGgGu8y7ypARAh7lAKC3mdnsx08yf91Py/DDMAlCF8hDegCWMMFG
K4kBkAGX/cUp+dk7Ch+W5Q==
=BIHo
-----END PGP SIGNATURE-----

On Mar 1, 2007, at 12:32 , Patric Bechtel wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Gregory Stark schrieb am 01.03.2007 10:23:
>> "Patric Bechtel" <bechtel(at)ipcon(dot)de> writes:
>>
>>> Maybe you want to have a look here:
>>> http://www2.hursley.ibm.com/decimal/DPDecimal.html

Speaking of decimal encodings, does anyone know if DPD is patent-
encumbered? I believe Chen-Ho is patented (on which DPD was
apparently based), though the patent may have expired.

Michael Glaesemann
grzm seespotcode net

Michael Glaesemann schrieb am 01.03.2007 12:41:
>
> On Mar 1, 2007, at 12:32 , Patric Bechtel wrote:
>
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Gregory Stark schrieb am 01.03.2007 10:23:
>>> "Patric Bechtel" <bechtel(at)ipcon(dot)de> writes:
>>>
>>>> Maybe you want to have a look here:
>>>> http://www2.hursley.ibm.com/decimal/DPDecimal.html
>
> Speaking of decimal encodings, does anyone know if DPD is
patent-encumbered? I believe Chen-Ho is patented (on which DPD was
apparently based), though the patent may have expired.
>
> Michael Glaesemann
> grzm seespotcode net
It's covered by the ICU license (very liberal, I'm no lawyer, but AFAICT
BSD compatible), so I don't think it's patented. There are ready
implementations for it for GCC etc. And an ANSI/IEEE proposal is made
for it, too. So no, I think no patents so far.

Patric

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> If we stored the digits in base 2 with a base 10 exponent would it really be
> too hard to output the digits?

Exact decimal fractions are no longer exact when converted to base 2.

regards, tom lane

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Tom Lane schrieb am 02.03.2007 14:38:
> Gregory Stark <stark(at)enterprisedb(dot)com> writes:
>> If we stored the digits in base 2 with a base 10 exponent would it really be
>> too hard to output the digits?
>
> Exact decimal fractions are no longer exact when converted to base 2.
>
> regards, tom lane
>
> ---------------------------(end of broadcast)---------------------------
> TIP 6: explain analyze is your friend
>

I think multiplying with base 10 until it's a whole number, then saving
that exponent with it, that's how I understood it.

Patric
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)
Comment: GnuPT 2.5.2

iD8DBQFF5833fGgGu8y7ypARAirsAKCen8BkMyW4cfkoqwEpGo3lThYrJACfWs8L
tnWKkJ/a9aQiO0YQls/YGHg=
=YNlB
-----END PGP SIGNATURE-----

Patric Bechtel <bechtel(at)ipcon(dot)de> writes:
> Tom Lane schrieb am 02.03.2007 14:38:
>> Exact decimal fractions are no longer exact when converted to base 2.

> I think multiplying with base 10 until it's a whole number, then saving
> that exponent with it, that's how I understood it.

That hardly seems likely to win in terms of calculation efficiency ---
for example, adding two numbers will now likely require a multiplication
in order to align the values for addition. Having to store the exponent
doesn't sound that great for the original complaint of too much overhead
for short numbers, either...

regards, tom lane

"Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Patric Bechtel <bechtel(at)ipcon(dot)de> writes:
>> Tom Lane schrieb am 02.03.2007 14:38:
>>> Exact decimal fractions are no longer exact when converted to base 2.
>
>> I think multiplying with base 10 until it's a whole number, then saving
>> that exponent with it, that's how I understood it.
>
> That hardly seems likely to win in terms of calculation efficiency ---
> for example, adding two numbers will now likely require a multiplication
> in order to align the values for addition. Having to store the exponent
> doesn't sound that great for the original complaint of too much overhead
> for short numbers, either...

Adding two numbers with two different exponents would require multiplying to
set the exponents equal.

a) normally you're adding together numbers of the same type so normally you'll
have the same precision.

b) It's only going to hurt for very large numbers where handling base-10^n
numbers is *so* bad that the argument kind of breaks down.

c) I was picturing storing the exponent relative to the decimal place instead
of relative to the first digit as we do now. That means numbers like 1x10^6
might take more space but numbers like 123456 would take less since we
could define a missing exponent to represent an exponent of 0.

Incidentally -- doing what I just castigated Jonah for doing -- I looked
around and both libgmp and the java math.BigDecimal libraries use base-2
digits. The latter with base-10 exponents no less.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Greg, do you want to submit a patch for this or add a TODO item for this?

---------------------------------------------------------------------------

Gregory Stark wrote:
>
> I've uploaded a quick hack to store numerics in < 8 bytes when possible.
>
> http://community.enterprisedb.com/numeric-hack-1.patch
>
> This is a bit of a kludge since it doesn't actually provide any interface for
> external clients of the numeric module to parse the resulting data. Ie, the
> macros in numeric.h will return garbage.
>
> But I'm not entirely convinced that matters. It's not like those macros were
> really useful to any other modules anyways since there was no way to extract
> the actual digits.
>
> The patch is also slightly unsatisfactory because as I discovered numbers like
> 1.1 are stored as two digits currently. But it does work and it does save a
> substantial amount of space for integers.
>
> postgres=# select n,pg_column_size(n) from n;
> n | pg_column_size
> ----------+----------------
> 1 | 2
> 11 | 2
> 101 | 2
> 1001 | 3
> 10001 | 9
> 100001 | 9
> 1.1 | 9
> 10.1 | 9
> 100.1 | 9
> 1000.1 | 9
> 10000.1 | 11
> 100000.1 | 11
>
> I had hoped to get the second batch to be 3-4 bytes. But even now note how
> much space is saved for integers <10000.
>
> --
> Gregory Stark
> EnterpriseDB http://www.enterprisedb.com
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/docs/faq

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

"Bruce Momjian" <bruce(at)momjian(dot)us> writes:

> Greg, do you want to submit a patch for this or add a TODO item for this?

Well I never got any approval or rejection in principle so I don't know if
such a patch would be accepted even if it were implemented reasonably. If it
has the consensus needed to be a TODO item I would go ahead and do it.

The main design issue is that I was proposing to make it impossible to access
the internals of the numeric storage using macros. Currently some of the data
(the sign, dscale, and weight) is visible without having to call any special
numeric functions. I was proposing to use representations where those might
not be as easily accessible.

However I don't think we have any consumers of that data outside of numeric.c
anyways. Is there anything using that functionality currently? Do we mind
losing it?

> ---------------------------------------------------------------------------
>
> Gregory Stark wrote:
>>
>> I've uploaded a quick hack to store numerics in < 8 bytes when possible.
>>
>> http://community.enterprisedb.com/numeric-hack-1.patch
>>
>> This is a bit of a kludge since it doesn't actually provide any interface for
>> external clients of the numeric module to parse the resulting data. Ie, the
>> macros in numeric.h will return garbage.
>>
>> But I'm not entirely convinced that matters. It's not like those macros were
>> really useful to any other modules anyways since there was no way to extract
>> the actual digits.
>>
>> The patch is also slightly unsatisfactory because as I discovered numbers like
>> 1.1 are stored as two digits currently. But it does work and it does save a
>> substantial amount of space for integers.
>>
>> postgres=# select n,pg_column_size(n) from n;
>> n | pg_column_size
>> ----------+----------------
>> 1 | 2
>> 11 | 2
>> 101 | 2
>> 1001 | 3
>> 10001 | 9
>> 100001 | 9
>> 1.1 | 9
>> 10.1 | 9
>> 100.1 | 9
>> 1000.1 | 9
>> 10000.1 | 11
>> 100000.1 | 11
>>
>> I had hoped to get the second batch to be 3-4 bytes. But even now note how
>> much space is saved for integers <10000.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Gregory Stark wrote:
> The main design issue is that I was proposing to make it impossible to access
> the internals of the numeric storage using macros. Currently some of the data
> (the sign, dscale, and weight) is visible without having to call any special
> numeric functions. I was proposing to use representations where those might
> not be as easily accessible.
>
> However I don't think we have any consumers of that data outside of numeric.c
> anyways. Is there anything using that functionality currently? Do we mind
> losing it?

The data would still be available through a function, right? If there's
no-one accessing that information currently, there's no
backwards-compatibility issue. I think this is a non-issue.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com