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

111–120 of 124 posts

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

#111

Post by thesz »

gvinciguerra wrote: post #103
thesz wrote: post #99

Earlier quoted context omitted.

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/i…

From a Big-Oh point of view, the answer is a big yes. No matter the memory technology or the disk page size, be it 256B or 16KB, the PGM-index can scale as B-trees or even better (see my comment here https://news.ycombinator.com/item?id=25901889 ).

Can you provide us with (preferably drop-in) replacement of LMDB as a proof?

Because your big-O looks like big-O of cache-oblivious algorithm and I saw no proof of that.

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

#112

Post by AnbeSivam »

jandrewrogers wrote: post #102
YesThatTom2 wrote: post #61

Earlier quoted context omitted.

Same question. Can you give me an example of an indexing scheme that works on non-sortable data? I can’t think of any.

The canonical example is indexing rectangles. They have no total order. It is far from the only example. Any data type where equality and intersection are not equivalent test functions will effectively be non-sortable. There are many indexing schemes for data with these properties. They focus on topological relationships rather than order relationships.

Do you know of any blog/papers which talks about this - using topology for such interval data types.

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

#113

Post by zupa-hu »

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…

Thanks, that's a very good point!

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

#114

Post by virattara »

virattara wrote: post #47
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…

Does Savitch's theorem apply here? If yes then you can have a strict bound in section 7.1.

Did I say something wrong?

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

#115

Post by zupa-hu »

gvinciguerra wrote: post #55
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" an…

Hi @gvinciguerra, thanks for your reply!

I mainly stated your solution is about the size of the index and not the values because others comments at the time questioned if it's possible at all. I wanted to add my bits trying to decipher what this is. :)

I have implemented a custom index myself so I'm really interested in this stuff but I have to admit I don't understand the language used to explain it. I'm not sure who the audience is. If it's not only targeted at researchers but also random programmers out there, maybe consider adding either an ELI5 translation to things or more proof that it's worth investing time in this (eg. learning your lingo). For example, by adding performance charts. I totally missed that.

Wow, looking at it again, I now see you have some charts at the bottom of your slides. I'm pretty sure 99% of your visitors did not find it. And even so, I'm not quite sure I understand those charts.

My 2 cents:

1) Simplify them. Don't pack so much info in a single chart. This prevents me from getting to the AHA moment. Maybe show them on separate tabs.

2) Move this chart/these charts to the top of your home page. I knew this is about an index before landing on your site, so when I landed, I had exactly 1 question in my mind: Should I care? Your homepages did not answer that. I found links to papers which I don't even open as I believe they are huge time investment and I want to first figure out if I should invest more time. I was happy about the slides because slides are about selling the big ideas. It was better than the home page but in the end I left not having my only question answered. I saved the link. I will probably remember to look at it again when I have special requirements for an index. But I'm not motivated to invest more time right now, I'll keep reading my book in the mornings instead of your paper.

(I'm sharing this so you can improve the site if you want.)

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

#116

Post by gvinciguerra »

virattara wrote: post #114
virattara wrote: post #47

Earlier quoted context omitted.

Does Savitch's theorem apply here? If yes then you can have a strict bound in section 7.1.

Did I say something wrong?

Not at all @virattara ;)

I don't have an answer right now, I just need to think about it more deeply

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

#118

Post by ddorian43 »

ldng wrote: post #65
ddorian43 wrote: post #38

Earlier quoted context omitted.

There are a lot of fixes PostgreSQL can do before this exotic one. Starting from ZHeap etc etc.

ZHeap a fix ? A different data management option, yes. A fix, no.

In the sense of lowering per-row-overhead, supposed to be faster on commit and slower on rollback(usual workloads).

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

#119

Post by Traudl »

petergeoghegan wrote: post #15
saurabhnanda wrote: post #13

Any Postgres implementation of this yet?

Not likely. I have done a lot of work on B-Tree indexing in Postgres in the past several years, and this is all Greek to me.

It looks like it found its way into Google Bigtable though: https://arxiv.org/abs/2012.12501

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

#120

Post by gvinciguerra »

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.

Hi @crazypython and thank you! Yep, I just added an implementation of the multidimensional PGM-index in the main repo. If you want to improve it, you are more than welcome. Drop me an email if you have some ideas. Thanks again!
Post reply on HN