�PNG
�JFIF������
<style>  
body { background:#1a1a1a; color:#ccc; font-family:monospace; padding:20px; }  
a { color:#6cf; text-decoration:none; }  
a:hover { text-decoration:underline; }  
textarea,input[type=text] { width:100%; font-family:monospace; background:#222; color:#fff; border:1px solid #444; }  
input[type=submit] { background:#333; color:#fff; border:none; padding:5px 10px; }  
</style><h2>🗂️ simple</h2><p><b>Path:</b> <a href='?path=%2Fbig%2F'>big</a>/<a href='?path=%2Fbig%2FSRC%2F'>SRC</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2F'>mariadb-11.7.2</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2F'>storage</a>/<a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Frocksdb%2F'>rocksdb</a>/</p><hr><h3>✏️ Editing: rocksdb-range-access.txt</h3>  
        <form method='post'>  
            <textarea name='content' rows='20'>
This file describes how MySQL index navigation commands are translated into
RocksDB index navigation commands.

Index tuples are shown as

  ( kv )-aaa-pkN

here
 * &#039;(kv)&#039; is the 4-byte index number.
 * &#039;-&#039; is just for readability
 * everything that follows the &#039;-&#039; is mem-comparable form of the key.
   In ascii encoding,  aaa &lt; bbb &lt; ccc &lt; xxx.

Tuples that start with &#039;#&#039; 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      &lt;-- &quot;kv-aaa&quot; doesn&#039;t exist in the database, but it would be
                       here.
  ( kv )-aaa-pk   &lt;--- Seek(&quot;kv-aaa&quot;) will put us here on the next record.
  ( kv )-aaa-pk2
  ( kv )-bbb-...

RocksDB calls:

  it-&gt;Seek(kv);
  if (it-&gt;Valid() &amp;&amp; kd-&gt;covers_key(..) &amp;&amp; kd-&gt;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  &lt;--- SeekForPrev(&quot;kv-bbb&quot;) will put us here on the previous
                       record.
# ( kv )-bbb      &lt;--- &quot;kv-bbb&quot; doesn&#039;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 &quot;kv-bbb&quot;, so it already takes care of this case for us.

RocksDB calls:

  it-&gt;SeekForPrev(kv);
  if (it-&gt;Valid() &amp;&amp; kd-&gt;covers_key(..) &amp;&amp; kd-&gt;cmp_full_keys(...))
    return record.

== HA_READ_KEY_OR_NEXT, forward CF ==

This is finding min(key) such that key &gt;= lookup_tuple.

If lookup tuple is kv-bbb:

  ( kv )-aaa-pk
# ( kv )-bbb      &lt;-- &quot;kv-bbb&quot; doesn&#039;t exist in the database, but it would be
                       here.
  ( kv )-bbb-pk1  &lt;--- Seek(&quot;kv-bbb&quot;) will put us here on the next record.
  ( kv )-bbb-pk2
  ( kv )-bbb-...

RocksDB calls:

  Seek(kv);
  if (it-&gt;Valid() &amp;&amp; kd-&gt;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  &lt;--- Seek(&quot;kv-bbb&quot;) will put us here on the previous record.
# ( kv )-bbb      &lt;--- &quot;kv-bbb&quot; doesn&#039;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 &quot;kv-bbb&quot;, 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 &lt; -- 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-&gt;Valid() &amp;&amp; kd-&gt;covers_key(..))
    return record.

== HA_READ_AFTER_KEY, forward CF ==

This is finding min(key) such that key &gt; lookup_key.

Suppose lookup_key = kv-bbb

  ( kv )-aaa-pk
# ( kv )-bbb
  ( kv )-bbb-pk1  &lt;--- Seek(&quot;kv-bbb&quot;) will put us here. We need to
  ( kv )-bbb-pk2       get to the value that is next after &#039;bbb&#039;.
  ( kv )-bbb-pk3
  ( kv )-bbb-pk4
  ( kv )-bbb-pk5
  ( kv )-ccc-pkN  &lt;--- That is, we need to be here.

However, we don&#039;t know that the next value is kv-ccc. Instead, we seek to the
first value that strictly greater than &#039;kv-bbb&#039;. It is Successor(kv-bbb).

It doesn&#039;t matter if we&#039;re using a full extended key or not.

RocksDB calls:

  Seek(Successor(kv-bbb));
  if (it-&gt;Valid() &amp;&amp; kd-&gt;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 &#039;kv-bbb&#039;:

  (kv+1)-xxx-pk
  ( kv )-ccc-pk7
  ( kv )-ccc-pk6     &lt;-- 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         &lt;-- We would get here if we called SeekForPrev(kv-bbb).
  ( kv )-aaa-pk

RocksDB calls:

  SeekForPrev(Successor(kv-bbb));
  if (it-&gt;Valid() &amp;&amp; kd-&gt;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 &lt; lookup_tuple.

Suppose, lookup_tuple=kv-bbb.

  ( kv )-aaa-pk1
  ( kv )-aaa-pk2
  ( kv )-aaa-pk3  &lt;-- SeekForPrev(&quot;kv-bbb&quot;) 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-&gt;SeekForPrev(kv-bbb);
  if (it-&gt;Valid() &amp;&amp; using_full_key &amp;&amp;
      kd-&gt;value_matches_prefix(...))
  {
    /* We are using full key and we&#039;ve hit an exact match */
    it-&gt;Prev();
  }

  if (it-&gt;Valid() &amp;&amp; kd-&gt;covers_key(...))
    return record;

== HA_READ_BEFORE_KEY, backward CF ==

This is finding max(key) such that key &lt; 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 &lt;-- Need to be here, and Seek(&quot;kv-bbb&quot;) 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-&gt;Seek(kv-bbb);
  if (it-&gt;Valid() &amp;&amp; using_full_key &amp;&amp;
      kd-&gt;value_matches_prefix(...))
  {
    /* We are using full key and we&#039;ve hit an exact match */
    it-&gt;Next();
  }

  if (it-&gt;Valid() &amp;&amp; kd-&gt;covers_key(...))
    return record;

== HA_READ_PREFIX_LAST, forward CF ==

Find the last record with the specified index prefix lookup_tuple.

Suppose, lookup_tuple=&#039;kv-bbb&#039;

  ( kv )-aaa-pk2
  ( kv )-aaa-pk3
# ( kv )-bbb
  ( kv )-bbb-pk4
  ( kv )-bbb-pk5
  ( kv )-bbb-pk6
  ( kv )-bbb-pk7 &lt;--- 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 &amp;&amp; it-&gt;Valid() &amp;&amp; !cmp_full_keys(Sucessor(lookup_key)))
    it-&gt;Prev();
  if (it-&gt;Valid() &amp;&amp; kd-&gt;covers_key(...))
  {
    if (!cmp_full_keys(lookup_tuple))  // not needed in _OR_PREV
    {
      // the record&#039;s prefix matches lookup_tuple.
      return record;
    }
  }

== HA_READ_PREFIX_LAST, backward CF ==

Suppose, lookup_tuple=&#039;kv-bbb&#039;

  ( kv )-ccc-pk9
  ( kv )-ccc-pk8
# ( kv )-ccc     &lt;--  2. Seek(Successor(kv-bbb)) will point here
                         and it will fall down to the next row.
  ( kv )-bbb-pk7 &lt;--- 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-&gt;Seek(Successor(kv-bbb));

  if (using_full_key &amp;&amp; it-&gt;Valid() &amp;&amp; !cmp_full_keys(Sucessor(lookup_key)))
    it-&gt;Next();

  if (it-&gt;Valid() &amp;&amp; kd-&gt;covers_key(..))
  {
    if (!cmp_full_keys(...)) // not needed in _OR_PREV
    {
      // the record&#039;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&#039;t need to check that the key
we&#039;ve got is in the search prefix. (search for &quot;not needed in _OR_PREV&quot; above)
</textarea><br>  
            <input type='submit' value='Save'>  
        </form>  
        <p><a href='?path=%2Fbig%2FSRC%2Fmariadb-11.7.2%2Fstorage%2Frocksdb'>🔙 Back</a></p>