[zupa-hu]

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 cases.

Did I misunderstand?

[gvinciguerra]

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....

[zupa-hu]

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.)

[zupa-hu]

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.

[ncmncm]

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 you home in.

[eloff]

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.

[ncmncm]

"In-memory" doesn't mean so much as it once did. Faulting a page into cache from RAM takes hundreds or even thousands of cycles. Same for faulting an index page, if the whole index doesn't fit in cache.

A B-tree replaces a log2(N) binary search of the whole range into a K-ary search, with log-base-K(N) probes; but adds searches through the K keys per tree node, which all have to be brought into cache.

Even once the K keys have been brought into cache, a binary search in the index page is quite slow on modern hardware because the iterations involve randomly mispredicted branches.

A great advantage of PGM indexes seems to be that the whole index can be held in (L3) cache. Faulting a line from L3 to L1 cache takes only ~30 cycles. Once the index has been walked, you are close to the desired record and can walk forward or back a few steps to locate it.

If you have to handle insertions, it is often better to keep an overflow table searched first (or last) so you can batch-rebuild during downtime. Deletions may be handled by marking dead entries, and updates are easy. Most multigigabyte tables don't see much churn, relative to their size.

[zupa-hu]

Thanks, that's a very good point!