5 cara untuk mengimplementasikan pencarian case-insensitive di SQLite dengan dukungan Unicode penuh

Baru-baru ini saya membutuhkan pencarian case-insensitive di SQLite untuk memeriksa apakah item dengan nama yang sama sudah ada di salah satu proyek saya – listOK. Pada awalnya, ini tampak seperti tugas yang sederhana, tetapi setelah menyelam lebih dalam, ternyata mudah, tetapi tidak sederhana sama sekali, dengan banyak tikungan dan belokan.

Kemampuan SQLite bawaan dan kekurangannya

Di SQLite Anda bisa mendapatkan pencarian case-insensitive dalam tiga cara:

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

Jika Anda menggunakan SQLAlchemy dan ORM-nya, pendekatan ini akan terlihat sebagai berikut:

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

Semua pendekatan ini tidak ideal. Pertama , tanpa pertimbangan khusus mereka tidak menggunakan indeks pada bidang yang mereka kerjakan, dengan LIKE menjadi pelaku terburuk:dalam banyak kasus tidak mampu menggunakan indeks. Selengkapnya tentang penggunaan indeks untuk kueri peka huruf besar/kecil ada di bawah.

Kedua , dan yang lebih penting, mereka memiliki pemahaman yang agak terbatas tentang apa yang dimaksud dengan case-insensitive:

SQLite hanya memahami huruf besar/kecil untuk karakter ASCII secara default. Operator LIKE peka huruf besar/kecil secara default untuk karakter unicode yang berada di luar rentang ASCII. Misalnya, ekspresi 'a' LIKE 'A' adalah TRUE tetapi 'æ' LIKE 'Æ' adalah FALSE.

Tidak masalah jika Anda berencana untuk bekerja dengan string yang hanya berisi huruf alfabet bahasa Inggris, angka, dll. Saya membutuhkan spektrum Unicode penuh, jadi solusi yang lebih baik adalah.

Di bawah ini saya merangkum lima cara untuk mencapai pencarian/perbandingan case-insensitive di SQLite untuk semua simbol Unicode. Beberapa dari solusi ini dapat disesuaikan dengan database lain dan untuk mengimplementasikan LIKE yang sadar Unicode , REGEXP , MATCH , dan fungsi lainnya, meskipun topik ini berada di luar cakupan postingan ini.

Kami akan melihat pro dan kontra dari setiap pendekatan, detail implementasi, dan, terakhir, pada indeks dan pertimbangan kinerja.

Solusi

1. Ekstensi ICU

Dokumentasi SQLite resmi menyebutkan ekstensi ICU sebagai cara untuk menambahkan dukungan lengkap untuk Unicode di SQLite. ICU adalah singkatan dari International Components for Unicode.

ICU memecahkan masalah LIKE yang tidak peka huruf besar-kecil dan perbandingan/pencarian, plus menambahkan dukungan untuk susunan yang berbeda untuk ukuran yang baik. Bahkan mungkin lebih cepat daripada beberapa solusi yang lebih baru karena ditulis dalam C dan lebih terintegrasi dengan SQLite.

Namun, ia datang dengan tantangannya:

1. Ini adalah jenis baru ketergantungan:bukan pustaka Python, tetapi ekstensi yang harus didistribusikan bersama dengan aplikasi.

2. ICU perlu dikompilasi sebelum digunakan, kemungkinan untuk OS dan platform yang berbeda (tidak diuji).

3. ICU sendiri tidak menerapkan konversi Unicode, tetapi bergantung pada sistem operasi yang digarisbawahi – Saya telah melihat beberapa penyebutan masalah khusus OS, terutama dengan Windows dan macOS.

Semua solusi lain akan bergantung pada kode Python Anda untuk melakukan perbandingan, jadi penting untuk memilih pendekatan yang tepat untuk mengonversi dan membandingkan string.

Memilih fungsi python yang tepat untuk perbandingan case-insensitive

Untuk melakukan perbandingan dan pencarian case-insensitive, kita perlu menormalkan string menjadi satu case. Naluri pertama saya adalah menggunakan str.lower() untuk ini. Ini akan berhasil di sebagian besar keadaan, tetapi itu bukan cara yang tepat. Lebih baik menggunakan str.casefold() (dokumen):

Kembalikan salinan string yang dilipat. String casefolded dapat digunakan untuk pencocokan caseless.

Casefolding mirip dengan huruf kecil tetapi lebih agresif karena dimaksudkan untuk menghapus semua perbedaan huruf besar/kecil dalam sebuah string. Misalnya, huruf kecil Jerman 'ß' setara dengan "ss". Karena sudah huruf kecil, lower() tidak akan melakukan apa pun untuk 'ß'; casefold() mengubahnya menjadi "ss".

Oleh karena itu, di bawah ini kita akan menggunakan str.casefold() fungsi untuk semua konversi dan perbandingan.

2. Penyusunan yang ditentukan aplikasi

Untuk melakukan pencarian case-insensitive untuk semua simbol Unicode, kita perlu mendefinisikan susunan baru dalam aplikasi setelah terhubung ke database (dokumentasi). Di sini Anda punya pilihan – membebani NOCASE bawaan atau buat sendiri – kami akan membahas pro dan kontra di bawah ini. Demi sebuah contoh kami akan menggunakan nama baru:

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
)

Pengumpulan memiliki beberapa keunggulan dibandingkan dengan solusi berikutnya:

1. Mereka mudah digunakan. Anda dapat menentukan susunan dalam skema tabel dan itu akan diterapkan secara otomatis ke semua kueri dan indeks di bidang ini kecuali jika Anda menentukan sebaliknya:
   

   CREATE TABLE test (text VARCHAR COLLATE UNICODE_NOCASE);
   

   Demi kelengkapan, mari kita lihat dua cara lagi untuk menggunakan susunan:
   

   -- 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. Collation menyediakan penyortiran case-insensitive dengan ORDER BY keluar dari kotak. Ini sangat mudah didapat jika Anda mendefinisikan susunan dalam skema tabel.

Pengumpulan berdasarkan kinerja memiliki beberapa kekhasan, yang akan kita bahas lebih lanjut.

3. Fungsi SQL yang ditentukan aplikasi

Cara lain untuk mencapai pencarian case-insensitive adalah dengan membuat fungsi SQL yang ditentukan aplikasi (dokumentasi):

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)

Dalam kedua kasus create_function menerima hingga empat argumen:

• nama fungsi yang akan digunakan dalam kueri SQL
• jumlah argumen yang diterima fungsi
• fungsi itu sendiri
• opsional bool deterministic , default False (ditambahkan dalam Python 3.8) – penting untuk indeks, yang akan kita bahas di bawah.

Seperti halnya susunan, Anda memiliki pilihan – kelebihan fungsi bawaan (misalnya, LOWER ) atau buat yang baru. Kami akan melihat lebih detail nanti.

4. Bandingkan di aplikasi

Cara lain pencarian peka huruf besar-kecil adalah membandingkan di aplikasi itu sendiri, terutama jika Anda dapat mempersempit pencarian dengan menggunakan indeks di bidang lain. Misalnya, dalam perbandingan case-insensitive listOK diperlukan untuk item dalam daftar tertentu. Oleh karena itu, saya dapat memilih semua item dalam daftar, menormalkannya menjadi satu kasus dan membandingkannya dengan item baru yang dinormalisasi.

Bergantung pada keadaan Anda, itu bukan solusi yang buruk, terutama jika subset yang akan Anda bandingkan kecil. Namun, Anda tidak akan dapat menggunakan indeks basis data pada teks, hanya pada parameter lain yang akan Anda gunakan untuk mempersempit cakupan.

Keuntungan dari pendekatan ini adalah fleksibilitasnya:dalam aplikasi Anda tidak hanya dapat memeriksa kesetaraan tetapi, misalnya, menerapkan perbandingan "kabur" untuk memperhitungkan kemungkinan kesalahan cetak, bentuk tunggal/jamak, dll. Ini adalah rute yang saya pilih untuk listOK karena bot membutuhkan perbandingan kabur untuk pembuatan item "pintar".

Selain itu, ini menghilangkan koneksi apa pun dengan database – ini adalah penyimpanan sederhana yang tidak tahu apa-apa tentang data.

5. Simpan bidang yang dinormalisasi secara terpisah

Ada satu solusi lagi:buat kolom terpisah di database dan simpan teks normal yang akan Anda cari di sana. Misalnya, tabel mungkin memiliki struktur ini (hanya bidang yang relevan):

Ini mungkin terlihat berlebihan pada awalnya:Anda harus selalu memperbarui versi yang dinormalisasi dan secara efektif menggandakan ukuran name bidang. Namun, dengan ORM atau bahkan secara manual, ini mudah dilakukan dan ruang disk plus RAM relativitasnya murah.

Keuntungan dari pendekatan ini:

• Ini benar-benar memisahkan aplikasi dan database – Anda dapat dengan mudah beralih.

• Anda dapat melakukan pra-proses file yang dinormalisasi jika kueri Anda memerlukannya (pangkas, hapus tanda baca atau spasi, dll.).

Haruskah Anda membebani fungsi dan susunan bawaan?

Saat menggunakan fungsi dan susunan SQL yang ditentukan aplikasi, Anda sering memiliki pilihan:gunakan nama unik atau fungsi bawaan yang berlebihan. Kedua pendekatan memiliki pro dan kontra dalam dua dimensi utama:

Pertama, keandalan/prediktabilitas ketika karena alasan tertentu (kesalahan satu kali, bug, atau sengaja) Anda tidak mendaftarkan fungsi atau susunan ini:

• Overloading:database akan tetap bekerja, tetapi hasilnya mungkin tidak benar:

  • fungsi/kolasi bawaan akan berperilaku berbeda dari rekan kustomnya;
  • jika Anda menggunakan sekarang tidak ada susunan dalam indeks, itu akan tampak berfungsi, tetapi hasilnya mungkin salah bahkan saat membaca;
  • jika tabel dengan indeks dan indeks menggunakan fungsi/penyusunan kustom diperbarui, indeks mungkin rusak (diperbarui menggunakan implementasi bawaan), tetapi terus bekerja seolah-olah tidak terjadi apa-apa.

• Tidak kelebihan beban:database tidak akan berfungsi dalam hal apa pun jika fungsi atau susunan yang tidak ada digunakan:

  • jika Anda menggunakan indeks pada fungsi yang tidak ada, Anda akan dapat menggunakannya untuk membaca, tetapi tidak untuk pembaruan;
  • indeks dengan susunan yang ditentukan aplikasi tidak akan berfungsi sama sekali, karena indeks menggunakan susunan saat menelusuri di indeks.

Kedua, aksesibilitas di luar aplikasi utama:migrasi, analitik, dll.:

• Overloading:Anda akan dapat memodifikasi database tanpa masalah, mengingat risiko merusak indeks.

• Tidak kelebihan beban:dalam banyak kasus Anda perlu mendaftarkan fungsi atau susunan ini atau mengambil langkah ekstra untuk menghindari bagian database yang bergantung padanya.

Jika Anda memutuskan untuk membebani secara berlebihan, mungkin ide yang baik untuk membangun kembali indeks berdasarkan fungsi atau susunan khusus jika ada data yang salah dicatat di sana, misalnya:

-- Rebuild all indexes using this collation
REINDEX YOUR_COLLATION_NAME;

-- Rebuild particular index
REINDEX index_name;

-- Rebuild all indexes
REINDEX;

Performa fungsi dan susunan yang ditentukan aplikasi

Fungsi atau susunan khusus jauh lebih lambat daripada fungsi bawaan:SQLite "mengembalikan" ke aplikasi Anda setiap kali ia memanggil fungsi. Anda dapat dengan mudah memeriksanya dengan menambahkan penghitung global ke fungsi:

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

Jika Anda jarang melakukan kueri atau database Anda kecil, Anda tidak akan melihat perbedaan yang berarti. Namun, jika Anda tidak menggunakan indeks pada fungsi/pemeriksaan ini, database dapat melakukan pemindaian tabel lengkap yang menerapkan fungsi/pemeriksaan pada setiap baris. Tergantung pada ukuran tabel, perangkat keras, dan jumlah permintaan, kinerja rendah mungkin mengejutkan. Nanti saya akan menerbitkan ulasan fungsi yang ditentukan aplikasi dan kinerja susunan.

Sebenarnya, susunan sedikit lebih lambat daripada fungsi SQL karena untuk setiap perbandingan mereka perlu melipat dua string, bukan satu. Meskipun perbedaan ini sangat kecil:dalam pengujian saya, fungsi casefold lebih cepat daripada collation serupa sekitar 25% yang berjumlah perbedaan 10 detik setelah 100 juta iterasi.

Indeks dan pencarian peka huruf besar/kecil

Indeks dan fungsi

Mari kita mulai dengan dasar-dasarnya:jika Anda mendefinisikan indeks di bidang apa pun, indeks itu tidak akan digunakan dalam kueri pada fungsi yang diterapkan ke bidang ini:

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

Untuk kueri seperti itu, Anda memerlukan indeks terpisah dengan fungsi itu sendiri:

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

Di SQLite, ini dapat dilakukan pada fungsi kustom juga, tetapi harus ditandai sebagai deterministik (artinya dengan input yang sama akan mengembalikan hasil yang sama):

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

Setelah itu Anda dapat membuat indeks pada fungsi SQL kustom:

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

Indeks dan susunan

Situasi dengan susunan dan indeks serupa:agar kueri menggunakan indeks, mereka harus menggunakan susunan yang sama (tersirat atau disediakan secara tegas), jika tidak, itu tidak akan berfungsi.

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

Seperti disebutkan di atas, susunan dapat ditentukan untuk kolom dalam skema tabel. Ini adalah cara yang paling nyaman – ini akan diterapkan ke semua kueri dan indeks pada bidang masing-masing secara otomatis kecuali jika Anda menentukan sebaliknya:

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

Solusi mana yang harus dipilih?

Untuk memilih solusi kita memerlukan beberapa kriteria untuk perbandingan:

1. Kesederhanaan – betapa sulitnya menerapkan dan memeliharanya

2. Kinerja – seberapa cepat kueri Anda

3. Ruang ekstra – berapa banyak ruang basis data tambahan yang dibutuhkan solusi

4. Kopling – seberapa banyak solusi Anda menyatukan kode dan penyimpanan

Seperti biasa, pilihan solusi akan bergantung pada kasus penggunaan dan tuntutan kinerja Anda. Secara pribadi, saya akan menggunakan susunan khusus, membandingkan di aplikasi, atau menyimpan string yang dinormalisasi. Misalnya, di listOK, saya pertama kali menggunakan collation dan beralih ke membandingkan di aplikasi saat menambahkan pencarian fuzzy.