Re: GIN versus zero-key queries

От:

Jeff Davis <pgsql@j-davis.com>

Дата:

26 марта 2009 г. в 17:45:49

On Wed, 2009-03-25 at 13:25 -0400, Tom Lane wrote:
> I am not sure whether the statement in 52.5 is still accurate, though.
> We have an API definition by which extractQuery can distinguish "all
> match" from "no match".  If we just legislate that "some match" isn't
> a valid behavior for zero-key queries, then the code is correct and the
> documentation is wrong.  However, if the above quote is correct, then
> I think newScanKey() is buggy.

Legislating that "some match" is invalid for zero-key queries seems
reasonable to me.

If the operator class author wants it to throw an error for zero keys
(as the documentation says should happen), they can do that easily
enough without being forced. However, if the opclass author finds "all
match" to be useful behavior (which seems reasonable), I don't see a
reason to stop them.

Regards,Jeff Davis

Re: GIN versus zero-key queries

От:

Bruce Momjian <bruce@momjian.us>

Дата:

15 апреля 2009 г. в 20:46:01


Where are we on this?

---------------------------------------------------------------------------

Tom Lane wrote:
> Teodor Sigaev  writes:
> >> We have an API definition by which extractQuery can distinguish "all
> >> match" from "no match".  If we just legislate that "some match" isn't
> >> a valid behavior for zero-key queries, then the code is correct and the
> 
> > Right now I don't see an example with zero keys and "some match", consistent 
> > method will not have any information about indexed tuple and hence it could not 
> > produce any reasonable result. It seems to me, that paragraph should be removed 
> > at all.
> 
> Well, we still have to document the fact that GIN fails when presented
> with a query that would require a full-index scan.  I've updated section
> 52.5 as attached.  (I removed the claim that multiple matches were a
> problem, since this is obviously not true for a bitmap scan, and I
> suppose that the plain indexscan code must have had a way to deal with
> it too.)
> 
> More generally, though, I find myself quite unhappy with the fact that
> GIN doesn't provide reasonable behavior for the no-keys corner cases.
> If we are going to provide operator classes that claim to implement
> index acceleration of standard operators, it is not okay for them
> to not match the exact semantics of those operators.  Right now it's
> a mess for empty arrays, and it's even more of a mess for arrays
> containing nulls.  array_contain_compare() considers nulls as never
> matching, which means that
> 
> regression=# select array[1,null] <@ array[1,null];
>  ?column? 
> ----------
>  f
> (1 row)
> 
> which is entirely bizarre when you compare that result to
> 
> regression=# select array[1,null] = array[1,null];
>  ?column? 
> ----------
>  t
> (1 row)
> 
> It's obviously too late to do anything about this for 8.4, but I would
> like to have a TODO item to figure out how to do this right.  We need to
> adjust the behavior of the operators to be consistent, and then we need
> to make it possible for GIN to implement them exactly.  I wonder whether
> we should not change GIN to automatically do something reasonable for
> empty indexed values, ie stick them into the index in some special way
> denoting "no indexable keys for this item".  The dummy-value solution
> is not something that operator classes should have to come up with,
> and not all data types present a reasonable way to have dummy values
> anyway.
> 
> 			regards, tom lane
> 
> 
>  
>   GIN doesn't support full index scans.  The reason for
>   this is that extractValue</> is allowed to return zero keys,
>   as for example might happen with an empty string or empty array.  In such
>   a case the indexed value will be unrepresented in the index.  It is
>   therefore impossible for GIN to guarantee that a
>   scan of the index can find every row in the table.
>  
> 
>  
>   Because of this limitation, when extractQuery returns
>   nkeys = 0</> to indicate that all values match the query,
>   GIN will emit an error.  (If there are multiple ANDed
>   indexable operators in the query, this happens only if they all return zero
>   for nkeys</>.)
>  
> 
>  
>   It is possible for an operator class to circumvent the restriction against
>   full index scan.  To do that, extractValue</> must return at least
>   one (possibly dummy) key for every indexed value, and
>   extractQuery must convert an unrestricted search into
>   a partial-match query that will scan the whole index.  This is inefficient
>   but might be necessary to avoid corner-case failures with operators such
>   as LIKE</> or subset inclusion.
>  
> 
>  
>   GIN assumes that indexable operators are strict.
>   This means that extractValue</> will not be called at all on
>   a NULL value (so the value will go unindexed), and
>   extractQuery will not be called on a NULL comparison
>   value either (instead, the query is presumed to be unmatchable).
>  
> 
>  
>   A possibly more serious limitation is that GIN cannot
>   handle NULL keys — for example, an array containing a NULL cannot
>   be handled except by ignoring the NULL.
>  
> 
> -- 
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers

--  Bruce Momjian          http://momjian.us EnterpriseDB                             http://enterprisedb.com
 + If your life is a hard drive, Christ can be your backup. +

Re: GIN versus zero-key queries

От:

Tom Lane <tgl@sss.pgh.pa.us>

Дата:

9 апреля 2009 г. в 16:21:01

Teodor Sigaev  writes:
>> We have an API definition by which extractQuery can distinguish "all
>> match" from "no match".  If we just legislate that "some match" isn't
>> a valid behavior for zero-key queries, then the code is correct and the

> Right now I don't see an example with zero keys and "some match", consistent 
> method will not have any information about indexed tuple and hence it could not 
> produce any reasonable result. It seems to me, that paragraph should be removed 
> at all.

Well, we still have to document the fact that GIN fails when presented
with a query that would require a full-index scan.  I've updated section
52.5 as attached.  (I removed the claim that multiple matches were a
problem, since this is obviously not true for a bitmap scan, and I
suppose that the plain indexscan code must have had a way to deal with
it too.)

More generally, though, I find myself quite unhappy with the fact that
GIN doesn't provide reasonable behavior for the no-keys corner cases.
If we are going to provide operator classes that claim to implement
index acceleration of standard operators, it is not okay for them
to not match the exact semantics of those operators.  Right now it's
a mess for empty arrays, and it's even more of a mess for arrays
containing nulls.  array_contain_compare() considers nulls as never
matching, which means that

regression=# select array[1,null] <@ array[1,null];?column? 
----------f
(1 row)

which is entirely bizarre when you compare that result to

regression=# select array[1,null] = array[1,null];?column? 
----------t
(1 row)

It's obviously too late to do anything about this for 8.4, but I would
like to have a TODO item to figure out how to do this right.  We need to
adjust the behavior of the operators to be consistent, and then we need
to make it possible for GIN to implement them exactly.  I wonder whether
we should not change GIN to automatically do something reasonable for
empty indexed values, ie stick them into the index in some special way
denoting "no indexable keys for this item".  The dummy-value solution
is not something that operator classes should have to come up with,
and not all data types present a reasonable way to have dummy values
anyway.
		regards, tom lane

 GIN doesn't support full index scans.  The reason for this is that extractValue</> is allowed to return zero keys, as for example might happen with an empty string or empty array.  In such a case the indexed value will be unrepresented in the index.  It is therefore impossible for GIN to guarantee that a scan of the index can find every row in the table.
 Because of this limitation, when extractQuery returns nkeys = 0</> to indicate that all values match the query, GIN will emit an error.  (If there are multiple ANDed indexable operators in the query, this happens only if they all return zero for nkeys</>.)
 It is possible for an operator class to circumvent the restriction against full index scan.  To do that, extractValue</> must return at least one (possibly dummy) key for every indexed value, and extractQuery must convert an unrestricted search into a partial-match query that will scan the whole index.  This is inefficient but might be necessary to avoid corner-case failures with operators such as LIKE</> or subset inclusion.
 GIN assumes that indexable operators are strict. This means that extractValue</> will not be called at all on a NULL value (so the value will go unindexed), and extractQuery will not be called on a NULL comparison value either (instead, the query is presumed to be unmatchable).
 A possibly more serious limitation is that GIN cannot handle NULL keys — for example, an array containing a NULL cannot be handled except by ignoring the NULL.

GIN versus zero-key queries

От:

Tom Lane <tgl@sss.pgh.pa.us>

Дата:

25 марта 2009 г. в 14:44:52

Our fine manual sayeth (in section 52.5)
 When extractQuery returns zero keys, GIN will emit an error. Depending on the operator, a void query might match all, some, or none of the indexed values (for example, every array contains the empty array, but does not overlap the empty array), and GIN cannot determine the correct answer, nor produce a full-index-scan result if it could determine that that was correct.

However, the behavior actually implemented by newScanKey() doesn't seem
to agree with this.  If there are multiple scankeys (ie, multiple
indexable clauses) then what actually happens is you get an error
report only if *all* the clauses are zero-key queries.  If some clauses
are zero-key and some are normal, it effectively ignores the zero-key
ones and sails ahead with the normal ones.  This amounts to assuming
that the zero-key queries match all possible indexed values.  But as
noted by the manual, that's not a correct conclusion for some operator
semantics.

I am not sure whether the statement in 52.5 is still accurate, though.
We have an API definition by which extractQuery can distinguish "all
match" from "no match".  If we just legislate that "some match" isn't
a valid behavior for zero-key queries, then the code is correct and the
documentation is wrong.  However, if the above quote is correct, then
I think newScanKey() is buggy.

Comments?
		regards, tom lane

Re: GIN versus zero-key queries

От:

Teodor Sigaev <teodor@sigaev.ru>

Дата:

9 апреля 2009 г. в 12:10:35

> We have an API definition by which extractQuery can distinguish "all
> match" from "no match".  If we just legislate that "some match" isn't
> a valid behavior for zero-key queries, then the code is correct and the

Right now I don't see an example with zero keys and "some match", consistent 
method will not have any information about indexed tuple and hence it could not 
produce any reasonable result. It seems to me, that paragraph should be removed 
at all.

-- 
Teodor Sigaev                                   E-mail: teodor@sigaev.ru                                                   WWW: http://www.sigaev.ru/