PGCon2012 - Slide release #12

PGCon 2012
The PostgreSQL Conference

Alexander Korotkov
Day Talks - 2 - Friday - 2012-05-18
Room MRT 212
Start time 15:00
Duration 01:00
ID 383
Event type Lecture
Track Advanced Features
Language used for presentation English

Index support for regular expression search

Regular expressions (regex) are powerful tool for text processing. When dealing with large string collections it's important to search fast on that collections (i.e. search using index). Indexing for regex search is a quite hard task. This talk presents novel technique (and WIP patch for PostgreSQL implementing it) for regex search using trigram indexes. Proposed technique provides more comprehensive trigram extraction than analogues, i.e. higher performance.

There are two existed approaches for index-based regex search. The FREE indexing engine is based on extractions continued text fractions from regex and perform substring search. Google Code Search approach present more sophisticated recursive analysis of regex with extraction of various regex attributes. This talk presents novel technique of regex analysis which is based on automata transformation rather than original regex analysis. Superiority of proposed technique will be proved by examples and tests.

The talk would be organized as following:

  • Introduction.
    • Regular expressions
    • Finite automata
    • pg_trgm contrib module
  • Existing techniques for index-based regular expression search
    • FREE indexing engine
    • Google Code Search
  • Proposed technique
    • Description
    • Examples
    • Comparison with analogues
    • Limitations
  • Performance results