BTrees! (was Re: Understanding loading mechanism)

--0000000000002052850582911208
Content-Type: text/plain; charset="UTF-8"

On Fri, Feb 22, 2019 at 9:30 PM Qiwen Chen <[email protected]> wrote:

> If I use IFBTree ( integer-keyed float-valued BTree) to store some time
> series data.
>

Interesting. What's the domain? Financial data? Scientific?

How does the loading work?
>

BTrees store data stored by key in such a way that only part of a tree
needs to be loaded into memory to fetch data for a subset of keys.
Similarly, if only a subset of keys (like 1) is modified, then only a
subset of the BTree is modified and stored.

See: https://en.wikipedia.org/wiki/B-tree

The leaves of the tree, where the data are stored are called buckets.
Internal tree nodes help find the right bucket for a key or key range.


> For example, if  l want to load the entire time series into memory, how
> many trips happen between the client and server?
>

That depends on the access pattern.  Assuming you iterated over the tree,
you would load roughly N/100 objects, where N is the number of values in
the tree.  (This is governed by a compile-time max bucket-size parameter,
which for IFBTrees, 120.)
Each load requires a round-trip.

Recently, we added a prefetch API that mitigates round trips (by
effectively doing them in parallel) if you know you're going to load
multiple objects.  This could conceivably leveraged when iterating over a
BTree.

Loading the entire tree into memory defeats one of the design goals, which
is to have trees that are much larger than application memory.  Sometimes,
when we want to iterate over trees that are larger than memory, we
periodically explicitly invoke garbage collection (normally invoked
implicitly at transaction boundaries) to free memory got leaves were done
with.

In the document, it says it uses lazy loading.  Does it mean each key value
> pair is loaded from the db to memory one at a time?
>

No, it means the minimum number of nodes (internal or bucket) are loaded to
retrieve a given key or key range.

The primary use case of BTrees is storing very large mappings where you
usually only want to access very small subsets of keys.

There's a feature of our implementation though that might be useful for
time series data, depending on the application.  I mentioned that BTrees
are trees of nodes with data in buckets at the leaves of the trees.  But
BTrees are *also* linked lists of buckets.  Each internal node has a
reference to it's first bucket and each bucket has a reference to the next
bucket in the tree.  This is to allow efficient iteration.

In the example above, to iterate over the entire tree, we only had to load
the top node and the buckets. We didn't have to load or traverse internal
nodes.

As always, picking and tuning data structures depends on application usage
(update and access) patterns, but I can imagine time-series applications
for which BTrees could work very well, especially with some compile-time
tuning (much larger bucket sizes and different storage types).

Early in my career I worked a lot with hydrologic time series data that was
collected over short fixed time intervals (5 or 15 minutes).  This data was
very expensive to store at the time (early eighties, when a 300MB disk was
the size of a dishwasher and wildly more expensive).  Storage of the data
was wildly important and the nature of this data allowed it to be very
compressible, typically 90-95%, which was an important factor in it's
storage.

(I could imagine a variation of BTrees for fixed-time-interval data that
avoided storing time values in buckets.)

Of course, storage is much cheaper now, but we store a lot more data.  The
same factors that made a custom storage format for time-series data
attractive in the 80s, makes columnar formats like Parquet and ORC popular
today.

(Hm, writing that made me wonder if it would be useful to have a BTree
variant that used Numpy/Arrow/xnd arrays to store bucket data.  Perhaps
memory-mapped...Hm....)

Jim

-- 
Jim Fulton
http://jimfulton.info

-- 
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].
For more options, visit https://groups.google.com/d/optout.

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

<div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr">On Fri, Feb 22, 2019 at =
9:30 PM Qiwen Chen &lt;<a href=3D"mailto:[email protected]">[email protected]=
</a>&gt; wrote:<br></div><div class=3D"gmail_quote"><blockquote class=3D"gm=
ail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,=
204,204);padding-left:1ex"><div dir=3D"ltr">If I use IFBTree ( integer-keye=
d float-valued BTree) to store some time series data.</div></blockquote><di=
v><br></div><div>Interesting. What&#39;s the domain? Financial data? Scient=
ific?<br></div><div><br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:=
1ex"><div dir=3D"ltr"> How does the loading work?</div></blockquote><div><b=
r></div><div>BTrees store data stored by key in such a way that only part o=
f a tree needs to be loaded into memory to fetch data for a subset of keys.=
=C2=A0 Similarly, if only a subset of keys (like 1) is modified, then only =
a subset of the BTree is modified and stored.</div><div><br></div><div>See:=
=C2=A0<a href=3D"https://en.wikipedia.org/wiki/B-tree">https://en.wikipedia=
.org/wiki/B-tree</a></div><div><br></div><div>The leaves of the tree, where=
 the data are stored are called buckets. Internal tree nodes help find the =
right bucket for a key or key range.</div><div>=C2=A0</div><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid r=
gb(204,204,204);padding-left:1ex"><div dir=3D"ltr"> For example, if =C2=A0l=
 want to load the entire time series into memory, how many trips happen bet=
ween the client and server?</div></blockquote><div><br></div><div>That depe=
nds on the access pattern.=C2=A0 Assuming you iterated over the tree,=C2=A0=
 you would load roughly N/100 objects, where N is the number of values in t=
he tree.=C2=A0 (This is governed by a compile-time max bucket-size paramete=
r, which for IFBTrees, 120.)=C2=A0=C2=A0</div><div>Each load requires a rou=
nd-trip.=C2=A0=C2=A0</div><div><br></div><div>Recently, we added a prefetch=
 API that mitigates round trips (by effectively doing them in parallel) if =
you know you&#39;re going to load multiple objects.=C2=A0 This could concei=
vably leveraged when iterating over a BTree.</div><div><br></div><div>Loadi=
ng the entire tree into memory defeats one of the design goals, which is to=
 have trees that are much larger than application memory.=C2=A0 Sometimes, =
when we want to iterate over trees that are larger than memory, we periodic=
ally explicitly invoke garbage collection (normally invoked implicitly at t=
ransaction boundaries) to free memory got leaves were done with.</div><div>=
<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8=
ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr=
"> In the document, it says it uses lazy loading.=C2=A0 Does it mean each k=
ey value pair is loaded from the db to memory one at a time?</div></blockqu=
ote><div><br></div><div>No, it means the minimum number of nodes (internal =
or bucket) are loaded to retrieve a given key or key range.</div><div><br><=
/div><div>The primary use case of BTrees is storing very large mappings whe=
re you usually only want to access very small subsets of keys.</div><div><b=
r></div><div>There&#39;s a feature of our implementation though that might =
be useful for time series data, depending on the application.=C2=A0 I menti=
oned that BTrees are trees of nodes with data in buckets at the leaves of t=
he trees.=C2=A0 But BTrees are <i>also</i> linked lists of buckets.=C2=A0 E=
ach internal node has a reference to it&#39;s first bucket and each bucket =
has a reference to the next bucket in the tree.=C2=A0 This is to allow effi=
cient iteration.=C2=A0</div><div><br></div><div>In the example above, to it=
erate over the entire tree, we only had to load the top node and the bucket=
s. We didn&#39;t have to load or traverse internal nodes.</div><div><br></d=
iv><div>As always, picking and tuning data structures depends on applicatio=
n usage (update and access) patterns, but I can imagine time-series applica=
tions for which BTrees could work very well, especially with some compile-t=
ime tuning (much larger bucket sizes and different storage types).</div><di=
v><br></div><div>Early in my career I worked a lot with hydrologic time ser=
ies data that was collected over short fixed time intervals (5 or 15 minute=
s).=C2=A0 This data was very expensive to store at the time (early eighties=
, when a 300MB disk was the size of a dishwasher and wildly more expensive)=
.=C2=A0 Storage of the data was wildly important and the nature of this dat=
a allowed it to be very compressible, typically 90-95%, which was an import=
ant factor in it&#39;s storage.</div><div><br></div><div>(I could imagine a=
 variation of BTrees for fixed-time-interval data that avoided storing time=
 values in buckets.)</div><div><br></div><div>Of course, storage is much ch=
eaper now, but we store a lot more data.=C2=A0 The same factors that made a=
 custom storage format for time-series data attractive in the 80s, makes co=
lumnar formats like Parquet and ORC popular today.</div><div><br></div><div=
>(Hm, writing that made me wonder if it would be useful to have a BTree var=
iant that used Numpy/Arrow/xnd arrays to store bucket data.=C2=A0 Perhaps m=
emory-mapped...Hm....)</div><div><br></div><div>Jim=C2=A0</div><div><br></d=
iv></div>-- <br><div dir=3D"ltr" class=3D"gmail_signature">Jim Fulton<br><a=
 href=3D"http://jimfulton.info" target=3D"_blank">http://jimfulton.info</a>=
<br></div></div></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 />
For more options, visit <a href=3D"https://groups.google.com/d/optout">http=
s://groups.google.com/d/optout</a>.<br />

--0000000000002052850582911208--