BasicKV::PrefixLookup: I notice the founction may return one KV pair. it is designing for that or a bug?

zz-jason / leanstore

LeanStore is a larger-than-memory database, optimized for NVMe SSD and multi-core CPU, achieves performance close to in-memory systems without having to keep all data in memory.

MIT License

22 stars 2 forks source link

BasicKV::PrefixLookup: I notice the founction may return one KV pair. it is designing for that or a bug? #133

Open SYaoJun opened 4 days ago

SYaoJun commented 4 days ago

expection

if I insert five pairs: "hello": 1, "hey": 2, "hi": 3, "holy":4,
"haha": 5

the prefixlookup("he") should return 2 kv pairs: "hello": 1, "hey": 2, but the current code maybe return one kv pair, or return all the ascscan KV pairs.

code

zz-jason commented 4 days ago

It's a bug, BasicKv hasn't been fully tested. Would you like to fix this issue?

SYaoJun commented 4 days ago

yes, I can follow the BasicKV::ScanAsc() function, which use a pessimistic method. Actually, I want to fix it based on optimistic method. But I don't know how to handle the situation when a leaf node need move to their neighbor leaf

zz-jason commented 4 days ago

When latch conflict happens (the page being scanned is modified by others at the same time), an optimistic scan needs to:

retry from the beginning (or retry scanning from the upper bound key of the last unchanged page)
clear all the previously scanned and buffered key values

The current API sends each scanned key value to a custom callback, which makes the retry hard to implement. The easiest way to correctly implement ScanDesc or ScanAsc is to use a pessimistic shared iterator.