5 způsobů, jak implementovat vyhledávání bez rozlišení velkých a malých písmen v SQLite s plnou podporou Unicode

Nedávno jsem potřeboval vyhledávání v SQLite bez rozlišení velkých a malých písmen, abych zkontroloval, zda položka se stejným názvem již existuje v jednom z mých projektů – listOK. Zpočátku to vypadalo jako jednoduchý úkol, ale po hlubším ponoru se ukázalo, že je to snadné, ale vůbec ne jednoduché, s mnoha zvraty.

Vestavěné schopnosti SQLite a jejich nevýhody

V SQLite můžete získat vyhledávání bez rozlišení malých a velkých písmen třemi způsoby:

-- 1. Use a NOCASE collation
-- (we will look at other ways for applying collations later):
SELECT * 
    FROM items 
    WHERE text = "String in AnY case" COLLATE NOCASE;

-- 2. Normalize all strings to the same case,
-- does not matter lower or upper:
SELECT * 
    FROM items 
    WHERE LOWER(text) = "string in lower case";

-- 3. Use LIKE operator which is case insensitive by default:
SELECT * 
    FROM items 
    WHERE text LIKE "String in AnY case";

Pokud používáte SQLAlchemy a její ORM, budou tyto přístupy vypadat následovně:

from sqlalchemy import func
from sqlalchemy.orm.query import Query

from package.models import YourModel


text_to_find = "Text in AnY case"

# NOCASE collation
Query(YourModel)
.filter(
    YourModel.field_name.collate("NOCASE") == text_to_find
)

# Normalizing text to the same case
Query(YourModel)
.filter(
    func.lower(YourModel.field_name) == text_to_find.lower()
).all()

# LIKE operator. No need to use SQLAlchemy's ilike
# since SQLite LIKE is already case-insensitive.
Query(YourModel)
.filter(YourModel.field_name.like(text_to_find))

Všechny tyto přístupy nejsou ideální. Za prvé , bez zvláštních ohledů nepoužívají indexy na poli, na kterém pracují, s LIKE být nejhorším pachatelem:ve většině případů není schopen používat indexy. Více o použití indexů pro dotazy bez rozlišení malých a velkých písmen je uvedeno níže.

Druhý a co je důležitější, mají poměrně omezené chápání toho, co znamená nerozlišovat malá a velká písmena:

SQLite ve výchozím nastavení rozumí pouze velkým/malým písmenům pro znaky ASCII. Operátor LIKE rozlišuje malá a velká písmena ve výchozím nastavení pro znaky unicode, které jsou mimo rozsah ASCII. Například výraz 'a' LIKE 'A' je PRAVDA, ale 'æ' LIKE 'Æ' je NEPRAVDA.

Není problém, pokud plánujete pracovat s řetězci, které obsahují pouze písmena anglické abecedy, čísla atd. Potřeboval jsem celé spektrum Unicode, takže bylo na místě lepší řešení.

Níže shrnuji pět způsobů, jak dosáhnout vyhledávání/porovnávání bez rozlišení velkých a malých písmen v SQLite pro všechny symboly Unicode. Některá z těchto řešení lze upravit pro jiné databáze a pro implementaci LIKE s podporou Unicode , REGEXP , MATCH a další funkce, ačkoli tato témata jsou mimo rozsah tohoto příspěvku.

Podíváme se na klady a zápory každého přístupu, detaily implementace a nakonec na indexy a úvahy o výkonu.

Řešení

1. Rozšíření JIP

Oficiální dokumentace SQLite zmiňuje rozšíření ICU jako způsob, jak přidat kompletní podporu pro Unicode v SQLite. ICU znamená International Components for Unicode.

JIP řeší problémy obou LIKE bez ohledu na malá a velká písmena a porovnání/vyhledávání, plus přidává podporu pro různé porovnávání pro dobrou míru. Může být dokonce rychlejší než některá pozdější řešení, protože je napsán v C a je těsněji integrován s SQLite.

Přichází však se svými problémy:

1. Je to nový typ závislosti:ne knihovna Python, ale rozšíření, které by mělo být distribuováno společně s aplikací.

2. ICU je třeba před použitím zkompilovat, potenciálně pro různé OS a platformy (netestováno).

3. ICU samo o sobě neimplementuje převody Unicode, ale spoléhá na podtržený operační systém – viděl jsem několik zmínek o problémech specifických pro OS, zejména u Windows a macOS.

Všechna ostatní řešení budou záviset na vašem kódu Pythonu při provádění porovnání, takže je důležité zvolit správný přístup ke konverzi a porovnávání řetězců.

Výběr správné funkce pythonu pro porovnání bez ohledu na velikost písmen

Abychom mohli provádět porovnání a vyhledávání bez ohledu na velikost písmen, musíme normalizovat řetězce na jeden případ. Můj první instinkt byl použít str.lower() pro tohle. Ve většině případů to bude fungovat, ale není to správný způsob. Je lepší použít str.casefold() (dokumenty):

Vraťte složenou kopii řetězce. Pro párování bez pouzdra lze použít řetězce složené z pouzdra.

Skládání malých písmen je podobné psaní malými písmeny, ale je agresivnější, protože je určeno k odstranění všech rozdílů mezi malými a malými písmeny v řetězci. Například německé malé písmeno „ß“ je ekvivalentní „ss“. Protože je to již malá písmena, lower() neudělá nic s 'ß'; casefold() převede jej na "ss".

Proto níže použijeme str.casefold() funkce pro všechny konverze a srovnání.

2. Porovnání definované aplikací

Pro vyhledávání všech Unicode symbolů bez rozlišení velkých a malých písmen musíme v aplikaci po připojení k databázi (dokumentaci) definovat nové řazení. Zde máte na výběr – přetížit vestavěný NOCASE nebo si vytvořte vlastní – níže probereme výhody a nevýhody. Pro příklad použijeme nový název:

import sqlite3

# Custom collation, maybe it is more efficient
# to store strings
def unicode_nocase_collation(a: str, b: str):
    if a.casefold() == b.casefold():
        return 0
    if a.casefold() < b.casefold():
        return -1
    return 1

connection.create_collation(
    "UNICODE_NOCASE", unicode_nocase_collation
)

# Connect to the DB and register the function
connection = sqlite3.connect("your_db_path")
connection.create_collation(
    "UNICODE_NOCASE", unicode_nocase_collation
)

# Or, if you use SQLAlchemy you need to register
# the collation via an event
@sa.event.listens_for(sa.engine.Engine, 'connect')
def sqlite_engine_connect(connection, _):
    connection.create_collation(
    "UNICODE_NOCASE", unicode_nocase_collation
)

Porovnání má několik výhod ve srovnání s následujícími řešeními:

1. Snadno se používají. Ve schématu tabulky můžete určit řazení a bude automaticky použito na všechny dotazy a indexy v tomto poli, pokud neurčíte jinak:
   

   CREATE TABLE test (text VARCHAR COLLATE UNICODE_NOCASE);
   

   Pro úplnost se podívejme na další dva způsoby použití porovnávání:
   

   -- In a particular query:
   SELECT * FROM items
       WHERE text = "Text in AnY case" COLLATE UNICODE_NOCASE;
   
   -- In an index:
   CREATE INDEX IF NOT EXISTS idx1 
       ON test (text COLLATE UNICODE_NOCASE);
   
   -- Word of caution: your query and index 
   -- must match exactly,including collation, 
   -- otherwise, SQLite will perform a full table scan.
   -- More on indexes below.
   EXPLAIN QUERY PLAN
       SELECT * FROM test WHERE text = 'something';
   -- Output: SCAN TABLE test
   EXPLAIN QUERY PLAN
       SELECT * FROM test WHERE text = 'something' COLLATE NOCASE;
   -- Output: SEARCH TABLE test USING COVERING INDEX idx1 (text=?)
   

2. Třídění umožňuje třídění bez ohledu na velikost písmen pomocí ORDER BY z krabice. Je obzvláště snadné jej získat, pokud definujete řazení ve schématu tabulky.

Výkonnostní kolace mají některé zvláštnosti, o kterých budeme dále diskutovat.

3. Aplikací definovaná funkce SQL

Dalším způsobem, jak dosáhnout vyhledávání bez rozlišení velkých a malých písmen, je vytvoření aplikace SQL funkce (dokumentace):

import sqlite3

# Custom function
def casefold(s: str):
    return s.casefold()

# Connect to the DB and register the function
connection = sqlite3.connect("your_db_path")
connection.create_function("CASEFOLD", 1, casefold)

# Or, if you use SQLAlchemy you need to register 
# the function via an event
@sa.event.listens_for(sa.engine.Engine, 'connect')
def sqlite_engine_connect(connection, _):
    connection.create_function("CASEFOLD", 1, casefold)

V obou případech create_function přijímá až čtyři argumenty:

• název funkce, jak bude použita v dotazech SQL
• počet argumentů, které funkce přijímá
• samotnou funkci
• volitelné bool deterministic , výchozí False (přidáno v Pythonu 3.8) – je důležité pro indexy, o kterých budeme diskutovat níže.

Stejně jako u porovnávání máte na výběr – přetížení vestavěné funkce (například LOWER ) nebo vytvořit nový. Podíváme se na to podrobněji později.

4. Porovnejte v aplikaci

Dalším způsobem vyhledávání bez rozlišení velkých a malých písmen by bylo porovnávání v samotné aplikaci, zvláště pokud byste mohli zúžit vyhledávání pomocí indexu v jiných polích. Například v listOK je pro položky v konkrétním seznamu potřeba srovnání bez ohledu na velikost písmen. Proto jsem mohl vybrat všechny položky v seznamu, normalizovat je na jeden případ a porovnat je s normalizovanou novou položkou.

V závislosti na vašich okolnostech to není špatné řešení, zvláště pokud je podmnožina, se kterou budete porovnávat, malá. Nebudete však moci využívat databázové indexy na text, pouze na další parametry, které budete používat ke zúžení rozsahu.

Výhodou tohoto přístupu je jeho flexibilita:v aplikaci můžete kontrolovat nejen rovnost, ale například implementovat „fuzzy“ porovnání, abyste zohlednili možné tiskové chyby, tvary jednotného/množného čísla atd. Toto je cesta, kterou jsem zvolil pro listOK protože bot potřeboval fuzzy srovnání pro vytvoření "chytrých" položek.

Navíc eliminuje jakékoli propojení s databází – jde o jednoduché úložiště, které o datech nic neví.

5. Uložte normalizované pole samostatně

Existuje ještě jedno řešení:vytvořte v databázi samostatný sloupec a ponechte si tam normalizovaný text, podle kterého budete hledat. Tabulka může mít například tuto strukturu (pouze relevantní pole):

Zpočátku to může vypadat přehnaně:vždy musíte udržovat normalizovanou verzi aktualizovanou a efektivně zdvojnásobit velikost name pole. Nicméně s ORM nebo dokonce manuálně je to snadné a místo na disku plus RAM jsou levné.

Výhody tohoto přístupu:

• Zcela odděluje aplikaci a databázi – můžete snadno přepínat.

• Pokud to vaše dotazy vyžadují, můžete předběžně zpracovat normalizovaný soubor (oříznout, odstranit interpunkci nebo mezery atd.).

Měli byste přetížit vestavěné funkce a porovnávání?

Při používání funkcí a porovnávání SQL definovaných aplikací máte často na výběr:použít jedinečný název nebo přetížit vestavěnou funkcionalitu. Oba přístupy mají svá pro a proti ve dvou hlavních dimenzích:

Za prvé, spolehlivost/předvídatelnost když z nějakého důvodu (jednorázová chyba, chyba nebo úmyslně) nezaregistrujete tyto funkce nebo porovnávání:

• Přetížení:databáze bude stále fungovat, ale výsledky nemusí být správné:

  • vestavěná funkce/kompletace se bude chovat jinak než jejich vlastní protějšky;
  • pokud jste nyní v indexu použili chybějící řazení, bude se zdát, že funguje, ale výsledky mohou být chybné i při čtení;
  • Pokud dojde k aktualizaci tabulky s indexem a indexem pomocí vlastní funkce/kolování, může dojít k poškození indexu (aktualizace pomocí vestavěné implementace), ale pokračovat v práci, jako by se nic nestalo.

• Nepřetěžování:databáze nebude fungovat v žádném ohledu tam, kde jsou použity chybějící funkce nebo porovnávání:

  • pokud použijete index na chybějící funkci, budete jej moci použít pro čtení, ale ne pro aktualizace;
  • indexy s řazením definovaným aplikací nebudou vůbec fungovat, protože používají řazení při vyhledávání v indexu.

Za druhé, dostupnost mimo hlavní aplikaci:migrace, analýzy atd.:

• Přetížení:budete moci bez problémů upravovat databázi, s ohledem na riziko poškození indexů.

• Nepřetěžování:v mnoha případech budete muset zaregistrovat tyto funkce nebo porovnávání nebo podniknout další kroky, abyste se vyhnuli částem databáze, které na nich závisí.

Pokud se rozhodnete přetížit, může být dobrým nápadem znovu sestavit indexy na základě vlastních funkcí nebo porovnávání pro případ, že se tam zaznamenají nesprávná data, například:

-- Rebuild all indexes using this collation
REINDEX YOUR_COLLATION_NAME;

-- Rebuild particular index
REINDEX index_name;

-- Rebuild all indexes
REINDEX;

Výkon funkcí a řazení definovaných aplikací

Vlastní funkce nebo řazení jsou mnohem pomalejší než vestavěné funkce:SQLite se „vrací“ do vaší aplikace pokaždé, když funkci volá. Můžete to snadno zkontrolovat přidáním globálního počítadla do funkce:

counter = 0

def casefold(a: str):
    global counter
    counter += 1
    return a.casefold()

# Work with the database

print(counter)
# Number of times the function has been called

Pokud se dotazujete zřídka nebo je vaše databáze malá, neuvidíte žádný smysluplný rozdíl. Pokud však pro tuto funkci/porovnání nepoužijete index, databáze může provést úplné prohledání tabulky s použitím funkce/porovnání na každý řádek. V závislosti na velikosti tabulky, hardwaru a počtu požadavků může překvapit nízký výkon. Později zveřejním přehled funkcí definovaných aplikací a výkonu porovnávání.

Přísně vzato, kolace jsou o něco pomalejší než funkce SQL, protože pro každé porovnání potřebují složit dva řetězce místo jednoho. I když je tento rozdíl velmi malý:v mých testech byla funkce Casefold rychlejší než podobné porovnávání přibližně o 25 %, což představovalo rozdíl 10 sekund po 100 milionech iterací.

Indexy a vyhledávání bez rozlišení velkých a malých písmen

Indexy a funkce

Začněme se základy:pokud definujete index pro libovolné pole, nebude použit v dotazech na funkci aplikovanou na toto pole:

CREATE TABLE table_name (id INTEGER, name VARCHAR);
CREATE INDEX idx1 ON table_name (name);
EXPLAIN QUERY PLAN
    SELECT id, name FROM table_name WHERE LOWER(name) = 'test';
-- Output: SCAN TABLE table_name

Pro takové dotazy potřebujete samostatný index se samotnou funkcí:

CREATE INDEX idx1 ON table_name (LOWER(name));
EXPLAIN QUERY PLAN
    SELECT id, name 
        FROM table_name WHERE LOWER(name) = 'test';
-- Output: SEARCH TABLE table_name USING INDEX idx1 (<expr>=?)

V SQLite to lze provést i na vlastní funkci, ale musí být označena jako deterministická (to znamená, že se stejnými vstupy vrací stejný výsledek):

connection.create_function(
    "CASEFOLD", 1, casefold, deterministic=True
)

Poté můžete vytvořit index pro vlastní funkci SQL:

CREATE INDEX idx1 
    ON table_name (CASEFOLD(name));
EXPLAIN QUERY PLAN
    SELECT id, name 
        FROM table_name WHERE CASEFOLD(name) = 'test';
-- Output: SEARCH TABLE table_name USING INDEX idx1 (<expr>=?)

Indexy a řazení

Situace s kolacemi a indexy je podobná:aby dotaz mohl využít index, musí použít stejné řazení (předpokládané nebo poskytnuté výslovně), jinak to nebude fungovat.

-- Table without specified collation will use BINARY
CREATE TABLE test (id INTEGER, text VARCHAR);

-- Create an index with a different collation
CREATE INDEX IF NOT EXISTS idx1 ON test (text COLLATE NOCASE);


-- Query will use default column collation -- BINARY
-- and the index will not be used
EXPLAIN QUERY PLAN
    SELECT * FROM test WHERE text = 'test';
-- Output: SCAN TABLE test


-- Now collations match and index is used
EXPLAIN QUERY PLAN
    SELECT * FROM test WHERE text = 'test' COLLATE NOCASE;
-- Output: SEARCH TABLE test USING INDEX idx1 (text=?)

Jak bylo uvedeno výše, řazení lze zadat pro sloupec ve schématu tabulky. Toto je nejpohodlnější způsob – použije se na všechny dotazy a indexy v příslušném poli automaticky, pokud neurčíte jinak:

-- Using application defined collation UNICODE_NOCASE from above
CREATE TABLE test (text VARCHAR COLLATE UNICODE_NOCASE);

-- Index will be built using the collation
CREATE INDEX idx1 ON test (text);

-- Query will utilize index and collation automatically
EXPLAIN QUERY PLAN
    SELECT * FROM test WHERE text = 'something';
-- Output: SEARCH TABLE test USING COVERING INDEX idx1 (text=?)

Jaké řešení zvolit?

Pro výběr řešení potřebujeme některá kritéria pro srovnání:

1. Jednoduchost – jak obtížné je jej zavést a udržovat

2. Výkon – jak rychlé budou vaše dotazy

3. Místo navíc – kolik dalšího databázového prostoru řešení vyžaduje

4. Spojka – jak moc vaše řešení propojuje kód a úložiště

Jako obvykle bude výběr řešení záviset na vašem případu použití a požadavcích na výkon. Osobně bych šel buď s vlastním řazením, porovnáváním v aplikaci nebo ukládáním normalizovaného řetězce. Například v listOK jsem nejprve použil porovnávání a po přidání fuzzy vyhledávání jsem v aplikaci přešel na porovnávání.