PGM Indexes: Learned indexes that match B-tree performance with 83x less space • Hacker News Board

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#51

Post by contravariant » Mon, Jan 25, 2021, 11:20 AM UTC

legulere wrote: post #2

In the example they sort the data array. Does that mean this works just on sorted arrays? Insert and delete performance would be horrible I guess.

In the full paper they quote a rather interesting method [1] that allows you to insert values in amortized O(log(n)) time (deletes are apparently handled with tombstones, presumably rebuilding the whole thing when a sufficiently large proportion is deleted).

A very abridged explanation of how they handle inserts: you split the collection in a list of collections where position k contains either nothing or a collection size 2^k. When you want to add a new value you find the first empty spot and fill it by building a set of your new value together with the collections of all the preceding spots (because the sizes are all sequential powers of two this will fit exactly). Provided that merging the collections takes linear time this takes an amortized O(log(n)) per inserted item.

Of course once you have this you can use it for any learned index that can be learned in linear time.

[1]: M. H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer, 1983.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#52

Post by foolmeonce » Mon, Jan 25, 2021, 11:26 AM UTC

joe_the_user wrote: post #19

I don't get it. I've implemented B-trees. The majority of space the used by a B-tree is the data itself. Each N-ary leaf of the tree is a basically a vector of data with maybe some bookkeeping at the ends. The leaves are more than half of the tree. Sure, you can compress the data. But that depends on the data, completely random data can't be compress. Other data can be. But a point blank 83x space claim seems bizarre…

> completely random data can't be compress

Given that a normal B-Tree can't retrieve the original order, it must be more compressible than random data and a representation that would let you represent a wrong order has invalid sequences, so it must be less space efficient than one that would use those sequences to mean something valid.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#53

Post by ComodoHacker » Mon, Jan 25, 2021, 11:30 AM UTC

gvinciguerra wrote: post #43

Hello everyone. I'm Giorgio, the co-author of the PGM-index paper together with Paolo Ferragina. First of all, I'd like to thank @hbrundage for sharing our work here and also all those interested in it. I'll do my best to answer any doubt in this thread. Also, I'd like to mention two other related papers: - "Why are learned indexes so effective?" presented at ICML 20, and co-authored with Paolo Ferragina and Fabrizio…

Can PGM index and linear approximation models in general be applied to clustered indexes, where actual data of variable size are stored in the index along with the keys?

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#54

Post by gvinciguerra » Mon, Jan 25, 2021, 11:33 AM UTC

jabberwcky wrote: post #20

Only watched the video, was disappointed by https://youtu.be/gCKJ29RaggU?t=408 , where they are comparing against tiny b*tree page sizes that nothing uses any more - 4k, 16k and 64k are way more common

Hi @jabberwcky! The plot refers to a B+tree implementation optimised for main-memory (https://panthema.net/2007/stx-btree/). We didn't show the performance for larger/smaller page sizes because in our machine they performed poorly. Indeed, you can see from the figure that the fastest B+tree configuration had page size set to 512 bytes. The one using 1024-byte pages is already much slower, that's why we didn't clutter the plot with page sizes larger than 1k ;)

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#55

Post by gvinciguerra » Mon, Jan 25, 2021, 11:43 AM UTC

zupa-hu wrote: post #34

The slides: https://pgm.di.unipi.it/slides-pgm-index-vldb.pdf It seems they are only talking about compressing the index (keys) not the values. Also, the slides seem to imply the keys need to be set in sorted order? That way their memory locations will be in increasing order too. That’s quite an important limitation, that means the index is read-only in practice once populated. Though it may still be useful in some c…

Hi @zupa-hu!

In the paper we focused on indexing keys, as the compression of keys and values is an orthogonal problem. For example, you can compress disk pages containing keys and values with a method of your choice, and then use the PGM-index to efficiently locate the page containing the query key.

For what concerns insertion and deletions (in non-sorted order), they are discussed in Section 3 "Dynamic PGM-index" and experimented in Section 7.3. The implementation is available at https://github.com/gvinciguerra/PGM-index/blob/master/includ... and the documentation at https://pgm.di.unipi.it/docs/cpp-reference/#classpgm_1_1_dyn....

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#56

Post by mr_gibbins » Mon, Jan 25, 2021, 12:01 PM UTC

gvinciguerra wrote: post #54

jabberwcky wrote: post #20

Only watched the video, was disappointed by https://youtu.be/gCKJ29RaggU?t=408 , where they are comparing against tiny b*tree page sizes that nothing uses any more - 4k, 16k and 64k are way more common

Hi @jabberwcky! The plot refers to a B+tree implementation optimised for main-memory ( https://panthema.net/2007/stx-btree/ ). We didn't show the performance for larger/smaller page sizes because in our machine they performed poorly. Indeed, you can see from the figure that the fastest B+tree configuration had page size set to 512 bytes. The one using 1024-byte pages is already much slower, that's why we didn't clutt…

This sounds like a great advancement, however an implementation in RDBMS products may be some way away yet - MSSQL uses 8KB pages by default, and I believe (without checking) that most other RDBMSes use at least 4KB. B+ tree index implementations on RDBMS products may be here to stay for a while yet unless these performance issues can be minimised, or unless there is a paradigm shift to use smaller pages - which would have a knock-on effect to query performance unrelated to indexes, such as number of page lookups, increased I/O for non-contiguous page reads...

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#57

Post by dmos62 » Mon, Jan 25, 2021, 12:09 PM UTC

I've only heard of B-trees in passing. In what kinds of situations are these data structures used?

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#58

Post by dboreham » Mon, Jan 25, 2021, 12:39 PM UTC

xucheng wrote: post #28

joe_the_user wrote: post #19

I don't get it. I've implemented B-trees. The majority of space the used by a B-tree is the data itself. Each N-ary leaf of the tree is a basically a vector of data with maybe some bookkeeping at the ends. The leaves are more than half of the tree. Sure, you can compress the data. But that depends on the data, completely random data can't be compress. Other data can be. But a point blank 83x space claim seems bizarre…

The size comparison here only concerns the size of index. That is the size of the data is excluded.

Parent means the size of the key data present in the index, I suspect. In a B-tree every byte of every key value is present.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#59

Post by jokoon » Mon, Jan 25, 2021, 12:41 PM UTC

I've already thought about the idea of making statistics to optimize access time, so I guess this a viable implementation to do it correctly.

That's pretty amazing... I can somehow imagine this tech landing on every modern computer, allowing users to search for anything that is on their machine.

Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space

#60

Post by danbruc » Mon, Jan 25, 2021, 12:41 PM UTC

jltsiren wrote: post #26

Some context: A few years ago, there was a paper from Google ( https://dl.acm.org/doi/10.1145/3183713.3196909 ) that made learned data structures popular for a while. They started from the idea that indexes such as B-trees approximate an increasing function with one-sided error. By using that perspective and allowing two-sided error, they were able to make the index very small (and consequently quite fast). Many data…

Only having skimmed the work, read the following as a somewhat educated guess.

I think one could see this similar to repeated applications of interpolation search. If you are looking for x in a sorted array of n numbers between a and b, then index (x - a) / (b - a) * (n - 1) would be a good guess assuming uniform distribution of the numbers.

But as one can not assume a uniform distribution in general, one does that repeatedly. The first interpolation leads to better interpolation coefficients for the relevant subrange, which may lead to even better interpolation coefficient for an even smaller subrange until one eventually finds what one was looking for.

If there is no structure in the data that can be exploited, this degenerates into a more or less ordinary tree as we one certainly fit a line through two points, but if at some level a larger range of the data can be well approximated with the interpolation function, then it can save space and search time because one can get close to all the values in the range with only one set of interpolation coefficients and only one interpolation.