Thread: 64-bit hash function for hstore and citext data type
Hi all, Commit[1] has added 64-bit hash functions for core data types and in the same discussion thread[2] Robert Haas suggested to have the similar extended hash function for hstore and citext data type. Attaching patch proposes the same. Regards, Amul 1] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=81c5e46c490e2426db243eada186995da5bb0ba7 2] http://postgr.es/m/CA+Tgmoafx2yoJuhCQQOL5CocEi-w_uG4S2xT0EtgiJnPGcHW3g@mail.gmail.com
Attachment
On 2018/09/26 11:20, amul sul wrote: > Hi all, > > Commit[1] has added 64-bit hash functions for core data types and in the same > discussion thread[2] Robert Haas suggested to have the similar extended hash > function for hstore and citext data type. Attaching patch proposes the same. > > Regards, > Amul > > 1] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=81c5e46c490e2426db243eada186995da5bb0ba7 > 2] http://postgr.es/m/CA+Tgmoafx2yoJuhCQQOL5CocEi-w_uG4S2xT0EtgiJnPGcHW3g@mail.gmail.com > I reviewed citext-add-extended-hash-function-v1.patch and hstore-add-extended-hash-function-v1.patch. I could patch and test them without trouble and could not find any issues. I think both patches are well. Best regards,
On Wed, Nov 21, 2018 at 10:34 AM Hironobu SUZUKI <hironobu@interdb.jp> wrote: > > On 2018/09/26 11:20, amul sul wrote: > > Hi all, > > > > Commit[1] has added 64-bit hash functions for core data types and in the same > > discussion thread[2] Robert Haas suggested to have the similar extended hash > > function for hstore and citext data type. Attaching patch proposes the same. > > > > Regards, > > Amul > > > > 1] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=81c5e46c490e2426db243eada186995da5bb0ba7 > > 2] http://postgr.es/m/CA+Tgmoafx2yoJuhCQQOL5CocEi-w_uG4S2xT0EtgiJnPGcHW3g@mail.gmail.com > > > > > I reviewed citext-add-extended-hash-function-v1.patch and > hstore-add-extended-hash-function-v1.patch. > > I could patch and test them without trouble and could not find any issues. > Thanks to looking at the patch. Regards, Amul
On 9/26/18 12:20 PM, amul sul wrote: > Hi all, > > Commit[1] has added 64-bit hash functions for core data types and in the same > discussion thread[2] Robert Haas suggested to have the similar extended hash > function for hstore and citext data type. Attaching patch proposes the same. > I wonder if the hstore hash function is actually correct. I see it pretty much just computes hash on the varlena representation. The important question is - can there be two different encodings for the same hstore value? If that's possible, those two versions would end up with a different hash value, breaking the hashing scheme. I'm not very familiar with hstore internals so I don't know if that's actually possible, but if you look at hstore_cmp, that seems to be far more complex than just comparing the varlena values directly. regards -- Tomas Vondra http://www.2ndQuadrant.com PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>>>>> "Tomas" == Tomas Vondra <tomas.vondra@2ndquadrant.com> writes: Tomas> I wonder if the hstore hash function is actually correct. I see Tomas> it pretty much just computes hash on the varlena representation. Tomas> The important question is - can there be two different encodings Tomas> for the same hstore value? I was going to say "no", but in fact on closer examination there is an edge case caused by the fact that hstoreUpgrade allows an _empty_ hstore from pg_upgraded 8.4 data through without modifying it. (There's also a vanishingly unlikely case involving the pgfoundry release of hstore-new.) I'm inclined to fix this in hstoreUpgrade rather than complicate hstore_hash with historical trivia. Also there have been no field complaints - I guess it's unlikely that there is much pg 8.4 hstore data in the wild that anyone wants to hash. -- Andrew (irc:RhodiumToad)
Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
> "Tomas" == Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> Tomas> The important question is - can there be two different encodings
> Tomas> for the same hstore value?
> I was going to say "no", but in fact on closer examination there is an
> edge case caused by the fact that hstoreUpgrade allows an _empty_ hstore
> from pg_upgraded 8.4 data through without modifying it. (There's also a
> vanishingly unlikely case involving the pgfoundry release of hstore-new.)
Ugh. Still, that's a pre-existing problem in hstore_hash, and so I don't
think it's a blocker for this patch.
> I'm inclined to fix this in hstoreUpgrade rather than complicate
> hstore_hash with historical trivia. Also there have been no field
> complaints - I guess it's unlikely that there is much pg 8.4 hstore data
> in the wild that anyone wants to hash.
Changing hstoreUpgrade at this point seems like wasted/misguided effort.
I don't doubt that there was a lot of 8.4 hstore data out there, but how
much remains unmigrated? If we're going to take this seriously at all,
my inclination would be to change hstore_hash[_extended] to test for
the empty-hstore case and force the same value it gets for such an
hstore made today.
In the meantime, I went ahead and pushed these patches. The only
non-cosmetic changes I made were to remove the changes in
citext--unpackaged--1.0.sql/hstore--unpackaged--1.0.sql; those
were wrong, because the point of those files is to migrate pre-9.1
databases into the extension system. Such a database would not
contain an extended hash function, and so adding an ALTER EXTENSION
command for that function would cause the script to fail.
regards, tom lane
I wrote:
> Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
>> I'm inclined to fix this in hstoreUpgrade rather than complicate
>> hstore_hash with historical trivia. Also there have been no field
>> complaints - I guess it's unlikely that there is much pg 8.4 hstore data
>> in the wild that anyone wants to hash.
> Changing hstoreUpgrade at this point seems like wasted/misguided effort.
Oh, cancel that --- I was having a momentary brain fade about how that
function is used. I agree your proposal is sensible.
regards, tom lane
>>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes: >>> I'm inclined to fix this in hstoreUpgrade rather than complicate >>> hstore_hash with historical trivia. Also there have been no field >>> complaints - I guess it's unlikely that there is much pg 8.4 hstore >>> data in the wild that anyone wants to hash. >> Changing hstoreUpgrade at this point seems like wasted/misguided effort. Tom> Oh, cancel that --- I was having a momentary brain fade about how Tom> that function is used. I agree your proposal is sensible. Here's what I have queued up to push: -- Andrew (irc:RhodiumToad) From d5890f49da6a77b1325a3f5822c6b092a2cd41ae Mon Sep 17 00:00:00 2001 From: Andrew Gierth <rhodiumtoad@postgresql.org> Date: Sat, 24 Nov 2018 09:59:49 +0000 Subject: [PATCH] Fix hstore hash function for empty hstores upgraded from 8.4. Hstore data generated on pg 8.4 and pg_upgraded to current versions remains in its original on-disk format unless modified. The same goes for values generated by the addon hstore-new module on pre-9.0 versions. (The hstoreUpgrade function converts old values on the fly when read in, but the on-disk value is not modified by this.) Since old-format empty hstores (and hstore-new hstores) have representations compatible with the new format, hstoreUpgrade thought it could get away without modifying such values; but this breaks hstore_hash (and the new hstore_hash_extended) which assumes bit-perfect matching between semantically identical hstore values. Only one bit actually differs (the "new version" flag in the count field) but that of course is enough to break the hash. Fix by making hstoreUpgrade unconditionally convert all old values to new format. Backpatch all the way, even though this changes a hash value in some cases, because in those cases the hash value is already failing - for example, a hash join between old- and new-format empty hstores will be failing to match, or a hash index on an hstore column containing an old-format empty value will be failing to find the value since it will be searching for a hash derived from a new-format datum. (There are no known field reports of this happening, probably because hashing of hstores has only been useful in limited circumstances and there probably isn't much upgraded data being used this way.) Per concerns arising from discussion of commit eb6f29141be. Original bug is my fault. Discussion: https://postgr.es/m/60b1fd3b-7332-40f0-7e7f-f2f04f777747%402ndquadrant.com --- contrib/hstore/hstore_compat.c | 47 +++++++++++++++++------------------------- 1 file changed, 19 insertions(+), 28 deletions(-) diff --git a/contrib/hstore/hstore_compat.c b/contrib/hstore/hstore_compat.c index b95ce9b4aa..1d4e7484e4 100644 --- a/contrib/hstore/hstore_compat.c +++ b/contrib/hstore/hstore_compat.c @@ -238,34 +238,35 @@ hstoreUpgrade(Datum orig) HStore *hs = (HStore *) PG_DETOAST_DATUM(orig); int valid_new; int valid_old; - bool writable; /* Return immediately if no conversion needed */ - if ((hs->size_ & HS_FLAG_NEWVERSION) || - hs->size_ == 0 || + if (hs->size_ & HS_FLAG_NEWVERSION) + return hs; + + /* Do we have a writable copy? If not, make one. */ + if ((void *) hs == (void *) DatumGetPointer(orig)) + hs = (HStore *) PG_DETOAST_DATUM_COPY(orig); + + if (hs->size_ == 0 || (VARSIZE(hs) < 32768 && HSE_ISFIRST((ARRPTR(hs)[0])))) + { + HS_SETCOUNT(hs, HS_COUNT(hs)); + HS_FIXSIZE(hs, HS_COUNT(hs)); return hs; + } valid_new = hstoreValidNewFormat(hs); valid_old = hstoreValidOldFormat(hs); - /* Do we have a writable copy? */ - writable = ((void *) hs != (void *) DatumGetPointer(orig)); if (!valid_old || hs->size_ == 0) { if (valid_new) { /* - * force the "new version" flag and the correct varlena length, - * but only if we have a writable copy already (which we almost - * always will, since short new-format values won't come through - * here) + * force the "new version" flag and the correct varlena length. */ - if (writable) - { - HS_SETCOUNT(hs, HS_COUNT(hs)); - HS_FIXSIZE(hs, HS_COUNT(hs)); - } + HS_SETCOUNT(hs, HS_COUNT(hs)); + HS_FIXSIZE(hs, HS_COUNT(hs)); return hs; } else @@ -302,15 +303,10 @@ hstoreUpgrade(Datum orig) elog(WARNING, "ambiguous hstore value resolved as hstore-new"); /* - * force the "new version" flag and the correct varlena length, but - * only if we have a writable copy already (which we almost always - * will, since short new-format values won't come through here) + * force the "new version" flag and the correct varlena length. */ - if (writable) - { - HS_SETCOUNT(hs, HS_COUNT(hs)); - HS_FIXSIZE(hs, HS_COUNT(hs)); - } + HS_SETCOUNT(hs, HS_COUNT(hs)); + HS_FIXSIZE(hs, HS_COUNT(hs)); return hs; #else elog(WARNING, "ambiguous hstore value resolved as hstore-old"); @@ -318,13 +314,8 @@ hstoreUpgrade(Datum orig) } /* - * must have an old-style value. Overwrite it in place as a new-style one, - * making sure we have a writable copy first. + * must have an old-style value. Overwrite it in place as a new-style one. */ - - if (!writable) - hs = (HStore *) PG_DETOAST_DATUM_COPY(orig); - { int count = hs->size_; HEntry *new_entries = ARRPTR(hs); -- 2.11.1
Thanks Tom for enhancing & committing these patches. Regards, Amul On Sat, Nov 24, 2018 at 12:15 AM Tom Lane <tgl@sss.pgh.pa.us> wrote: > > Andrew Gierth <andrew@tao11.riddles.org.uk> writes: > > "Tomas" == Tomas Vondra <tomas.vondra@2ndquadrant.com> writes: > > Tomas> The important question is - can there be two different encodings > > Tomas> for the same hstore value? > > > I was going to say "no", but in fact on closer examination there is an > > edge case caused by the fact that hstoreUpgrade allows an _empty_ hstore > > from pg_upgraded 8.4 data through without modifying it. (There's also a > > vanishingly unlikely case involving the pgfoundry release of hstore-new.) > > Ugh. Still, that's a pre-existing problem in hstore_hash, and so I don't > think it's a blocker for this patch. > > > I'm inclined to fix this in hstoreUpgrade rather than complicate > > hstore_hash with historical trivia. Also there have been no field > > complaints - I guess it's unlikely that there is much pg 8.4 hstore data > > in the wild that anyone wants to hash. > > Changing hstoreUpgrade at this point seems like wasted/misguided effort. > I don't doubt that there was a lot of 8.4 hstore data out there, but how > much remains unmigrated? If we're going to take this seriously at all, > my inclination would be to change hstore_hash[_extended] to test for > the empty-hstore case and force the same value it gets for such an > hstore made today. > > In the meantime, I went ahead and pushed these patches. The only > non-cosmetic changes I made were to remove the changes in > citext--unpackaged--1.0.sql/hstore--unpackaged--1.0.sql; those > were wrong, because the point of those files is to migrate pre-9.1 > databases into the extension system. Such a database would not > contain an extended hash function, and so adding an ALTER EXTENSION > command for that function would cause the script to fail. > > regards, tom lane