Re: WIP: index support for regexp search - Mailing list pgsql-hackers

One thing that bothers me with this algoritm is that the overflow mechanism is all-or-nothing. In many cases, even when there is a huge number of states in the diagram, you could still extract at least a few trigrams that must be present in any matching string, with little effort. At least, it seems like that to a human :-).

For example, consider this:

explain analyze select count(*) from azjunk4 where txt ~ ('^aabaacaadaaeaafaagaahaaiaajaakaalaamaanaaoaapaaqaaraasaataauaavaawaaxaayaazabaabbabcabdabeabfabgabhabiabjabkablabmabnaboabpabqabrabsabtabuabvabwabxabyabzacaacbaccacdaceacfacgachaciacjackaclacmacnacoacpacqacracsactacuacvacwacxacyaczadaadbadcaddadeadfadgadhadiadjadkadladmadnadoadpadqadradsadtaduadvadwadxadyadzaeaaebaecaedaeeaefaegaehaeiaejaekaelaemaenaeoaepaeqaeraesaetaeuaevaewaexaeyaezafaafbafcafdafeaffafgafhafiafjafkaflafmafnafoafpafqafrafsaftafuafvafwafxafyafzagaagbagcagdageagfaggaghagiagjagkaglagmagnagoagpagqagragsagtaguagvagwagxagyagzahaahbahcahdaheahfahgahhahiahjahkahlahmahnahoahpahqahrahs$');

you get a query plan like this (the long regexp string edited out):

 Aggregate  (cost=228148.02..228148.03 rows=1 width=0) (actual time=131.100..131
.101 rows=1 loops=1)
   ->  Bitmap Heap Scan on azjunk4  (cost=228144.01..228148.02 rows=1 width=0) (
actual time=131.096..131.096 rows=0 loops=1)
         Recheck Cond: (txt ~ <ridiculously long regexp>)
         Rows Removed by Index Recheck: 10000
         ->  Bitmap Index Scan on azjunk4_trgmrgx_txt_01_idx (cost=0.00..228144
.01 rows=1 width=0) (actual time=82.914..82.914 rows=10000 loops=1)
               Index Cond: (txt ~ <ridiculously long regexp>)
 Total runtime: 131.230 ms
(7 rows)

That ridiculously long string exceeds the number of states (I think, could be number of paths or arcs too), and the algorithm gives up, resorting to scanning the whole index as can be seen by the "Rows Removed by Index Recheck" line. However, it's easy to see that any matching string must contain *any* of the possible trigrams the algorithm extracts. If it could safely return just a few of them, say "aab" and "abz", and discard the rest, that would already be much better than a full index scan.

Would it be safe to simply stop short the depth-first search on overflow, and proceed with the graph that was constructed up to that point?