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

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

Victor Baybekov wrote:

Hi!

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
<https://gist.github.com/buybackoff/59dabc70fa5ec8351bbe#file-mdb_cursor_get_le>.
I call it from C# via P/Invoke, the test code is here
<https://gist.github.com/buybackoff/59dabc70fa5ec8351bbe#file-c-test-via-pinvoke>.
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
MOVE_PREV.


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/