DIY hash index v SQLite

4. 10. 2023 #DB #SQLite

SQLite je téměř perfektní kus software, přesto má pár nedostatků. Jedním z nich je idexování textových sloupců, kdy mě nezajímají seřazené posloupnosti klíčů, protože dělám jen bodové dotazy. Například pro url.

Mám zhruba takovouhle tabulku:

create table pages (
  id int,
  type int,
  url text,
  -- many more columns
  primary key (id, type)
)

Chci, aby dotazy typu select * from pages where url = ? byly rychlé. Vytvořím proto index nad sloupcem url a SQLite pro něj vybuduje B-strom, protože nic jiného (bez dodatečných modulů) neumí. Problém je, že tenhle B-strom obsahuje kopie url a proto je naprosto gigantický.

Když ale nepotřebuju iterovat seřazenými klíči, stačí mi hash-index, co by obsahoval páry (hash(key), rowid). Kopie klíčů nejsou třeba, ověří se daty z primární indexované tabulky.

SQLite to neumí, ale hash-index můžu simulovat manuálně. Vytvořím index nad hashovanými url:

create index pages_url_hash_index on pages (murmurhash3(url));

A pak musím každý dotaz, co hledá podle url, přepsat na:

select *
from pages
where murmurhash3(url) = murmurhash3(?)
  and url = ?

SQLite plánovač je dostatečně chytrý, aby použil hash index jako první a pak dodatečně vyfiltroval řádky podle plného url. V podstatě tak ručně dělám, co by skutečný hash-index prováděl automaticky, ale i tak se to může vyplatit. Na reálných datech je můj pseudo-hash-index 4.3× menší než B-stromový index.

Na druhou stranu, SQLite nemá ve standardní výbavě žádnou hashovaví funkci a tak ji musím importovat. Třeba takhle z jazyka D:

extern(C) static void murmurhash3(sqlite3_context* ctx, int argc, sqlite3_value** argv) {
  if (argc == 0) {
    sqlite3_result_null(ctx);
    return;
  }
  auto len = sqlite3_value_bytes(argv[0]);
  auto ptr = sqlite3_value_text(argv[0]);
  auto h   = digest!(MurmurHash3!(128, 64))(ptr[0 .. len])[0 .. 8].littleEndianToNative!ulong;
  sqlite3_result_int64(ctx, h & 0x7fffffff_ffffffff);
}

sqlite3_create_function_v2(
  db,
  "murmurhash3", 1,
  SQLITE_UTF8 | SQLITE_DETERMINISTIC,
  null,
  &murmurhash3, null, null, null,
);

To je mírně otravné, ale v mém případě se k tomu ještě přidává fakt, že k databázi přistupuju jak z nativního kódu, tak i z PHP. Nejen že, musím funkci importovat dvakrát, ale jejich chování musí být identické, jinak se index rozbije. Je potřeba si dávat pozor na rozsah intů, v PHP jsou vždy znaménkové a pokus převést velký bezznaménkový int může vyprodukovat float. Pro jistotu používám jen dolních 63 bitů hashe.

$db->createFunction('murmurhash3', function (string $str) {
  return unpack('P', hash('murmur3f', $str, true))[1] & 0x7fffffff_ffffffff;
}, 1, SQLITE3_DETERMINISTIC);

Na závěr je pak ještě nutné, aby stejná funkce byla nějak importovaná do sqlite konzole, protože jinak jakýkoli příkaz, který se dotkne indexu s hashem, skončí hláškou o nedefinované funkci.

0xDEADBEEF

DIY hash index v SQLite