trigram indexing

Trigram indexing breaks strings into three-character sequences to enable high-speed fuzzy matching and regular expression searches across massive datasets.

Trigram indexing functions by decomposing text into overlapping chunks of three characters (e.g., 'index' becomes ' i', ' in', 'ind', 'nde', 'dex', 'ex '). This approach allows databases like PostgreSQL, via the pg_trgm module, to calculate string similarity and execute LIKE or regex queries without scanning every row. It is the industry standard for implementing performant autocomplete features and typo-tolerant search engines. By indexing these 3-gram signatures in a GIST or GIN structure, developers can achieve sub-second response times on substring matches across millions of records.

https://www.postgresql.org/docs/current/pgtrgm.html