Re: Proposal: q-gram GIN and GiST indexes

Alexander Korotkov <aekorotkov(at)gmail(dot)com> writes:
> On Tue, Apr 5, 2011 at 5:05 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> I am probably being stupid here, but doesn't the number of links to
>> rows grow proportionately to the number of n-grams?

> Number of links to rows grow proportionally to total number of extracted
> q-grams, but not proportionally to number of unique q-grams.

Sure. The number of links is exactly proportional to the size of the
text, no? An n-character text contains exactly n-q+1 q-grams, no more,
no less. You might have some rules that cause you to discard some of
them, but basically the TID portion of the index will be proportional
to data volume, with no measurable dependence on q.

Or at least that's what it seems like before I've had my morning
caffeine fix...

regards, tom lane