When writing the post on Unicode case-insensitive search in SQLite I got interested in the performance of application-defined functions and collations: they must introduce overhead, the question is how much and whether it is something to be concerned about.
To answer these questions I made a simple test suite measuring the performance of both built-in SQLite and application-defined functions and collations – the full code is at the very end of the post. The basic idea of the performance test:
Create 10,000 rows of random strings (same across all tests).
For every function/collation: run a
SELECTquery for each of the strings, i.e. 10,000 times. Without an index, it will force a full table scan each time. In total it gives 100m calls to the function/collation being tested.
Build an index that can be used in the queries above.
Run the same queries with an index.
Repeat it 10 times to smooth out the effect of random factors and average the result.
I omit some details, feel free to look into the code. For bonus credit, we count the number of calls to some of the functions and collations. All performance was measured without counters since they introduce overhead that would distort the results.
Note on absolute numbers vs. relative comparison
In this kind of test, it does not make sense to compare absolute numbers: different hardware will produce different results. What took my computer 30 seconds to do, may take yours 15, 42, or any other number of seconds. The purpose of this exercise is to test the relative performance of the functions and whether it matters.
All figures are in seconds and include running the test in full, meaning in most cases 100m calls. One notable exception: relevant indexes are built only once per test.
We have three main test subjects:
def do_nothing(a: str): return a def get_len(a: str): return len(a) def casefold(a: str): return a.casefold()
|Function||Description||Time, 10k queries|
|No function||To establish a baseline for how long pure calls take||4.372|
||Does nothing, establishes baseline overhead for calling an application-defined function compared to running no function||23.877|
||Built-in string length function to compare with custom get_length||5.799|
||Custom string length function; the only function that has identical built-in counterpart||22.0|
||Built-in function to returning string in lower case, works only for ASCII symbols||12.012|
||Returns casefolded (i.e. “aggressively lowered” string) with full Unicode support||29.102|
Conclusion: application-defined functions have relatively significant overhead: for 100m calls it amounted to 23.877 - 4.372 ≈ 19 seconds. To put it in perspective the overhead of calling
casefold function amounted to 19 / 29.102 ≈ 65% of its running time.
Main contestants in the collations category:
def do_nothing_collation(a: str, b: str): return -1 def comparison_collation(a: str, b: str): if a < b: return -1 if a > b: return 1 return 0 def unicode_nocase(a: str, b: str): if a.casefold() < b.casefold(): return -1 if a.casefold() > b.casefold(): return 1 return 0 def unicode_nocase_opt(a: str, b: str): a = a.casefold() b = b.casefold() if a < b: return -1 if a > b: return 1 return 0
|Collation||Description||Time, 10k queries|
||Always returns -1, meaning that the first element is less than the second, to establish a baseline||18.855|
||Simply compares incoming strings, case-sensitive||23.355|
||Built-in case-insensitive collation, works only for ASCII symbols||4.593|
||Case-insensitive search with full Unicode support; naive implementation: in the worst case it casefolds each string twice||36.272|
||Optimized version of previous collation: it casefolds the strings only once and stores them in case they are needed the second time||32.741|
Do-nothing application-defined collation performed similarly to do-nothing function, implying similar overhead – in total 14 seconds on 100m calls.
From a purely computational standpoint collations are slower than SQL functions: collations operate with two strings, contain conditions and comparisons. During full table lookups, a function will be faster.
The optimized version of the collation is about 10% faster compared to naive. Other tweaks – new variable vs. overwriting and assignment vs. walrus operator vs. unpacking – did not affect the performance in any measurable way.
The next question is how indexes affect the performance of application-defined functions and collations. The short answer is: indexes make the queries almost instantaneous, eliminating all meaningful overhead.
|Function/collation||Without index, 10k queries||Time to build index||With index, 10k queries|
In all cases, 10k
SELECTqueries with an index took less than 0.1 seconds, compared to 5-20+ seconds without an index.
Building an index is a relatively expensive operation – one building of an index took longer than 10k queries using it (except for
unicode_nocasewhich is likely just a fluctuation).
Number of calls
As a side effect, the test suite also counts the number of calls to functions/collations when building and using indexes. With application-defined functions, there were no surprises: the function was called
N (number of elements) times when building an index and was not called at all when using it.
With collations the situation is different. When building an index on a table with 10k random strings the collation was called about 124k times, which is approximately
O(N * log N) and corresponds to what we should expect according to the SQLite documentation.
The collation is still used when traversing the index tree. The number of times is approximately
log N, i.e. 14 times for an index of 10k items.
Side note: selecting all items without an index with
ORDER BY triggers the same number of calls as building an index both for SQL functions and collations.
Conclusion: does the overhead matter?
Not much for several reasons.
First, sure, application-defined functions and collations involve relatively significant overhead, but they are still very fast, thanks to the overall efficiency of SQLite. If your database is small and requests are not very frequent, you will not see any issues even without indexes.
Second, if your database is large, you will need indexes anyway. With them, the performance overhead will be eliminated.
Finally, you do not have a choice. If you are thinking of application-defined functions or collations, you have to do something that SQLite itself cannot and any solution will have its cost, regardless of the solution.
If anything, this for the lack of a better word “research” underscores the importance of using the right indexes and their effect on performance.
I see no use in publishing this code on GitHub. The code below requires no additional dependencies and can be run with Python 3.8+.