Hi @magicalhippo and @midjji. Please, have a look at the main repo, I just uploaded an implementation of the multidimensional PGM-index supporting orthogonal range searches ;)
86 karma · joined January 25, 2021
I don't have an answer right now, I just need to think about it more deeply
Right now I'm focusing more on the design of compressed data structures. RDBMS are complex systems, and gaining sufficient knowledge of their internals would require several months of work. Though, it would wonderful for me to collaborate with some RDBMS engineers to integrate my current research efforts in their system.
Actually, some time ago, we asked a bachelor's student at the University of Pisa to integrate the PGM-index in Redis (which is simpler than an RDBMS). He did it, and the results were really promising, -3x overall memory usage with respect to Redis ZSETs.
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.
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.
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 example, the Intel's Optane DC Persistent Memory accesses blocks of 256 bytes, while the Intel's Optane DC SSD accesses blocks of 4 KB. I guess that data structures with blocks of 16K-256K are disproportionate in these cases.
About LSM-trees, nothing prevents you to use a PGM-index (which you can construct during the compaction of levels, thus without scanning data twice) to speed up the search on a long immutable level. Or also, to use a PGM-index on data which is organised into RLE-compressed disk pages ;)
You may find interesting these other papers of ours:
- The ALENEX21 paper "A 'learned' approach to quicken and compress rank/select dictionaries" (http://pages.di.unipi.it/vinciguerra/publication/learned-ran..., https://github.com/gvinciguerra/la_vector), where we introduce a compressed bitvector supporting efficient rank and select queries, which is competitive with several well-established implementations of succinct data structures.
- The ICML20 paper "Why are learned indexes so effective?" (http://pages.di.unipi.it/vinciguerra/publication/learned-ind...) where we prove that, under some general assumptions on the input data, the space of the PGM-index is actually O(n/B^2) whp (versus Θ(n/B) of classic B-trees).
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....
The worst-case bounds are discussed in *Section 2.2* and *Theorem 1*. Essentially, we have the following bounds:
Query: O(log_c(m) log_2(ε/B)) I/Os Space of the index: O(m)
where: n = number of input keys B = disk page size ε = user-given maximum error of the piecewise linear approximation (determines how many keys you need to search at each level) m = number of segments in the piecewise linear approximation c = fan out of the data structure (differently from standard B-trees it is not fixed, and it is potentially large)
Intuitively, the query complexity comes from the fact that the PGM-index has O(log_c(m)) levels, and at each level you do a binary search that costs O(log_2(ε/B)) I/Os.
Note that m and c depend on the "linearity" of the given input data. For example, if the input data can be approximated by a few segments, i.e. if m=O(1), and you choose ε=Θ(B), then the PGM-index takes O(1) space and answer queries in O(1) I/Os!
In general, you can remove the dependence from m and c if you can prove a lower bound on the length of a segment (i.e. the number of keys it "covers"), irrespective of the input data. We proved that the length of a single segment is at least 2ε (thus c≥2ε), or equivalently, that the number of segments m is upper bounded by n/(2ε) [Lemma 2, the proof is very straightforward]. Again, if you choose ε=Θ(B), then you have the following (rather pessimistic) worst-case bounds:
Query: O(log_B(n)) I/Os Space of the index: O(n/B)
Basically, these bounds tell you that the PGM-index is *never* worse in time and in space complexity than a B-tree!
---
However, in our experiments, the performance of the PGM-index was better than what the above bounds show, and this motivated us to study what happens when you make some (general) assumptions on the input data. The results of this study are in the ICML20 paper "Why are learned indexes so effective?" (http://pages.di.unipi.it/vinciguerra/publication/learned-ind...).
We found that, if you assume that the gaps between input sorted keys are taken from a distribution with finite mean and variance, then you can prove (Corollary 2 of the ICML20 paper) that the space of the PGM-index is actually O(n/B^2) whp (versus Θ(n/B) of classic B-trees).
Note that the result applies to *any* distribution, as long as the mean and variance of the RVs modelling the gaps are finite. Indeed, we specialised our main result to some well-known distributions, such as Uniform, Lognormal, Pareto, Exponential, and Gamma (Corollary 1 of the paper).
Yep, the example of Figure 2 shows only a static PGM-index on a sorted array.
Insertion and deletions are discussed in Section 3 "Dynamic PGM-index" and experimented in Section 7.3.
The Dynamic PGM-index is open-source too: you can find the implementation 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...
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 Lillo.
PDF, slides and video: http://pages.di.unipi.it/vinciguerra/publication/learned-ind...
TL;DR: In the VLDB 20 paper, we proved a (rather pessimistic) statement that "the PGM-index has the same worst-case query and space bounds of B-trees". Here, we show that actually, under some general assumptions on the input data, the PGM-index improves the space bounds of B-trees from O(n/B) to O(n/B^2) with high probability, where B is the disk page size.
- "A 'learned' approach to quicken and compress rank/select dictionaries" presented at ALENEX 21, and co-authored with Antonio Boffa and Paolo Ferragina.
PDF and code: http://pages.di.unipi.it/vinciguerra/publication/learned-ran...
TL;DR: You can use piecewise linear approximations to compress not only the index but the data too! We present a compressed bitvector/container supporting efficient rank and select queries, which is competitive with several well-established implementations of succinct data structures.