stoianmihail / plex

PLEX: Towards Practical Learned Indexing

PLEX: Towards Practical Learned Indexing

PLEX only has a single hyperparameter ϵ (maximum prediction error) and offers a better trade-off between build and lookup time than state-of-the-art approaches.

Build

mkdir -p build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make
./example

Examples

Using ts::Builder to index sorted data:

// Create random keys.
std::vector<uint64_t> keys(1e6);
generate(keys.begin(), keys.end(), rand);
keys.push_back(424242);
std::sort(keys.begin(), keys.end());

// Build PLEX
uint64_t min = keys.front();
uint64_t max = keys.back();
ts::Builder tsb(min, max, keys.size());

for (const auto& key : keys) tsb.AddKey(key);
auto ts = tsb.Finalize();

// Search using PLEX
ts::SearchBound bound = ts.GetSearchBound(424242);
std::cout << "The search key is in the range: ["
			<< bound.begin << ", " << bound.end << ")" << std::endl;
auto start = std::begin(keys) + bound.begin, last = std::begin(keys) + bound.end;
auto pos = std::lower_bound(start, last, 424242) - begin(keys);
assert(keys[pos] == 424242);
std::cout << "The key is at position: " << pos << std::endl;

Cite

Please cite our AIDB@VLDB 2021 paper if you use this code in your own work.

plex's Issues

Array Out of Bounds in TrieSpline finalize

I haven't spent too much time looking into the root cause of this, but I suspect it's a simple off-by-one error somewhere within the ComputeCHTStatistics method in ts/builder.h.

When building a TrieSpline over perfectly sequential data (i.e., one single spline perfectly covers the key range), occasionally the value of alreadyCommon will be one larger than the value of the returned by ComputeLcp, resulting in the lcp vector containing {4294967295, 4294967295}. This causes an massive out of range array access on line 314, when the values in lcp are used as indexes into counter.

counters[lcp[index]]++;

This doesn't happen for every possible interval, but I've provided a reproducer below which consistently produces the problem.

int main (int argc, char **argv) {
    size_t n = 4097;
    auto bldr = ts::builder<size_t>(436712, 440808, 1024);

    for (size_t i=436712; i<n + 436712; i++) {
        bldr.addkey(i);
    }

    auto ts = bldr.finalize();
}

Typically, the range interval sizes that cause these seem to be one off from a power of two (4097, 1023, etc.), but that's just anecdotal. I haven't looked into this much beyond determining it wasn't a problem in my code!