5 manieren om hoofdletterongevoelig zoeken in SQLite te implementeren met volledige Unicode-ondersteuning

Onlangs had ik een hoofdletterongevoelige zoekopdracht in SQLite nodig om te controleren of een item met dezelfde naam al bestaat in een van mijn projecten - listOK. In eerste instantie leek het een eenvoudige taak, maar bij een diepere duik bleek het gemakkelijk te zijn, maar helemaal niet eenvoudig, met veel wendingen.

Ingebouwde SQLite-mogelijkheden en hun nadelen

In SQLite kunt u op drie manieren een hoofdletterongevoelige zoekopdracht krijgen:

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

Als u SQLAlchemy en zijn ORM gebruikt, zien deze benaderingen er als volgt uit:

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

Al deze benaderingen zijn niet ideaal. Eerste , zonder speciale overwegingen maken ze geen gebruik van indexen op het veld waaraan ze werken, met LIKE de ergste overtreder zijn:in de meeste gevallen is het niet in staat om indexen te gebruiken. Hieronder vindt u meer over het gebruik van indexen voor niet-hoofdlettergevoelige zoekopdrachten.

Tweede , en wat nog belangrijker is, ze hebben een vrij beperkt begrip van wat niet-hoofdlettergevoelig betekent:

SQLite begrijpt standaard alleen hoofdletters/kleine letters voor ASCII-tekens. De LIKE-operator is hoofdlettergevoelig standaard voor Unicode-tekens die buiten het ASCII-bereik vallen. De uitdrukking 'a' LIKE 'A' is bijvoorbeeld TRUE, maar 'æ' LIKE 'Æ' is FALSE.

Het is geen probleem als je van plan bent om te werken met strings die alleen Engelse letters, cijfers, enz. bevatten. Ik had het volledige Unicode-spectrum nodig, dus een betere oplossing was op zijn plaats.

Hieronder vat ik vijf manieren samen om hoofdletterongevoelig te zoeken/vergelijken in SQLite voor alle Unicode-symbolen. Sommige van deze oplossingen kunnen worden aangepast aan andere databases en voor het implementeren van Unicode-bewuste LIKE , REGEXP , MATCH , en andere functies, hoewel deze onderwerpen buiten het bestek van dit bericht vallen.

We zullen kijken naar de voor- en nadelen van elke aanpak, implementatiedetails en, ten slotte, naar indexen en prestatieoverwegingen.

Oplossingen

1. ICU-verlenging

Officiële SQLite-documentatie vermeldt de ICU-extensie als een manier om volledige ondersteuning voor Unicode in SQLite toe te voegen. ICU staat voor International Components for Unicode.

ICU lost de problemen op van zowel hoofdlettergevoelige LIKE en vergelijken/zoeken, plus voegt voor een goede maatregel ondersteuning toe voor verschillende sorteringen. Het kan zelfs sneller zijn dan sommige van de latere oplossingen, omdat het is geschreven in C en nauwer is geïntegreerd met SQLite.

Het komt echter met zijn uitdagingen:

1. Het is een nieuw type van afhankelijkheid:geen Python-bibliotheek, maar een extensie die samen met de applicatie moet worden gedistribueerd.

2. ICU moet voor gebruik worden gecompileerd, mogelijk voor verschillende besturingssystemen en platforms (niet getest).

3. ICU implementeert zelf geen Unicode-conversies, maar vertrouwt op het onderstreepte besturingssysteem - ik heb meerdere keren melding gemaakt van OS-specifieke problemen, vooral met Windows en macOS.

Alle andere oplossingen zijn afhankelijk van uw Python-code om de vergelijking uit te voeren, dus het is belangrijk om de juiste benadering te kiezen voor het converteren en vergelijken van strings.

De juiste python-functie kiezen voor hoofdletterongevoelige vergelijking

Om hoofdletterongevoelige vergelijking en zoekactie uit te voeren, moeten we tekenreeksen normaliseren naar één hoofdletter. Mijn eerste instinct was om str.lower() . te gebruiken voor deze. Het zal in de meeste gevallen werken, maar het is niet de juiste manier. Het is beter om str.casefold() . te gebruiken (docs):

Retourneer een in een doos gevouwen kopie van de tekenreeks. Opgevouwen strings kunnen worden gebruikt voor caseless matching.

Casefolding lijkt op kleine letters, maar is agressiever omdat het bedoeld is om alle case-onderscheidingen in een string te verwijderen. De Duitse kleine letter 'ß' is bijvoorbeeld gelijk aan 'ss'. Omdat het al kleine letters zijn, lower() zou niets doen aan 'ß'; casefold() converteert het naar "ss".

Daarom gebruiken we hieronder de str.casefold() functie voor alle conversies en vergelijkingen.

2. Door de applicatie gedefinieerde sortering

Om een ​​hoofdletterongevoelige zoekopdracht voor alle Unicode-symbolen uit te voeren, moeten we een nieuwe sortering in de toepassing definiëren nadat we verbinding hebben gemaakt met de database (documentatie). Hier heb je een keuze - overbelast de ingebouwde NOCASE of maak je eigen - we zullen de voor- en nadelen hieronder bespreken. Omwille van een voorbeeld gebruiken we een nieuwe naam:

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
)

Verzamelingen hebben verschillende voordelen ten opzichte van de volgende oplossingen:

1. Ze zijn gemakkelijk te gebruiken. U kunt sortering specificeren in het tabelschema en het wordt automatisch toegepast op alle query's en indexen in dit veld, tenzij u anders opgeeft:
   

   CREATE TABLE test (text VARCHAR COLLATE UNICODE_NOCASE);
   

   Laten we voor de volledigheid nog twee manieren bekijken om sorteringen te gebruiken:
   

   -- 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. Sorteren biedt hoofdletterongevoelig sorteren met ORDER BY uit de doos. Het is vooral gemakkelijk te verkrijgen als u de sortering definieert in het tabelschema.

Prestatiegerichte sorteringen hebben enkele eigenaardigheden, die we verder zullen bespreken.

3. Door de toepassing gedefinieerde SQL-functie

Een andere manier om hoofdletterongevoelig te zoeken, is door een toepassingsgedefinieerde SQL-functie (documentatie) te maken:

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)

In beide gevallen create_function accepteert maximaal vier argumenten:

• naam van de functie zoals deze zal worden gebruikt in de SQL-query's
• aantal argumenten dat de functie accepteert
• de functie zelf
• optionele bool deterministic , standaard False (toegevoegd in Python 3.8) – het is belangrijk voor indexen, die we hieronder zullen bespreken.

Net als bij sorteringen heeft u de keuze:ingebouwde functie overbelasten (bijvoorbeeld LOWER ) of maak een nieuwe aan. We zullen er later in meer detail naar kijken.

4. Vergelijk in de applicatie

Een andere manier om hoofdletterongevoelig te zoeken, is vergelijken in de app zelf, vooral als u de zoekopdracht kunt verfijnen door een index op andere velden te gebruiken. In listOK is bijvoorbeeld een hoofdletterongevoelige vergelijking nodig voor items in een bepaalde lijst. Daarom kon ik alle items in de lijst selecteren, ze normaliseren tot één case en ze vergelijken met het genormaliseerde nieuwe item.

Afhankelijk van uw omstandigheden is het geen slechte oplossing, vooral als de subset waarmee u gaat vergelijken klein is. U kunt echter geen database-indexen voor de tekst gebruiken, alleen voor andere parameters die u zult gebruiken om het bereik te verkleinen.

Het voordeel van deze aanpak is de flexibiliteit:in de applicatie kun je niet alleen de gelijkheid controleren, maar bijvoorbeeld ook "fuzzy" vergelijking implementeren om rekening te houden met mogelijke drukfouten, enkelvoud/meervoudsvormen, enz. Dit is de route die ik heb gekozen voor listOK omdat de bot een vage vergelijking nodig had voor het maken van "slimme" items.

Bovendien elimineert het elke koppeling met de database - het is een eenvoudige opslag die niets over de gegevens weet.

5. Sla genormaliseerd veld apart op

Er is nog een oplossing:maak een aparte kolom aan in de database en bewaar de genormaliseerde tekst waarop je zoekt. De tabel kan bijvoorbeeld deze structuur hebben (alleen relevante velden):

Dit lijkt op het eerste gezicht misschien overdreven:u moet altijd de genormaliseerde versie up-to-date houden en de grootte van de name effectief verdubbelen veld. Met ORM's of zelfs handmatig is het echter gemakkelijk te doen en de schijfruimte plus RAM is relatief goedkoop.

Voordelen van deze aanpak:

• Het ontkoppelt de applicatie en de database volledig - je kunt gemakkelijk wisselen.

• U kunt genormaliseerde bestanden vooraf verwerken als uw vragen dit vereisen (bijsnijden, leestekens of spaties verwijderen, enz.).

Moet je ingebouwde functies en sorteringen overbelasten?

Bij het gebruik van applicatiegedefinieerde SQL-functies en sorteringen heeft u vaak de keuze:gebruik een unieke naam of overbelast ingebouwde functionaliteit. Beide benaderingen hebben hun voor- en nadelen in twee hoofddimensies:

Ten eerste, betrouwbaarheid/voorspelbaarheid wanneer u om de een of andere reden (een eenmalige fout, bug of opzettelijk) deze functies of sorteringen niet registreert:

• Overbelasting:de database zal nog steeds werken, maar de resultaten zijn mogelijk niet correct:

  • de ingebouwde functie/sortering zal zich anders gedragen dan hun aangepaste tegenhangers;
  • als je nu afwezige sortering in een index hebt gebruikt, lijkt het te werken, maar de resultaten kunnen zelfs tijdens het lezen verkeerd zijn;
  • als de tabel met index en index met aangepaste functie/sortering wordt bijgewerkt, kan de index beschadigd raken (bijgewerkt met ingebouwde implementatie), maar blijf werken alsof er niets is gebeurd.

• Niet overbelastend:de database zal in geen enkel opzicht werken als de afwezige functies of sorteringen worden gebruikt:

  • als u een index gebruikt voor een afwezige functie, kunt u deze gebruiken om te lezen, maar niet voor updates;
  • indexen met door een applicatie gedefinieerde sortering werken helemaal niet, omdat ze de sortering gebruiken tijdens het zoeken in de index.

Ten tweede, toegankelijkheid buiten de hoofdtoepassing:migraties, analyses, enz.:

• Overbelasting:u kunt de database zonder problemen wijzigen, rekening houdend met het risico op corrupte indexen.

• Niet overbelasten:in veel gevallen moet u deze functies of sorteringen registreren of extra stappen ondernemen om delen van de database te vermijden die ervan afhankelijk zijn.

Als u besluit te overbelasten, kan het een goed idee zijn om indexen opnieuw op te bouwen op basis van aangepaste functies of sorteringen voor het geval er verkeerde gegevens worden vastgelegd, bijvoorbeeld:

-- Rebuild all indexes using this collation
REINDEX YOUR_COLLATION_NAME;

-- Rebuild particular index
REINDEX index_name;

-- Rebuild all indexes
REINDEX;

Prestaties van door de applicatie gedefinieerde functies en sorteringen

Aangepaste functies of sortering zijn veel langzamer dan ingebouwde functies:SQLite "keert terug" naar uw toepassing telkens wanneer deze de functie aanroept. U kunt het eenvoudig controleren door een globale teller aan de functie toe te voegen:

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

Als u zelden query's uitvoert of uw database klein is, zult u geen betekenisvol verschil zien. Als u echter geen index voor deze functie/sortering gebruikt, kan de database een volledige tabelscan uitvoeren door de functie/sortering op elke rij toe te passen. Afhankelijk van de grootte van de tafel, de hardware en het aantal verzoeken, kunnen de lage prestaties verrassend zijn. Later zal ik een recensie publiceren van door de applicatie gedefinieerde functies en de prestaties van sorteringen.

Strikt genomen zijn collaties iets langzamer dan SQL-functies, omdat ze voor elke vergelijking twee strings moeten vouwen in plaats van één. Hoewel dit verschil erg klein is:in mijn tests was de casefold-functie ongeveer 25% sneller dan vergelijkbare sortering, wat neerkwam op een verschil van 10 seconden na 100 miljoen iteraties.

Indexen en hoofdletterongevoelig zoeken

Indexen en functies

Laten we beginnen met de basis:als u een index op een veld definieert, wordt deze niet gebruikt in query's op een functie die op dit veld wordt toegepast:

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

Voor dergelijke queries heb je een aparte index nodig met de functie zelf:

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

In SQLite kan het ook op een aangepaste functie worden gedaan, maar het moet als deterministisch worden gemarkeerd (wat betekent dat het met dezelfde invoer hetzelfde resultaat retourneert):

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

Daarna kunt u een index maken op een aangepaste SQL-functie:

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

Indexen en sorteringen

De situatie met sorteringen en indexen is vergelijkbaar:als een zoekopdracht een index wil gebruiken, moet deze dezelfde sortering gebruiken (impliciet of uitdrukkelijk verstrekt), anders werkt het niet.

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

Zoals hierboven vermeld, kan sortering worden opgegeven voor een kolom in het tabelschema. Dit is de handigste manier - het wordt automatisch toegepast op alle query's en indexen in het respectieve veld, tenzij u anders opgeeft:

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

Welke oplossing kiezen?

Om een ​​oplossing te kiezen, hebben we enkele vergelijkingscriteria nodig:

1. Eenvoud – hoe moeilijk het is om het te implementeren en te onderhouden

2. Prestaties - hoe snel uw zoekopdrachten zullen zijn

3. Extra ruimte – hoeveel extra databaseruimte de oplossing nodig heeft

4. Koppeling – hoeveel uw oplossing de code en opslag verweven

Zoals gewoonlijk hangt de keuze van de oplossing af van uw gebruikssituatie en prestatie-eisen. Persoonlijk zou ik kiezen voor aangepaste sortering, vergelijken in de app of een genormaliseerde reeks opslaan. In listOK heb ik bijvoorbeeld eerst een sortering gebruikt en ben ik overgegaan op vergelijken in de app toen ik vaag zoeken had toegevoegd.