1899194 - Retrieving all rows using IDBIndex.openCursor is significantly slower than IDBObjectStore.openCursor

Status: RESOLVED FIXED

(Core :: Storage: IndexedDB, enhancement, P3)

Description

[josh]

User Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:126.0) Gecko/20100101 Firefox/126.0

Steps to reproduce:

I am storing ~122,511 rows in IndexedDB, and then I am trying to retrieve them all to populate a search index. The store has an extra index on the 'version' property to retrieve rows from the latest version.

1. Visit https://idb-perf-repro.netlify.app/lots-of-rows/
2. Click 'Fetch + write to IndexedDB'
3. Click 'Load IDBObjectStore.openCursor' to load all rows from the store
4. Click 'Load IDBIndex.openCursor' to load all rows from the store, using the index

In this demo, all rows in the store have the same index value that is used for retrieval.

Actual results:

On my computer:
IDBObjectStore.openCursor loads 122511 rows in 2,790ms
IDBIndex.openCursor loads 122511 rows in 16,710ms

Google Chrome, on the same computer:
IDBObjectStore.openCursor loads 122511 rows in 3,070ms
IDBIndex.openCursor loads 122511 rows in 3,520ms

Although Firefox is consistently slightly faster than Chrome at loading all rows from the store, Firefox is significantly slower when loading the same amount of rows when specifying a value from the index.

Expected results:

IDBIndex.openCursor should have comparable performance to IDBObjectStore.openCursor, as it does in other browsers.

Comment 1

[josh]

Additional background:

The store is created with:

dbOpenRequest.onupgradeneeded = () => {
  const store = dbOpenRequest.result.createObjectStore(STORE_NAME, {
    keyPath: ["tableName", "key"],
  });

  store.createIndex("version", "version", { unique: false });
};

With each row looking like:

const row = {
  version: '225530.24.05.01.1730-24-bnet.55439',
  tableName: "Location",
  key: 654321,
  definition: { object }
}

I have profiled it using the Firefox preset - not sure if this is helpful or not https://share.firefox.dev/3WSUT8Z

Comment 2

[BugBot [:suhaib / :marco/ :calixte]]

The Bugbug bot thinks this bug should belong to the 'Core::JavaScript Engine' component, and is moving the bug to that component. Please correct in case you think the bot is wrong.

Comment 3

[Jens Stutte [:jstutte]]

(In reply to josh from comment #1)

I have profiled it using the Firefox preset - not sure if this is helpful or not https://share.firefox.dev/3WSUT8Z

Could you profile it again after ticking Bypass selections above and record all registered threads in the profiler settings, please ? Thank you!

Comment 4

[josh]

(In reply to Jens Stutte [:jstutte] from comment #3)

Could you profile it again after ticking Bypass selections above and record all registered threads in the profiler settings, please ? Thank you!

Here ya go! https://share.firefox.dev/3wRw2ba

Hope this includes the right details.

Comment 5

[Jens Stutte [:jstutte]]

Thanks, that contains all I expected. From the flame graph on the IndexedDB thread stands out:

Connection::stepStatement SELECT index_table.value as sort_column, index_table.value_locale, index_table.object_data_key, object_data.file_ids, object_data.data FROM index_data AS index_table JOIN object_data ON index_table.object_store_id = object_data.object_store_id AND index_table.object_data_key = object_data.key WHERE index_table.index_id = :id AND sort_column <= :range_bound AND sort_column >= :current_key AND ( sort_column > :current_key OR index_table.object_data_key > :object_store_position )  ORDER BY sort_column ASC,...

which seems to be called very often. Jari, any thoughts?

Comment 6

[Jari Jalkanen [:jari]]

We should optimize the query.

Comment 7

[Arnaud Bienner]

IMO it's expected that browsing indexes will be slower than using getAll, and this is the behavior I obverse on Chrome and Safari, where this is ~25% slower.

However, for Firefox, it's 5 times slower, so clearly something to improve here.

Running Firefox Profiler (profiles attached), I can see we spend a fair amount of time in sqlite code when using cursor, which is not the case when using getAll.

The corresponding code making the SQL statements lives in ActorsParent.cpp.

Here are the corresponding SQL queries created:
continueQuery:

SELECT index_table.value as sort_column, index_table.value_locale, index_table.object_data_key, object_data.file_ids, object_data.data
FROM index_data AS index_table
	JOIN object_data
	ON index_table.object_store_id = object_data.object_store_id
	AND index_table.object_data_key = object_data.key
	WHERE
		index_table.index_id = :id
		AND sort_column <= :range_bound
		AND sort_column >= :current_key
		AND (sort_column > :current_key
			 OR index_table.object_data_key > :object_store_position )
ORDER BY sort_column ASC, index_table.object_data_key ASC LIMIT :limit

continuePrimaryKeyQuery (conditions slightly reordered to ease comparison with the previous query):

SELECT index_table.value as sort_column, index_table.value_locale, index_table.object_data_key, object_data.file_ids, object_data.data
FROM index_data AS index_table
	JOIN object_data
	ON index_table.object_store_id = object_data.object_store_id
	AND index_table.object_data_key = object_data.key
	WHERE
		index_table.index_id = :id
		AND sort_column <= :range_bound
		AND (sort_column > :current_key
				OR (sort_column == :current_key
				 	AND index_table.object_data_key >= :object_store_position))
ORDER BY sort_column ASC, index_table.object_data_key ASC LIMIT :limit

The important parts are the sort_column/object_data_key conditions:
continueQuery:

AND sort_column >= :current_key
		AND (sort_column > :current_key
			 OR index_table.object_data_key > :object_store_position

continuePrimaryKeyQuery:

AND (sort_column > :current_key
				OR (sort_column == :current_key
				 	AND index_table.object_data_key >= :object_store_position)

Turns out this is pretty inefficient, because apparently this can't be well optimized and we end up doing multiple comparisons on intermediate results (a O(n²) algorithm).

However, this could be rewritten using row values comparison.

Basically, having (for continueQuery):
(sort_column, index_table.object_data_key) > ( :current_key, :object_store_position)
combining both checks.

For continuePrimaryKeyQuery, we simply need to use >= instead of >.

This is semantically equivalent to the previous SQL statement, i.e. "Get record whose key is > current_key, or equal to current_key, but which store_position is > (or >= for the primary key query) object_store_position".

Comment 8

[Arnaud Bienner]

Attachment: IDBCursor-slow.json.xz

Comment 9

[Arnaud Bienner]

Attachment: IDBGetAll-fast.json.xz

Comment 10

[Arnaud Bienner]

Attachment: image.png

Profiler with IDB cursor

Comment 11

[Arnaud Bienner]

Attached screenshot from the profiler: the grey part, on the IndexedDB thread, is almost non-existent on the getAll profile. This corresponds mostly to sqlite3 code.

Comment 12

[Arnaud Bienner]

Attachment: IDBCursor.png

Comment 13

[Arnaud Bienner]

Attachment: Bug 1899194 - More test coverage for IDBCursor continue/continuePrimaryKey

Comment 14

[Arnaud Bienner]

Attachment: Bug 1899194 - IDBCursor: use row values comparison to make SQL queries faster

Comment 15

[Arnaud Bienner]

With the fix, using IDBIndex.openCursor is now only ~20% slower (similar to Safari and Chrome's behavior)

Comment 16

[Arnaud Bienner]

@josh: Thanks for reporting the issue, and also for providing a small web app to reproduce the issue: this was really helpful :)

Comment 17

[Arnaud Bienner]

Attachment: Bug 1899194 - Add IndexedDB cursor performance tests

Comment 18

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/433795d7a725
https://hg.mozilla.org/integration/autoland/rev/3d4fac52a840
Add IndexedDB cursor performance tests r=perftest-reviewers,dom-storage-reviewers,frontend-codestyle-reviewers,jari,sparky

Comment 19

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/3d4fac52a840

Comment 20

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/4228d040c098
https://hg.mozilla.org/integration/autoland/rev/0765dd9023f5
More test coverage for IDBCursor continue/continuePrimaryKey r=dom-storage-reviewers,jari
https://github.com/mozilla-firefox/firefox/commit/05b826144257
https://hg.mozilla.org/integration/autoland/rev/92b03805a618
IDBCursor: use row values comparison to make SQL queries faster r=dom-storage-reviewers,jari

Comment 21

[Web Platform Test Sync Bot [:wpt-sync] (Matrix: #interop:mozilla.org)]

Created web-platform-tests PR https://github.com/web-platform-tests/wpt/pull/61302 for changes under testing/web-platform/tests

Comment 22

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/0765dd9023f5
https://hg.mozilla.org/mozilla-central/rev/92b03805a618

Comment 23

[Web Platform Test Sync Bot [:wpt-sync] (Matrix: #interop:mozilla.org)]

Upstream PR merged by moz-wptsync-bot