Earlier quoted context omitted.
It failed to attract customers and was sold at a fire sale. (I was an investor.)
I was a happy customer!
That makes you part of a very exclusive club :-(
PGM Indexes: Learned indexes that match B-tree performance with 83x less space
101–110 of 124 posts
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#102Earlier quoted context omitted.
Isn’t sorting required for range based indexes?
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.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#103Earlier quoted context omitted.
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/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).
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#104And here I was thinking probabilistic graphical models were finally getting the spotlight :)
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#105Many devs are probably familiar with perfect hashes as the gperf tool seems omnipresent on Linux machines. Is this a related concept? The learning part makes me suspect so but the slopes and interpolation part makes me doubt it.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#106Earlier quoted context omitted.
The paper says 83x, and even makes stronger claims that are fairly unqualified: In short, the experimental achievements of the PGM-index are: (i) better space occupancy than the FITing-tree by up to 75% and than the CSS-tree by a factor 83×, with the same or better query time; (ii) uniform improvement of the performance of RMI in terms of query time and space occupancy, and 15× faster construction, while requiring no…
Have you examined the results presented in section 7? They take pains to qualify these claims. If you are curious, the authors have provided completely reproducible experiments.
I didn't say that these specific claims are simply false. Just that they sure seem to hint at extraordinary improvements in a broad range of cases. The website itself also seems to me to be suggestive in just the same way, only much more so.
I myself don't think that that amounts to taking pains to qualify their claims. Other people will have to make their own minds up about whether or not that's the case.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#107Earlier quoted context omitted.
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.
"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.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#108Earlier 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…
> What is the reason behind us not having deployed massive amounts of search indices into the world that were built using this method?
There are a lot of other strategies for segmented data indexes. Many of which are roughly equivalent to this in practice. For example, using a computed strategy for distributing data among various nodes on a server. In such a situation, a master node can run a computation on an indexed value to identify the node(s) in the cluster which contain the data and send a query request to only the nodes containing that information.
I would think the biggest drawback to this particular strategy is, often times, you need to analyze the data in the index to get an answer anyway. So it's not really beneficial to throw away the index data. For example, if the indexed field is a timestamp, and the result set is often sorted on that field, then it makes total sense to keep the index values and use that to perform sorting while a separate thread fetches the data needed to flesh out the query.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#109Their 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…
Are you aware of any contemporary on-disk or in memory DB system that typically uses a page size of 4KiB or less? And if not, are you expecting that to become a trend in the future?
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#110Earlier 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…
It is, arguably, deployed at scale, if you squint and call it delta compression. The reason its not more widely used is there are drawbacks. Updates can be more expensive, for instance: what was a single-key change perhaps blew up a 1000 key "line" and now all those keys need reshuffling. You also see more muted returns because generally keys in indexes point to something, so compressing the keys creates complexity in how you map each key to its value or reference. Compared to a solution that stores keys close to their values, a solution that packs keys together gets poor cache locality for resolving the values, and may need mapping tables.
Basically, delta compression is used all over the place, but it isnt a silver bullet.