Fixing GIN for empty/null/full-scan cases
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 value
2 = placeholder for zero-key item
3 = 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
On Tue, Jan 4, 2011 at 4:09 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
* 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.
This is the only part of this proposal that bothers me a little bit.
It would be nice if the system could determine whether a GIN index is
"upgraded from 9.0 or earlier and thus doesn't contain these entries"
- and avoid trying to use the index for these sorts of queries in
cases where it might return wrong answers.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Robert Haas <robertmhaas@gmail.com> writes:
On Tue, Jan 4, 2011 at 4:09 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
* 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.
This is the only part of this proposal that bothers me a little bit.
It would be nice if the system could determine whether a GIN index is
"upgraded from 9.0 or earlier and thus doesn't contain these entries"
- and avoid trying to use the index for these sorts of queries in
cases where it might return wrong answers.
I don't think it's really worth the trouble. The GIN code has been
broken for these types of queries since day one, and yet we've had only
maybe half a dozen complaints about it. Moreover there's no practical
way to "avoid trying to use the index", since in many cases the fact
that a query requires a full-index scan isn't determinable at plan time.
The best we could really do is throw an error at indexscan start, and
that doesn't seem all that helpful. But it probably wouldn't take much
code either, if you're satisfied with that answer. (I'm envisioning
adding a version ID to the GIN metapage and then checking that before
proceeding with a full-index scan.)
regards, tom lane
On 1/4/11 1:49 PM, Tom Lane wrote:
I don't think it's really worth the trouble. The GIN code has been
broken for these types of queries since day one, and yet we've had only
maybe half a dozen complaints about it. Moreover there's no practical
way to "avoid trying to use the index", since in many cases the fact
that a query requires a full-index scan isn't determinable at plan time.
Actually, there's been a *lot* of complaining about the GIN issues.
It's just that most of that complaining doesn't reach -hackers.
The common pattern I've seen in our practice and on IRC is:
1) user has GiST indexes
2) user tries converting them to GIN
3) user gets "full index scan" errors
4) user switches back and gives up
I agree that backwards compatibility should not be a priority; it is
sufficient to tell users to reindex. For one thing, anyone who *is*
using GIN presently will have written their application code to avoid
full index scans.
--
-- Josh Berkus
PostgreSQL Experts Inc.
http://www.pgexperts.com
On Tue, Jan 4, 2011 at 4:49 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Robert Haas <robertmhaas@gmail.com> writes:
On Tue, Jan 4, 2011 at 4:09 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
* 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.This is the only part of this proposal that bothers me a little bit.
It would be nice if the system could determine whether a GIN index is
"upgraded from 9.0 or earlier and thus doesn't contain these entries"
- and avoid trying to use the index for these sorts of queries in
cases where it might return wrong answers.I don't think it's really worth the trouble. The GIN code has been
broken for these types of queries since day one, and yet we've had only
maybe half a dozen complaints about it. Moreover there's no practical
way to "avoid trying to use the index", since in many cases the fact
that a query requires a full-index scan isn't determinable at plan time.The best we could really do is throw an error at indexscan start, and
that doesn't seem all that helpful. But it probably wouldn't take much
code either, if you're satisfied with that answer. (I'm envisioning
adding a version ID to the GIN metapage and then checking that before
proceeding with a full-index scan.)
I'd be satisfied with that answer. It at least makes it a lot more
clear when you've got a problem. If this were a more common scenario,
I'd probably advocate for a better solution, but the one you propose
seems adequate given the frequency of the problem as you describe it.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Attached is a WIP patch along the lines I suggested earlier: this covers
the core code and docs, but doesn't yet do anything to the various
opclass-specific functions. Testing it, I find that there was a gap in
my previous thinking. The patch works for cases like
select ... where arraycol = '{}'
which previously failed for lack of ability to do a full-index scan.
However, it doesn't work for cases like
select ... where arraycol <@ '{1,2}'
This correctly returns {1}, {2}, and {1,2} --- but it doesn't find {}.
There are empty-item placeholder entries in the index for the latter,
but since the query does contain some real keys, it's not a full-index
scan and thus it doesn't look for the empty-item placeholders.
There are basically two ways we could fix this: with or without the
extractQuery function's cooperation. Without any help from
extractQuery, it would be necessary for *every* GIN query to include
empty-item placeholders in the search and then see if the consistentFn
would succeed on those rows. That seems pretty unattractive from an
efficiency standpoint, not to mention that it opens the possibility
I mentioned before of old consistentFns assuming without checking
that there's at least one true check[] entry.
What seems like a better idea is for extractQuery to explicitly tell
us whether or not an empty indexed item can match the query. In the
terms of this patch, that amounts to including a GIN_CAT_EMPTY_ITEM
placeholder as one of the search targets. Now, there are two ways
we could do that, too:
1. Explicitly include the EMPTY_ITEM target as part of the Datum[] array
returned by extractQuery. That seems a bit grotty on a couple of
grounds, one being that we couldn't use just a bool isNull[] auxiliary
array but would have to expose GinNullCategory or something similar to
the opclasses. Another problem with it is that then the "empty" target
would presumably be included in the check[] array, with the result that
an "empty" heap item would have one check[] value set, which would mess
up simple AND/OR combination logic such as you see in
ginarrayconsistent().
2. Add another output bool parameter to extractQuery that it must set
true (from a default false state) if the query could match with no check
values set. This would prompt the GIN code to search for EMPTY_ITEM
placeholders, but they'd not be part of the check[] array.
With either one of these approaches, we can avoid the
backwards-compatibility problem of a consistentFn being passed cases
that it's not expecting, because it's not going to see any such cases
without an update to its cohort extractQueryFn. (In particular, if the
extractQueryFn returns zero keys and doesn't take an additional action
to say that an empty item can match, then we'll treat that as an
unsatisfiable query instead of calling a consistentFn that might
misbehave on such a case.)
I think I like option #2 better. Comments?
regards, tom lane
Em 06-01-2011 21:31, Tom Lane escreveu:
I think I like option #2 better. Comments?
+1.
--
Euler Taveira de Oliveira
http://www.timbira.com/
I wrote:
2. Add another output bool parameter to extractQuery that it must set
true (from a default false state) if the query could match with no check
values set. This would prompt the GIN code to search for EMPTY_ITEM
placeholders, but they'd not be part of the check[] array.
On further reflection: if we're going to go this route, we really ought
to take one more step and allow the opclass to demand a full-index scan.
The reason for this is cases like tsvector's NOT operator:
SELECT ... WHERE tsvectorcol @@ '! unwanted'::tsquery
Right now, this will do what it says on the tin if implemented as a
seqscan. It will fail (silently, I think) if implemented as a GIN index
search. We didn't use to have any way of making it behave sanely as
an indexsearch, but the mechanisms I'm building now would support doing
this right.
So, instead of just a bool, I'm now proposing adding an int return
argument specified like this:
searchMode is an output argument that allows extractQuery to specify
details about how the search will be done. If *searchMode is set to
GIN_SEARCH_MODE_DEFAULT (which is the value it is initialized to
before call), only items that match at least one of the returned
keys are considered candidate matches. If *searchMode is set to
GIN_SEARCH_MODE_INCLUDE_EMPTY, then in addition to items containing
at least one matching key, items that contain no keys at all are
considered candidate matches. (This mode is useful for implementing
is-subset-of operators, for example.) If *searchMode is set to
GIN_SEARCH_MODE_ALL, then all non-null items in the index are
considered candidate matches, whether they match any of the returned
keys or not. (This mode is much slower than the other two choices,
since it requires scanning essentially the entire index, but it may
be necessary to implement corner cases correctly. An operator that
needs this mode in most cases is probably not a good candidate for a
GIN operator class.) The symbols to use for setting this mode are
defined in access/gin.h.
The default mode is equivalent to what used to happen implicitly, so
this is still backwards-compatible with existing opclasses.
Don't have code to back up this spec yet, but I believe I see how to do
it.
regards, tom lane
On Jan 4, 2011, at 3:18 PM, Josh Berkus wrote:
Actually, there's been a *lot* of complaining about the GIN issues.
It's just that most of that complaining doesn't reach -hackers.The common pattern I've seen in our practice and on IRC is:
1) user has GiST indexes
2) user tries converting them to GIN
3) user gets "full index scan" errors
4) user switches back and gives up
We (PGX) actually have a client who could use this. Tom, if you have patches as you work on this (or, better, a branch in a Git repo), I could do some testing on your client's code with it. It would involve converting from a GiST to a GIN index and then seeing how well the queries fare. Would that be helpful to you?
Best,
David
"David E. Wheeler" <david@kineticode.com> writes:
We (PGX) actually have a client who could use this. Tom, if you have patches as you work on this (or, better, a branch in a Git repo), I could do some testing on your client's code with it. It would involve converting from a GiST to a GIN index and then seeing how well the queries fare. Would that be helpful to you?
Well, actually, I just committed it. If you want to test, feel free.
Note that right now only the anyarray && <@ @> operators are genuinely
fixed ... I plan to hack on tsearch and contrib pretty soon though.
regards, tom lane
On Jan 7, 2011, at 4:19 PM, Tom Lane wrote:
Well, actually, I just committed it. If you want to test, feel free.
Note that right now only the anyarray && <@ @> operators are genuinely
fixed ... I plan to hack on tsearch and contrib pretty soon though.
Hrm, the queries I wrote for this sort of thing use intarray:
WHERE blah @@ '(12|14)'::query_int
That's not done yet though, right?
Best,
David
"David E. Wheeler" <david@kineticode.com> writes:
On Jan 7, 2011, at 4:19 PM, Tom Lane wrote:
Well, actually, I just committed it. If you want to test, feel free.
Note that right now only the anyarray && <@ @> operators are genuinely
fixed ... I plan to hack on tsearch and contrib pretty soon though.
Hrm, the queries I wrote for this sort of thing use intarray:
WHERE blah @@ '(12|14)'::query_int
That's not done yet though, right?
Right. Maybe sometime this weekend.
regards, tom lane
"David E. Wheeler" <david@kineticode.com> writes:
On Jan 7, 2011, at 4:19 PM, Tom Lane wrote:
Well, actually, I just committed it. If you want to test, feel free.
Note that right now only the anyarray && <@ @> operators are genuinely
fixed ... I plan to hack on tsearch and contrib pretty soon though.
Hrm, the queries I wrote for this sort of thing use intarray:
I'm going to work on contrib/intarray first (before tsearch etc)
so that you can do whatever testing you want sooner.
One of the things that first got me annoyed about the whole GIN
situation is that intarray's definitions of the <@ and @> operators were
inconsistent with the core operators of the same names. I believe that
the inconsistency has to go away. Really the only reason that intarray
has its own versions of these operators at all is that it can be faster
than the generic anyarray versions in core. There seem to be three ways
in which intarray is simpler/faster than the generic operators:
* restricted to integer arrays
* restricted to 1-D arrays
* doesn't allow nulls in the arrays
The first of these is pretty important from a speed perspective, and
it's also basically free because of the type system: the parser won't
attempt to apply intarray's operators to anything that's not an integer
array. The second one seems a little more dubious. AFAICS the code
isn't actually exploiting 1-D-ness anywhere; it always uses
ArrayGetNItems() to compute the array size, for example. I propose that
we just drop that restriction and let it accept arrays that are
multidimensional, implicitly linearizing the elements in storage order.
(Any created arrays will still be 1-D though.)
The third restriction is a bit harder to decide what to do about.
If we keep it then intarray's <@ etc will throw errors in some cases
where core would not have. However, dealing with nulls will make the
code significantly uglier and probably slower than it is now; and that's
not work that I'm excited about doing right now anyway. So what I
propose for the moment is that intarray still have that restriction.
Maybe someone else will feel like fixing it later.
I will however fix the issue described here:
http://archives.postgresql.org/pgsql-bugs/2010-12/msg00032.php
that intarray sometimes throws "nulls not allowed" errors on
arrays that once contained nulls but now don't. That can be
done with a relatively localized patch --- we just need to look
a little harder when the ARR_HASNULL flag is set.
Comments, objections?
regards, tom lane
On Jan 8, 2011, at 1:59 PM, Tom Lane wrote:
Hrm, the queries I wrote for this sort of thing use intarray:
I'm going to work on contrib/intarray first (before tsearch etc)
so that you can do whatever testing you want sooner.
No, of course not.
One of the things that first got me annoyed about the whole GIN
situation is that intarray's definitions of the <@ and @> operators were
inconsistent with the core operators of the same names. I believe that
the inconsistency has to go away. Really the only reason that intarray
has its own versions of these operators at all is that it can be faster
than the generic anyarray versions in core. There seem to be three ways
in which intarray is simpler/faster than the generic operators:* restricted to integer arrays
* restricted to 1-D arrays
* doesn't allow nulls in the arrays
My understanding is that they also perform much better if the values in an integer array are ordered. Does that matter?
Best,
David
"David E. Wheeler" <david@kineticode.com> writes:
On Jan 8, 2011, at 1:59 PM, Tom Lane wrote:
There seem to be three ways
in which intarray is simpler/faster than the generic operators:* restricted to integer arrays
* restricted to 1-D arrays
* doesn't allow nulls in the arrays
My understanding is that they also perform much better if the values in an integer array are ordered. Does that matter?
Some of the operations sort the array contents as an initial step. I'm
not sure how much faster they'll be if the array is already ordered,
but in any case they don't *require* presorted input.
regards, tom lane
"David E. Wheeler" <david@kineticode.com> writes:
On Jan 7, 2011, at 4:19 PM, Tom Lane wrote:
Well, actually, I just committed it. If you want to test, feel free.
Note that right now only the anyarray && <@ @> operators are genuinely
fixed ... I plan to hack on tsearch and contrib pretty soon though.
Hrm, the queries I wrote for this sort of thing use intarray:
WHERE blah @@ '(12|14)'::query_int
That's not done yet though, right?
intarray is done now, feel free to test ...
regards, tom lane
Tom,
On Jan 8, 2011, at 9:41 PM, Tom Lane wrote:
"David E. Wheeler" <david@kineticode.com> writes:
On Jan 7, 2011, at 4:19 PM, Tom Lane wrote:
Well, actually, I just committed it. If you want to test, feel free.
Note that right now only the anyarray && <@ @> operators are genuinely
fixed ... I plan to hack on tsearch and contrib pretty soon though.Hrm, the queries I wrote for this sort of thing use intarray:
WHERE blah @@ '(12|14)'::query_int
That's not done yet though, right?intarray is done now, feel free to test ...
Thanks, working on it now. I'm restoring a dump from 8.4, but got these erors:
pg_restore: [archiver (db)] Error from TOC entry 3227; 2616 46485 OPERATOR CLASS gin__int_ops postgres
pg_restore: [archiver (db)] could not execute query: ERROR: function ginarrayextract(anyarray, internal) does not exist
Command was: CREATE OPERATOR CLASS gin__int_ops
FOR TYPE integer[] USING gin AS
STORAGE integer ,
OPERATOR 3 &&(integer[],int...
pg_restore: [archiver (db)] could not execute query: ERROR: operator class "contrib.gin__int_ops" does not exist for access method "gin"
Command was: ALTER OPERATOR CLASS contrib.gin__int_ops USING gin OWNER TO postgres;
pg_restore: [archiver (db)] Error from TOC entry 3254; 3600 16245434 TEXT SEARCH DICTIONARY en_mls_20101103 postgres
Did a signature change or something? Is there something that needs a compatibility interface of some kind?
Thanks,
David
"David E. Wheeler" <david@kineticode.com> writes:
Thanks, working on it now. I'm restoring a dump from 8.4, but got these erors:
pg_restore: [archiver (db)] Error from TOC entry 3227; 2616 46485 OPERATOR CLASS gin__int_ops postgres
pg_restore: [archiver (db)] could not execute query: ERROR: function ginarrayextract(anyarray, internal) does not exist
Did a signature change or something?
Yeah. I think if you just load up the current contrib/intarray first,
you'll be fine (ignore all the object-already-exists errors).
Is there something that needs a compatibility interface of some kind?
No, what we need is a decent extension package manager ;-)
regards, tom lane
On Jan 12, 2011, at 4:35 PM, Tom Lane wrote:
Did a signature change or something?
Yeah. I think if you just load up the current contrib/intarray first,
you'll be fine (ignore all the object-already-exists errors).
Oh, from 9.1devel? yeah, okay. Will do that tomorrow (finishing the current load to make sure that there are no other errors I can't ignore, but won't see among all the intarray stuff tomorrow).
Is there something that needs a compatibility interface of some kind?
No, what we need is a decent extension package manager ;-)
Yeah. Maybe you can do that this weekend? Or, I dunno, while you “sleep” tonight?
Best,
David
"David E. Wheeler" <david@kineticode.com> writes:
On Jan 12, 2011, at 4:35 PM, Tom Lane wrote:
No, what we need is a decent extension package manager ;-)
Yeah. Maybe you can do that this weekend? Or, I dunno, while you �sleep� tonight?
Supposedly it's in the queue for the upcoming CF :-)
regards, tom lane
