From 06eaf7232e9a920468c0f8d74dcf2fe8b555501c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 13 Apr 2024 14:24:36 +0200 Subject: Adding upstream version 1:10.11.6. Signed-off-by: Daniel Baumann --- storage/rocksdb/rocksdb-range-access.txt | 292 +++++++++++++++++++++++++++++++ 1 file changed, 292 insertions(+) create mode 100644 storage/rocksdb/rocksdb-range-access.txt (limited to 'storage/rocksdb/rocksdb-range-access.txt') diff --git a/storage/rocksdb/rocksdb-range-access.txt b/storage/rocksdb/rocksdb-range-access.txt new file mode 100644 index 00000000..6b5a0db9 --- /dev/null +++ b/storage/rocksdb/rocksdb-range-access.txt @@ -0,0 +1,292 @@ + +This file describes how MySQL index navigation commands are translated into +RocksDB index navigation commands. + +Index tuples are shown as + + ( kv )-aaa-pkN + +here + * '(kv)' is the 4-byte index number. + * '-' is just for readability + * everything that follows the '-' is mem-comparable form of the key. + In ascii encoding, aaa < bbb < ccc < xxx. + +Tuples that start with '#' do not exist in the database. They are only shown +to demonstrate where Seek() calls end up with. + +== HA_READ_KEY_EXACT, forward CF == + + (kv-1)-xxx-pk +# ( kv )-aaa <-- "kv-aaa" doesn't exist in the database, but it would be + here. + ( kv )-aaa-pk <--- Seek("kv-aaa") will put us here on the next record. + ( kv )-aaa-pk2 + ( kv )-bbb-... + +RocksDB calls: + + it->Seek(kv); + if (it->Valid() && kd->covers_key(..) && kd->cmp_full_keys(...)) + return record. + +== HA_READ_KEY_EXACT, backward CF == + +When we need to seek to a tuple that is a prefix of a full key: + + (kv+1)-xxx-pk + ( kv )-ccc-pk + ( kv )-bbb-pk3 + ( kv )-bbb-pk2 + ( kv )-bbb-pk1 <--- SeekForPrev("kv-bbb") will put us here on the previous + record. +# ( kv )-bbb <--- "kv-bbb" doesn't exist in the database, but it would be + ( kv )-aaa-pk here. + +Even when (kv)-bbb-pk1 is the last record in the CF, SeekForPrev() will find the +last record before "kv-bbb", so it already takes care of this case for us. + +RocksDB calls: + + it->SeekForPrev(kv); + if (it->Valid() && kd->covers_key(..) && kd->cmp_full_keys(...)) + return record. + +== HA_READ_KEY_OR_NEXT, forward CF == + +This is finding min(key) such that key >= lookup_tuple. + +If lookup tuple is kv-bbb: + + ( kv )-aaa-pk +# ( kv )-bbb <-- "kv-bbb" doesn't exist in the database, but it would be + here. + ( kv )-bbb-pk1 <--- Seek("kv-bbb") will put us here on the next record. + ( kv )-bbb-pk2 + ( kv )-bbb-... + +RocksDB calls: + + Seek(kv); + if (it->Valid() && kd->covers_key(..)) + return record. + +== HA_READ_KEY_OR_NEXT, backward CF == + +When specified key tuple is a key prefix: + + (kv+1)-xxx-pk + ( kv )-ccc-pk + ( kv )-bbb-pk3 + ( kv )-bbb-pk2 + ( kv )-bbb-pk1 <--- Seek("kv-bbb") will put us here on the previous record. +# ( kv )-bbb <--- "kv-bbb" doesn't exist in the database, but it would be + here. + ( kv )-aaa-pk + +Even when (kv)-bbb-pk1 is the last record in the CF, SeekForPrev() will find the +last record before "kv-bbb", so it already takes care of this case for us. + +Another kind of special case is when we need to seek to the full value. +Suppose, the lookup tuple is kv-bbb-pk1: + + (kv+1)-xxx-pk + ( kv )-ccc-pk + ( kv )-bbb-pk3 + ( kv )-bbb-pk2 + ( kv )-bbb-pk1 < -- SeekForPrev(kv-bbb-pk1) + ( kv )-bbb-pk0 + +Then, SeekForPrev(kv-bbb-pk1) may position us exactly at the tuple we need. +Even If kv-bbb-pk1 is not present in the database, we will be positioned on +kv-bbb-pk2 no matter whether kv-bbb-pk2 is the last key or not. + +RocksDB calls: + + SeekForPrev(...); + if (it->Valid() && kd->covers_key(..)) + return record. + +== HA_READ_AFTER_KEY, forward CF == + +This is finding min(key) such that key > lookup_key. + +Suppose lookup_key = kv-bbb + + ( kv )-aaa-pk +# ( kv )-bbb + ( kv )-bbb-pk1 <--- Seek("kv-bbb") will put us here. We need to + ( kv )-bbb-pk2 get to the value that is next after 'bbb'. + ( kv )-bbb-pk3 + ( kv )-bbb-pk4 + ( kv )-bbb-pk5 + ( kv )-ccc-pkN <--- That is, we need to be here. + +However, we don't know that the next value is kv-ccc. Instead, we seek to the +first value that strictly greater than 'kv-bbb'. It is Successor(kv-bbb). + +It doesn't matter if we're using a full extended key or not. + +RocksDB calls: + + Seek(Successor(kv-bbb)); + if (it->Valid() && kd->covers_key(...)) + return record; + +Note that the code is the same as with HA_READ_KEY_OR_NEXT, except that +we seek to Successor($lookup_key) instead of $lookup_key itself. + +== HA_READ_AFTER_KEY, backward CF == + +Suppose, the lookup key is 'kv-bbb': + + (kv+1)-xxx-pk + ( kv )-ccc-pk7 + ( kv )-ccc-pk6 <-- We get here when we call Seek(Successor(kv-bbb)) +# Successor(kv-bbb) + ( kv )-bbb-pk5 + ( kv )-bbb-pk4 + ( kv )-bbb-pk3 + ( kv )-bbb-pk2 + ( kv )-bbb-pk1 +# ( kv )-bbb <-- We would get here if we called SeekForPrev(kv-bbb). + ( kv )-aaa-pk + +RocksDB calls: + + SeekForPrev(Successor(kv-bbb)); + if (it->Valid() && kd->covers_key(...)) + return record. + +Note that the code is the same as with HA_READ_KEY_OR_NEXT, except that +we seek to Successor($lookup_key) instead of $lookup_key itself. + +== HA_READ_BEFORE_KEY, forward CF == + +This is finding max(key) such that key < lookup_tuple. + +Suppose, lookup_tuple=kv-bbb. + + ( kv )-aaa-pk1 + ( kv )-aaa-pk2 + ( kv )-aaa-pk3 <-- SeekForPrev("kv-bbb") will put us here. +# ( kv )-bbb + ( kv )-bbb-pk4 + ( kv )-bbb-pk5 + ( kv )-bbb-pk6 + +If the lookup tuple is a full key (e.g. kv-bbb-pk3), and the key is present in +the database, the iterator will be positioned on the key. We will need to call +Prev() to get the next key. + +RocksDB calls: + + it->SeekForPrev(kv-bbb); + if (it->Valid() && using_full_key && + kd->value_matches_prefix(...)) + { + /* We are using full key and we've hit an exact match */ + it->Prev(); + } + + if (it->Valid() && kd->covers_key(...)) + return record; + +== HA_READ_BEFORE_KEY, backward CF == + +This is finding max(key) such that key < lookup_tuple. +Suppose, lookup_tuple=kv-bbb, a prefix of the full key. + + ( kv )-bbb-pk6 + ( kv )-bbb-pk5 + ( kv )-bbb-pk4 +# ( kv )-bbb + ( kv )-aaa-pk3 <-- Need to be here, and Seek("kv-bbb") will put us here + ( kv )-aaa-pk2 + ( kv )-aaa-pk1 + +If the lookup tuple is a full key (e.g. kv-bbb-pk4), and the key is present in +the database, the iterator will be positioned on the key. We will need to call +Next() to get the next key. + +RocksDB calls: + + it->Seek(kv-bbb); + if (it->Valid() && using_full_key && + kd->value_matches_prefix(...)) + { + /* We are using full key and we've hit an exact match */ + it->Next(); + } + + if (it->Valid() && kd->covers_key(...)) + return record; + +== HA_READ_PREFIX_LAST, forward CF == + +Find the last record with the specified index prefix lookup_tuple. + +Suppose, lookup_tuple='kv-bbb' + + ( kv )-aaa-pk2 + ( kv )-aaa-pk3 +# ( kv )-bbb + ( kv )-bbb-pk4 + ( kv )-bbb-pk5 + ( kv )-bbb-pk6 + ( kv )-bbb-pk7 <--- SeekForPrev(Successor(kv-bbb)) will get us here +# ( kv )-ccc + ( kv )-ccc-pk8 + ( kv )-ccc-pk9 + +RocksDB calls: + + SeekForPrev(Successor(kv-bbb)); + if (using_full_key && it->Valid() && !cmp_full_keys(Sucessor(lookup_key))) + it->Prev(); + if (it->Valid() && kd->covers_key(...)) + { + if (!cmp_full_keys(lookup_tuple)) // not needed in _OR_PREV + { + // the record's prefix matches lookup_tuple. + return record; + } + } + +== HA_READ_PREFIX_LAST, backward CF == + +Suppose, lookup_tuple='kv-bbb' + + ( kv )-ccc-pk9 + ( kv )-ccc-pk8 +# ( kv )-ccc <-- 2. Seek(Successor(kv-bbb)) will point here + and it will fall down to the next row. + ( kv )-bbb-pk7 <--- 1. Need to be here. + ( kv )-bbb-pk6 + ( kv )-bbb-pk5 + ( kv )-bbb-pk4 +# ( kv )-bbb + ( kv )-aaa-pk3 + ( kv )-aaa-pk2 + + +RocksDB calls: + + it->Seek(Successor(kv-bbb)); + + if (using_full_key && it->Valid() && !cmp_full_keys(Sucessor(lookup_key))) + it->Next(); + + if (it->Valid() && kd->covers_key(..)) + { + if (!cmp_full_keys(...)) // not needed in _OR_PREV + { + // the record's prefix matches lookup_tuple. + return record; + } + } + +== HA_READ_PREFIX_LAST_OR_PREV, forward or backward CF == + +This is just like HA_READ_PREFIX_LAST but we don't need to check that the key +we've got is in the search prefix. (search for "not needed in _OR_PREV" above) -- cgit v1.2.3