Reminds me of TokuDB. What happened to it?
PGM Indexes: Learned indexes that match B-tree performance with 83x less space
11–20 of 124 posts
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#12In 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.
Skimming the paper it appears so. B-trees also require sorted data.
B-trees don't need sorted data. The B-tree insertion algorithm performs the sorting for you.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#13Any Postgres implementation of this yet?
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#14Earlier quoted context omitted.
Skimming the paper it appears so. B-trees also require sorted data.
B-trees don't need sorted data. The B-tree insertion algorithm performs the sorting for you.
B-trees need sortable data; GP is not saying that the data has to be pre-sorted, but that it can't be unorderable or otherwise uncomparable.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#15Any 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.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#16Reminds me of TokuDB. What happened to it?
It failed to attract customers and was sold at a fire sale. (I was an investor.)
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#17Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#18They should have chosen another name, the acronym PGM already stands for Probabilistic Graphical Model and they overlap in possible usages.
You mean like they had to call the bug planet in Starship Troopers “Planet P” because all the other names in the universe had been taken?
I thought it was called Klendathu
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#19I 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 - or it's comparing to a very inefficient implementation of a B-tree.
Edit: It seems the 83x claim is a product of the HN submission. I could not find it on the page. But even the page should say something like "a compressed index that allows full speed look-up" (akin to succinct data structures) and then it would make sense.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#20Only 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