Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@482F

sqlite3でキーの配列に対応するレコードを取得する方法の実行時間比較

Posted at

前提

Node.js で sqlite3 モジュールを使用して試していきます
色々見当違いなことをしているかもしれないので見つけた方はコメントで指摘していただけると嬉しいです

やりたいこと

下記のようなテーブルが存在するとします

id (PK) hash (UNIQUE)
1 abc
2 def
3 ghi

この時、['def', 'def', 'ghi', 'abc'] という配列から [2, 2, 3, 1] という配列を得る良い方法を調べたのですが
うまく見つけられませんでした
そのため取得する方法を 4 種類考えて実際の実行時間を計測してみました

ベスト (ベター) プラクティスをお持ちの方はコメントで教えてください (切実)

手順

レコード作成

ハッシュ値作成

とりあえず 1-100 の整数値の md5 ハッシュ値を作成します

const length = 100
const crypto = require('crypto')
const hashes = Array(length)
  .fill(0)
  .map((_, i) => crypto.createHash('md5').update(i.toString()).digest('hex'))

テーブル作成 & インサート

id (INTEGER) と hash (TEXT) をカラムに持つテーブルを作成し、
先ほど作成したハッシュ値をレコードとしてインサートします

const sqlite3 = require('sqlite3')
const db = new sqlite3.Database('./test.db')

db.serialize(() => {
  db.run(`CREATE TABLE IF NOT EXISTS hashes (
    id INTEGER UNIQUE NOT NULL PRIMARY KEY,
    hash TEXT UNIQUE NOT NULL
  )`)
  db.run(`INSERT OR IGNORE INTO hashes (
    hash
  ) VALUES ${Array(hashes.length).fill('(?)').join(',')}`,
    ...hashes
  )
})

検索用キー配列作成

重複を許すハッシュ値の配列を作成します
キーの個数は生成したレコードの 1/2 にします (適当)
1% の確率でテーブルに存在しないキーが生成されます

const keys = Array(Math.ceil(length / 2))
  .fill(0)
  .map(() => Math.ceil(Math.random() * length * 1.01))
  .map(createHash)

検索関数作成

実際に keys から id の配列を得るための関数を作ります
前提として db.get と db.all を async 化した dbGet と dbAll 関数を作成しています

コード 
async function dbGet(db, ...args) {
  return new Promise((resolve) =>
    db.get(...args, (err, result) => resolve(result))
  )
}

async function dbAll(db, ...args) {
  return new Promise((resolve) =>
    db.all(...args, (err, result) => resolve(result))
  )
}

1. 愚直に一つずつ SELECT

何のひねりもなく、SELECT id FROM hashes WHERE hash = ? を N 件回します

async function f1(keys) {
  return await Promise.all(
    keys.map((key) =>
      dbGet(db, 'SELECT id FROM hashes WHERE hash = ?', key).then(
        (row) => row?.id
      )
    )
  )
}

2. WHERE IN を使う

SELECT * FROM hashes WHERE hash IN (?, ?, ?, ..., ?) を実行します
結果は keys の順番と一致しないため、js 側で加工してやる必要があります

async function f2(keys) {
  const rows = await dbAll(
    db,
    `SELECT * FROM hashes WHERE hash IN (${Array(keys.length)
      .fill('?')
      .join(',')})`,
    ...keys
  )
  const dict = {}
  for (const { id, hash } of rows) {
    dict[hash] = id
  }
  return keys.map((key) => dict[key])
}

3. SELECT で一時的なテーブルを作成して LEFT OUTER JOIN する

SELECT hashes.id FROM (SELECT ? AS hash UNION ALL SELECT ? UNION ALL ... SELECT ?) AS temp LEFT OUTER JOIN hashes ON temp.hash = hashes.hash します。長いですね
SELECT ? で一行を作成し、すべてを UNION ALL で結合して一つのダミーテーブルを用意してから LEFT OUTER JOIN で id を引っ張ってきます

async function f3(keys) {
  return (
    await dbAll(
      db,
      `SELECT hashes.id FROM (SELECT ? AS hash
        ${Array(keys.length - 1)
          .fill('UNION ALL SELECT ?')
          .join('')}
      ) AS temp LEFT OUTER JOIN hashes ON temp.hash = hashes.hash`,
      ...keys
    )
  )?.map?.((row) => row.id)
}

4. テーブルを作って検索して消す

f3 と似た感じですが、実際にテーブルを作って検索します

async function f4(keys) {
  return new Promise((resolve) =>
    db.serialize(() => {
      db.run('CREATE TABLE IF NOT EXISTS temp (hash TEXT NOT NULL)')
      db.run(
        `INSERT INTO temp (hash) VALUES ${Array(keys.length)
          .fill('(?)')
          .join(',')}`,
        ...keys
      )
      const result = dbAll(
        db,
        'SELECT hashes.id FROM temp LEFT OUTER JOIN hashes ON temp.hash = hashes.hash'
      ).then((rows) => rows.map((row) => row.id))
      db.run('DROP TABLE temp', () => result.then((r) => resolve(r)))
      return result
    })
  )
}

計測関数作成

実行時間を測る関数も作っておきます

async function measureTime(label, func) {
  const start = process.hrtime()
  const result = await func()
  const end = process.hrtime(start)
  const timeStr =
    end[0].toString() +
    '.' +
    Math.round(end[1] / 100)
      .toString()
      .padStart(6, '0')
  console.log(label, result?.slice?.(0, 5), timeStr)
}

試しに実行

length === 100

計測関数と被計測関数ができたので動かしてみましょう。

await measureTime('f1', () => f1(keys))
await measureTime('f2', () => f2(keys))
await measureTime('f3', () => f3(keys))
await measureTime('f4', () => f4(keys))

f1 [ 69, 8, 46, 49, 6 ] 0.076587
f2 [ 69, 8, 46, 49, 6 ] 0.017027
f3 [ 69, 8, 46, 49, 6 ] 0.006351
f4 [ 69, 8, 46, 49, 6 ] 0.153142

良い感じですね。length を 25565 にして計測してみましょう (25565 以上にするとテーブルを作る段階で死にます)

length === 25565

f1 [ 6161, 14471, 17540, 20194, 22783 ] 2.1165730
f2 [ 6161, 14471, 17540, 20194, 22783 ] 0.752933
f3 undefined 0.175657
f4 [ 6161, 14471, 17540, 20194, 22783 ] 0.700146

f3 が死んでる・・・
length を色々変えて試したところ、keys の長さが 500 を超えると db.all が undefined を返すようになってしまっています
sqlite3 の仕様なんですかね？UNION ALL の上限が 500 なのかな？
原因は良く分かりませんが、せっかく一番早い f3 がうまくいかないのは残念なので与えられた keys を 500 ずつに分割して実行する f3Alt 関数を作成します

async function f3Alt(keys) {
  const keyss = []
  const length = 500
  for (let i = 0; i < keys.length / length; i++) {
    keyss.push(keys.slice(i * length, (i + 1) * length))
  }
  return (await Promise.all(keyss.map(f3))).flat()
}

f1    [ 3162, 4337, 24559, 24876, 23262 ] 2.1619436
f2    [ 3162, 4337, 24559, 24876, 23262 ] 0.677855
f3Alt [ 3162, 4337, 24559, 24876, 23262 ] 0.586890
f4    [ 3162, 4337, 24559, 24876, 23262 ] 0.724264

うまくいきました！分割実行してなお f3 の UNION ALL 方式が一番早いですね

結論

100 回実行して箱ひげ図を作りました
f4 の最低値がやたら低いのが気になりますが、最速としては f3Alt (UNION ALL) が一番なのではないかと思います
書くのが面倒なので普段使いでは f2 (WHERE IN) を使いますけどね

image.png

おまけ

上記のコードを組み合わせたうまいこと動くものを置いておきます

コード 
const sqlite3 = require('sqlite3')
const db = new sqlite3.Database('./test.db')

async function dbGet(db, ...args) {
  return new Promise((resolve) =>
    db.get(...args, (err, result) => resolve(result))
  )
}

async function dbAll(db, ...args) {
  return new Promise((resolve) =>
    db.all(...args, (err, result) => resolve(result))
  )
}

async function measureTime(label, func) {
  const start = process.hrtime()
  const result = await func()
  const end = process.hrtime(start)
  const timeStr =
    end[0].toString() +
    '.' +
    Math.round(end[1] / 100)
      .toString()
      .padStart(6, '0')
  console.log(label, result?.slice?.(0, 5), timeStr)
}

async function f1(keys) {
  return await Promise.all(
    keys.map((key) =>
      dbGet(db, 'SELECT id FROM hashes WHERE hash = ?', key).then(
        (row) => row?.id
      )
    )
  )
}

async function f2(keys) {
  const rows = await dbAll(
    db,
    `SELECT * FROM hashes WHERE hash IN (${Array(keys.length)
      .fill('?')
      .join(',')})`,
    ...keys
  )
  const dict = {}
  for (const { id, hash } of rows) {
    dict[hash] = id
  }
  return keys.map((key) => dict[key])
}

async function f3(keys) {
  return (
    await dbAll(
      db,
      `SELECT hashes.id FROM (SELECT ? AS hash
        ${Array(keys.length - 1)
          .fill('UNION ALL SELECT ?')
          .join('')}
      ) AS temp LEFT OUTER JOIN hashes ON temp.hash = hashes.hash`,
      ...keys
    )
  )?.map?.((row) => row.id)
}

async function f3Alt(keys) {
  const keyss = []
  const length = 500
  for (let i = 0; i < keys.length / length; i++) {
    keyss.push(keys.slice(i * length, (i + 1) * length))
  }
  return (await Promise.all(keyss.map(f3))).flat()
}

async function f4(keys) {
  return new Promise((resolve) =>
    db.serialize(() => {
      db.run('CREATE TABLE IF NOT EXISTS temp (hash TEXT NOT NULL)')
      db.run(
        `INSERT INTO temp (hash) VALUES ${Array(keys.length)
          .fill('(?)')
          .join(',')}`,
        ...keys
      )
      const result = dbAll(
        db,
        'SELECT hashes.id FROM temp LEFT OUTER JOIN hashes ON temp.hash = hashes.hash'
      ).then((rows) => rows.map((row) => row.id))
      db.run('DROP TABLE temp', () => result.then((r) => resolve(r)))
      return result
    })
  )
}

async function createTable(hashes) {
  return db.serialize(() => {
    db.run(`CREATE TABLE IF NOT EXISTS hashes (
      id INTEGER UNIQUE NOT NULL PRIMARY KEY,
      hash TEXT UNIQUE NOT NULL
    )`)
    db.run(
      `INSERT OR IGNORE INTO hashes (
      hash
    ) VALUES ${Array(hashes.length).fill('(?)').join(',')}`,
      ...hashes
    )
  })
}

async function main(length) {
  const crypto = require('crypto')

  const createHash = (num) =>
    crypto.createHash('md5').update(num.toString()).digest('hex')

  const hashes = Array(length)
    .fill(0)
    .map((_, i) => createHash(i))

  await createTable(hashes)

  const keys = Array(Math.ceil(length / 2))
    .fill(0)
    .map(() => Math.ceil(Math.random() * length * 1.01))
    .map(createHash)

  await measureTime('f1   ', () => f1(keys))
  await measureTime('f2   ', () => f2(keys))
  // await measureTime('f3   ', () => f3(keys))
  await measureTime('f3Alt', () => f3Alt(keys))
  await measureTime('f4   ', () => f4(keys))
}

main(25565)
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?