5 façons d'implémenter une recherche insensible à la casse dans SQLite avec prise en charge complète d'Unicode

Récemment, j'avais besoin d'une recherche insensible à la casse dans SQLite pour vérifier si un élément portant le même nom existe déjà dans l'un de mes projets - listOK. Au début, cela ressemblait à une tâche simple, mais après une plongée plus profonde, cela s'est avéré facile, mais pas simple du tout, avec de nombreux rebondissements.

Fonctionnalités SQLite intégrées et leurs inconvénients

Dans SQLite, vous pouvez obtenir une recherche insensible à la casse de trois manières :

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

Si vous utilisez SQLAlchemy et son ORM, ces approches ressembleront à ceci :

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

Toutes ces approches ne sont pas idéales. Premier , sans considérations particulières, ils n'utilisent pas d'index sur le champ sur lequel ils travaillent, avec LIKE être le pire contrevenant :dans la plupart des cas, il est incapable d'utiliser des index. Vous trouverez ci-dessous plus d'informations sur l'utilisation des index pour les requêtes insensibles à la casse.

Deuxième , et plus important encore, ils ont une compréhension plutôt limitée de ce que signifie insensible à la casse :

SQLite ne comprend que les majuscules/minuscules pour les caractères ASCII par défaut. L'opérateur LIKE est sensible à la casse par défaut pour les caractères Unicode qui sont au-delà de la plage ASCII. Par exemple, l'expression 'a' LIKE 'A' est TRUE mais 'æ' LIKE 'Æ' est FALSE.

Ce n'est pas un problème si vous prévoyez de travailler avec des chaînes qui ne contiennent que des lettres de l'alphabet anglais, des chiffres, etc. J'avais besoin du spectre Unicode complet, donc une meilleure solution s'imposait.

Ci-dessous, je résume cinq façons de réaliser une recherche/comparaison insensible à la casse dans SQLite pour tous les symboles Unicode. Certaines de ces solutions peuvent être adaptées à d'autres bases de données et pour implémenter LIKE compatible Unicode , REGEXP , MATCH , et d'autres fonctions, bien que ces sujets sortent du cadre de cet article.

Nous examinerons les avantages et les inconvénients de chaque approche, les détails de mise en œuvre et, enfin, les index et les considérations de performances.

Solution

1. Extension USI

La documentation officielle de SQLite mentionne l'extension ICU comme un moyen d'ajouter une prise en charge complète d'Unicode dans SQLite. ICU signifie Composants internationaux pour Unicode.

ICU résout les problèmes de LIKE insensibles à la casse et comparaison/recherche, plus ajoute la prise en charge de différentes collations pour une bonne mesure. Il peut même être plus rapide que certaines des solutions les plus récentes car il est écrit en C et est plus étroitement intégré à SQLite.

Cependant, cela vient avec ses défis :

1. C'est un nouveau type de dépendance :pas une bibliothèque Python, mais une extension qui doit être distribuée avec l'application.

2. ICU doit être compilé avant utilisation, potentiellement pour différents systèmes d'exploitation et plates-formes (non testé).

3. ICU n'implémente pas lui-même les conversions Unicode, mais s'appuie sur le système d'exploitation souligné - j'ai vu plusieurs mentions de problèmes spécifiques au système d'exploitation, en particulier avec Windows et macOS.

Toutes les autres solutions dépendront de votre code Python pour effectuer la comparaison, il est donc important de choisir la bonne approche pour convertir et comparer les chaînes.

Choisir la bonne fonction python pour une comparaison insensible à la casse

Pour effectuer une comparaison et une recherche insensibles à la casse, nous devons normaliser les chaînes à une seule casse. Mon premier réflexe a été d'utiliser str.lower() pour ça. Cela fonctionnera dans la plupart des cas, mais ce n'est pas la bonne méthode. Mieux vaut utiliser str.casefold() (documents) :

Renvoie une copie pliée de la chaîne. Les chaînes mises en casse peuvent être utilisées pour une correspondance sans casse.

Le pliage de casse est similaire à la minuscule mais plus agressif car il est destiné à supprimer toutes les distinctions de casse dans une chaîne. Par exemple, la lettre minuscule allemande "ß" équivaut à "ss". Comme il est déjà en minuscules, lower() ne ferait rien à 'ß'; casefold() le convertit en "ss".

Par conséquent, ci-dessous, nous utiliserons le str.casefold() fonction pour toutes les conversions et comparaisons.

2. Classement défini par l'application

Pour effectuer une recherche insensible à la casse pour tous les symboles Unicode, nous devons définir un nouveau classement dans l'application après la connexion à la base de données (documentation). Ici, vous avez le choix - surchargez le NOCASE intégré ou créez le vôtre - nous discuterons des avantages et des inconvénients ci-dessous. À titre d'exemple, nous utiliserons un nouveau nom :

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
)

Les classements présentent plusieurs avantages par rapport aux solutions suivantes :

1. Ils sont faciles à utiliser. Vous pouvez spécifier le classement dans le schéma de la table et il sera automatiquement appliqué à toutes les requêtes et tous les index sur ce champ, sauf indication contraire :
   

   CREATE TABLE test (text VARCHAR COLLATE UNICODE_NOCASE);
   

   Par souci d'exhaustivité, examinons deux autres façons d'utiliser les classements :
   

   -- 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. Le classement fournit un tri insensible à la casse avec ORDER BY hors de la boîte. Il est particulièrement facile à obtenir si vous définissez le classement dans le schéma de la table.

Les classements en termes de performances présentent certaines particularités, dont nous discuterons plus loin.

3. Fonction SQL définie par l'application

Une autre façon d'effectuer une recherche insensible à la casse consiste à créer une fonction SQL définie par l'application (documentation) :

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)

Dans les deux cas create_function accepte jusqu'à quatre arguments :

• nom de la fonction tel qu'il sera utilisé dans les requêtes SQL
• nombre d'arguments acceptés par la fonction
• la fonction elle-même
• booléen facultatif deterministic , par défaut False (ajouté dans Python 3.8) - il est important pour les index, dont nous parlerons ci-dessous.

Comme pour les classements, vous avez le choix :surchargez la fonction intégrée (par exemple, LOWER ) ou créer un nouveau. Nous l'examinerons plus en détail plus tard.

4. Comparez dans l'application

Une autre méthode de recherche insensible à la casse serait de comparer dans l'application elle-même, surtout si vous pouviez affiner la recherche en utilisant un index sur d'autres champs. Par exemple, dans listOK, une comparaison insensible à la casse est nécessaire pour les éléments d'une liste particulière. Par conséquent, je pouvais sélectionner tous les éléments de la liste, les normaliser à un cas et les comparer avec le nouvel élément normalisé.

Selon votre situation, ce n'est pas une mauvaise solution, surtout si le sous-ensemble avec lequel vous comparerez est petit. Cependant, vous ne pourrez pas utiliser les index de base de données sur le texte, uniquement sur d'autres paramètres que vous utiliserez pour réduire la portée.

L'avantage de cette approche est sa flexibilité :dans l'application, vous pouvez non seulement vérifier l'égalité mais, par exemple, implémenter une comparaison "floue" pour prendre en compte d'éventuelles fautes d'impression, des formes singulier/pluriel, etc. C'est la voie que j'ai choisie pour listOK car le bot avait besoin d'une comparaison floue pour la création "intelligente" de l'élément.

De plus, il élimine tout couplage avec la base de données - c'est un simple stockage qui ne sait rien des données.

5. Stockez le champ normalisé séparément

Il existe une autre solution :créez une colonne distincte dans la base de données et conservez-y le texte normalisé sur lequel vous effectuerez la recherche. Par exemple, le tableau peut avoir cette structure (uniquement les champs pertinents) :

Cela peut sembler excessif au premier abord :vous devez toujours maintenir la version normalisée à jour et effectivement doubler la taille du name domaine. Cependant, avec les ORM ou même manuellement, c'est facile à faire et l'espace disque plus la RAM est relativement bon marché.

Avantages de cette approche :

• Il dissocie complètement l'application et la base de données - vous pouvez facilement basculer.

• Vous pouvez pré-traiter le fichier normalisé si vos requêtes l'exigent (couper, supprimer la ponctuation ou les espaces, etc.).

 Devez-vous surcharger les fonctions et classements intégrés ?

Lorsque vous utilisez des fonctions et des classements SQL définis par l'application, vous avez souvent le choix :utiliser un nom unique ou surcharger la fonctionnalité intégrée. Les deux approches ont leurs avantages et leurs inconvénients dans deux dimensions principales :

Premièrement, fiabilité/prévisibilité lorsque pour une raison quelconque (une erreur ponctuelle, un bogue ou intentionnellement), vous n'enregistrez pas ces fonctions ou classements :

• Surcharge :la base de données fonctionnera toujours, mais les résultats peuvent ne pas être corrects :

  • la fonction/le classement intégré se comportera différemment de ses homologues personnalisés ;
  • si vous avez utilisé le classement maintenant absent dans un index, cela semblera fonctionner, mais les résultats peuvent être erronés même lors de la lecture ;
  • si la table avec index et index utilisant une fonction/un classement personnalisé est mise à jour, l'index peut être corrompu (mis à jour à l'aide de l'implémentation intégrée), mais continue de fonctionner comme si de rien n'était.

• Pas de surcharge :la base de données ne fonctionnera en aucun cas là où les fonctions ou classements absents sont utilisés :

  • si vous utilisez un index sur une fonction absente vous pourrez l'utiliser pour la lecture, mais pas pour les mises à jour ;
  • les index avec un classement défini par l'application ne fonctionneront pas du tout, car ils utilisent le classement lors de la recherche dans l'index.

Deuxièmement, l'accessibilité en dehors de l'application principale :migrations, analyses, etc. :

• Surcharge :vous pourrez modifier la base de données sans problème, en gardant à l'esprit le risque de corruption des index.

• Ne pas surcharger :dans de nombreux cas, vous devrez enregistrer ces fonctions ou classements ou prendre des mesures supplémentaires pour éviter les parties de la base de données qui en dépendent.

Si vous décidez de surcharger, il peut être judicieux de reconstruire les index en fonction de fonctions ou de classements personnalisés au cas où des données erronées y seraient enregistrées, par exemple :

-- Rebuild all indexes using this collation
REINDEX YOUR_COLLATION_NAME;

-- Rebuild particular index
REINDEX index_name;

-- Rebuild all indexes
REINDEX;

Performances des fonctions et classements définis par l'application

Les fonctions personnalisées ou le classement sont beaucoup plus lents que les fonctions intégrées :SQLite "retourne" à votre application chaque fois qu'elle appelle la fonction. Vous pouvez facilement le vérifier en ajoutant un compteur global à la fonction :

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

Si vous interrogez rarement ou si votre base de données est petite, vous ne verrez aucune différence significative. Cependant, si vous n'utilisez pas d'index sur cette fonction/collation, la base de données peut effectuer une analyse complète de la table en appliquant la fonction/collation sur chaque ligne. Selon la taille de la table, le matériel et le nombre de requêtes, la faible performance peut être surprenante. Plus tard, je publierai un examen des fonctions définies par l'application et des performances des classements.

Strictement parlant, les classements sont un peu plus lents que les fonctions SQL car pour chaque comparaison, ils doivent plier deux chaînes au lieu d'une. Bien que cette différence soit très faible :lors de mes tests, la fonction Casefold était plus rapide que le classement similaire pour environ 25 %, ce qui équivalait à une différence de 10 secondes après 100 millions d'itérations.

Index et recherche insensible à la casse

Index et fonctions

Commençons par les bases :si vous définissez un index sur n'importe quel champ, il ne sera pas utilisé dans les requêtes sur une fonction appliquée à ce champ :

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

Pour de telles requêtes, vous avez besoin d'un index séparé avec la fonction elle-même :

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

Dans SQLite, cela peut également être fait sur une fonction personnalisée, mais elle doit être marquée comme déterministe (ce qui signifie qu'avec les mêmes entrées, elle renvoie le même résultat) :

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

Après cela, vous pouvez créer un index sur une fonction SQL personnalisée :

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

Index et classements

La situation avec les classements et les index est similaire :pour qu'une requête utilise un index, elle doit utiliser le même classement (implicite ou fourni expressément), sinon cela ne fonctionnera pas.

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

Comme indiqué ci-dessus, le classement peut être spécifié pour une colonne dans le schéma de table. C'est le moyen le plus pratique - il sera automatiquement appliqué à toutes les requêtes et index sur le champ respectif, sauf indication contraire :

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

Quelle solution choisir ?

Pour choisir une solution, nous avons besoin de quelques critères de comparaison :

1. Simplicité – combien il est difficile de le mettre en œuvre et de le maintenir

2. Performances – la rapidité de vos requêtes

3. Espace supplémentaire – combien d'espace de base de données supplémentaire la solution nécessite

4. Couplage – dans quelle mesure votre solution mêle code et stockage

Comme d'habitude, le choix de la solution dépendra de votre cas d'utilisation et de vos exigences en matière de performances. Personnellement, j'opterais pour un classement personnalisé, une comparaison dans l'application ou le stockage d'une chaîne normalisée. Par exemple, dans listOK, j'ai d'abord utilisé un classement et je suis passé à la comparaison dans l'application lors de l'ajout d'une recherche floue.