0xDEADBEEF

Degenerované fulltext hledání v SQLite

SQLite3 toho umí překvapivě hodně. Mimo všeho, co člověk čeká od relační databáze, nabízí i modul fts5 pro fulltextové hledání. Zajímavé na něm je, že se dá flexibilně konfigurovat, aby efektivně dělal něco více specializovaného než fultext hledání.

Mám situaci, kdy potřebuju jedinou věc: hledat záznamy, které mají určitou kombinaci tagů, žádné řazení podle relevance, stačí je jen vypsat podle rowid, tak jak leží v databázi¹ . Na to není třeba, aby fts5 uchovávalo všechna data vyžadovaná generickým fulltext hledáním a index může být mnohem menší.

Vzal jsem kus dat z bandcamp exploreru na otestování kolik místa zabere index: 836762 alb, 198151 různých tagů, 6131834 párů album/tag.²

create virtual table tags_fts using fts5(tags);

97.6 MB

Tohle umí všechno: hledání frází, zvýraznění snippetu, řazení dle relevance a pokročilé operátory.

create virtual table tags_fts using fts5(tags, content = '');

30.4 MB

Neuchovává původní text, jen invertovaný index. Na takovém indexu není možné dělat update a delete, a dotazy můžou vrátit jen rowid.

create virtual table tags_fts using fts5(tags, content = '', detail = column);

30.3 MB

Invertovaný index typicky ukládá seznamy trojic – rowid, sloupec v němž se termín nachází a pozice termínu v daném sloupci.

detail = column způsobí, že se ukládá pouze rowid a číslo sloupce, zahodí se pozice v dokumentu. Ve výsledku není možné hledat fráze.

Nedojde téměř k žádnému zmenšení. Asi to má něco společného s faktem, že je indexovaný jen jeden sloupec tags. Tabulky s více zaindexovanými sloupci se skutečně zmenší.

create virtual table tags_fts using fts5(tags, content = '', detail = none);

17.9 MB

detail = none z trojice zahodí vše kromě rowid. Můžu se tak dotazovat jen jestli je hledaný termín přítomný v jakémkoli sloupci daného řádku.

create virtual table tags_fts using fts5(tags, content = '', detail = none, columnsize = 0);

9.5 MB

columnsize = 0 zahodí informace o počtu tokenů v každém dokumentu, kterou používá rankovací funkce bm25. Takový index umí zjistit pouze rowid řádků, které obsahují některé z dané množiny tagů. Neumí vytřídit řádky, které odpovídají lépe. To je přesně funkcionalita, kterou jsem chtěl a stačí na ni 10× méně místa než pro klasický fulltext index.

1. Trik je v tom nastavit rowid tak, aby odpovídalo řadícímu kritériu a do dostupných 64 bitů zakódovat co nejvíc informací (pozitivní/negativní, vyhrazené rozsahy, nejnižší bity jako identifikátory). Virtuální tabulky a without rowid nejdou dohromady.
2. Z tohohle je vidět, že jsem článek napsal minulý listopad, kdy BC explorer měl mnohem menší databázi. Teď má zaindexované 4.7 miliony alb a singlů.