GeezerVison is showing github.com — MDB_INTEGERKEY and endianness · Issue #105 · lmdbjava/lmdbjava
MDB_INTEGERKEY and endianness #105DescriptionI am facing an issue while using range search using KeyRange.
In lmdb, the following is stored:
key: event timestamp in millis
value: event payload
What I want to do:
- count query by for a given time range (how many events between 1000 hrs to 1010 hrs)
- fetch all the events for a given time range
Issue:
- if counts are queried using
KeyRange.all(), correct count is returned.
- but, if queried using specific range, it does not return current count:
KeyRange.closed(min, max) returns 0
Observations:
- strangely, if queried using
KeyRange.closed(min, max * numberOfKeys), it returns correct result.
- if the keys are
dense, then things work as expected
long start = toMillis(LocalDateTime.of(2018, Month.JANUARY, 1, 0, 0));
for(int i = 0; i < numberOfKeys; i++) {
dbi.put(bb(start + i), bb(i));
}
- in this scenario,
KeyRange.closed() etc. work as expected.
My question is :
am I using the correct APIs for my usecase? is it a configuration issue?
Note:
- Java version
$ java -version
java version "1.8.0_181"
Java(TM) SE Runtime Environment (build 1.8.0_181-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.181-b13, mixed mode)
- Windows 10 dev environment
A reproducible test case: gist Activitybp-alex commented on Dec 8, 2018 I think you stumbled on a corner case where some intersection of MDB_INTEGERKEY, native (Little Endian) byte order and a custom comparator were creating issues.
I simplified your code to the following so that it uses Big Endian and it now passes:
package org.lmdbjava;
import java.io.File;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.file.Files;
import java.time.LocalDateTime;
import java.time.Month;
import java.time.ZoneOffset;
import static java.nio.ByteBuffer.allocateDirect;
import static java.nio.ByteOrder.BIG_ENDIAN;
import org.junit.Test;
import static org.lmdbjava.DbiFlags.*;
public final class IntegerKeyTest2 {
private static final int keyCount = 10;
private final ByteBuffer KEY = allocateDirect(8).order(BIG_ENDIAN);
private final ByteBuffer VALUE = allocateDirect(4).order(BIG_ENDIAN);
private final Env<ByteBuffer> env;
private final Dbi<ByteBuffer> db;
public IntegerKeyTest2() throws IOException {
File dir = Files.createTempDirectory(IntegerKeyTest2.class.getSimpleName())
.toFile();
env = Env.create().open(dir);
db = env.openDbi(IntegerKeyTest2.class.getSimpleName(),
MDB_CREATE, MDB_DUPSORT);
}
@Test
public void execute() {
long[] keys = createSortedKeys();
for (int i = 0; i < keys.length; i++) {
add(keys[i], i);
}
rangeTest(KeyRange.all(), keys.length);
long min = keys[0];
long max = keys[keys.length - 1];
System.out.println("MIN " + min + " MAX " + max);
KeyRange<ByteBuffer> range = KeyRange.closed(bb(min), bb(max * keyCount));
rangeTest(range, keys.length);
KeyRange<ByteBuffer> range2 = KeyRange.closed(bb(min), bb(max));
rangeTest(range2, keys.length); // fails for this case
}
private void rangeTest(KeyRange<ByteBuffer> range, int expected) {
try (Txn<ByteBuffer> txn = env.txnRead();
CursorIterator<ByteBuffer> itr = db.iterate(txn, range)) {
int count = 0;
for (CursorIterator.KeyVal<ByteBuffer> kv : itr.iterable()) {
count++;
}
assert count == expected : "Expected: " + expected + ", got: " + count;
}
}
private static long[] createSortedKeys() {
long[] xs = new long[keyCount];
LocalDateTime start = LocalDateTime.of(2018, Month.JANUARY, 1, 0, 0);
for (int i = 0; i < xs.length; i++) {
xs[i] = toMillis(start.plusHours(i));
}
return xs;
}
private void add(long key, int value) {
KEY.clear();
KEY.putLong(key).flip();
VALUE.clear();
VALUE.putInt(value).flip();
db.put(KEY, VALUE);
}
private static ByteBuffer bb(long a) {
ByteBuffer buffer = allocateDirect(8).order(BIG_ENDIAN);
buffer.putLong(a).flip();
return buffer;
}
private static long toMillis(LocalDateTime time) {
return time.toInstant(ZoneOffset.UTC).toEpochMilli();
}
}Note that it isn't necessary to explicitly set the byte order to Big Endian, as that's the ByteBuffer default. However I would suggest doing so to help future readers of the code recognise the intent. As an aside my own code uses Big Endian whenever storing numbers inside LMDB keys. bp-alex commented on Dec 16, 2018 Closing this ticket because I have provided code that passes the test earlier. kogupta commented on Dec 18, 2018 It seems there is an issue with MDB_INTEGERKEY and CursorIterator.
The following test case is slight modification of the previous case : populates a db with 10 keys, do range lookups; range lookup is done using CursorIterator and raw Cursor navigation.
Cursor navigation works with MDB_INTEGERKEY and native byte ordering, CursorIterator doesn't.
Javadoc says:
/**
* Numeric keys in native byte order: either unsigned int or size_t. The keys
* must all be of the same size.
*/
MDB_INTEGERKEY(0x08),
Probably native ordering is not enabled while CursorIterator is being processed.
import org.junit.Before;
import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.TemporaryFolder;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.lmdbjava.*;
import java.io.File;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.time.LocalDateTime;
import java.time.Month;
import java.time.ZoneOffset;
import java.util.Arrays;
import java.util.Collection;
import java.util.Random;
import static java.nio.ByteBuffer.allocateDirect;
import static java.nio.ByteOrder.BIG_ENDIAN;
import static java.nio.ByteOrder.nativeOrder;
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.number.OrderingComparison.lessThan;
import static org.lmdbjava.DbiFlags.*;
import static org.lmdbjava.KeyRange.closed;
@RunWith(Parameterized.class)
public final class IntegerKeyTest {
private static final boolean disableIteratorTest = false;
private static final int keyCount = 10;
@Rule
public final TemporaryFolder tmp = new TemporaryFolder();
@Parameterized.Parameter(0)
public boolean hasIntegerKey;
private ByteOrder keyByteOrder;
private ByteBuffer KEY;
private ByteBuffer VALUE;
private Env<ByteBuffer> env;
private Dbi<ByteBuffer> db;
private long[] sortedKeys;
@Parameterized.Parameters(name = "hasIntKey: {0}")
public static Collection data() {
Object[][] data = {{true}, {false}};
return Arrays.asList(data);
}
@Before
public void init() throws IOException {
System.out.printf("---- init: hasIntKey => %s ----%n", hasIntegerKey);
DbiFlags[] dbiFlags = hasIntegerKey ?
new DbiFlags[]{MDB_CREATE, MDB_INTEGERKEY, MDB_DUPSORT} :
new DbiFlags[]{MDB_CREATE, MDB_DUPSORT};
File dir = tmp.newFolder();
env = Env.create().open(dir);
db = env.openDbi("int-test-db", dbiFlags);
keyByteOrder = hasIntegerKey ? nativeOrder() : BIG_ENDIAN;
KEY = allocateDirect(8).order(keyByteOrder);
VALUE = allocateDirect(4).order(BIG_ENDIAN);
sortedKeys = createSortedKeys();
populateDB(sortedKeys);
}
@Test
public void allKeys() {
iteratorRangeTest(KeyRange.all(), sortedKeys.length);
}
@Test
public void allKeysSparseRange() {
long min = sortedKeys[0];
long max = sortedKeys[sortedKeys.length - 1];
cursorRangeTest(min, max * keyCount, sortedKeys.length);
KeyRange<ByteBuffer> range = closed(bb(min), bb(max * keyCount));
iteratorRangeTest(range, sortedKeys.length);
}
@Test
public void allKeysExactRange() {
long min = sortedKeys[0];
long max = sortedKeys[sortedKeys.length - 1];
cursorRangeTest(min, max, sortedKeys.length);
KeyRange<ByteBuffer> range = closed(bb(min), bb(max));
iteratorRangeTest(range, sortedKeys.length);
}
@Test
public void subset() {
long min = sortedKeys[0];
long max = sortedKeys[sortedKeys.length - 1];
System.out.println("---- 6 rows expected ----");
cursorRangeTest(min, sortedKeys[5], 6);
iteratorRangeTest(closed(bb(min), bb(sortedKeys[5])), 6);
System.out.println("---- 4 rows expected ----");
cursorRangeTest(sortedKeys[2], sortedKeys[5], 4);
iteratorRangeTest(closed(bb(sortedKeys[2]), bb(sortedKeys[5])), 4);
System.out.println("---- 1 row expected ----");
cursorRangeTest(max, max * 2, 1);
iteratorRangeTest(closed(bb(max), bb(max * 2)), 1);
}
@Test
public void invalidRange() {
long max = sortedKeys[sortedKeys.length - 1];
cursorRangeTest(max + 1, max * 2, 0);
iteratorRangeTest(closed(bb(max + 1), bb(max * 2)), 0);
}
private void populateDB(long[] keys) {
shuffle(keys);
for (int i = 0; i < keys.length; i++) {
System.out.printf("Pair: %,d ==> %d%n", keys[i], i);
add(keys[i], i);
}
Arrays.sort(sortedKeys);
}
private void iteratorRangeTest(KeyRange<ByteBuffer> range, int expected) {
if(disableIteratorTest) return;
int count = 0;
try (Txn<ByteBuffer> txn = env.txnRead();
CursorIterator<ByteBuffer> itr = db.iterate(txn, range)) {
for (CursorIterator.KeyVal<ByteBuffer> kv : itr.iterable()) {
count++;
}
}
assertThat(count, is(expected));
}
private void cursorRangeTest(long from, long to, int expected) {
assertThat(from, is(lessThan(to)));
int count = 0;
try (Txn<ByteBuffer> txn = env.txnRead();
Cursor<ByteBuffer> cursor = db.openCursor(txn)) {
ByteBuffer start = allocateDirect(8).order(keyByteOrder).putLong(from);
start.flip();
if (cursor.get(start, GetOp.MDB_SET_RANGE)) {
long curr = cursor.key().order(keyByteOrder).getLong();
for (boolean b = curr <= to; b;
b = cursor.next() &&
(curr = cursor.key().order(keyByteOrder).getLong()) <= to) {
System.out.printf("Current key: %,d%n", curr);
count++;
}
}
}
assertThat(count, is(expected));
}
private void add(long key, int value) {
KEY.clear();
KEY.putLong(key).flip();
VALUE.clear();
VALUE.putInt(value).flip();
db.put(KEY, VALUE);
}
private static long[] createSortedKeys() {
long[] xs = new long[keyCount];
LocalDateTime start = LocalDateTime.of(2018, Month.JANUARY, 1, 0, 0);
for (int i = 0; i < xs.length; i++) {
LocalDateTime time = start.plusHours(i);
long millis = time.toInstant(ZoneOffset.UTC).toEpochMilli();
xs[i] = millis;
}
return xs;
}
private static void shuffle(long[] arr) {
Random rnd = new Random();
for (int i = arr.length; i > 1; i--)
swap(arr, i - 1, rnd.nextInt(i));
}
private static void swap(long[] arr, int i, int j) {
long tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private ByteBuffer bb(long a) {
ByteBuffer buffer = allocateDirect(8).order(keyByteOrder);
buffer.putLong(a).flip();
return buffer;
}
}Dependencies: junit:junit:4.12:test, org.hamcrest:hamcrest-all:1.3:test, org.lmdbjava:lmdbjava:0.6.1.
Other details:
$ java -version
java version "1.8.0_191"
Java(TM) SE Runtime Environment (build 1.8.0_191-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.191-b12, mixed mode)
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 16.04.5 LTS
Release: 16.04
Codename: xenial
kogupta commented on Dec 18, 2018 My use case is solved with the very specific way of Cursor navigation as shown above;
but I really prefer the elegant 👍 , idiomatic CursorIterator - it is more generic and WAY less error prone! bp-alex commented on Dec 19, 2018 CursorIterator requires Java-side awareness of the key ordering. This is why its constructor accepts a Comparator. If a Comparator is not provided it will default to any comparator passed when the Dbi was created, or, failing that, a Comparator for the Env buffer type.
Try the following method:
private Comparator<ByteBuffer> makeComparator() {
return (ByteBuffer o1, ByteBuffer o2) -> {
long o1l = o1.order(keyByteOrder).getLong();
long o2l = o2.order(keyByteOrder).getLong();
o1.flip();
o2.flip();
return Long.compare(o1l, o2l);
};
}Then you just pass it within your iteratorRangeTest method (db.iterate(txn, range, makeComparator())) and your test passes. Consider making the Comparator static in normal usage.
In recognition this needs to be documented more clearly I have added further JavaDocs to CursorIterator.
As mentioned earlier I always use Big Endian when storing numbers within keys. This avoids extra Comparator effort (as the buffer's normal byte ordering can be used) while simplifying composite keys where several numbers (and/or characters) are written at different offsets. It also avoids different DbiFlag settings, which is helpful with superclasses or dynamically generated DAOs or standalone tools you may write to help introspect the LMDB file, rewrite it in key order to save space etc. Feel free to use Little Endian though if that's better for your needs (conceptually it should be faster, although I'd be surprised if it was of measurable impact given the wider overheads of I/O, LMDB, JNI, GC etc). changed the title [-]Understanding KeyRange[/-] [+]`MDB_INTEGERKEY` and endianness[/+] on Dec 20, 2018changed the title [-]`MDB_INTEGERKEY` and endianness[/-] [+]MDB_INTEGERKEY and endianness[/+] on Dec 20, 2018kogupta commented on Dec 20, 2018 @benalexau yes, providing the native-order aware comparator works 👍 .
Changed the issue heading to MDB_INTEGERKEY and endianness;
there is nothing wrong with KeyRange, heading is clearer about the discussion intent.
regarding change: 6cec06c
If iterating over keys stored with {@link DbiFlags#MDB_INTEGERKEY} you must
provide a Java __iterator__ when constructing the {@link Dbi} or this class. It
is more efficient to use an __iterator__ only with this class, as this avoids
LMDB calling back into Java code to perform the integer key comparison.
Did you mean comparator instead of iterator? bp-alex commented on Dec 20, 2018 Oops! Thanks for letting me know. Fixed now.
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|