Re: WIP: index support for regexp search

On 25.11.2012 22:55, Alexander Korotkov wrote:
> On Tue, Nov 20, 2012 at 1:43 PM, Heikki Linnakangas<hlinnakangas@vmware.com
>> wrote:
>
>> Glad to see this patch hasn't been totally forgotten. Being able to use
>> indexes for regular expressions would be really cool!
>>
>> Back in January, I asked for some high-level description of how the
>> algorithm works (http://archives.postgresql.**
>> org/message-id/4F187D5C.30701@**enterprisedb.com<http://archives.postgresql.org/message-id/4F187D5C.30701@enterprisedb.com>).
>> That's still sorely needed. Googling around, I found the slides for your
>> presentation on this from PGConf.EU - it would be great to have the
>> information from that presentation included in the patch.
>
>
> New version of patch is attached. The changes are following:
> 1) A big comment with high-level description of what is going on.
> 2) Regression tests.
> 3) Documetation update.
> 4) Some more refactoring.

Great, that top-level comment helped tremendously! I feel enlightened.

I fixed some spelling, formatting etc. trivial stuff while reading 
through the patch, see attached. Below is some feedback on the details:

* I don't like the PG_TRY/CATCH trick. It's not generally safe to catch 
an error, without propagating it further or rolling back the whole 
(sub)transation. It might work in this case, as you're only suppressing 
errors with the special sqlcode that are used in the same file, but it 
nevertheless feels naughty. I believe none of the limits that are being 
checked are strict; it's OK to exceed the limits somewhat, as long as 
you terminate the processing in a reasonable time, in case of 
pathological input. I'd suggest putting an explicit check for the limits 
somewhere, and not rely on ereport(). Something like this, in the code 
that recurses:

if (trgmCNFA->arcsCount > MAX_RESULT_ARCS ||
     hash_get_num_entries(trgmCNFA->states) > MAX_RESULT_STATES)
{
	trgmCNFA->overflowed = true;
	return;
}

And then check for the overflowed flag at the top level.

* This part of the high-level comment was not clear to me:

>  * States of the graph produced in the first stage are marked with "keys". Key is a pair
>  * of a "prefix" and a state of the original automaton. "Prefix" is a last
>  * characters. So, knowing the prefix is enough to know what is a trigram when we read some new
>  * character. However, we can know single character of prefix or don't know any
>  * characters of it. Each state of resulting graph have an "enter key" (with that
>  * key we've entered this state) and a set of keys which are reachable without
>  * reading any predictable trigram. The algorithm of processing each state
>  * of resulting graph are so:
>  * 1) Add all keys which achievable without reading of any predictable trigram.
>  * 2) Add outgoing arcs labeled with trigrams.
>  * Step 2 leads to creation of new states and recursively processing them. So,
>  * we use depth-first algorithm.

I didn't understand that. Can you elaborate? It might help to work 
through an example, with some ascii art depicting the graph.

* It would be nice to add some comments to TrgmCNFA struct, explaining 
which fields are valid at which stages. For example, it seems that 
'trgms' array is calculated only after building the CNFA, by 
getTrgmVector() function, while arcsCount is updated on the fly, while 
recursing in the getState() function.

* What is the representation used for the path matrix? Needs a comment.

* What do the getColorinfo() and scanColorMap() functions do? What 
exactly does a color represent? What's the tradeoff in choosing 
MAX_COLOR_CHARS?

- Heikki