[Date Prev][Date Next] [Chronological] [Thread] [Top]

Re: LMDB set range to return less than or equal key

Victor Baybekov wrote:

In my use case I have found that MDB_SET_RANGE and MDB_GET_BOTH_RANGE
queries are much more useful, in 90+% cases, when they return less than
or equal key, not greater or equal.

I have tested a quick implementation of "get less or equal", and it is
c.50% slower in memory. I must say that if someone told me, before I
learned about LMDB, that even with 50% less than original performance
such numbers are possible, I would not believe - both are millions ops
per seconds in my isolated in-memory microbenchmark. But still, such
queries are building blocks of N operations that could require
non-linear (N^x, x > 1) number of queries and I am interested if I could
easily speed this up closer to the built-in MDB_SET_RANGE. The C code is
in this gist
I call it from C# via P/Invoke, the test code is here
I made sure that only C methods are different, all other code is the
same in C#. But even with the P/Invoke overhead the difference is visible.

My naive approach is to use MDB_SET_RANGE as the first step and, if the
key from this query is not equal to the requested key, to call

That should work fine.

Other than an additional call to MOVE_PREV, it requires
allocation of a copy of the original key, because MDB_SET_RANGE
overwrites it and I haven't found a better way to compare the requested
key with the key returned after MDB_SET_RANGE.

You don't need to copy the entire key, you just need to save a copy of its address. I've commented accordingly on your gist.

  -- Howard Chu
  CTO, Symas Corp.           http://www.symas.com
  Director, Highland Sun     http://highlandsun.com/hyc/
  Chief Architect, OpenLDAP  http://www.openldap.org/project/