5 начина за внедряване на търсене, независимо от главните букви, в SQLite с пълна поддръжка на Unicode

Наскоро имах нужда от търсене в SQLite, независимо от главните букви, за да проверя дали вече съществува елемент със същото име в един от моите проекти – listOK. Първоначално изглеждаше като проста задача, но след по-дълбоко гмуркане се оказа лесна, но никак не проста, с много обрати.

Вградените възможности на SQLite и техните недостатъци

В SQLite можете да получите нечувствително търсене по три начина:

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

Ако използвате SQLAlchemy и неговия ORM, тези подходи ще изглеждат по следния начин:

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

Всички тези подходи не са идеални. Първо , без специални съображения те не използват индекси в областта, върху която работят, с LIKE като най-лошият нарушител:в повечето случаи не е в състояние да използва индекси. Повече за използването на индекси за заявки, нечувствителни към главни букви, е по-долу.

Втори , и което е по-важно, те имат доста ограничено разбиране за това какво означават независими от главни букви:

SQLite разбира само главни/малки букви за ASCII знаци по подразбиране. Операторът LIKE е чувствителен към малките букви по подразбиране за unicode символи, които са извън обхвата на ASCII. Например изразът 'a' LIKE 'A' е ВЯРЕН, но 'æ' LIKE 'Æ' е FALSE.

Не е проблем, ако планирате да работите с низове, които съдържат само букви, цифри на английската азбука и т.н. Имах нужда от пълния спектър на Unicode, така че трябваше по-добро решение.

По-долу обобщавам пет начина за постигане на търсене/сравнение без значение на главни и малки букви в SQLite за всички символи на Unicode. Някои от тези решения могат да бъдат адаптирани към други бази данни и за внедряване на Unicode-съобразен LIKE , REGEXP , MATCH , и други функции, въпреки че тези теми са извън обхвата на тази публикация.

Ще разгледаме плюсовете и минусите на всеки подход, подробностите за внедряването и накрая, индексите и съображенията за производителност.

Решения

1. Разширение за интензивно лечение

Официалната документация на SQLite споменава разширението на ICU като начин за добавяне на пълна поддръжка за Unicode в SQLite. ICU означава международни компоненти за Unicode.

ICU решава проблемите и на двата нечувствителни LIKE и сравнение/търсене, плюс добавя поддръжка за различни съпоставяния за добра мярка. Може дори да е по-бърз от някои от по-късните решения, тъй като е написан на C и е по-тясно интегриран със SQLite.

Това обаче идва със своите предизвикателства:

1. Това е нов вид на зависимост:не библиотека на Python, а разширение, което трябва да се разпространява заедно с приложението.

2. ICU трябва да бъде компилиран преди употреба, потенциално за различни ОС и платформи (не е тестван).

3. ICU сам по себе си не прилага преобразувания в Unicode, а разчита на подчертаната операционна система – виждал съм многократно споменаване на проблеми, специфични за ОС, особено с Windows и macOS.

Всички други решения ще зависят от вашия Python код за извършване на сравнението, така че е важно да изберете правилния подход за преобразуване и сравняване на низове.

Избор на правилната функция на Python за сравнение без значение на главни букви

За да извършим сравнение и търсене, независимо от главните букви, трябва да нормализираме низовете към един регистър. Първият ми инстинкт беше да използвам str.lower() за това. При повечето обстоятелства ще работи, но не е правилният начин. По-добре да използвате str.casefold() (документи):

Върнете сгънато в регистър копие на низа. Сгънати низове могат да се използват за съвпадение без регистър.

Сгъването на малки букви е подобно на малките букви, но е по-агресивно, тъй като е предназначено да премахне всички разлики на малки букви в низа. Например, немската малка буква „ß“ е еквивалентна на „ss“. Тъй като вече е с малки букви, lower() няма да направи нищо на 'ß'; casefold() го преобразува в "ss".

Следователно по-долу ще използваме str.casefold() функция за всички преобразувания и сравнения.

2. Съпоставяне, дефинирано от приложението

За да извършим търсене без значение на главни и малки букви за всички символи на Unicode, трябва да дефинираме ново съпоставяне в приложението след свързване с базата данни (документация). Тук имате избор – претоварете вградения NOCASE или създайте свой собствен – ние ще обсъдим плюсовете и минусите по-долу. За пример ще използваме ново име:

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
)

Сравненията имат няколко предимства в сравнение със следните решения:

1. Те са лесни за използване. Можете да посочите съпоставяне в схемата на таблицата и то ще се прилага автоматично към всички заявки и индекси в това поле, освен ако не посочите друго:
   

   CREATE TABLE test (text VARCHAR COLLATE UNICODE_NOCASE);
   

   За пълнота, нека разгледаме още два начина за използване на съпоставяния:
   

   -- 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. Съпоставянето осигурява сортиране независимо от главните букви с ORDER BY извън кутията. Особено лесно е да го получите, ако дефинирате съпоставянето в схемата на таблицата.

Съпоставянията по отношение на производителността имат някои особености, които ще обсъдим по-нататък.

3. Дефинирана от приложението SQL функция

Друг начин за постигане на търсене, независимо от главните букви, е да се създаде SQL функция, дефинирана от приложението (документация):

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)

И в двата случая create_function приема до четири аргумента:

• име на функцията, както ще се използва в SQL заявките
• брой аргументи, които функцията приема
• самата функция
• по избор bool deterministic , по подразбиране False (добавено в Python 3.8) – важно е за индексите, които ще обсъдим по-долу.

Както при съпоставянията, имате избор – претоварване на вградената функция (например LOWER ) или създайте нов. Ще го разгледаме по-подробно по-късно.

4. Сравнете в приложението

Друг начин за търсене, независимо от главните букви, би било сравняването в самото приложение, особено ако можете да стесните търсенето, като използвате индекс в други полета. Например, в listOK е необходимо сравнение, независимо от главните букви, за елементи в конкретен списък. Следователно можех да избера всички елементи в списъка, да ги нормализирам в един случай и да ги сравня с нормализирания нов елемент.

В зависимост от вашите обстоятелства това не е лошо решение, особено ако подмножеството, с което ще сравнявате, е малко. Въпреки това няма да можете да използвате индекси на база данни за текста, а само за други параметри, които ще използвате, за да стесните обхвата.

Предимството на този подход е неговата гъвкавост:в приложението можете да проверите не само равенството, но, например, да приложите „размито“ сравнение, за да вземете предвид възможни печатни грешки, форми за единствено/множествено число и т.н. Това е маршрутът, който избрах за listOK тъй като ботът се нуждаеше от неясно сравнение за създаването на „интелигентен“ елемент.

Освен това елиминира всякакво свързване с базата данни – това е просто съхранение, което не знае нищо за данните.

5. Съхранявайте нормализираното поле отделно

Има още едно решение:създайте отделна колона в базата данни и задръжте там нормализиран текст, в който ще търсите. Например таблицата може да има следната структура (само съответните полета):

Това може да изглежда прекомерно в началото:винаги трябва да поддържате нормализираната версия актуализирана и ефективно да удвоявате размера на name поле. Въпреки това, с ORM или дори ръчно това е лесно да се направи, а дисковото пространство плюс RAM е относително евтино.

Предимства на този подход:

• Той напълно разделя приложението и базата данни – можете лесно да превключвате.

• Можете да обработите предварително нормализирано файл, ако вашите заявки го изискват (отрежете, премахнете пунктуацията или интервалите и т.н.).

Трябва ли да претоварите вградените функции и съпоставяния?

Когато използвате дефинирани от приложението SQL функции и съпоставяния, често имате избор:да използвате уникално име или да претоварите вградената функционалност. И двата подхода имат своите плюсове и минуси в две основни измерения:

Първо,надеждност/предвидимост когато по някаква причина (еднократна грешка, бъг или умишлено) не регистрирате тези функции или съпоставяния:

• Претоварване:базата данни ще продължи да работи, но резултатите може да не са правилни:

  • вградената функция/колекция ще се държи по различен начин от техните персонализирани аналози;
  • ако сте използвали съпоставяне сега отсъстващо в индекс, изглежда, че работи, но резултатите може да са грешни дори при четене;
  • ако таблицата с индекс и индекс с помощта на персонализирана функция/съпоставяне се актуализира, индексът може да се повреди (актуализиран чрез вградена реализация), но да продължи да работи, сякаш нищо не се е случило.

• Не се претоварва:базата данни няма да работи в никакви отношения, където се използват отсъстващите функции или съпоставяния:

  • ако използвате индекс за отсъстваща функция, ще можете да го използвате за четене, но не и за актуализации;
  • Индексите с дефинирано от приложението съпоставяне изобщо няма да работят, тъй като използват съпоставянето, докато търсят в индекса.

Второ,достъпност извън основното приложение:миграции, анализи и др.:

• Претоварване:ще можете да модифицирате базата данни без проблем, като имате предвид риска от повреда на индекси.

• Без претоварване:в много случаи ще трябва да регистрирате тези функции или съпоставяния или да предприемете допълнителни стъпки, за да избегнете части от базата данни, които зависят от нея.

Ако решите да претоварите, може да е добра идея да изградите отново индекси въз основа на персонализирани функции или съпоставяния, в случай че получат грешни данни, записани там, например:

-- Rebuild all indexes using this collation
REINDEX YOUR_COLLATION_NAME;

-- Rebuild particular index
REINDEX index_name;

-- Rebuild all indexes
REINDEX;

Изпълнение на дефинирани от приложението функции и съпоставяне

Персонализираните функции или съпоставянето са много по-бавни от вградените функции:SQLite се "връща" към вашето приложение всеки път, когато извика функцията. Можете лесно да го проверите, като добавите глобален брояч към функцията:

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

Ако отправяте заявки рядко или вашата база данни е малка, няма да видите никаква значима разлика. Въпреки това, ако не използвате индекс за тази функция/съпоставяне, базата данни може да извърши пълно сканиране на таблицата, прилагайки функцията/съпоставянето на всеки ред. В зависимост от размера на таблицата, хардуера и броя на заявките, ниската производителност може да е изненадваща. По-късно ще публикувам преглед на дефинираните от приложението функции и ефективността на съпоставянето.

Строго погледнато, съпоставянето е малко по-бавно от SQL функциите, тъй като за всяко сравнение те трябва да сгънат два низа вместо един. Въпреки че тази разлика е много малка:в моите тестове функцията за сгъване на регистри беше по-бърза от подобното съпоставяне за около 25%, което представлява разлика от 10 секунди след 100 милиона итерации.

Индекси и търсене без значение на главни букви

Индекси и функции

Нека започнем с основите:ако дефинирате индекс за което и да е поле, той няма да се използва в заявки за функция, приложена към това поле:

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

За такива заявки имате нужда от отделен индекс със самата функция:

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

В SQLite може да се направи и на персонализирана функция, но трябва да бъде маркирана като детерминистична (което означава, че със същите входове връща същия резултат):

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

След това можете да създадете индекс на персонализирана 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>=?)

Индекси и съпоставяне

Ситуацията със съпоставянето и индексите е подобна:за да може заявка да използва индекс, те трябва да използват същото съпоставяне (подразбиращо се или предоставено изрично), в противен случай няма да работи.

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

Както бе отбелязано по-горе, съпоставянето може да бъде определено за колона в схемата на таблицата. Това е най-удобният начин – автоматично ще се прилага към всички заявки и индекси в съответното поле, освен ако не посочите друго:

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

Кое решение да изберете?

За да изберем решение, се нуждаем от някои критерии за сравнение:

1. Простота – колко е трудно да се приложи и поддържа

2. Ефективност – колко бързи ще бъдат вашите заявки

3. Допълнително пространство – колко допълнително пространство в базата данни изисква решението

4. Съединител – доколко вашето решение преплита кода и съхранението

Както обикновено, изборът на решение ще зависи от вашия случай на използване и изисквания за производителност. Лично аз бих използвал персонализирано сортиране, сравняване в приложението или съхраняване на нормализиран низ. Например в listOK първо използвах съпоставяне и преминах към сравняване в приложението, когато добавих размито търсене.