Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

pgm.di.unipi.it

Post reply on HN
Print view View original

91–100 of 124 posts

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

#91

Post by gvinciguerra »

BenoitP wrote: post #46
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…

Thank you for your work! Are there current efforts in your research going in mainstream RDBMS (say postgres)? The space improvements are so great columns could just be indexed by default.

Thank you so much for your interest, BenoitP!

Right now I'm focusing more on the design of compressed data structures. RDBMS are complex systems, and gaining sufficient knowledge of their internals would require several months of work. Though, it would wonderful for me to collaborate with some RDBMS engineers to integrate my current research efforts in their system.

Actually, some time ago, we asked a bachelor's student at the University of Pisa to integrate the PGM-index in Redis (which is simpler than an RDBMS). He did it, and the results were really promising, -3x overall memory usage with respect to Redis ZSETs.

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

#93

Post by byteshift »

crazypython wrote: post #75

This is interesting. Could this be adapted to store 2D data, like how a quadtree is a 2D range tree? (If you link me to a paper / pseudocode for that, I could implement it.) I imagine it would be useful in GIS, gaming, etc.

We index geospatial data using a learned index in this work (cf. Section 3): http://cidrdb.org/cidr2021/papers/cidr2021_paper19.pdf

Code: https://github.com/learnedsystems/RadixSpline

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

#94

Post by eloff »

MadVikingGod wrote: post #69
kreeben wrote: post #63

Earlier quoted context omitted.

I'm almost good at math. Could you enlighten me, when you say "slope", are you talking about the slope of a line as defined by "The Equation of a Straight line" [0], i.e. the "m" in "y=mx+b"? And what do you mean by "intercept". Are you referring to the "b" in that same equation? If that's true, in what way is that an optimization to storing "x" and "y" at each node? [0] https://www.mathsisfun.com/equation_of_line.ht…

In a traditional tree you just store a bunch of y's. So let's say 7 points are just y0-y6. In a tree you would need at least 7 keys stored. In this you would just have m and b stored and you would use the formula to look up the index.

Thanks, that really helps get an intuition for how this works! It's pretty clever really.

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

#95

Post by RMarcus »

crazypython wrote: post #75

This is interesting. Could this be adapted to store 2D data, like how a quadtree is a 2D range tree? (If you link me to a paper / pseudocode for that, I could implement it.) I imagine it would be useful in GIS, gaming, etc.

Check out work by Jialin Ding and Vikram Nathan, they both work on multi-dimensional learned index structures.

https://arxiv.org/pdf/2006.13282.pdf

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

#96

Post by RMarcus »

whyuselearning wrote: post #24

Why use learning when you can fit? http://databasearchitects.blogspot.com/2019/05/why-use-learn...

We produced a detailed comparison of such "fitting" and "learning" techniques, available here: https://vldb.org/pvldb/vol14/p1-marcus.pdf

(Thomas Neumann, one of authors of the blog post, is a co-author of the linked paper)

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

#97

Post by eloff »

ncmncm wrote: post #42
zupa-hu wrote: post #37

Earlier quoted context omitted.

Of course it begs the question: if the keys are sorted, what do we need an index for? A simple halfing method would trivially do it then with btree like performance and infinitely better index size (0). Maybe they may have made an improvement here trading some space for even better lookup times? In that case, the 83x space over btree indexes is certainly possible - given that infinite improvement is possible too.

Binary search is quite slow on modern hardware, particularly for this use, where you would need to fault in a page for each probe. With a billion records that is 30 probes. They get much better than log2(n). This is a lot like how you look up words in the dictionary. It is roughly radix-like, but the closer you get, the better the fit. If you are looking up a word that starts with S, you adjust to how broad S is as y…

This is on in memory data. So binary search would seem reasonable except that you can't do inserts, updates, or deletes efficiently in an ordered array. That inevitably leads to using a btree or trie structure.

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

#98

Post by jeffbee »

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…

An interesting case in which Google trolled people into action by publishing a purely hypothetical paper for which there's no evidence they intended to put it into actual practice.

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

#99

Post by thesz »

gvinciguerra wrote: post #79
thesz wrote: post #72

Their slides https://pgm.di.unipi.it/slides-pgm-index-vldb.pdf about PGM index, page 21. They stop at page size of 1024 bytes - that indicates they are tested in-memory situation. And, which is worse, their compression ratio advantage almost halves when block size is doubled. Thus, what about B-tree with blocks of 16K or even 256K? Also, what about log-structured merge trees where bigger levels can use bigger pages a…

Hi @thesz! The experiment you are referring to is done in main memory with an optimised in-memory B+tree implementation. We didn't plot the performance for larger page sizes because in our machine they performed poorly, as you can already see from the configuration with 1024-byte pages. So we're not favouring our approach at all. Note also that next-gen memories have smaller and smaller access granularities. For exam…

These blocks of 256 bytes most probably are stored in wear-leveling database of some sort hidden inside NVME. These databases are often LSM-tree-based. So, writing larger blocks still has benefits, especially when you use compression.

If you think you only need 256 byte pages, average price for 10G hard disk drive is ~$300 [1] and average price for 2G SSD drive is also ~$300 [2].

[1] https://pcpartpicker.com/trends/internal-hard-drive/?__cf_ch...

[2] https://pcpartpicker.com/trends/internal-hard-drive/?__cf_ch...

Five times price/Gb difference. If you need large storage, you need hard disks.

B-trees are good with hard disks, is PGM index good with them too?

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

#100

Post by jandrewrogers »

AlphaSite wrote: post #10
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.

Isn’t sorting required for range based indexes?

Not necessarily. If you have indexing structures for data types that do not have a total order, only a partial order, you can store and do an indexed range search on data types that do have a total order. The primary implication is that the output of the range search will not reflect the total order in the way it would for a traditional B+Tree.
Post reply on HN