Re: WIP: index support for regexp search

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
Removedby 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?

- Heikki