Thread: 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@ipcon.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@ipcon.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@ipcon.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@ipcon.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@enterprisedb.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@enterprisedb.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@ipcon.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@sss.pgh.pa.us> writes: > Patric Bechtel <bechtel@ipcon.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@momjian.us> http://momjian.us EnterpriseDB http://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. +
"Bruce Momjian" <bruce@momjian.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