Fixing GIN for empty/null/full-scan cases - Mailing list pgsql-hackers

I've been thinking about how to fix GIN's assorted corner-case problems,
as has been discussed several times, most recently here:
http://archives.postgresql.org/pgsql-hackers/2010-10/msg00521.php
See also
http://wiki.postgresql.org/wiki/Todo#GIN

There are basically three related issues:

1. GIN doesn't store anything in the index for a NULL item.
2. GIN doesn't store anything in the index for an empty (zero-key) item.
3. GIN can't deal with NULL key values.

(An "item" is a composite value to be indexed, such as a tsvector or
array.  A "key" is an individual indexable value, such as a lexeme or
array element.)

Because of #1 and #2, GIN can't handle full-index scans.  This is not
because the code can't scan all of the index, but because doing so
wouldn't necessarily return a TID for every existing heap row.

We have to fix #1 and #2, and then get rid of the prohibition on
full-index scans, in order to deal with the complaints that appear in our
TODO list.  The problem with NULL key values is somewhat less pressing,
because most GIN-indexable operators are strict enough to not care about
null keys, so we could perhaps just ignore nulls.  But I'm inclined to
think that it'd be best to fix that now while we're whacking the code and
opclass APIs around, rather than probably having to go back for yet
another round later.  A concrete example of a hit we'll take if we don't
index nulls is that array-is-contained-in would have to be treated as a
lossy rather than lossless index search, since there'd be no way to tell
from the index whether the array item contains any nulls (rendering it not
contained in anything).


As far as storage in the index goes, NULL key values seem perfectly simple
to deal with: just allow a null to get stored for the key value of a GIN
index entry.  What we discussed doing to fix #1 and #2 was to store a
"dummy" index entry, rather than no entries at all.  The least complicated
way to do that would be to store a NULL key.  That would mean that,
for example with integer arrays, all three of these item values would have
identical index entries:NULL::int[]'{}'::int[]'{NULL}'::int[]
So any searches that need to yield different answers for these cases
(ie find some but not all of them) would have to be treated as lossy.
That's not necessarily a show-stopper, but I'm inclined to think that
it is worth working a bit harder so that we can distinguish them.

It's already true that GIN requires special-case code to construct its
index entries (look at GinFormTuple).  What I'm thinking we could do
without too much additional ugliness is store either the key value (for
the normal, non-null key case) or an int16 representing a "category":1 = null key value2 = placeholder for zero-key
item3= placeholder for null item
 
The index entry's IndexTupleHasNulls flag would be sufficient to
distinguish whether a key or a category flag is present, since there
are no other potentially-null values in a GIN index entry.  There is
room in this scheme for more "categories" if we ever need any, though
I can't think of what they'd be.


The other sticky problem is how to extend the GIN opclass support function
API definitions for all this.  I propose the following:

compare(): doesn't really need any changes.  Just as in btree, we only
need to call the key comparison function for non-null keys.  The various
categories of nulls can have hard-wired comparison behavior.

extractValue(): needs an extension so it can return null key values.
I propose adding a third argument:Datum *extractValue(Datum inputValue, int32 *nkeys,                    bool
**nullFlags)
If the function wants to return any nulls, it has to palloc an array
of nkeys bools and store a pointer to it at *nullFlags.  We can initialize
*nullFlags to NULL (implying no null keys) for backwards compatibility
with existing functions that aren't aware of the third argument.  In the
case of a null item value, we needn't call the function at all, we can
just generate the dummy entry directly.  Zero-key items can be handled
compatibly with the current behavior: if nkeys is returned as zero,
we'll generate a dummy entry instead of generating nothing at all.

extractQuery(): likewise, needs to be able to return null query element
values.  I propose adding a sixth argument:Datum *extractQuery(Datum query, int32 *nkeys, StrategyNumber n,
             bool **pmatch, Pointer **extra_data,                    bool **nullFlags)
 
As above, we can initialize *nullFlags to NULL for backwards
compatibility.  We will continue to assume that a null query value means
an unsatisfiable query, so we don't need to be able to call extractQuery
with a null input query.  We'll keep the current convention that returning
nkeys = -1 means an unsatisfiable query while returning zero requests a
full index scan.

consistent(): needs to be able to deal with possible nulls in the
extracted query values.  I think the best way to deal with this is to pass
through not just the null array but also the extracted datum array,
instead of forcing consistent() to possibly repeat the work of
extractQuery().  So the proposed signature is
bool consistent(bool check[], StrategyNumber n, Datum query,                int32 nkeys, Pointer extra_data[], bool
*recheck,       Datum query_keys[], bool is_null[])
 

where the last two arguments are new and will just be ignored by existing
opclasses.  The check[] array will now have IS NOT DISTINCT FROM
semantics: that is, we'll set check[i] true if query_keys[i] is a null and
there's a null key value in the index for the current heap TID.  If the
consistent() function wants to verify that check[i]==true means real
equality, it has to check is_null[i] as well.

An important point in connection with full-index scans is that it will now
be possible for consistent() to be called with nkeys == 0.  The reason to
do that rather than just assuming the result is TRUE is that we need to
know whether to recheck.  Also, I have noticed that some consistent()
functions assume that there's always at least one TRUE element in check[]
(see ginarrayconsistent for example).  This assumption now fails, since
for a zero-key placeholder entry we will need to call the consistent()
function with no check[] flags set.  Since no such assumption is
sanctioned by the documented spec for consistent(), I don't feel bad about
breaking it.  (Note: for a null-item placeholder, we'll assume the
consistent() result is FALSE without calling it.  Such an index entry
could only give rise to an index hit in a qual-free index scan.)

comparePartial(): I think we can avoid changing the API here.  It should
be okay to assume that null index values never match any form of partial
search.  If we arrange to sort them to the end, we can just stop a partial
scan as soon as we hit a null.

The upshot of the above conventions is that it'll still be the case that
GIN-indexable operators must be strict: they cannot return TRUE if either
directly given argument is NULL.  However, operators that can succeed even
though some element of a composite argument is NULL will work properly now.


At this point you're probably asking yourself "so, how
backwards-compatible is all this?".  Here's my analysis:

* Existing GIN indexes are upwards compatible so far as on-disk storage
goes, but they will of course be missing entries for empty, null, or
null-containing items.  Users who want to do searches that should find
such items will need to reindex after updating to 9.1.

* Existing extractValue() and extractQuery() functions will work as well
(or poorly) as before.  Presumably they either ignore potential null key
values or throw error if they find one.

* Existing consistent() functions will still work as before, if they are
being used in conjunction with existing extractValue() and extractQuery()
functions, since those will never return any null key or query values.
There's a small possibility that one would give a false-positive answer
if called with no true check[] items; but such cases would have failed
outright in 9.0 or before, so no previously-working queries would be
broken.


Comments?
        regards, tom lane