# Proposal for a \`fdb.range\_near(key, limit)\`

**URL:** <https://forums.foundationdb.org/t/proposal-for-a-fdb-range-near-key-limit/1726>\
**Category:** Development\
**Created:** [November 10, 2019, 7:11pm UTC](https://forums.foundationdb.org/t/proposal-for-a-fdb-range-near-key-limit/1726 "2019-11-10T19:11:24Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![amirouche](https://sea1.discourse-cdn.com/foundationdb/user_avatar/forums.foundationdb.org/amirouche/32/2096_2.png) [@amirouche](https://forums.foundationdb.org/u/amirouche)\
**Post date:** [November 10, 2019, 7:11pm UTC](https://forums.foundationdb.org/t/proposal-for-a-fdb-range-near-key-limit/1726/1 "2019-11-10T19:11:24Z")

</div>

While working on approximate string matching ([https://stackoverflow.com/q/58065020/140837](https://stackoverflow.com/q/58065020/140837)) I stumbled upon the need to lookup the nearest keys around an input key. Hence the idea to have a `fdb.range_near(key, limit)`.

A workaround could be the query by prefixes of `key` of decreasing length until reaching `limit` found keys or the empty prefix. That seems like a waste because results of `db.range_prefix(key[:len(key) - n]` are included in `db.range_prefix(key[:len(key) - n - 1]` (where `n` is strictly bigger than the length of the associated subspace prefix)

Maybe [RankedSet](https://forums.foundationdb.org/t/how-to-model-a-leaderboard/373/12) will be a better solution?

---

<div class="post-metadata">

**Author:** ![alexmiller](https://sea1.discourse-cdn.com/foundationdb/user_avatar/forums.foundationdb.org/alexmiller/32/326_2.png) [@alexmiller](https://forums.foundationdb.org/u/alexmiller)\
**Post date:** [November 10, 2019, 7:14pm UTC](https://forums.foundationdb.org/t/proposal-for-a-fdb-range-near-key-limit/1726/2 "2019-11-10T19:14:49Z")

</div>

Could you explain precisely what you would wish the semantics of `range_near` to be?

---

<div class="post-metadata">

**Author:** ![amirouche](https://sea1.discourse-cdn.com/foundationdb/user_avatar/forums.foundationdb.org/amirouche/32/2096_2.png) [@amirouche](https://forums.foundationdb.org/u/amirouche)\
**Post date:** [November 10, 2019, 8:35pm UTC](https://forums.foundationdb.org/t/proposal-for-a-fdb-range-near-key-limit/1726/3 "2019-11-10T20:35:23Z")

</div>

I wish to be able to fetch at most `LIMIT` key-value pairs around `KEY`. For instance,  
given the following database:

```nohighlight
+=========+=========+
| key | value |
+=========+=========+
| b'\x00' | "foo" |
+---------+---------+
| b'\x01' | "abc" |
+---------+---------+
| b'\x02' | "qux" |
+---------+---------+
| b'\x03' | "bar" |
+---------+---------+
| b'\x04' | "baz" |
+=========+=========+

```

I would like, the following python code:

```python
db.range_near(b'\x02', limit=3)

```

To return the following key-value pairs:

```nohighlight
+=========+=========+
| key | value |
+=========+=========+
| b'\x01' | "abc" |
+---------+---------+
| b'\x02' | "qux" |
+---------+---------+
| b'\x03' | "bar" |
+=========+=========+

```

---

<div class="post-metadata">

**Author:** ![gaurav](https://avatars.discourse-cdn.com/v4/letter/g/b487fb/32.png) [@gaurav](https://forums.foundationdb.org/u/gaurav)\
**Post date:** [November 11, 2019, 5:52am UTC](https://forums.foundationdb.org/t/proposal-for-a-fdb-range-near-key-limit/1726/4 "2019-11-11T05:52:06Z")

</div>

Would something like [key-selectors](https://apple.github.io/foundationdb/developer-guide.html#key-selectors) help? For your previous example, we could fetch n/2 keys above and n/2 below the pivot key and then do another call to make up for any shortfall.

---

<div class="post-metadata">

**Author:** ![amirouche](https://sea1.discourse-cdn.com/foundationdb/user_avatar/forums.foundationdb.org/amirouche/32/2096_2.png) [@amirouche](https://forums.foundationdb.org/u/amirouche)\
**Post date:** [November 11, 2019, 7:50am UTC](https://forums.foundationdb.org/t/proposal-for-a-fdb-range-near-key-limit/1726/5 "2019-11-11T07:50:58Z")

</div>

Yes, indeed key selectors can help.

Thanks.

---

<div class="post-metadata">

**Author:** ![amirouche](https://sea1.discourse-cdn.com/foundationdb/user_avatar/forums.foundationdb.org/amirouche/32/2096_2.png) [@amirouche](https://forums.foundationdb.org/u/amirouche)\
**Post date:** [November 11, 2019, 4:34pm UTC](https://forums.foundationdb.org/t/proposal-for-a-fdb-range-near-key-limit/1726/6 "2019-11-11T16:34:51Z")

</div>

> [@gaurav](#):
>
> For your previous example, we could fetch n/2 keys above and n/2 below the pivot key and then do another call to make up for any shortfall.

That will not necessarily be the nearest keys. To be sure, that the returned keys are the nearest, one will need to fetch `LIMIT` keys above and `LIMIT` keys below, and compute the nearest keys. That is not bad. In my case, `LIMIT` is not more than 10.

(By the way, I am still not sure about the “approximate string matching” algorithm I wrote about in the original post).

Thanks!

---

<div class="post-metadata">

**Author:** ![gaurav](https://avatars.discourse-cdn.com/v4/letter/g/b487fb/32.png) [@gaurav](https://forums.foundationdb.org/u/gaurav)\
**Post date:** [November 11, 2019, 4:59pm UTC](https://forums.foundationdb.org/t/proposal-for-a-fdb-range-near-key-limit/1726/7 "2019-11-11T16:59:18Z")

</div>

Yes, if there is a notion of ‘nearness’ then one would need to fetch n keys on each side. I was trying to fetch n keys ‘around’ the pivot key, as mentioned in the example. I will read the original post more carefully and see if there is anything possible for it.