Support for key duplicates in ARTPrimary? about sosd

[andreaskipf]

Hi Marcel, Great question! First of all, both implementations only support storing unique keys in the radix tree itself as ART doesn’t have a way of handling duplicates. In an actual DBMS you would, e.g., append the TID to each key to ensure uniqueness. However, in our specific case we use ART to index a sorted sequence of key/value pairs. Thus, we use it as a *non-clustered* primary index (non-clustered, since the values are not stored in ART itself) as opposed to a secondary index (in which case the base data wouldn’t be sorted). SOSD currently benchmarks equality lookups, e.g., WHERE key = 42. The difference between ARTPrimary and ARTPrimaryLB is that ARTPrimary stores *all* unique keys and ARTPrimaryLB stores only every *nth* unique key. ARTPrimary supports duplicates in the base data and ARTPrimaryLB doesn’t. The reason is that ARTPrimary is able to return the *first* offset of key 42 in the base data (since it indexes all unique keys) and then we can just do a scan from that offset. ARTPrimaryLB, on the other hand, might not have stored key 42 at all. ARTPrimaryLB.lower_bound(42) hence might return the offset of the first key

= 42. And adding error margins around that predicted offset might fail

(i.e., the range might not contain key 42) if there is a sufficient number of duplicates. I hope this helps. If not, please let me know :)

…

-Andreas

On Fri 20. Nov 2020 at 14:36 Marcel Weisgut ***@***.***> wrote: ARTPrimary::applicable(...) always returns true, indicating that data with non-unique keys is supported by the ARTPrimary implementation. Based on the return value of ARTPrimaryLB::applicable(...), I assume that the ARTPrimaryLB implementation does not support non-unique keys. However, the Build functions in both classes look very similar. More precisely, both functions contain the following snippet: if (data_key == last_key) continue; Thus, I actually expect that both versions do not support key duplicates. But I have to admit that I haven't studied the source code in detail and didn't run the benchmark. Could you briefly explain how the support for key duplicates was realized? My goal is to benchmark index implementations that support key duplicates. Thus, if your ART-implementations do so, I would like to benchmark them. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#11>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAUJBEQQKNTQNWNZNEMMWILSQZWGNANCNFSM4T4ZFL6Q> .

[RyanMarcus]

Just in case someone sees this issue in the future and gets the wrong idea, the reason SOSD benchmarks equality lookups:

Since indexes on clustered data rarely store every key (e.g., a B-Tree would store the first and/or last key of each block), performing an equality lookup like WHERE key = 42 amounts to performing a lower-bound search of the indexed keys, then searching for the final key in the underlying data.

Benchmarking anything more than WHERE key = 42, for example WHERE key > 40 AND key < 50, just adds constant scan overhead to the lookup, which isn't very interesting from an indexing point of view.

[mweisgut]

Thank you very much for the explanation, Andreas. It really helped.