Search on SQLite: Postulo's Unicode LIKE spends about 1 microsecond per row and column, twice what an ASCII fast path needs #1134

New issue

Closed

opened 2026-10-31 03:04:16 +00:00 by tiagoagueda · 0 comments

tiagoagueda commented

2026-10-31 03:04:16 +00:00

Owner

What exists today

core/sqlite_like.py:36-51 replaces SQLite's like on every connection (#505) with a Python function so that icontains, iexact, istartswith and iendswith fold case in every script. Each call converts both arguments with str(), looks the pattern up in an lru_cache of compiled regular expressions (_compile, lines 19-33, which turns %term% into .*term.* with re.IGNORECASE | re.DOTALL) and runs fullmatch. SQLite calls it once per row per searched column, so a list filter that searches several columns calls it rows times columns.

The scout named str(value) as the cost; that is wrong. str() of a str returns the same object and costs a few nanoseconds. The cost is the Unicode case-insensitive regular expression with a leading .*, which for a miss tries every start position.

Measurement (work/s2.py in the audit scratchpad, timeit, 200,000 calls each, the project's .venv, while other agents were running):

case	current	ASCII fast path
ASCII pattern, ASCII value, match	706-893 ns	416-447 ns
ASCII pattern, ASCII value, miss	1,007-1,029 ns	388-435 ns
ASCII pattern, non-ASCII value	about 1,000 ns	unchanged (slow path)
20,000 ASCII rows x 2 columns, `%zurich%`, best of 15	47.9-54.7 ms	28.6-36.1 ms

A variant that keeps the regular expression but uses search without the .* wrappers was also tried: no gain (47.1 ms on the same table), so the regex engine's Unicode case folding is the cost, not the backtracking.

What would change

In like, before the regular expression: when the value is a str and value.isascii() (constant time in CPython) and the pattern, parsed with the same escape rule as _compile, is %literal% with no other unescaped wildcard and an ASCII literal, answer literal.lower() in value.lower(). The parsed literal is cached beside _compile. literal% (istartswith), %literal (iendswith) and a bare literal (iexact) take startswith, endswith and == the same way. Everything else, including any non-ASCII value or pattern, takes the current path unchanged.

Behaviour is identical: for strings that contain only ASCII, Python's Unicode IGNORECASE folds exactly A-Z to a-z, which is what str.lower() does to ASCII; characters whose folding crosses into ASCII (the Kelvin sign, long s, dotted capital I, ß) are non-ASCII and so never reach the fast path. Checked: 0 differences between the current function and the fast path over 100,000 random ASCII pattern and value pairs including %, _ and the escape character; the test files below were not run. tests/test_search.py and tests/test_tables.py, which hold the #505 examples École and Αθηναϊκή, must keep passing. A unit test of like comparing both paths over a fixed table of ASCII, escape and non-ASCII cases guards the equivalence.

No library is needed; SQLite's ICU extension would replace the function entirely but is not in the Python standard library build.

What it saves or protects

small: a text search on SQLite about 40 % faster where the text is ASCII (1,000 ns down to about 400 ns per row and column; 48 ms down to 29 ms over 20,000 rows and 2 columns); none on PostgreSQL

Accessibility

none

Decisions

Cover istartswith, iendswith and iexact too? Recommended: yes, the same parse gives all four shapes.
Worth it on a personal instance? Recommended: yes but low priority; a list of a few thousand rows saves a few milliseconds per filtered request, and the change is a dozen lines with an equivalence test.

Found by the efficiency and reliability audit of 2026-10-30 (finding S2; index postulo/postulo#1108). Checked against main at daee30b15 (2026-10-30).

## What exists today `core/sqlite_like.py:36-51` replaces SQLite's `like` on every connection (#505) with a Python function so that `icontains`, `iexact`, `istartswith` and `iendswith` fold case in every script. Each call converts both arguments with `str()`, looks the pattern up in an `lru_cache` of compiled regular expressions (`_compile`, lines 19-33, which turns `%term%` into `.*term.*` with `re.IGNORECASE | re.DOTALL`) and runs `fullmatch`. SQLite calls it once per row per searched column, so a list filter that searches several columns calls it rows times columns. The scout named `str(value)` as the cost; that is wrong. `str()` of a `str` returns the same object and costs a few nanoseconds. The cost is the Unicode case-insensitive regular expression with a leading `.*`, which for a miss tries every start position. Measurement (`work/s2.py` in the audit scratchpad, `timeit`, 200,000 calls each, the project's `.venv`, while other agents were running): | case | current | ASCII fast path | |---|---|---| | ASCII pattern, ASCII value, match | 706-893 ns | 416-447 ns | | ASCII pattern, ASCII value, miss | 1,007-1,029 ns | 388-435 ns | | ASCII pattern, non-ASCII value | about 1,000 ns | unchanged (slow path) | | 20,000 ASCII rows x 2 columns, `%zurich%`, best of 15 | 47.9-54.7 ms | 28.6-36.1 ms | A variant that keeps the regular expression but uses `search` without the `.*` wrappers was also tried: no gain (47.1 ms on the same table), so the regex engine's Unicode case folding is the cost, not the backtracking. ## What would change In `like`, before the regular expression: when the value is a `str` and `value.isascii()` (constant time in CPython) and the pattern, parsed with the same escape rule as `_compile`, is `%literal%` with no other unescaped wildcard and an ASCII literal, answer `literal.lower() in value.lower()`. The parsed literal is cached beside `_compile`. `literal%` (`istartswith`), `%literal` (`iendswith`) and a bare literal (`iexact`) take `startswith`, `endswith` and `==` the same way. Everything else, including any non-ASCII value or pattern, takes the current path unchanged. Behaviour is identical: for strings that contain only ASCII, Python's Unicode `IGNORECASE` folds exactly A-Z to a-z, which is what `str.lower()` does to ASCII; characters whose folding crosses into ASCII (the Kelvin sign, long s, dotted capital I, `ß`) are non-ASCII and so never reach the fast path. Checked: 0 differences between the current function and the fast path over 100,000 random ASCII pattern and value pairs including `%`, `_` and the escape character; the test files below were not run. `tests/test_search.py` and `tests/test_tables.py`, which hold the #505 examples *École* and *Αθηναϊκή*, must keep passing. A unit test of `like` comparing both paths over a fixed table of ASCII, escape and non-ASCII cases guards the equivalence. No library is needed; SQLite's ICU extension would replace the function entirely but is not in the Python standard library build. ## What it saves or protects small: a text search on SQLite about 40 % faster where the text is ASCII (1,000 ns down to about 400 ns per row and column; 48 ms down to 29 ms over 20,000 rows and 2 columns); none on PostgreSQL ## Accessibility none ## Decisions - **Cover `istartswith`, `iendswith` and `iexact` too?** Recommended: yes, the same parse gives all four shapes. - **Worth it on a personal instance?** Recommended: yes but low priority; a list of a few thousand rows saves a few milliseconds per filtered request, and the change is a dozen lines with an equivalence test. --- Found by the efficiency and reliability audit of 2026-10-30 (finding S2; index postulo/postulo#1108). Checked against `main` at `daee30b15` (2026-10-30).

tiagoagueda added this to the 0.6.0 milestone

2026-10-31 03:04:16 +00:00

tiagoagueda added the

performance

enhancement

labels

2026-10-31 03:04:16 +00:00

tiagoagueda referenced this issue

2026-10-31 03:04:41 +00:00

Efficiency and reliability audit of 2026-10-30: index #1108

tiagoagueda referenced this issue from a pull request that will close it,

2026-11-11 13:40:10 +00:00