Re: Understanding GIN posting trees

> Oh, I see. You essentially do a merge join of all the posting trees of
> query keys.
>
> Hmm, but we do need to scan all the posting trees of all the matched
> keys in whole anyway. We could collect all TIDs in the posting lists of
> all the keys into separate TIDBitmaps, and then combine the bitmaps,
> calling consistentFn for each TID that was present in at least one
> bitmap. I guess the performance characteristics of that would be
> somewhat different from what we have now, and you'd need to keep a lot
> of in-memory bitmaps if the query contains a lot of keys.
I hope to reimplement amgettuple interface someday and this interface is
designed for small startup cost. With bitmaps per search key it will be impossible.

> While we're at it, it just occurred to me that it if the number of query
> keys is limited, say <= 16, you could build a lookup table for each
> combination of keys either occurring or not. You could use then use that
> instead of calling consistentFn for each possible match. You could even
> use the table to detect common cases like "all/any keys must match",
> perhaps opening some optimization opportunities elsewhere.
I'm afraid that it becomes looking as a separate optimizer/planner :)

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/