DeleteRangeBasic in indexed_db_backing_store.cc walks a cursor over the store's data range (this takes care of store records and index records).

For each entry it calls LevelDBTransaction::Remove() which calls LevelDBTransaction::Set() which checks the in-memory map and then mints a deletion entry. Also, iterators are notified on each item. This is a fair amount of churn - we can probably do better. 

Ideas:

* Pass the range to LevelDBTransaction::RemoveRange(). That should clear the in-memory map since it's useless at that point anyway.
* We can avoid swapping in the value.
* Only notify iterators once.

With the obvious changes above, I got about a 4x speedup.

What's frustrating is that once I made the change, it takes the same amount of time to seek+iterate.

Maybe as part of the commit we should also issue CompactRange calls.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/339d49e89f42347c7b85ac31cb0e9ebd8163025d

commit 339d49e89f42347c7b85ac31cb0e9ebd8163025d
Author: jsbell <jsbell@chromium.org>
Date: Thu Feb 23 01:18:10 2017

IndexedDB: Optimize range deletion operations (e.g. clearing a store)

Range deletion in leveldb involves walking over the range to identify
keys to remove. The wrapper class used by IndexedDB to implement
transactions was applying this same logic, which was inefficient due
to (1) complexity in walking two iterators (one for the uncommitted
transaction data and one for the backing store data) and (2) notifying
iterators for every record.

This was optimized by clearing the range in the uncommitted data
first, then simply walking the range in the backing store, and
deferring notifying iterators until the end. This required removing
the |delete_count| out param plumbed through various methods, but it
was only used in tests.

On a test for clearing a store with 100k index entries, a 4x speedup
was observed.

BUG=693799
TEST=content_unittests --gtest_filter='LevelDBTransactionTest.*'

Review-Url: https://codereview.chromium.org/2708223002
Cr-Commit-Position: refs/heads/master@{#452324}

[modify] https://crrev.com/339d49e89f42347c7b85ac31cb0e9ebd8163025d/content/browser/indexed_db/indexed_db_backing_store.cc
[modify] https://crrev.com/339d49e89f42347c7b85ac31cb0e9ebd8163025d/content/browser/indexed_db/indexed_db_backing_store.h
[modify] https://crrev.com/339d49e89f42347c7b85ac31cb0e9ebd8163025d/content/browser/indexed_db/indexed_db_backing_store_unittest.cc
[modify] https://crrev.com/339d49e89f42347c7b85ac31cb0e9ebd8163025d/content/browser/indexed_db/indexed_db_database.cc
[modify] https://crrev.com/339d49e89f42347c7b85ac31cb0e9ebd8163025d/content/browser/indexed_db/leveldb/leveldb_transaction.cc
[modify] https://crrev.com/339d49e89f42347c7b85ac31cb0e9ebd8163025d/content/browser/indexed_db/leveldb/leveldb_transaction.h
[add] https://crrev.com/339d49e89f42347c7b85ac31cb0e9ebd8163025d/content/browser/indexed_db/leveldb/leveldb_transaction_unittest.cc
[modify] https://crrev.com/339d49e89f42347c7b85ac31cb0e9ebd8163025d/content/browser/indexed_db/leveldb/leveldb_unittest.cc
[modify] https://crrev.com/339d49e89f42347c7b85ac31cb0e9ebd8163025d/content/test/BUILD.gn

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/a9e4f703d78e0cf23ecba81eced44ec3a9712bec

commit a9e4f703d78e0cf23ecba81eced44ec3a9712bec
Author: keishi <keishi@chromium.org>
Date: Thu Feb 23 09:39:29 2017

Revert of IndexedDB: Optimize range deletion operations (e.g. clearing a store) (patchset #1 id:1 of https://codereview.chromium.org/2708223002/ )

Reason for revert:
Possibly related to indexdb test failures https://bugs.chromium.org/p/chromium/issues/detail?id=693048

Original issue's description:
> IndexedDB: Optimize range deletion operations (e.g. clearing a store)
>
> Range deletion in leveldb involves walking over the range to identify
> keys to remove. The wrapper class used by IndexedDB to implement
> transactions was applying this same logic, which was inefficient due
> to (1) complexity in walking two iterators (one for the uncommitted
> transaction data and one for the backing store data) and (2) notifying
> iterators for every record.
>
> This was optimized by clearing the range in the uncommitted data
> first, then simply walking the range in the backing store, and
> deferring notifying iterators until the end. This required removing
> the |delete_count| out param plumbed through various methods, but it
> was only used in tests.
>
> On a test for clearing a store with 100k index entries, a 4x speedup
> was observed.
>
> BUG=693799
> TEST=content_unittests --gtest_filter='LevelDBTransactionTest.*'
>
> Review-Url: https://codereview.chromium.org/2708223002
> Cr-Commit-Position: refs/heads/master@{#452324}
> Committed: https://chromium.googlesource.com/chromium/src/+/339d49e89f42347c7b85ac31cb0e9ebd8163025d

TBR=cmumford@chromium.org,dmurph@chromium.org,jsbell@chromium.org
# Skipping CQ checks because original CL landed less than 1 days ago.
NOPRESUBMIT=true
NOTREECHECKS=true
NOTRY=true
BUG=693799

Review-Url: https://codereview.chromium.org/2710203002
Cr-Commit-Position: refs/heads/master@{#452442}

[modify] https://crrev.com/a9e4f703d78e0cf23ecba81eced44ec3a9712bec/content/browser/indexed_db/indexed_db_backing_store.cc
[modify] https://crrev.com/a9e4f703d78e0cf23ecba81eced44ec3a9712bec/content/browser/indexed_db/indexed_db_backing_store.h
[modify] https://crrev.com/a9e4f703d78e0cf23ecba81eced44ec3a9712bec/content/browser/indexed_db/indexed_db_backing_store_unittest.cc
[modify] https://crrev.com/a9e4f703d78e0cf23ecba81eced44ec3a9712bec/content/browser/indexed_db/indexed_db_database.cc
[modify] https://crrev.com/a9e4f703d78e0cf23ecba81eced44ec3a9712bec/content/browser/indexed_db/leveldb/leveldb_transaction.cc
[modify] https://crrev.com/a9e4f703d78e0cf23ecba81eced44ec3a9712bec/content/browser/indexed_db/leveldb/leveldb_transaction.h
[delete] https://crrev.com/8514e79471d9dfa4a9376317b86f45b57e11eea6/content/browser/indexed_db/leveldb/leveldb_transaction_unittest.cc
[modify] https://crrev.com/a9e4f703d78e0cf23ecba81eced44ec3a9712bec/content/browser/indexed_db/leveldb/leveldb_unittest.cc
[modify] https://crrev.com/a9e4f703d78e0cf23ecba81eced44ec3a9712bec/content/test/BUILD.gn

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/1d62ad3d5531d0becbcb1a5798747a9671db6297

commit 1d62ad3d5531d0becbcb1a5798747a9671db6297
Author: jsbell <jsbell@chromium.org>
Date: Thu Mar 02 17:21:20 2017

IndexedDB: Optimize range deletion operations (e.g. clearing a store)

Range deletion in leveldb involves walking over the range to identify
keys to remove. The wrapper class used by IndexedDB to implement
transactions was applying this same logic but then also (1) doing a
Seek() on each found record to mark it deleted and (2) notifying
iterators for every record.

This was optimized by teaching the transaction wrapper how to clear
ranges itself. The |delete_count| out param plumbed through various
methods was removed, but it was only used in tests.

On a test for clearing a store with 100k index entries, a 2x speedup
was observed.

BUG=693799
TEST=content_unittests --gtest_filter='LevelDBTransaction*'

Review-Url: https://codereview.chromium.org/2719023007
Cr-Commit-Position: refs/heads/master@{#454290}

[modify] https://crrev.com/1d62ad3d5531d0becbcb1a5798747a9671db6297/content/browser/indexed_db/indexed_db_backing_store.cc
[modify] https://crrev.com/1d62ad3d5531d0becbcb1a5798747a9671db6297/content/browser/indexed_db/indexed_db_backing_store.h
[modify] https://crrev.com/1d62ad3d5531d0becbcb1a5798747a9671db6297/content/browser/indexed_db/indexed_db_backing_store_unittest.cc
[modify] https://crrev.com/1d62ad3d5531d0becbcb1a5798747a9671db6297/content/browser/indexed_db/indexed_db_database.cc
[modify] https://crrev.com/1d62ad3d5531d0becbcb1a5798747a9671db6297/content/browser/indexed_db/leveldb/leveldb_transaction.cc
[modify] https://crrev.com/1d62ad3d5531d0becbcb1a5798747a9671db6297/content/browser/indexed_db/leveldb/leveldb_transaction.h
[add] https://crrev.com/1d62ad3d5531d0becbcb1a5798747a9671db6297/content/browser/indexed_db/leveldb/leveldb_transaction_unittest.cc
[modify] https://crrev.com/1d62ad3d5531d0becbcb1a5798747a9671db6297/content/browser/indexed_db/leveldb/leveldb_unittest.cc
[modify] https://crrev.com/1d62ad3d5531d0becbcb1a5798747a9671db6297/content/test/BUILD.gn

Putting this back in the pool for future work.

This issue has been Available for over a year. If it's no longer important or seems unlikely to be fixed, please consider closing it out. If it is important, please re-triage the issue.

Sorry for the inconvenience if the bug really should have been left as Available.

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot

Hopefully tackled soon?