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, 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

[jsbell, 2017-02-21 21:25:51]

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

[jsbell, 2017-02-21 21:26:05]

cmumford@ - please take a look?

[commit-bot: I haz the power, 2017-02-21 21:27:50]

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

[jsbell, 2017-02-21 22:29:35]

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, 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.

R=cmumford@chromium.org
BUG=693799
TEST=content_unittests --gtest_filter='LevelDBTransactionTest.*'
==========

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, 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.

R=cmumford@chromium.org
BUG=693799
TEST=content_unittests --gtest_filter='LevelDBTransactionTest.*'
==========

[jsbell, 2017-02-21 22:29:35]

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

[commit-bot: I haz the power, 2017-02-21 23:31:32]

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

[commit-bot: I haz the power, 2017-02-21 23:31:33]

Dry run: Try jobs failed on following builders:
  cast_shell_linux on master.tryserver.chromium.linux (JOB_TIMED_OUT, no build
URL)
  chromeos_amd64-generic_chromium_compile_only_ng on
master.tryserver.chromium.linux (JOB_TIMED_OUT, no build URL)
  chromeos_daisy_chromium_compile_only_ng on master.tryserver.chromium.linux
(JOB_TIMED_OUT, no build URL)
  linux_chromium_asan_rel_ng on master.tryserver.chromium.linux (JOB_TIMED_OUT,
no build URL)
  linux_chromium_chromeos_rel_ng on master.tryserver.chromium.linux
(JOB_TIMED_OUT, no build URL)
  linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_TIMED_OUT, no
build URL)

[dmurph, 2017-02-22 23:08:34]

lgtm, thanks for adding all of those other tests in leveldb_transaction.

[jsbell, 2017-02-22 23:24:53]

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, 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.

R=cmumford@chromium.org
BUG=693799
TEST=content_unittests --gtest_filter='LevelDBTransactionTest.*'
==========

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

[jsbell, 2017-02-22 23:25:42]

The CQ bit was checked by jsbell@chromium.org

[commit-bot: I haz the power, 2017-02-22 23:26:56]

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-02-23 01:18:18]

CQ is committing da patch.

Bot data: {"patchset_id": 1, "attempt_start_ts": 1487805942814010, "parent_rev":
"9974e4f50017f116c3696ce9cc38680e77ac14f1", "commit_rev":
"339d49e89f42347c7b85ac31cb0e9ebd8163025d"}

[commit-bot: I haz the power, 2017-02-23 01:19:17]

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

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, 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/+/339d49e89f42347c7b85ac31cb0e...
==========

[commit-bot: I haz the power, 2017-02-23 01:19:20]

Committed patchset #1 (id:1) as
https://chromium.googlesource.com/chromium/src/+/339d49e89f42347c7b85ac31cb0e...

[findit-for-me, 2017-02-23 03:28:17]

FYI: Findit identified this CL at revision 452324 as the culprit for
failures in the build cycles as shown on:
https://findit-for-me.appspot.com/waterfall/culprit?key=ag9zfmZpbmRpdC1mb3Itb...

[keishi, 2017-02-23 09:38:32]

A revert of this CL (patchset #1 id:1) has been created in
https://codereview.chromium.org/2710203002/ by keishi@chromium.org.

The reason for reverting is: Possibly related to indexdb test failures
https://bugs.chromium.org/p/chromium/issues/detail?id=693048.

[Marc Treib, 2017-02-23 09:42:19]

On 2017/02/23 03:28:17, findit-for-me wrote:
> FYI: Findit identified this CL at revision 452324 as the culprit for
> failures in the build cycles as shown on:
>
https://findit-for-me.appspot.com/waterfall/culprit?key=ag9zfmZpbmRpdC1mb3Itb...

The failure this refers to is in RenderWidgetHostViewGuestTest.VisibilityTest, I
don't see how this CL would have caused that.

However, lots of indexeddb webkit_tests are failing with this CL in the blame
list, e.g. on:
https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Linu...
https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Linu...
https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Win7
https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Win7...

[Marc Treib, 2017-02-23 09:43:15]

A revert of this CL (patchset #1 id:1) has been created in
https://codereview.chromium.org/2712713005/ by treib@chromium.org.

The reason for reverting is: Suspected cause for lots of indexeddb webkit_tests 
failures, e.g. on the following builders:

https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Linu...
https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Linu...
https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Win7
https://uberchromegw.corp.google.com/i/chromium.webkit/builders/WebKit%20Win7....