Last less than or last less or equal with limit added to keyselector returns different values

Using FoundationDB
1

I am developing Clojure bindings for FoundationDB and I came across a strange behavior where if I add a number to KeySelector it seems to go to the lowest value and then move from there if I give a number higher than the result set. The implementation is as below where I take a key and make it a tuple. Then I add the limit value to the keyselector object.

Pseudo-code Java implementation of the Clojure code

function last-less-than (Transaction tr, string key, int limit) {
  var begin = KeySelector.LastLessThan(ToTuple(key));
  var end  = kv.add(limit);
  var range = tr.getRange(begin, end);
  return RangeToList(range);
}

Test cases for last-less-than. Assume Keys are set with the given value i.e. [“bar”] => 1, [“bar1”] => 1, etc. Then to-search is the key passed along with the limit.

Keys : [[“bar”] [“bar1”] [“bar2”] [“car”]]
Value : 1
limit : 1
to-search : bar1

[[[“bar”] “1”]]

Keys : [[“bar”] [“bar1”] [“bar2”] [“car”]]
Value : 1
limit : 2
to-search : bar1

[[[“bar”] “1”] [[“bar1”] “1”]]

Keys : [[“bar”] [“bar1”] [“bar2”] [“car”]]
Value : 1
limit : 2
to-search : bar1

[[[“bar”] “1”] [[“bar1”] “1”] [[“bar2”] “1”]]

(defn last-less-than
  "Returns key and value pairs with keys less than the given key for the given limit
  "
  ([tr key]
   (last-less-than tr key 1))
  ([tr key limit]
   (let [key         (KeySelector/lastLessThan (key->packed-tuple key))
         end         (.add key limit)
         range-query (.getRange tr key end)]
     (range->kv range-query))))

Some test cases

(let [fd (. FDB selectAPIVersion 510)
      keys [["bar"] ["bar1"] ["bar2"] ["car"]]
      value "1"]
  (with-open [db (.open fd)]
    (tr! db (set-keys tr keys value))))

nil

(let [fd (. FDB selectAPIVersion 510)]
  (with-open [db (.open fd)]
    (tr! db (last-less-than "bar1"))))

[[["bar"] "1"]] ;; limit 1 by default

(let [fd (. FDB selectAPIVersion 510)]
  (with-open [db (.open fd)]
    (tr! db (last-less-than tr "bar1" 2))))

[[["bar"] "1"] [["bar1"] "1"]]  ;; Seems to go to last less than and then add from there

(let [fd (. FDB selectAPIVersion 510)]
  (with-open [db (.open fd)]
    (tr! db (last-less-than tr "bar1" 3))))

[[["bar"] "1"] [["bar1"] "1"] [["bar2"] "1"]] ;; Goes to bar2

(let [fd (. FDB selectAPIVersion 510)]
  (with-open [db (.open fd)]
    (tr! db (last-less-or-equal tr "bar1"))))

[["bar1" "1"]]

(let [fd (. FDB selectAPIVersion 510)]
  (with-open [db (.open fd)]
    (tr! db (last-less-or-equal tr "bar1" 3))))

[[["bar1"] "1"] [["bar2"] "1"] [["car"] "1"]]

(let [fd (. FDB selectAPIVersion 510)]
  (with-open [db (.open fd)]
    (tr! db (last-less-or-equal tr "bar1" 10))))

[[["bar1"] "1"] [["bar2"] "1"] [["car"] "1"] [["foo"] 1]]

(let [fd (. FDB selectAPIVersion 510)]
  (with-open [db (.open fd)]
    (tr! db (last-less-than  tr "bar1" 10))))

[[["bar"] "1"] [["bar1"] "1"] [["bar2"] "1"] [["car"] "1"] [["foo"] 1]]
2

I guess my question is what is the behavior you are expecting and how does actual behavior differ from expectations?

The easiest way to think of key selectors when used within range queries is that they go to (are resolved to) the given key for both the begin and end, and then the range is scanned from the first resolved-to key (inclusive) to the second resolved-to key (exclusive). So:

public AsyncIterable<KeyValue> lastLessThan(byte[] x, int limit) {
  KeySelector begin = KeySelector.lastLessThan(x);
  KeySelector end = begin.add(limit);
  return tr.getRange(begin, end);
}

Will do a range read from the first key (strictly) before x to the first key that is limit greater than x (stopping before it gets there). So, let’s say you had keys k1, k2, k3, and k4 in the database. Then if you give it k2 and 3 as x and limit, it will evaluate begin to k1 and end to k4 (it being three greater than k1), and then then the keys returned in the rage will be k1, k2, and k3.

Judging by the comments, it sounds like what you want is to get limit keys less than the given key. Then I think you want something like this:

public AsyncIterable<KeyValue> lastLessThan(byte[] x, int limit) {
  KeySelector end = KeySelector.firstGreaterThanOrEqual(x);
  KeySelector begin = end.add(-1 * limit);
  return tr.getRange(begin, end);
}

Then giving it, say, k3 and 2 will resolve the end key selector to k3 and the begin key selector to k1, so it will return k1 and k2. You could also do:

public AsyncIterable<KeyValue> lastLessThan(byte[] x, int limit) {
  return tr.getRange(new byte[0], x, /* limit = */ limit, /* reverse = */ true);
}

This will read (exclusively) from the given key backwards through the database and return the first limit keys it returns. The only difference (return value wise) from the other option I gave is that the keys will come back in reverse (descending) order.

1 Like
3

Thanks @alloc . That clears it up. I didn’t know that using lastLessThan returns a range with last less than key as the beginning to which adding given limits makes sense. Yes, I need to use negative limits to restrict the keys being less than the pivotal key passed. I didn’t know you can iterate a range in reverse. I can add this to my API. Thanks again for the code and pointers.

1 Like