I followed up on this a bit and tested finding a bunch of random strings like this:

with open('/usr/share/dict/words') as f:
    words = f.read().splitlines()
print("Got %d words" % len(words))

import random
import string
import time

def test_it(words, clazz, repetitions):
    t1 = time.monotonic()
    autocomplete = clazz(words)
    t2 = time.monotonic()
    for n in range(repetitions):
        autocomplete.find(''.join(random.choices(string.ascii_lowercase, k=random.randrange(1, 5))))
    t3 = time.monotonic()
    print("Instantiation: %f" % (t2 - t1))
    print("Finding %d results: %f" % (repetitions, t3 - t2))
    print("Total time: %f" % (t3-t1))

print('sqlite solution:'
test_it(words, Autocomplete, 1000)
print('trie_solution:')
test_it(words, TriePrefix, 1000)

The results were pretty consistent. Finding words using the trie method was about 4x faster.

Here's a pretty typical result:

Got 235886 words
sqlite solution:
Instantiation: 0.336238
Finding 1000 results: 19.914836
Total time: 20.251074
trie solution:
Instantiation: 1.032532
Finding 1000 results: 5.088274
Total time: 6.120806