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

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}
Committed: https://chromium.googlesource.com/chromium/src/+/1d62ad3d5531d0becbcb1a5798747a9671db6297

[jsbell, 2017-02-28 23:04:04]

The CQ bit was checked by jsbell@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-02-28 23:04:45]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[jsbell, 2017-03-01 00:16:04]

jsbell@chromium.org changed reviewers:
+ dmurph@chromium.org

[jsbell, 2017-03-01 00:16:04]

dmurph@ - can you take a look?

This is a redo of https://codereview.chromium.org/2708223002/ - the changes are:

* MOAR tests!
* Can't simply erase the in-memory range because the wrapper's iterators have
invariant that they are always pointing at a record. For example, if the store
has [a, b, c] and 'b' is deleted, the iterator is still pointing between 'a' and
'c' so that Next() returns 'c'.

This introduces the RemoveRange() API, removes the per-step Seek(), and adds
tests, but really just optimizes the implementation of the removal rather than
deeply reworking how iterators work. There is definitely room for further
optimization, though.

[commit-bot: I haz the power, 2017-03-01 00:49:45]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-03-01 00:49:45]

Dry run: Try jobs failed on following builders:
  linux_chromium_chromeos_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[dmurph, 2017-03-01 20:06:35]

lgtm with comment and naming nits - especially about describing what the two
iterators do and how they interact.

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
File content/browser/indexed_db/leveldb/leveldb_transaction.cc (right):

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:71: (upper_open ?
comparator_->Compare(it->Key(), end) < 0
Can you pull this out into a static helper method? It's really hard to
understand in it's current form, and it could benefit from a nice descriptive
method name.

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
File content/browser/indexed_db/leveldb/leveldb_transaction.h (left):

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
content/browser/indexed_db/leveldb/leveldb_transaction.h:24: 
Because this took me a while to understand:

Can you add documentation describing what the TransactionIterator vs
DataIterator is? To me it looks like DataIterator is for data that is
temporarily in the transaction, and TransactionIterator is actually reading
things from leveldb?

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
File content/browser/indexed_db/leveldb/leveldb_transaction.h (right):

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
content/browser/indexed_db/leveldb/leveldb_transaction.h:125: bool DeleteData();
Better name? "MaybeDeleteOnDataIterator"?

[jsbell, 2017-03-01 21:56:06]

The CQ bit was checked by jsbell@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-03-01 21:56:29]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[jsbell, 2017-03-01 22:45:26]

Feedback incorporated - can you take another look dmurph@ ?

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
File content/browser/indexed_db/leveldb/leveldb_transaction.cc (right):

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
content/browser/indexed_db/leveldb/leveldb_transaction.cc:71: (upper_open ?
comparator_->Compare(it->Key(), end) < 0
On 2017/03/01 20:06:35, dmurph wrote:
> Can you pull this out into a static helper method? It's really hard to
> understand in it's current form, and it could benefit from a nice descriptive
> method name.

Done. Feedback welcome!

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
File content/browser/indexed_db/leveldb/leveldb_transaction.h (left):

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
content/browser/indexed_db/leveldb/leveldb_transaction.h:24: 
On 2017/03/01 20:06:35, dmurph wrote:
> Because this took me a while to understand:
> 
> Can you add documentation describing what the TransactionIterator vs
> DataIterator is? To me it looks like DataIterator is for data that is
> temporarily in the transaction, and TransactionIterator is actually reading
> things from leveldb?

Done - feedback welcome!

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
File content/browser/indexed_db/leveldb/leveldb_transaction.h (right):

https://codereview.chromium.org/2719023007/diff/1/content/browser/indexed_db/...
content/browser/indexed_db/leveldb/leveldb_transaction.h:125: bool DeleteData();
On 2017/03/01 20:06:35, dmurph wrote:
> Better name? "MaybeDeleteOnDataIterator"?

I realized I could pull the non-DataIterator case in here so I did that,
simplifying the logic here. PTAL?

[commit-bot: I haz the power, 2017-03-01 23:06:24]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-03-01 23:06:25]

Dry run: This issue passed the CQ dry run.

[dmurph, 2017-03-01 23:06:56]

lgtm

[jsbell, 2017-03-02 17:16:01]

The CQ bit was checked by jsbell@chromium.org

[commit-bot: I haz the power, 2017-03-02 17:16:16]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-03-02 17:21:24]

CQ is committing da patch.

Bot data: {"patchset_id": 20001, "attempt_start_ts": 1488474961237530,
"parent_rev": "6e035cf67feec1c6547bf3a919bc3882636ac1af", "commit_rev":
"1d62ad3d5531d0becbcb1a5798747a9671db6297"}

[commit-bot: I haz the power, 2017-03-02 17:22:03]

Description was changed from

==========
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*'
==========

to

==========
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}
Committed:
https://chromium.googlesource.com/chromium/src/+/1d62ad3d5531d0becbcb1a579874...
==========

[commit-bot: I haz the power, 2017-03-02 17:22:05]

Committed patchset #2 (id:20001) as
https://chromium.googlesource.com/chromium/src/+/1d62ad3d5531d0becbcb1a579874...