5 cách triển khai tìm kiếm không phân biệt chữ hoa chữ thường trong SQLite với sự hỗ trợ đầy đủ của Unicode

Gần đây, tôi cần tìm kiếm không phân biệt chữ hoa chữ thường trong SQLite để kiểm tra xem một mục có cùng tên đã tồn tại trong một trong các dự án của tôi - listOK hay chưa. Ban đầu, nó trông giống như một nhiệm vụ đơn giản, nhưng khi đi sâu hơn, nó hóa ra dễ dàng, nhưng không đơn giản chút nào, với rất nhiều khúc mắc.

Các khả năng SQLite tích hợp và nhược điểm của chúng

Trong SQLite, bạn có thể nhận được tìm kiếm không phân biệt chữ hoa chữ thường theo ba cách:

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

Nếu bạn sử dụng SQLAlchemy và ORM của nó, các cách tiếp cận này sẽ như sau:

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

Tất cả những cách tiếp cận này không phải là lý tưởng. Đầu tiên , nếu không có những cân nhắc đặc biệt, họ không sử dụng các chỉ mục trên lĩnh vực mà họ đang làm việc, với LIKE là người vi phạm tồi tệ nhất:trong hầu hết các trường hợp, nó không có khả năng sử dụng các chỉ mục. Dưới đây là thông tin thêm về việc sử dụng chỉ mục cho các truy vấn không phân biệt chữ hoa chữ thường.

Thứ hai và quan trọng hơn, họ có hiểu biết khá hạn chế về ý nghĩa của phân biệt chữ hoa chữ thường:

SQLite chỉ hiểu chữ hoa / chữ thường cho các ký tự ASCII theo mặc định. Toán tử LIKE phân biệt chữ hoa chữ thường theo mặc định cho các ký tự unicode vượt quá phạm vi ASCII. Ví dụ:biểu thức 'a' LIKE 'A' là TRUE nhưng 'æ' LIKE 'Æ' là FALSE.

Sẽ không thành vấn đề nếu bạn định làm việc với các chuỗi chỉ chứa các chữ cái, chữ số trong bảng chữ cái tiếng Anh, v.v. Tôi cần phổ Unicode đầy đủ, vì vậy giải pháp tốt hơn là phù hợp.

Dưới đây tôi tóm tắt năm cách để đạt được tìm kiếm / so sánh không phân biệt chữ hoa chữ thường trong SQLite cho tất cả các ký hiệu Unicode. Một số giải pháp này có thể được điều chỉnh cho phù hợp với các cơ sở dữ liệu khác và để triển khai LIKE nhận biết Unicode , REGEXP , MATCH và các chức năng khác, mặc dù những chủ đề này nằm ngoài phạm vi của bài đăng này.

Chúng tôi sẽ xem xét ưu và nhược điểm của từng cách tiếp cận, chi tiết triển khai và cuối cùng là xem xét các chỉ mục và hiệu suất.

Giải pháp

1. Phần mở rộng ICU

Tài liệu SQLite chính thức đề cập đến phần mở rộng ICU như một cách để thêm hỗ trợ hoàn chỉnh cho Unicode trong SQLite. ICU là viết tắt của International Components for Unicode.

ICU giải quyết các vấn đề của cả LIKE không phân biệt chữ hoa chữ thường và so sánh / tìm kiếm, cộng thêm hỗ trợ cho các đối chiếu khác nhau để có một thước đo tốt. Nó thậm chí có thể nhanh hơn một số giải pháp sau này vì nó được viết bằng C và được tích hợp chặt chẽ hơn với SQLite.

Tuy nhiên, nó đi kèm với những thách thức:

Đây là một loại mới của phụ thuộc:không phải là một thư viện Python, mà là một phần mở rộng nên được phân phối cùng với ứng dụng.
ICU cần được biên dịch trước khi sử dụng, có khả năng dành cho các hệ điều hành và nền tảng khác nhau (chưa được thử nghiệm).
Bản thân ICU không thực hiện chuyển đổi Unicode mà dựa vào hệ điều hành bên dưới - tôi đã thấy nhiều đề cập về các vấn đề cụ thể đối với hệ điều hành, đặc biệt là với Windows và macOS.

Tất cả các giải pháp khác sẽ phụ thuộc vào mã Python của bạn để thực hiện so sánh, vì vậy điều quan trọng là phải chọn cách tiếp cận phù hợp để chuyển đổi và so sánh các chuỗi.

Chọn đúng hàm python để so sánh không phân biệt chữ hoa chữ thường

Để thực hiện so sánh và tìm kiếm không phân biệt chữ hoa chữ thường, chúng ta cần chuẩn hóa các chuỗi thành một trường hợp. Bản năng đầu tiên của tôi là sử dụng str.lower() cho điều này. Nó sẽ hoạt động trong hầu hết các trường hợp, nhưng nó không phải là cách thích hợp. Tốt hơn nên sử dụng str.casefold() (tài liệu):

Trả về một bản sao được gấp chữ thường của chuỗi. Các chuỗi gấp chữ hoa có thể được sử dụng để đối sánh không tính tiền.

Viết hoa chữ thường tương tự như viết thường nhưng tích cực hơn vì nó nhằm loại bỏ tất cả các phân biệt chữ hoa và chữ thường trong một chuỗi. Ví dụ, chữ cái thường trong tiếng Đức 'ß' tương đương với "ss". Vì nó đã là chữ thường nên lower() sẽ không làm gì với 'ß'; casefold() chuyển đổi nó thành "ss".

Do đó, bên dưới chúng tôi sẽ sử dụng str.casefold() chức năng cho tất cả các chuyển đổi và so sánh.

2. Đối chiếu do ứng dụng xác định

Để thực hiện tìm kiếm không phân biệt chữ hoa chữ thường cho tất cả các ký hiệu Unicode, chúng ta cần xác định một đối chiếu mới trong ứng dụng sau khi kết nối với cơ sở dữ liệu (tài liệu). Ở đây bạn có một sự lựa chọn - quá tải NOCASE tích hợp sẵn hoặc tạo của riêng bạn - chúng tôi sẽ thảo luận về những ưu và nhược điểm bên dưới. Để làm ví dụ, chúng tôi sẽ sử dụng một tên mới:

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
)

Ghép nối có một số ưu điểm so với các giải pháp tiếp theo:

Rất dễ dàng để sử dụng chúng. Bạn có thể chỉ định đối chiếu trong lược đồ bảng và nó sẽ tự động được áp dụng cho tất cả các truy vấn và chỉ mục trên trường này trừ khi bạn chỉ định khác:

CREATE TABLE test (text VARCHAR COLLATE UNICODE_NOCASE);

Để có sự đầy đủ, chúng ta hãy xem xét thêm hai cách sử dụng đối chiếu:

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

Đối chiếu cung cấp phân loại không phân biệt chữ hoa chữ thường với ORDER BY ngoài cái hộp. Nó đặc biệt dễ lấy nếu bạn xác định đối chiếu trong lược đồ bảng.

Các phép cộng tác thông minh về hiệu suất có một số đặc thù mà chúng ta sẽ thảo luận thêm.

3. Hàm SQL do ứng dụng xác định

Một cách khác để đạt được tìm kiếm không phân biệt chữ hoa chữ thường là tạo một hàm SQL do ứng dụng xác định (tài liệu):

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)

Trong cả hai trường hợp, create_function chấp nhận tối đa bốn đối số:

tên của hàm vì nó sẽ được sử dụng trong các truy vấn SQL
số đối số mà hàm chấp nhận
chính chức năng
bool tùy chọn deterministic , mặc định False (được thêm vào trong Python 3.8) - điều quan trọng đối với các chỉ mục, chúng ta sẽ thảo luận bên dưới.

Đối với các ảnh ghép, bạn có một sự lựa chọn - hàm tích hợp quá tải (ví dụ:LOWER ) hoặc tạo mới. Chúng ta sẽ xem xét nó chi tiết hơn ở phần sau.

4. So sánh trong ứng dụng

Một cách khác để tìm kiếm không phân biệt chữ hoa chữ thường sẽ là so sánh trong chính ứng dụng, đặc biệt nếu bạn có thể thu hẹp tìm kiếm bằng cách sử dụng chỉ mục trên các trường khác. Ví dụ, trong listOK, cần so sánh phân biệt chữ hoa chữ thường cho các mục trong một danh sách cụ thể. Do đó, tôi có thể chọn tất cả các mục trong danh sách, chuẩn hóa chúng thành một trường hợp và so sánh chúng với mục mới đã chuẩn hóa.

Tùy thuộc vào hoàn cảnh của bạn, đó không phải là một giải pháp tồi, đặc biệt nếu tập hợp con bạn sẽ so sánh với nhỏ. Tuy nhiên, bạn sẽ không thể sử dụng các chỉ mục cơ sở dữ liệu trên văn bản, chỉ trên các tham số khác mà bạn sẽ sử dụng để thu hẹp phạm vi.

Ưu điểm của cách tiếp cận này là tính linh hoạt của nó:trong ứng dụng, bạn không chỉ có thể kiểm tra sự bình đẳng mà còn có thể thực hiện so sánh "mờ" để tính đến các dấu sai có thể xảy ra, dạng số ít / số nhiều, v.v. Đây là cách mà tôi đã chọn cho listOK vì bot cần so sánh mờ để tạo mục "thông minh".

Ngoài ra, nó giúp loại bỏ bất kỳ khớp nối nào với cơ sở dữ liệu - đó là bộ lưu trữ đơn giản không biết gì về dữ liệu.

5. Lưu trữ riêng trường chuẩn hóa

Có một giải pháp khác:tạo một cột riêng biệt trong cơ sở dữ liệu và giữ ở đó văn bản chuẩn hóa mà bạn sẽ tìm kiếm. Ví dụ:bảng có thể có cấu trúc này (chỉ các trường liên quan):

id	tên	name_normalized
1	Viết hoa đầu câu	viết hoa câu
2	CHỮ VỐN	chữ in hoa
3	Ký hiệu không phải ASCII:Найди Меня	các ký hiệu không phải ascii:найди меня

Điều này thoạt nhìn có vẻ quá đáng:bạn luôn cần cập nhật phiên bản chuẩn hóa và tăng gấp đôi kích thước của name một cách hiệu quả đồng ruộng. Tuy nhiên, với ORM hoặc thậm chí thủ công, việc này rất dễ thực hiện và dung lượng ổ đĩa cộng với RAM tương đối rẻ.

Ưu điểm của phương pháp này:

Nó tách rời hoàn toàn ứng dụng và cơ sở dữ liệu - bạn có thể dễ dàng chuyển đổi.
Bạn có thể xử lý trước hồ sơ đã chuẩn hóa nếu các truy vấn của bạn yêu cầu (cắt, xóa dấu câu hoặc dấu cách, v.v.).

Bạn có nên làm quá tải các hàm và đối chiếu tích hợp sẵn không?

Khi sử dụng các hàm và đối chiếu SQL do ứng dụng xác định, bạn thường có lựa chọn:sử dụng một tên duy nhất hoặc chức năng tích hợp quá tải. Cả hai cách tiếp cận đều có ưu và nhược điểm theo hai khía cạnh chính:

Đầu tiên, độ tin cậy / khả năng dự đoán khi vì lý do nào đó (một lần nhầm lẫn, lỗi hoặc cố ý) bạn không đăng ký các chức năng hoặc đối chiếu này:

Quá tải:cơ sở dữ liệu sẽ vẫn hoạt động, nhưng kết quả có thể không chính xác:
- chức năng / đối chiếu tích hợp sẽ hoạt động khác với các đối tác tùy chỉnh của chúng;
- nếu bạn đã sử dụng hiện không có đối chiếu trong một chỉ mục, nó sẽ có vẻ hoạt động, nhưng kết quả có thể sai ngay cả khi đọc;
- nếu bảng có chỉ mục và chỉ mục sử dụng chức năng / đối chiếu tùy chỉnh được cập nhật, chỉ mục có thể bị hỏng (được cập nhật bằng cách sử dụng triển khai tích hợp), nhưng vẫn tiếp tục hoạt động như thể không có gì xảy ra.
Không quá tải:cơ sở dữ liệu sẽ không hoạt động ở bất kỳ khía cạnh nào khi các hàm hoặc đối chiếu vắng mặt được sử dụng:
- nếu bạn sử dụng một chỉ mục cho một chức năng vắng mặt, bạn sẽ có thể sử dụng nó để đọc, nhưng không thể sử dụng để cập nhật;
- các chỉ mục có đối chiếu do ứng dụng xác định sẽ hoàn toàn không hoạt động vì chúng sử dụng đối chiếu khi tìm kiếm trong chỉ mục.

Thứ hai, khả năng tiếp cận bên ngoài ứng dụng chính:di chuyển, phân tích, v.v.:

Quá tải:bạn sẽ có thể sửa đổi cơ sở dữ liệu mà không gặp vấn đề gì, lưu ý nguy cơ làm hỏng chỉ mục.
Không quá tải:trong nhiều trường hợp, bạn sẽ cần đăng ký các hàm hoặc đối chiếu này hoặc thực hiện các bước bổ sung để tránh các phần của cơ sở dữ liệu phụ thuộc vào nó.

Nếu bạn quyết định quá tải, có thể là một ý tưởng hay để xây dựng lại các chỉ mục dựa trên các chức năng tùy chỉnh hoặc đối chiếu trong trường hợp chúng nhận được dữ liệu sai được ghi ở đó, ví dụ:

-- Rebuild all indexes using this collation
REINDEX YOUR_COLLATION_NAME;

-- Rebuild particular index
REINDEX index_name;

-- Rebuild all indexes
REINDEX;

Hiệu suất của các chức năng và cấu trúc do ứng dụng xác định

Các hàm tùy chỉnh hoặc đối chiếu chậm hơn nhiều so với các hàm tích hợp sẵn:SQLite "quay trở lại" ứng dụng của bạn mỗi khi nó gọi hàm. Bạn có thể dễ dàng kiểm tra nó bằng cách thêm bộ đếm toàn cục vào hàm:

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

Nếu bạn hiếm khi truy vấn hoặc cơ sở dữ liệu của bạn nhỏ, bạn sẽ không thấy bất kỳ sự khác biệt có ý nghĩa nào. Tuy nhiên, nếu bạn không sử dụng chỉ mục trên hàm / đối chiếu này, cơ sở dữ liệu có thể thực hiện quét bảng hoàn chỉnh áp dụng hàm / đối chiếu trên mỗi hàng. Tùy thuộc vào kích thước của bảng, phần cứng và số lượng yêu cầu, hiệu suất thấp có thể đáng ngạc nhiên. Sau đó, tôi sẽ xuất bản một bài đánh giá về hiệu suất của các chức năng và đối chiếu do ứng dụng xác định.

Nói một cách chính xác, các phép đối chiếu chậm hơn một chút so với các hàm SQL vì đối với mỗi phép so sánh, chúng cần phải viết hoa chữ thường hai chuỗi, thay vì một. Mặc dù sự khác biệt này là rất nhỏ:trong các thử nghiệm của tôi, hàm casefold nhanh hơn so với đối chiếu tương tự khoảng 25%, tương đương với sự chênh lệch 10 giây sau 100 triệu lần lặp.

Chỉ mục và tìm kiếm không phân biệt chữ hoa chữ thường

Chỉ mục và chức năng

Hãy bắt đầu với những điều cơ bản:nếu bạn xác định một chỉ mục trên bất kỳ trường nào, nó sẽ không được sử dụng trong các truy vấn trên một hàm được áp dụng cho trường này:

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

Đối với các truy vấn như vậy, bạn cần một chỉ mục riêng với chính hàm:

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

Trong SQLite, nó cũng có thể được thực hiện trên một hàm tùy chỉnh, nhưng nó phải được đánh dấu là xác định (có nghĩa là với các đầu vào giống nhau, nó trả về cùng một kết quả):

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

Sau đó, bạn có thể tạo chỉ mục trên một hàm SQL tùy chỉnh:

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

Chỉ mục và đối chiếu

Tình huống với các đối chiếu và chỉ mục cũng tương tự:đối với một truy vấn sử dụng một chỉ mục, chúng phải sử dụng cùng một đối chiếu (ngụ ý hoặc cung cấp rõ ràng), nếu không, nó sẽ không hoạt động.

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

Như đã lưu ý ở trên, đối chiếu có thể được chỉ định cho một cột trong lược đồ bảng. Đây là cách thuận tiện nhất - nó sẽ tự động được áp dụng cho tất cả các truy vấn và chỉ mục trên trường tương ứng trừ khi bạn chỉ định khác:

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

Nên chọn giải pháp nào?

Để chọn một giải pháp, chúng ta cần một số tiêu chí để so sánh:

Tính đơn giản - khó khăn như thế nào để triển khai và duy trì nó
Hiệu suất - các truy vấn của bạn sẽ nhanh như thế nào
Thêm không gian - giải pháp yêu cầu bao nhiêu không gian cơ sở dữ liệu bổ sung
Khớp nối - giải pháp của bạn đan xen mã và dung lượng bao nhiêu

Giải pháp	Tính đơn giản	Hiệu suất (tương đối, không có chỉ mục)	Thêm không gian	Khớp nối
Phần mở rộng ICU	Khó:yêu cầu kiểu phụ thuộc và biên dịch mới	Trung bình đến cao	Không	Có
Đối chiếu tùy chỉnh	Đơn giản:cho phép đặt đối chiếu trong lược đồ bảng và tự động áp dụng nó cho bất kỳ truy vấn nào trên trường	Thấp	Không	Có
Hàm SQL tùy chỉnh	Phương tiện:yêu cầu xây dựng chỉ mục dựa trên nó hoặc sử dụng trong tất cả các truy vấn có liên quan	Thấp	Không	Có
So sánh trong ứng dụng	Đơn giản	Tùy thuộc vào trường hợp sử dụng	Không	Không
Lưu trữ chuỗi chuẩn hóa	Phương tiện:bạn cần cập nhật chuỗi chuẩn hóa	Thấp đến Trung bình	x2	Không

Như thường lệ, việc lựa chọn giải pháp sẽ phụ thuộc vào trường hợp sử dụng và nhu cầu hiệu suất của bạn. Cá nhân tôi sẽ sử dụng đối chiếu tùy chỉnh, so sánh trong ứng dụng hoặc lưu trữ một chuỗi chuẩn hóa. Ví dụ:trong listOK, lần đầu tiên tôi sử dụng đối chiếu và chuyển sang so sánh trong ứng dụng khi thêm tìm kiếm mờ.