google / google/leveldb

Drastically decreasing read performence when range of keys are deleted

Open
#610 5 comments 2 reactions 0 assignees View on GitHub
enhancement
Dominant language
C++
Stars
39.4k
Forks
8.2k
PR merge metrics
No merged PRs in 30d

Description

Performance of Iteration over a range of keys is drastically affected when multiple keys that share some comon prefix where previously deleted.

The use case to reproduce this issue is as follow:
1. Put a set of 1000 keys that share a common prefix.
2. Delete them all
3. For each key in the set do a search using a new DB::NewIterator (it would make more sense to use DB::get, but assume you are searching for more than one entry)
4. Repeat step 1, 2 and 3. Each loop performance hit is big.

I know that as mentioned in issue #83, commit 748539c183453bdeaff1eb0da8ccf5adacb796e7 would mitigate this issue. But as show by the following example, the implemented solution does not mitigate completely the issue. This is specially relevant when using LevelDB easily with prefix searches (or mutable indexes).

I made a simple unit test to show the issue:
```cpp
TEST(DBTest, RangeDeleteAndRead) {
do {
for (int k = 0; k < 27; ++k) {
Env *env = Env::Default();
uint64_t start_micros = env->NowMicros();
for (int i = 0; i < 2000; ++i) {
//search for prefix
std::string prefix = Key(i);
std::string key1 = prefix + "-1";
std::string key2 = prefix + "-2";
//range search with key prefix. No entries exist but each k+1 more time is lost here
Iterator *iter = db_->NewIterator(ReadOptions());
iter->Seek(prefix);
ASSERT_TRUE(!iter->Valid());
delete iter;

//insert values
Put(key1, "value1");
Put(key2, "value2");
}
uint64_t stop_micros = env->NowMicros();

//delete all entries
Iterator *iter = db_->NewIterator(ReadOptions());
WriteBatch wb;
iter->Seek("key");
while (iter->Valid()) {
if (iter->key().ToString().find("key") != 0) {
break;
}
wb.Delete(iter->key().ToString());
iter->Next();
}
WriteOptions wo;
db_->Write(wo, &wb);
delete iter;
unsigned int us = (stop_micros - start_micros)/1000;
fprintf(stderr,
"Run loop %d took %d ms\n",
k, us);
}
} while (ChangeOptions());
}
```

Running this test I get the following result:
```
==== Test DBTest.RangeDeleteAndRead
Run loop 0 took 78 ms
Run loop 1 took 1671 ms
Run loop 2 took 3219 ms
Run loop 3 took 4782 ms
Run loop 4 took 6312 ms
Run loop 5 took 7843 ms
...
Run loop 26 98922 ms
...
```
The performance issue due to the fact that [db_iter](https://github.com/google/leveldb/blob/6caf73ad9dae0ee91873bcb39554537b85163770/db/db_iter.cc#L173) knows nothing about the prefix being searched by the end user.

Adding something like:
```
if(!SharePrefix(&ikey)) {
break;
}
```
to [db_iter.cc#L179](https://github.com/google/leveldb/blob/6caf73ad9dae0ee91873bcb39554537b85163770/db/db_iter.cc#L179) improve drastically performance:
```
==== Test DBTest.RangeDeleteAndRead
Run loop 0 took 93 ms
Run loop 1 took 94 ms
Run loop 2 took 109 ms
Run loop 3 took 125 ms
Run loop 4 took 109 ms
Run loop 5 took 94 ms
...
Run loop 26 took 250 ms
...
```

Would it be nice to add an API to give prefix being searched to iterator and stop looking for more data when no more keys are available?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.