Read performance

[retorquere]

I'm looking to switch to blinkdb for its typescript support, but when I benchmark indexed search, blinkdb comes out substantially slower than lokijs:

var Benchmark = require('benchmark')
const Loki = require('lokijs')
const { createDB, createTable } = require( "blinkdb")
const { internalInsertMany } = require('blinkdb/dist/core/insertMany')
const { internalFirst } = require('blinkdb/dist/core/first')

const items = require('./mock.json')

const blinkdb = createDB()
const blinktable = createTable(blinkdb, 'citekeys')({
  primary: "id",
  indexes: ["firstmail"],
});
internalInsertMany(blinktable, items)

const DB = new Loki('better-bibtex', {})
const coll = DB.addCollection('citekeys', {
  indices: [ 'id', 'firstname' ],
  unique: [ 'id' ],
})
coll.insert(items)

var suite = new Benchmark.Suite;
suite
  .add('loki', function() { coll.findOne({ firstname: { $eq: `${Math.random()}` } }) })
  .add('blink', function() { internalFirst(blinktable, { where: { firstname: `${Math.random()}` } }) })
  .on('cycle', function(event) { console.log(String(event.target)) })
  .on('complete', function() { console.log('Fastest is ' + this.filter('fastest').map('name')); })
  .run();

(where mock.json has this content)

returns

loki x 1,466,141 ops/sec ±1.39% (84 runs sampled)
blink x 1,279 ops/sec ±1.49% (89 runs sampled)

and even when I turn off indexes in loki, it still comes out ahead:

loki x 18,342 ops/sec ±0.97% (95 runs sampled)
blink x 1,313 ops/sec ±1.29% (92 runs sampled)
Fastest is loki

I haven't tested more complex searches but search by single indexed field is something I'd be doing a fair bit of. Is this just not a good use-case for blinkdb?

[maradotwebp]

First issue I see is that you're creating a BlinkDB index on firstmail instead of firstname.

But I'll take a look at the query performance without indexes, BlinkDB shouldn't be 18x as slow as Loki when you search for a single key.

[retorquere]

Oopsie.

Both indexed:

loki x 1,501,305 ops/sec ±1.24% (90 runs sampled)
blink x 1,290,563 ops/sec ±0.93% (92 runs sampled)
Fastest is loki

Both unindexed:

loki x 17,738 ops/sec ±2.96% (91 runs sampled)
blink x 1,158 ops/sec ±6.18% (82 runs sampled)
Fastest is loki

[retorquere]

I'm also not seeing the performance in the sample from the front-page; unless I mucked it up again, I'm getting this (script below):

search should find 52 users
scan x 4,240 ops/sec ±4.25% (83 runs sampled)
sharding x 1,693,713 ops/sec ±1.56% (81 runs sampled)
loki x 42,372 ops/sec ±1.31% (86 runs sampled)
blinkdb x 933 ops/sec ±1.84% (80 runs sampled)
Fastest is sharding

script:

var Benchmark = require('benchmark');
const Loki = require('lokijs')
const { createDB, createTable, insertMany, many } = require( "blinkdb")

// data at https://gist.github.com/retorquere/c71d72f63a6a79ad3d0f6cd217e71b03
const items = require('./mock.json')

async function main() {
  const blinkdb = createDB()
  const blinktable = createTable(blinkdb, 'users')({
    primary: "id",
    indexes: ["age", "name"],
  });
  await insertMany(blinktable, items)
  
  const DB = new Loki('better-bibtex', {})
  const coll = DB.addCollection('citekeys', {
    indices: [ 'id', 'age', 'name' ],
    unique: [ 'id' ],
  })
  coll.insert(items)
  
  var suite = new Benchmark.Suite()

  const names = ['Davies', 'Gosling']
  const age = 24
  const n = items.filter(item => item.age > age && names.includes(item.name)).length
  console.log('> search should find', n, 'users')

  const shards = new Map
  for (const user of items) {
    if (!shards.has(user.name)) {
      shards.set(user.name, [ user ])
    }
    else {
      shards.get(user.name).push(user)
    }
  }

  suite
    .add('scan', function() {
      if (items.filter(item => item.age > age && names.includes(item.name)).length !== n) throw new Error('')
    })
    .add('sharding', function() {
      let found = []
      for (const name of names) {
        found = found.concat((shards.get(name) || []).filter(user => user.age > age))
      }
      if (found.length !== n) throw new Error('')
    })
    .add('loki', function() {
      if (coll.find({ name: { $in: names }, age: { $gt: age } }).length !== n) throw new Error('')
    })
    .add('blinkdb', {
      defer: true,
      fn: async function(deferred) {
        if ((await many(blinktable, { where: { name: { in: names }, age: { gt: age } }, })).length !== n) throw new Error('')
        deferred.resolve()
      }
    })
    .on('cycle', function(event) { console.log('> ' + String(event.target)) })
    .on('complete', function() {
      console.log('> Fastest is ' + this.filter('fastest').map('name'));
    })
    .run({ async: true });
}

main()

[retorquere]

And if I'm looking for names that are not in the dataset:

search should find 0 users
scan x 5,207 ops/sec ±4.94% (87 runs sampled)
sharding x 13,567,067 ops/sec ±1.86% (87 runs sampled)
loki x 1,055,781 ops/sec ±1.19% (87 runs sampled)
blinkdb x 1,261 ops/sec ±1.72% (77 runs sampled)
Fastest is sharding

but not only is loki faster in both cases, a table scan is also faster.

[retorquere]

And for 100.000 items (as per the case on the front page):

search should find 3 users
scan x 1,139,156 ops/sec ±1.15% (88 runs sampled)
sharding x 3,938,455 ops/sec ±3.28% (84 runs sampled)
loki x 255,922 ops/sec ±0.82% (90 runs sampled)
blinkdb x 119,386 ops/sec ±1.09% (79 runs sampled)
Fastest is sharding

[retorquere]

Is the benchmark from the front page in the benchmark suite? I can't find it but I'd love to tinker around with it. My numbers don't align with that graph at all, so there must be something relevantly different between how these tests are set up.

[retorquere]

Changed to tinybench like the blinkdb tests:

const { Bench } = require('tinybench');
const Loki = require('lokijs')
const { createDB, createTable, insertMany, many } = require( "blinkdb")

// data at https://gist.github.com/retorquere/c71d72f63a6a79ad3d0f6cd217e71b03
const items = require('./mock.json')

async function main() {
  const blinkdb = createDB()
  const blinktable = createTable(blinkdb, 'users')({
    primary: "id",
    indexes: ["age", "name"],
  });
  await insertMany(blinktable, items)
  
  const DB = new Loki('better-bibtex', {})
  const coll = DB.addCollection('citekeys', {
    indices: [ 'id', 'name', 'age' ],
    unique: ['id'],
  })
  coll.insert(items)
  
  var bench = new Bench

  const random = () => items[Math.round(Math.random() * items.length)]
  const names = [ random().name, random().name ]
  const age = random().age
  const n = items.filter(item => item.age > age && names.includes(item.name)).length
  console.log('> search should find', n, 'users')

  const partitions = new Map
  for (const user of items) {
    if (!partitions.has(user.name)) {
      partitions.set(user.name, [ user ])
    }
    else {
      partitions.get(user.name).push(user)
    }
  }

  bench
    .add('scan', function() {
      if (items.filter(item => item.age > age && names.includes(item.name)).length !== n) throw new Error('')
    })
    .add('partitions', () => {
      let found = []
      for (const name of names) {
        found = found.concat((partitions.get(name) || []).filter(user => user.age > age))
      }
      if (found.length !== n) throw new Error('')
    })
    .add('loki', () => {
      if (coll.find({ name: { $in: names }, age: { $gt: age } }).length !== n) throw new Error('')
    })
    .add('blinkdb', async () => {
      if ((await many(blinktable, { where: { name: { in: names }, age: { gt: age } }, })).length !== n) throw new Error('')
    })

  await bench.run()
  console.table(bench.table())
}

main()

(index)	Task Name	ops/sec	Average Time (ns)	Margin	Samples
0	'scan'	'505'	1978472.635444445	'±1.45%'	253
1	'partitions'	'386,787'	2585.400346700469	'±1.11%'	193440
2	'loki'	'8,665'	115399.97140832458	'±0.63%'	4333
3	'blinkdb'	'140'	7106147.1843383685	'±3.94%'	71

[maradotwebp]

Thanks for taking a look at this :) If you check the official benchmarks for BlinkDB, do you get similar results there (with BlinkDB consistently being slower than alternatives) ? The blinkdb benchmarks only compare my DB to LokiJS, but in my test runs BlinkDB generally reaches 0.8x - 1.2x of the performance of LokiJS, depending on the testcase.

I'll try implementing your testcase within the BlinkDB benchmarks from scratch, then we can see if there's any issues on either side.

[maradotwebp]

Is the benchmark from the front page in the benchmark suite?

Not really, I either did that manually a few versions ago or deleted it from the benchmarks in the last refactor. In either case, I should add it back in and update the values on the front page.

[maradotwebp]

I added a benchmark myself, available on the feature/add-front-page-test branch here: https://github.com/blinkdb-js/blinkdb/blob/feature/add-front-page-test/packages/benchmarks/src/benchmarks/blinkdb/front-page.ts You can run it by cloning the repo, navigating to the benchmark package, and running npm run start -- "blinkdb/front-page.ts" .

My results look like this for 100.000 items in the DB:

blinkdb/front-page.ts --- map is 1.43x faster than scan
┌─────────┬───────────┬────────────────────┬────────────────────┬───────────┬─────────┐
│ (index) │   name    │      ops/sec       │ Average Time (ns)  │  Margin   │ Samples │
├─────────┼───────────┼────────────────────┼────────────────────┼───────────┼─────────┤
│    0    │   'map'   │ 318.43057225700716 │ 3140401.981229661  │ '±2.76%'  │   160   │
│    1    │  'scan'   │ 221.94537258402815 │ 4505613.198226972  │ '±2.49%'  │   111   │
│    2    │ 'blinkdb' │ 105.78578801070266 │ 9453065.660378002  │ '±10.83%' │   53    │
│    3    │ 'lokijs'  │  79.3651495976927  │ 12599988.849880174 │ '±9.05%'  │   40    │
└─────────┴───────────┴────────────────────┴────────────────────┴───────────┴─────────┘

Comparing our respective implementations, a few things I noticed:

• Both BlinkDB and LokiJS have the option to clone returned objects. In BlinkDB this is turned on by default, in LokiJS off by default. Since I don't care about comparing the speed of clone implementations, I turn this off for BlinkDB in my benchmarks with createDB({ clone: false });. This doubles the performance of BlinkDB in this specific benchmark for me.
• Your scan is particularly slow, and your map/partitions particularly fast compared to mine. I haven't found a specific reason for this yet.

Maybe you can gain other insights or discover issues looking through the code of my benchmark?

[maradotwebp]

Testing with your dataset gets me a benchmark more comparable to yours, but BlinkDB is somehow still faster on my side.

My code

import { createDB, createTable, insertMany, many } from "blinkdb";
import loki from "lokijs";
import { Bench } from "tinybench";
// Same content as https://gist.github.com/retorquere/c71d72f63a6a79ad3d0f6cd217e71b03
import userJson from "./users.json";

interface User {
  id: number;
  name: string;
  // made age non-optional here
  age: number;
}

const blinkdb = createDB({ clone: false });
let blinkUserTable = createTable<User>(blinkdb, "users")({
  primary: "id",
  indexes: ["name", "age"] // added age index
});

const lokidb = new loki("users.db");
let lokiUserTable = lokidb.addCollection<User>("users", {
  unique: ["id"],
  indices: ["name", "age"] // added age index
});

let users: User[] = userJson;
let userMap: Map<string, User[]> = new Map();
for(const user of users) {
  userMap.set(user.name, [...(userMap.get(user.name) ?? []), user]);
}
lokiUserTable.insert(users);
insertMany(blinkUserTable, users);

const random = () => users[Math.round(Math.random() * users.length)];
const names = [random().name, random().name];
const age = random().age;

export const bench = new Bench()
  .add("scan", () => {
    users.filter(u => names.includes(u.name) && u.age && u.age > age);
  })
  .add("map", () => {
    let u: User[] = [];
    for(const name of names) {
      u = u.concat((userMap.get(name) ?? []).filter(u => u.age && u.age > age));
    }
  })
  .add("lokijs", () => {
    lokiUserTable.find({ name: { $in: names }, age: { $gt: age } });
  })
  .add("blinkdb", async () => {
    await many(blinkUserTable ,{ where: {
      name: { in: names },
      age: { gt: age }
    }});
  });

blinkdb/front-page.ts --- map is 42.64x faster than lokijs
┌─────────┬───────────┬────────────────────┬────────────────────┬──────────┬─────────┐
│ (index) │   name    │      ops/sec       │ Average Time (ns)  │  Margin  │ Samples │
├─────────┼───────────┼────────────────────┼────────────────────┼──────────┼─────────┤
│    0    │   'map'   │ 1489335.8240912817 │ 671.4402378725764  │ '±1.76%' │ 744668  │
│    1    │ 'lokijs'  │ 34925.248617732905 │ 28632.580713892505 │ '±1.07%' │  17463  │
│    2    │ 'blinkdb' │ 29151.137594377647 │ 34303.978593029904 │ '±3.88%' │  14576  │
│    3    │  'scan'   │ 2969.203635917305  │ 336790.6424144804  │ '±0.64%' │  1485   │
└─────────┴───────────┴────────────────────┴────────────────────┴──────────┴─────────┘

[retorquere]

How do you run this? I'm getting

Cannot use import statement outside a module

when I start it with npx ts-node.

[retorquere]

If you check the official benchmarks for BlinkDB, do you get similar results there (with BlinkDB consistently being slower than alternatives) ?

I haven't been able to get them to work yet.

and running npm run start -- "blinkdb/front-page.ts" .

That gets me

Unknown file extension ".ts" for /Users/emile/github/blinkdb/packages/benchmarks/src/index.ts

• Both BlinkDB and LokiJS have the option to clone returned objects. In BlinkDB this is turned on by default, in LokiJS off by default.

That is true. But when I turn clone off for blinkDB, my tests continue to show everything faster than blinkdb.

• Your scan is particularly slow,

It's supposed to be a benchmark for the worst case. Nothing should be slower than a full scan.

and your map/partitions particularly fast compared to mine. I haven't found a specific reason for this yet.

Javascript Map is just ridiculuously fast, and after selection of the partition it's all integer comparisons. It's doing half the work, and the fast half at that.

I was working on a lokijs partition command where you could select one partition and then filter on the much smaller resultset as usual. But lokijs has not been active for a long while, and I'd much prefer to move to blinkdb if we can get this apparent disparity sorted out.