Re: Store hashes of objects in BTrees instead of objects?

--000000000000e1e60f05c69cda66
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

As noted elsewhere, this would be problematic because:

- Hash collisions
- Loss of range searches.

(Unstable hashes could be mitigated using a custom hash function, at least
for selected types.)

A better approach, IMO, would be to build a scalable persistent hash table
on top of BTrees. Use a BTree to maintain the hash table.  The BTree values
could either be hash buckets containing keys with the same hash mapped to
their values, or target values in the common case of no collisions.

Jim

On Tue, Jul 6, 2021 at 8:43 PM =C3=89loi Rivard <[email protected]> wrote:

> Hello,
> The BTrees documentation
> <https://btrees.readthedocs.io/en/latest/overview.html#related-data-struc=
tures>
> tells us that :
>
> *There are variants of the data structures specialized to numbers, which
> are faster and more memory efficient than those dealing with objects.*
>
> Also Jason Madden did some benchmarking
> <https://github.com/zopefoundation/BTrees/issues/100#issuecomment-5182012=
10>
> to illustrate this.
>
> I just realized that, at least on my system, python hashes are less than
> 64bits long so they can fit as LOBTree keys.
>
> >>> from BTrees.LOBTree import LOBTree
> >>> h =3D hash("whatever")
> >>> h.bit_length()
> 63
>
> >>> t =3D LOBTree()
> >>> t[h] =3D "anything"
> >>> t[h]
> 'anything'
>
> I was wondering if there are drawbacks to systematically using hashes of
> strings as LOBTree keys, instead of those whole strings as OOBTree keys.
>
> What do you think?
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "zodb" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/zodb/5762150c-6e0a-4104-b2bb-f0b476c26a=
9en%40googlegroups.com
> <https://groups.google.com/d/msgid/zodb/5762150c-6e0a-4104-b2bb-f0b476c26=
a9en%40googlegroups.com?utm_medium=3Demail&utm_source=3Dfooter>
> .
>

--=20
You received this message because you are subscribed to the Google Groups "=
zodb" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to [email protected].
To view this discussion on the web visit https://groups.google.com/d/msgid/=
zodb/CAPDm-Fic0%3DoaFGdhJGFbqb%3D5SKO_d4iMtUME23%3Dtrpa1PhMvzg%40mail.gmail=
.com.

--000000000000e1e60f05c69cda66
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>As noted elsewhere, this would be problematic because=
:</div><div><br></div><div>- Hash collisions</div><div>- Loss of range sear=
ches.</div><div><br></div><div>(Unstable hashes could be mitigated using a =
custom hash function, at least for selected types.)</div><div><br></div><di=
v>A better approach, IMO, would be to build a scalable persistent hash tabl=
e on top of BTrees. Use a BTree to maintain the hash table.=C2=A0 The BTree=
 values could either be hash buckets containing keys with the same hash map=
ped to their values, or target values in the common case of no collisions.<=
/div><div><br></div><div>Jim<br></div></div><br><div class=3D"gmail_quote">=
<div dir=3D"ltr" class=3D"gmail_attr">On Tue, Jul 6, 2021 at 8:43 PM =C3=89=
loi Rivard &lt;<a href=3D"mailto:[email protected]">[email protected]</a>&gt;=
 wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>Hel=
lo,</div><div>The <a href=3D"https://btrees.readthedocs.io/en/latest/overvi=
ew.html#related-data-structures" target=3D"_blank">BTrees documentation</a>=
 tells us that :<br></div><div><br></div><div><i>There are variants of the =
data structures specialized to
numbers, which are faster and more memory efficient than those dealing
with objects.</i></div><div><br></div><div>Also Jason Madden <a href=3D"htt=
ps://github.com/zopefoundation/BTrees/issues/100#issuecomment-518201210" ta=
rget=3D"_blank">did some benchmarking</a> to illustrate this.</div><div><br=
></div><div>I just realized that, at least on my system, python hashes are =
less than 64bits long so they can fit as LOBTree keys.</div><div><br></div>=
<div>&gt;&gt;&gt; from BTrees.LOBTree import LOBTree<br>&gt;&gt;&gt; h =3D =
hash(&quot;whatever&quot;)<br>&gt;&gt;&gt; h.bit_length()<br>63<br><br>&gt;=
&gt;&gt; t =3D LOBTree()<br>&gt;&gt;&gt; t[h] =3D &quot;anything&quot;</div=
><div>&gt;&gt;&gt; t[h]</div><div>&#39;anything&#39;</div><div><br></div><d=
iv>I was wondering if there are drawbacks to systematically using hashes of=
 strings as LOBTree keys, instead of those whole strings as OOBTree keys. <=
br></div><div><br></div><div>What do you think?<br></div><div><br></div><di=
v><br></div>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;zodb&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:[email protected]" target=3D"_bla=
nk">[email protected]</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/zodb/5762150c-6e0a-4104-b2bb-f0b476c26a9en%40googlegroups.com?ut=
m_medium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank">https://groups.=
google.com/d/msgid/zodb/5762150c-6e0a-4104-b2bb-f0b476c26a9en%40googlegroup=
s.com</a>.<br>
</blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;zodb&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:[email protected]">zodb+unsubscri=
[email protected]</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/zodb/CAPDm-Fic0%3DoaFGdhJGFbqb%3D5SKO_d4iMtUME23%3Dtrpa1PhMvzg%4=
0mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.goog=
le.com/d/msgid/zodb/CAPDm-Fic0%3DoaFGdhJGFbqb%3D5SKO_d4iMtUME23%3Dtrpa1PhMv=
zg%40mail.gmail.com</a>.<br />

--000000000000e1e60f05c69cda66--