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

81–90 of 124 posts

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

#81

Post by gvinciguerra »

mr_gibbins wrote: post #56
gvinciguerra wrote: post #54

Earlier quoted context omitted.

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 woul…

Thank you @mr_gibbins.

I think an implementation in RDBMS is worth exploring. After all, the page size of the PGM-index can be tuned to match the one of the media you are storing your data to (or to match the default setting of the RDBMS).

About the paradigm shift to use smaller pages, it's worth mentioning technological innovations like the Intel's Optane DC Persistent Memory, in which the access granularity is 256 bytes. I expect that similar products will be available in the near future and that new/updated RDBMS implementations will take advantage of them.

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

#82

Post by hansvm »

xucheng wrote: post #30
hansvm wrote: post #23

Earlier quoted context omitted.

Not only is there a rough order, they explicitly require the ability to meaningfully embed data into the reals, and the performance gains come from assuming those embeddings have simple delta distributions. I wouldn't be surprised if the technique is worse than useless when that assumption is violated. Edit: I don't have time right now, but a toy example I like to throw at these kinds of problems is mapping primes to…

Due to the prime number theorem, your toy example actually has a very good approximated mapping.

Kind of. Appropriately normalizing the primes with some kind of function based on log(log(n)) would probably allow the article's technique to perform well (still struggling on larger primes -- you can't avoid needing a lot of bits to express those gaps), but it's precisely the shifting density which makes the problem hard to learn with any standard algorithm, and I don't think theirs would be an exception since they explicitly rely on gaps drawn from some fixed distribution.

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

#83

Post by claytonjy »

ddorian43 wrote: post #38
gigatexal wrote: post #27

Any chance it will make its way to Postgres?

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

Can custom index types be packaged into an extension, or would implementing this require deeper integration?

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

#84

Post by Out_of_Characte »

danbruc wrote: post #60
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 r…

Isn't it sometimes better to assume data has a structure rather than having less performance but knowing it works equally well with unstructured semi-random data?

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

#85

Post by gvinciguerra »

kreeben wrote: post #68
giovannibonetti wrote: post #64

Earlier quoted context omitted.

As parent said, it is a piecewise linear interpolation, which means it is divided into line segments. Hence you don't need the parameters for the whole index, only for each segment, as the parameters are the same for each point in the same segment.

"piecewise linear interpolation" After having linearly interpolated the points on the curve piecewise, instead of a smooth curve, you now have line segments that connect to other line segments, each point now connected to the next, not smoothly, but linearly, and each of those lines/segments can be optimized by storing only slope and intercept. Yes? That seems both ingenious and very, very straight-forward. What is t…

Hi @kreeben, the construction is very fast, it can be done in linear time with a single scan of the data. Just to give you some figures, we constructed a PGM-index on 10^12 key-value pairs (8 bytes + 8 bytes) loaded in main memory in less than 3 seconds.

About the information that we store, we prefer to say "piecewise linear approximation" because the line segments do not necessarily connect points, and they are not connected to each other. The guarantee of the piecewise linear approx is that each line segment is far from the input points by at most a user-given integer ε. With this guarantee, when we compute the approximate position p of a given query key q, we can always find the true position of q after a fast binary search in the range of positions [p-ε,p+ε].

The piecewise linear model is nothing more than a list of triples (key,slope,intercept). The key is needed because we need to know where a segment starts and where the previous one ends. The slope and the intercept are exactly as you said, the parameters that let us compute the approximate position via p = slope * q + intercept.

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

#86

Post by gpderetta »

magicalhippo wrote: post #48
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…

I enjoyed glossing over the paper (will read it properly after work), but it was not immediately obvious to me how to implement this for strings. I'm no expert in this area, so this might have an obvious answer. I mean I guess you could treat characters as base 2^32 or something like that and convert a string to a real that way, but often strings have a non-trivial sort orders.

If you do not need to do similarity searches, indexing over the (fixed size and numeric, possibly cryptographic) hash of the string might work.

edit: but that will map to an uniform range, making interpolation trivial. As this solution can be used for any type, I'm probably missing something. The index discussed in the paper can probably be used for range queries (which hashing would prevent), not just punctual searches.

edit: bah, I'm just reinventing an hash map.

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

#88

Post by gvinciguerra »

Gh0stRAT wrote: post #80
gvinciguerra wrote: post #70

Earlier quoted context omitted.

You are right, variable-length strings are difficult. You could try to pack as many characters as possible in a computer word (or in a big int data type), say P characters, and then use the PGM-index to find the strings that share a prefix of P chars with the given query string. I discussed this solution in a GitHub issue ( https://github.com/gvinciguerra/PGM-index/issues/8#issuecomm... ). It may work in practice, bu…

Hi Giorgio, thanks for sharing! You mentioned that tries have had recent advancements, could you please point me to a paper about these advancements so I can learn more? I did a quick Google search but wasn't able to find anything that seemed relevant.

Hi @Gh0stRAT, you are very welcome! For prefix search on strings, I recommend the classic String B-tree paper (https://dl.acm.org/doi/10.1145/301970.301973). Among recent results, there's the c-trie++ paper (https://arxiv.org/pdf/1904.07467.pdf) and the papers mentioned in their Related Work section.

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

#90

Post by danbruc »

Out_of_Characte wrote: post #84
danbruc wrote: post #60

Earlier quoted context omitted.

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 r…

Isn't it sometimes better to assume data has a structure rather than having less performance but knowing it works equally well with unstructured semi-random data?

But if you are inventing or implementing a general purpose data structure, then you can not assume any structure by definition, especially not when it comes to worst case performance. On the other hand you can certainly include special handling of common special cases that will improve the performance or even come up with special data structures that only work under specific circumstances but then outperform general purpose solutions. As always it is a trade-off, here between generality and performance.
Post reply on HN