DIY hash index v SQLite

4. 10. 2023, aktualizováno: 21. 5. 2024 #DB #SQLite

SQLite je téměř perfektní kus software, přesto má pár nedostatků. Jedním z nich je indexová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 = ?

Plánovač v novějších verzích SQLite² 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.

Nejen velký, ale i pomalý. Dlouhých stringů jako url se na 4kB stránku vejde málo a (protože sqlite, pokud vím, neprovádí žádnou kompresi indexů (tohle PDF, kapitola 3.5)) to má za následek hluboké B-stromy. Čím je index větší, tím více potřebuje paměti v page cache, aby fungoval rychle.
V mém případě má url průměrně 58 bajtů. Bude to 60+ bajtů i s metadaty a 10M klíčů potřebuje B-strom s 4 až 5 patry.
SQLite přibalené k debianu trixie (3.45) fungovalo dobře, ale verze v debianu bookworm (3.40, vydaná v listopadu 2022) nedokázala využít simulovaný hash index pro plánování dotazů.

0xDEADBEEF

DIY hash index v SQLite