31:T9a1,# IndexedDB Timings IndexedDB (IDB) is notoriously slow. There are some tricks, however, to get around this: **General Tricks** A main source of overhead for IDB is that of starting and ending a transaction so the first optimization is to batch operations into transactions. **Read Tricks** 1. Reading a single item from IDB at once is slow. Instead, we can read entires ranges or all items for a given store. 2. Even range reads can be slow. We can speed this further by storing pages, rather than individual objects, in IDB **Write Tricks** 1. Use [Relaxed Durability](https://developer.mozilla.org/en-US/docs/Web/API/IDBTransaction/durability) so the write doesn't have to be synced to disk before IDB returns 2. Same as read trick 2: store a page of items against a single key. The perf improvement from range reads, transactions and relaxed durability is well documented here: https://nolanlawson.com/2021/08/22/speeding-up-indexeddb-reads-and-writes/ This notebook explores reading and writing pages of objects rather than individual objects. In other words, we'll store N objects against a single key. If we want a specific object, we'll load the page that contains it and pluck it from that page. Similar to how SQLite atop IndexedDB functions which has been explored by the following two projects: - AbsurdSQL https://jlongster.com/future-sql-web and - WA-SQLite https://github.com/rhashimoto/wa-sqlite/discussions/86 But, in our case, we can do even better. SQLite backed by IndexedDB requires: 1. Crossing the JS -> WASM bridge 2. Serializing JS values as SQLite values 3. Finally writing to IndexedDB but via [asyncify](https://emscripten.org/docs/porting/asyncify.html) and after acquiring a weblock Using IndexedDB directly from JS and directly storing pages of native JS objects is presumably much faster than even what SQLite can do. ## Why this Notebook? Because, for a reactive app backed by a db, we need insane performance. [Performance that SQLite may not be able to give us](https://observablehq.com/@tantaman/in-memory-sqlite-perf). We want full memory speed with the ability to persist to disk lazily (or eagerly) rather than requiring every transaction to fsync. More detail in this [draft](https://github.com/vlcn-io/docs/blob/main/pages/blog/sqlite-isnt-it.mdx). The ultimate hypothesis we want to verify: > IndexedDB provides a performant enough key-value store on top of which to create a reactive database for the browser.32:T42d,# Write Benchmarks Tested below are various ways of organizing writes to indexed DB and comparing that perf against an in-memory SQLite DB. Write Strategies tested: 1. **idbNoTx**: 1 object & 1 transaction (tx) per write (expected to perform worst) 2. **idbTx**: 1 object per write, all objects written in the same tx. 3. **idbPaged**: All objects collected into an array and written against 1 key in 1 tx 4. **idbPagedPTreap**: All objects collected into a persistent [treap](https://en.wikipedia.org/wiki/Persistent_data_structure) and written against 1 key in 1 tx. The persistent treap is a likely structure we'll use for a custom DB implementation. 5. **sqliteMem**: writes objects to an in-memory SQLite db. For a deeper dive into SQLite perf, see: https://observablehq.com/@tantaman/in-memory-sqlite-perf These benchmarks are to discover if the page idea provides enough perf gains to warrant more in-depth research. If it does, we'll test different table widths (num columns), data types, secondary indices, etc. to see if performance holds more generally. 33:Tae1,// iddb: read single object, write single object writes = { sqlitedb.exec([ "DROP TABLE IF EXISTS keyval;", "CREATE TABLE keyval (k PRIMARY KEY, v);", "VACUUM;" ]); const stmt = sqlitedb.prepare("INSERT OR REPLACE INTO keyval VALUES (?, ?)"); const trials = [1, 10, 100, 1_000, 10_000, 100_000]; const idbNoTx = []; const idbTx = []; const idbPaged = []; const idbPagedPTreap = []; const sqliteMem = []; let a = 0; const comp = (l, r) => l.a - r.a; for (const numItems of trials) { if (numItems < 10_000) { idbNoTx.push({ size: numItems, time: await bench(async () => { if (numItems >= 10_000) { return 0; } for (let i = 0; i < numItems; ++i) { const tx = kvstore.transaction("keyval", "readwrite", { durability: "relaxed" }); await tx.store.put({ a: ++a }, makeKey("idbNoTx", numItems, i)); await tx.done; } }) }); } if (numItems < 10_000) { idbTx.push({ size: numItems, time: await bench(async () => { const tx = kvstore.transaction("keyval", "readwrite", { durability: "relaxed" }); const promises = []; for (let i = 0; i < numItems; ++i) { promises.push( tx.store.put({ a: ++a }, makeKey("idbTx", numItems, i)) ); } promises.push(tx.done); await Promise.all(promises); }) }); } idbPaged.push({ size: numItems, time: await bench(async () => { const page = []; for (let i = 0; i < numItems; ++i) { page.push({ a: ++a }); } const tx = kvstore.transaction("keyval", "readwrite", { durability: "relaxed" }); await tx.store.put(page, makeKey("paged", numItems)); await tx.done; }) }); idbPagedPTreap.push({ size: numItems, time: await bench(async () => { let page = new PersistentTreap(comp); for (let i = 0; i < numItems; ++i) { page = page.add({ a: ++a }); } const tx = kvstore.transaction("keyval", "readwrite", { durability: "relaxed" }); await tx.store.put(page._root, makeKey("ppTreap", numItems)); await tx.done; }) }); sqliteMem.push({ size: numItems, time: await bench(() => { sqlitedb.transaction(() => { for (let i = 0; i < numItems; ++i) { stmt.bind(1, makeKey("sqlite", numItems, i)); stmt.bind(2, ++a).stepReset(); } }); }) }); } return { idbNoTx, idbTx, idbPaged, idbPagedPTreap, sqliteMem }; }34:T658,// read what we wrote in the prior bench // 1. read pages // 2. read key ranges that fall within the page // 3. individual cursoring? reads = { writes; const trials = [1, 10, 100, 1_000, 10_000, 100_000]; const sqliteMem = []; const idbPaged = []; const idbPagedPTreap = []; const idbKeyRange = []; // read the single let a = 0; const stmt = sqlitedb.prepare("SELECT * FROM keyval WHERE k LIKE ?"); // TODO: change our primary keys to be ints for a more fair comparison `WHERE k > ? AND k < ?` for (const numItems of trials) { sqliteMem.push({ size: numItems, time: await bench(async () => { const items = []; stmt.bind(1, `sqlite-${numItems}-%`); while (stmt.step()) { items.push(stmt.get([])); } stmt.reset(); }) }); idbPaged.push({ size: numItems, time: await bench(async () => { const ret = await kvstore.get("keyval", makeKey("paged", numItems)); if (ret.length < numItems) { throw new Error("failed to retrieve"); } }) }); idbPagedPTreap.push({ size: numItems, time: await bench(async () => { const ret = await kvstore.get("keyval", makeKey("ppTreap", numItems)); if (!ret) { throw new Error("failed to retrieve"); // todo validate length outside bench } }) }); // TODO: test loading a single row that is within a page. // Presumably that is slow-ish since we incure page load time for just a single item? } return { sqliteMem, idbPaged, idbPagedPTreap, idbKeyRange }; }35:[] 2f:{"title":"IndexedDB Timings","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":65,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":16,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":96,"value":"{\n return Plot.plot({\n marks: [\n Object.entries(writes).map(([k, d]) =>\n Plot.line(\n d.map((n) => ({ ...n, group: k })),\n { x: \"size\", y: \"time\", stroke: \"group\", tip: true }\n )\n )\n ],\n color: {\n domain: [\"idbNoTx\", \"idbTx\", \"idbPaged\", \"idbPagedPTreap\", \"sqliteMem\"],\n legend: true\n },\n width: 1000,\n y: {\n type: \"pow\",\n exponent: 1 / 2,\n domain: [\n 0,\n Math.max(\n ...[].concat(\n ...Object.values(writes).map((x) => x.map((x) => x.time))\n )\n )\n ],\n grid: true\n }\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":187,"value":"## Write Conclusions\n\n- idbPaged is 20x faster than an in-memory SQLite DB that doesn't even persist!\n- Warrants further exploration of perf with:\n - Secondary indices\n - Tables with foreign key constraints\n - Different data types and object sizes\n- Interesting question: how slow is SQLite once persistence is tacked on? Even when that persistence is backed by a relaxed durability idb -- https://rhashimoto.github.io/wa-sqlite/demo/benchmarks.html","pinned":false,"hidden":false,"mode":"md"},{"id":90,"value":"# Read Benchmarks\n\n- How fast are reads when we chunk things into pages? Does it perform better than an indexeddb range scan?\n- How fast is a point read when we do page based storage?","pinned":false,"hidden":false,"mode":"md"},{"id":136,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":167,"value":"{\n return Plot.plot({\n marks: [\n Object.entries(reads).map(([k, d]) =>\n Plot.line(\n d.map((n) => ({ ...n, group: k })),\n { x: \"size\", y: \"time\", stroke: \"group\", tip: true }\n )\n )\n ],\n color: {\n domain: [\"idbPaged\", \"idbPagedPTreap\", \"sqliteMem\"],\n legend: true\n },\n width: 1000,\n y: {\n type: \"pow\",\n exponent: 1 / 2,\n domain: [\n 0,\n Math.max(\n ...[].concat(\n ...Object.values(writes).map((x) => x.map((x) => x.time))\n )\n )\n ],\n grid: true\n }\n });\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":125,"value":"# Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":11,"value":"idb = import(\"https://cdn.jsdelivr.net/npm/idb@8/+esm\");","pinned":true,"hidden":false,"mode":"ojs"},{"id":25,"value":"bench = async (fn) => {\n let best = Number.MAX_SAFE_INTEGER;\n const iterations = 5;\n const times = [];\n for (let i = 0; i < iterations; ++i) {\n const start = performance.now();\n await fn();\n const end = performance.now();\n times.push(end - start);\n best = Math.min(best, end - start);\n }\n times.sort();\n // return the median\n return times[Math.floor(iterations / 2)];\n // avg = avg / iterations;\n // return best;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":122,"value":"PersistentTreap = (\n await import(\"https://esm.sh/@vlcn.io/ds-and-algos@3.0.2/PersistentTreap\")\n).PersistentTreap","pinned":false,"hidden":false,"mode":"ojs"},{"id":30,"value":"sqlitedb = {\n const sqlite3Init = await import(\n \"https://esm.sh/@sqlite.org/sqlite-wasm@3.44.2-build1\"\n );\n const sqlite3 = await sqlite3Init.default({\n print: console.log,\n printErr: console.error\n });\n const db = new sqlite3.oo1.DB(\":memory:\");\n db.exec(\"PRAGMA foreign_keys = OFF\");\n return db;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":145,"value":"makeKey = (type, numItems, item) => `${type}-${numItems}-${item ?? 0}`","pinned":true,"hidden":false,"mode":"ojs"},{"id":150,"value":"kvstore = {\n console.log(\"opening\");\n const kvstore = await idb.openDB(\"test\", 1, {\n upgrade(db) {\n db.createObjectStore(\"keyval\");\n },\n blocking(currentVersion, blockedVersion, event) {\n const db = event.target.result;\n db.close();\n },\n blocked() {\n console.log(arguments);\n }\n });\n console.log(\"opened\");\n return kvstore;\n}","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}