5 sätt att implementera skiftlägeskänslig sökning i SQLite med fullt Unicode-stöd

Nyligen behövde jag en skiftlägesokänslig sökning i SQLite för att kontrollera om ett objekt med samma namn redan finns i ett av mina projekt – listOK. Till en början såg det ut som en enkel uppgift, men vid djupare dyk visade det sig vara lätt, men inte alls enkelt, med många vändningar.

Inbyggda SQLite-funktioner och deras nackdelar

I SQLite kan du få en skiftlägesokänslig sökning på tre sätt:

-- 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";

Om du använder SQLAlchemy och dess ORM kommer dessa metoder att se ut som följer:

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))

Alla dessa tillvägagångssätt är inte idealiska. Först , utan särskilda överväganden använder de inte index på fältet de arbetar med, med LIKE är den värsta förövaren:i de flesta fall är den oförmögen att använda index. Mer om användningen av index för skiftlägesokänsliga frågor finns nedan.

Andra , och ännu viktigare, de har en ganska begränsad förståelse för vad skiftlägesokänslig betyder:

SQLite förstår endast versaler/gemener för ASCII-tecken som standard. LIKE-operatorn är skiftlägeskänslig som standard för unicode-tecken som ligger utanför ASCII-intervallet. Till exempel är uttrycket 'a' LIKE 'A' SANT men 'æ' LIKE 'Æ' är FALSE.

Det är inte ett problem om du planerar att arbeta med strängar som bara innehåller bokstäver, siffror, etc. i engelska alfabetet. Jag behövde hela Unicode-spektrumet, så en bättre lösning var på sin plats.

Nedan sammanfattar jag fem sätt att uppnå skiftlägesokänslig sökning/jämförelse i SQLite för alla Unicode-symboler. Vissa av dessa lösningar kan anpassas till andra databaser och för implementering av Unicode-medveten LIKE , REGEXP , MATCH , och andra funktioner, även om dessa ämnen inte omfattas av detta inlägg.

Vi kommer att titta på för- och nackdelarna med varje tillvägagångssätt, implementeringsdetaljer och slutligen på index och prestandaöverväganden.

Lösningar

1. ICU-förlängning

Officiell SQLite-dokumentation nämner ICU-tillägget som ett sätt att lägga till komplett stöd för Unicode i SQLite. ICU står för International Components för Unicode.

ICU löser problemen med både skiftlägesokänsliga LIKE och jämförelse/sökning, plus lägger till stöd för olika sorteringar för en bra åtgärd. Det kan till och med vara snabbare än några av de senare lösningarna eftersom det är skrivet i C och är mer integrerat med SQLite.

Men det kommer med sina utmaningar:

1. Det är en ny typ beroende:inte ett Python-bibliotek, utan ett tillägg som ska distribueras tillsammans med applikationen.

2. ICU måste kompileras före användning, eventuellt för olika operativsystem och plattformar (ej testad).

3. ICU implementerar inte själv Unicode-konverteringar, utan förlitar sig på det understrukna operativsystemet – jag har sett flera omnämnanden av OS-specifika problem, särskilt med Windows och macOS.

Alla andra lösningar kommer att bero på din Python-kod för att utföra jämförelsen, så det är viktigt att välja rätt metod för att konvertera och jämföra strängar.

Att välja rätt python-funktion för skiftlägesokänslig jämförelse

För att utföra skiftlägesokänslig jämförelse och sökning måste vi normalisera strängar till ett fall. Min första instinkt var att använda str.lower() för detta. Det kommer att fungera i de flesta fall, men det är inte på rätt sätt. Bättre att använda str.casefold() (dokument):

Returnera en casefoldad kopia av strängen. Fodralvikta strängar kan användas för matchning utan fodral.

Casefolding liknar små bokstäver men mer aggressiv eftersom den är avsedd att ta bort alla skiftlägen i en sträng. Till exempel motsvarar den tyska gemena bokstaven "ß" "ss". Eftersom det redan är gemener, lower() skulle inte göra något åt ​​'ß'; casefold() konverterar det till "ss".

Därför kommer vi nedan att använda str.casefold() funktion för alla konverteringar och jämförelser.

2. Programdefinierad sortering

För att utföra en skiftlägesokänslig sökning efter alla Unicode-symboler måste vi definiera en ny sortering i applikationen efter att ha anslutit till databasen (dokumentation). Här har du ett val – överbelasta den inbyggda NOCASE eller skapa din egen – vi kommer att diskutera för- och nackdelarna nedan. För ett exempel kommer vi att använda ett nytt namn:

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
)

Kollationer har flera fördelar jämfört med nästa lösningar:

1. De är lätta att använda. Du kan ange sortering i tabellschemat och det kommer att tillämpas automatiskt på alla frågor och index i det här fältet om du inte anger något annat:
   

   CREATE TABLE test (text VARCHAR COLLATE UNICODE_NOCASE);
   

   För fullständighetens skull, låt oss titta på ytterligare två sätt att använda sammanställningar:
   

   -- 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. Sortering ger skiftlägeskänslig sortering med ORDER BY utanför lådan. Det är särskilt lätt att få om du definierar sorteringen i tabellschemat.

Prestandamässiga sammanställningar har vissa egenheter, som vi kommer att diskutera vidare.

3. Tillämpningsdefinierad SQL-funktion

Ett annat sätt att uppnå skiftlägesokänslig sökning är att skapa en applikationsdefinierad SQL-funktion (dokumentation):

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)

I båda fallen create_function accepterar upp till fyra argument:

• namnet på funktionen som den kommer att användas i SQL-frågorna
• antal argument som funktionen accepterar
• själva funktionen
• valfri bool deterministic , standard False (tillagt i Python 3.8) – det är viktigt för index, vilket vi kommer att diskutera nedan.

Precis som med sorteringar har du ett val – överbelasta inbyggd funktion (till exempel LOWER ) eller skapa nya. Vi kommer att titta på det mer i detalj senare.

4. Jämför i applikationen

Ett annat sätt för skiftlägesokänslig sökning skulle vara att jämföra i själva appen, särskilt om du kan begränsa sökningen genom att använda ett index på andra fält. Till exempel, i listOK behövs skiftlägesokänslig jämförelse för objekt i en viss lista. Därför kunde jag välja alla objekt i listan, normalisera dem till ett fall och jämföra dem med det normaliserade nya objektet.

Beroende på dina omständigheter är det ingen dålig lösning, särskilt om den delmängd du kommer att jämföra med är liten. Du kommer dock inte att kunna använda databasindex på texten, bara på andra parametrar som du kommer att använda för att begränsa omfattningen.

Fördelen med detta tillvägagångssätt är dess flexibilitet:i applikationen kan du inte bara kontrollera jämlikhet utan till exempel implementera "suddig" jämförelse för att ta hänsyn till möjliga tryckfel, singular-/pluralformer etc. Detta är den väg jag valde för listOK eftersom boten behövde suddig jämförelse för att skapa "smarta" objekt.

Dessutom eliminerar det all koppling till databasen – det är enkel lagring som inte vet något om data.

5. Lagra normaliserade fält separat

Det finns ytterligare en lösning:skapa en separat kolumn i databasen och håll kvar normaliserad text som du kommer att söka på. Tabellen kan till exempel ha denna struktur (endast relevanta fält):

Detta kan se överdrivet ut till en början:du måste alltid hålla den normaliserade versionen uppdaterad och effektivt dubbla storleken på name fält. Men med ORM eller till och med manuellt är det lätt att göra och diskutrymmet plus RAM är relativt billigt.

Fördelar med detta tillvägagångssätt:

• Det frikopplar helt applikationen och databasen – du kan enkelt byta.

• Du kan förbehandla normaliserade arkiverade filer om dina frågor kräver det (trimma, ta bort skiljetecken eller mellanslag, etc.).

Ska du överbelasta inbyggda funktioner och sammanställningar?

När du använder applikationsdefinierade SQL-funktioner och kollationer har du ofta ett val:använd ett unikt namn eller överbelasta inbyggd funktionalitet. Båda tillvägagångssätten har sina för- och nackdelar i två huvuddimensioner:

Först, tillförlitlighet/förutsägbarhet när du av någon anledning (ett engångsfel, bugg eller avsiktligt) inte registrerar dessa funktioner eller sammanställningar:

• Överbelastning:databasen kommer fortfarande att fungera, men resultaten kanske inte är korrekta:

  • den inbyggda funktionen/sorteringen kommer att bete sig annorlunda än sina anpassade motsvarigheter;
  • om du använde nu frånvarande sortering i ett index verkar det fungera, men resultaten kan bli felaktiga även vid läsning;
  • om tabellen med index och index som använder anpassad funktion/sortering uppdateras, kan indexet skadas (uppdateras med inbyggd implementering), men fortsätter att fungera som om ingenting hänt.

• Överbelastas inte:databasen kommer inte att fungera på något sätt där de frånvarande funktionerna eller sammanställningarna används:

  • om du använder ett index på en frånvarande funktion kommer du att kunna använda det för läsning, men inte för uppdateringar;
  • index med programdefinierad sortering fungerar inte alls, eftersom de använder sorteringen när de söker i indexet.

För det andra, tillgänglighet utanför huvudapplikationen:migrering, analys, etc.:

• Överbelastning:du kommer att kunna modifiera databasen utan problem, med tanke på risken för korrupta index.

• Inte överbelasta:i många fall måste du registrera dessa funktioner eller sammanställningar eller vidta extra åtgärder för att undvika delar av databasen som är beroende av den.

Om du bestämmer dig för att överbelasta kan det vara en bra idé att bygga om index baserat på anpassade funktioner eller sammanställningar ifall de får fel data registrerad där, till exempel:

-- Rebuild all indexes using this collation
REINDEX YOUR_COLLATION_NAME;

-- Rebuild particular index
REINDEX index_name;

-- Rebuild all indexes
REINDEX;

Prestanda för applikationsdefinierade funktioner och sammanställningar

Anpassade funktioner eller sortering är mycket långsammare än inbyggda funktioner:SQLite "återgår" till din applikation varje gång den anropar funktionen. Du kan enkelt kontrollera det genom att lägga till en global räknare till funktionen:

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

Om du frågar sällan eller om din databas är liten kommer du inte att se någon meningsfull skillnad. Men om du inte använder ett index på den här funktionen/sorteringen, kan databasen utföra en fullständig tabellskanning och tillämpa funktionen/sorteringen på varje rad. Beroende på storleken på tabellen, hårdvaran och antalet förfrågningar kan den låga prestandan vara förvånande. Senare kommer jag att publicera en recension av applikationsdefinierade funktioner och sammanställningsprestanda.

Strängt taget är sammanställningar lite långsammare än SQL-funktioner eftersom de för varje jämförelse behöver skifta två strängar istället för en. Även om denna skillnad är mycket liten:i mina tester var fallfoldningsfunktionen snabbare än liknande sammanställning med cirka 25 %, vilket uppgick till en skillnad på 10 sekunder efter 100 miljoner iterationer.

Index och skiftlägesokänslig sökning

Index och funktioner

Låt oss börja med grunderna:om du definierar ett index på något fält, kommer det inte att användas i frågor om en funktion som tillämpas på detta fält:

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

För sådana frågor behöver du ett separat index med själva funktionen:

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>=?)

I SQLite kan det också göras på en anpassad funktion, men den måste markeras som deterministisk (vilket betyder att med samma indata returnerar den samma resultat):

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

Efter det kan du skapa ett index på en anpassad SQL-funktion:

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>=?)

Indexer och sammanställningar

Situationen med sammanställningar och index är liknande:för att en fråga ska kunna använda ett index måste de använda samma sammanställning (underförstått eller uttryckligen tillhandahållet), annars kommer det inte att fungera.

-- 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=?)

Som nämnts ovan kan sortering anges för en kolumn i tabellschemat. Detta är det bekvämaste sättet – det kommer att tillämpas på alla frågor och index i respektive fält automatiskt om du inte anger något annat:

-- 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=?)

Vilken lösning ska man välja?

För att välja en lösning behöver vi några kriterier för jämförelse:

1. Enkelhet – hur svårt det är att implementera och underhålla det

2. Prestanda – hur snabba dina frågor kommer att vara

3. Extra utrymme – hur mycket extra databasutrymme lösningen kräver

4. Koppling – hur mycket din lösning flätar ihop koden och lagringen

Som vanligt kommer valet av lösning att bero på ditt användningsfall och prestandakrav. Personligen skulle jag välja antingen anpassad sortering, jämföra i appen eller lagra en normaliserad sträng. Till exempel, i listOK, använde jag först en sortering och gick över till att jämföra i appen när jag lade till fuzzy sökning.