Subject: Fixing GIN for empty/null/full-scan cases

From: Tom Lane <[email-masked]>
Date: Tue, 04 Jan 2011 16:09:17 -0500

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

---

From: Robert Haas <[email-masked]>
Date: Tue, 4 Jan 2011 16:37:46 -0500

> 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

---

From: Tom Lane <[email-masked]>
Date: Tue, 04 Jan 2011 16:49:27 -0500

> 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

---

From: Josh Berkus <[email-masked]>
Date: Tue, 04 Jan 2011 15:18:46 -0800

> 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

---

From: Robert Haas <[email-masked]>
Date: Tue, 4 Jan 2011 18:18:57 -0500

> 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.

---

From: Tom Lane <[email-masked]>
Date: Thu, 06 Jan 2011 19:31:20 -0500

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

---

From: Euler Taveira de Oliveira <[email-masked]>
Date: Fri, 07 Jan 2011 00:49:32 -0300

> I think I like option #2 better.  Comments?
+1.

-- 
   Euler Taveira de Oliveira
   http://www.timbira.com/

---

From: Tom Lane <[email-masked]>
Date: Fri, 07 Jan 2011 11:07:48 -0500

> 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

---

From: David E. Wheeler <[email-masked]>
Date: Fri, 7 Jan 2011 16:13:37 -0800

> 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

---

From: Tom Lane <[email-masked]>
Date: Fri, 07 Jan 2011 19:19:30 -0500

> 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 woul…

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

---

From: "David E. Wheeler" <[email-masked]>
Date: Fri, 7 Jan 2011 17:24:28 -0800

> 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

---

From: Tom Lane <[email-masked]>
Date: Fri, 07 Jan 2011 20:29:10 -0500

> That's not done yet though, right?

Right.  Maybe sometime this weekend.

			regards, tom lane

---

From: Tom Lane <[email-masked]>
Date: Sat, 08 Jan 2011 16:59:11 -0500

> 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

---

From: "David E. Wheeler" <[email-masked]>
Date: Sat, 8 Jan 2011 14:04:03 -0800

> so that you can do whatever testing you want sooner.

No, of course not.

> 	* 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

---

From: Tom Lane <[email-masked]>
Date: Sat, 08 Jan 2011 17:49:43 -0500

"David E. Wheeler" <[email-masked]> writes:
>> There seem to be three ways

> 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

---

From: Tom Lane <[email-masked]>
Date: Sun, 09 Jan 2011 00:41:13 -0500

> That's not done yet though, right?

intarray is done now, feel free to test ...

			regards, tom lane

---

From: "David E. Wheeler" <[email-masked]>
Date: Wed, 12 Jan 2011 16:08:22 -0800

Tom,

> 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

---

From: Tom Lane <[email-masked]>
Date: Wed, 12 Jan 2011 19:35:20 -0500

> 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

---

From: "David E. Wheeler" <[email-masked]>
Date: Wed, 12 Jan 2011 16:46:31 -0800

> 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).

> 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

---

From: Tom Lane <[email-masked]>
Date: Wed, 12 Jan 2011 20:12:03 -0500

> 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

---

From: Dimitri Fontaine <[email-masked]>
Date: Thu, 13 Jan 2011 12:24:18 +0100

Tom Lane <[email-masked]> writes:
>> Yeah. Maybe you can do that this weekend? Or, I dunno, while you sleep tonight?
>

Hehe, and some provision have been made to support upgrading from 9.0 to
9.1 too:

  http://pgsql.tapoueh.org/extensions/doc/html/extend-extension.html#AEN50748

But that won't solve the dump-from-9.0 and restore-into-9.1 by itself,
the only way for us to solve that problem that I can think of would be
to backpatch a new feature.  Do it the old-way until you upgrade from
9.1 to later might be our answer here.

Regards,
-- 
Dimitri Fontaine
http://2ndQuadrant.fr     PostgreSQL : Expertise, Formation et Support

---

From: Bruce Momjian <[email-masked]>
Date: Thu, 13 Jan 2011 22:16:33 -0500 (EST)

Robert Haas wrote:
> >>> null-containing items. ?Users who want to do searches that should find
> > I don't think it's really worth the trouble. ?The GIN code has been
> > maybe half a dozen complaints about it. ?Moreover there's no practical
> > 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

What does pg_upgrade need to do about this for 9.1?  Just tell people
they might get an GIN error someday?

-- 
  Bruce Momjian  <[email-masked]>        http://momjian.us
  EnterpriseDB                             http://enterprisedb.com

  + It's impossible for everything to be true. +

---

From: Tom Lane <[email-masked]>
Date: Thu, 13 Jan 2011 22:39:53 -0500

Bruce Momjian <[email-masked]> writes:
> What does pg_upgrade need to do about this for 9.1?

Nothing.  An existing GIN index can still do all the same queries it
could do before.

			regards, tom lane

---

From: David E. Wheeler <[email-masked]>
Date: Fri, 14 Jan 2011 17:39:25 -0800

Tom,

Well, I regret to say that what I found is…all over the place.

So I have a rather wide table with two GIST indexes, one on an integer[] column and one on a tsvector column. I duped the table and replaced those indexes with GIN indexes. And the results of my testing don't make much sense.

Well, first the good news: I got no NULL-related errors at all. There are a lot of rows with an empty array in the integer[] column. And I got the same results for my queries against the table with the GIN indexes as the one with the GiST indexes. So all that's good.

One of the reasons our client wants GIN for the integer[] column so bad is because recreating the GiST integer[] index is quite painful. Before I duped the table, I was just dropping and recreating the index on the original table. It was great to create the GIN index; for 400K rows, it took 1300 ms. After my initial round of testing, I dropped it and created the GiST index. That ran for…well, *hours*. Four at least, maybe six or seven (I forgot \timing and was letting it run on screen while I did some iOS hacking). I think something might be really wrong with GiST index creation for integer arrays, because the difference was just appalling. 

As a sanity check, I did the same thing today with the same table(s) on their ts_vector columns. Creating the GiST index took just under 7 seconds; the GIN index took 23.4 seconds. On a second attempt, GiST took 16371 ms and GIN 30452. I had expected GIN to be faster here, but both are within the realms of the acceptable, compared to the time it took to create the GiST index on the integer[] column.

As for the queries, here too I was surprised. As I said, the integer[] column had a lot of empty arrays. And the indexes look like so:

  "idx_gist_features" gist (features) WHERE deleted_at IS NULL AND status = 1
  "idx_gist_textsearch" gist (ts_index_col) WHERE deleted_at IS NULL AND status = 1

Just s/gist/gin/ for the gin indexes. For the integer[] column, I ran a bunch of queries like so (again, just s/gist/gin/ for the gin versions):

    explain analyze SELECT count(*) FROM gist_listings
      WHERE features @@ '(1369043)'::query_int
        AND deleted_at IS NULL AND mls_status_id = 1;

This integer had pretty high selectvity, 86 out of 406K rows.
Gist: 117.444 on the first run, around 3.2 ms thereafter
GIN:  Around 325 ms on all runs

    explain analyze SELECT count(*) FROM gist_listings
      WHERE features @@ '(1368798|1369043)'::query_int
        AND deleted_at IS NULL AND mls_status_id = 1;

Rows selected: 91528.
Gist: 4030.282 ms on the first run, around 210 ms thereafter.
GIN:  4309.259 ms on the first run, around 400 ms thereafter

    explain analyze SELECT count(*) FROM gist_listings
      WHERE features @@ '(1368799&1368800&1369043)'::query_int
        AND deleted_at IS NULL AND mls_status_id = 1;

Rows selected: 91528
Gist: 1738.568 ms on the first run, around  24 ms thereafter.
GIN:  4427.517 ms on the first run, around 340 ms thereafter

These numbers are a bit crazy-making, but the upshot is that Gist is slow out of the gate, but with data cached, it's pretty speedy. With indexscan and bitmapscan disabled, these queries all took 300-400 ms. So GIN was never better performing than a table scan. So while GIN is a big win for re-indexing (this database gets its intarray Gist indexes updated quite frequently, as they get quited bloated in a hurry), it's not a win at all for querying.

So, thinking that there might be something funky with intarray GIN support, we wanted to test performance of GIST vs. GIN on the tsquery column. Here GIN was a much bigger win. With a query like this:

    SELECT l.* FROM gist_listings
     WHERE ts_index_col @@ to_tsquery(regexp_replace(
         plainto_tsquery('english', '1 Infinite Loop')::text,
         '''(?=[[:space:]]|$)', ''':B', 'g'
     )) and deleted_at IS NULL AND status = 1;

With zero rows returned, GIN consistently executed in 20 ms. Gist took 838.274 for the first run and 25-30 ms on subsequent runs. So GIN is the clear winner here, except for index creation as noted above.

And here's one that selects a single row:

    SELECT l.* FROM gist_listings
     WHERE ts_index_col @@ to_tsquery(regexp_replace(
         plainto_tsquery('english', 'volkswagon')::text,
         '''(?=[[:space:]]|$)', ''':B', 'g'
     )) and deleted_at IS NULL AND status = 1;

GiST: 495.867 first run, 380 thereafter
GIN:  83.980 first run, 330 thereafter

Again, GIN is the clear winner here, though it's negligible when the data is in the cache.

So some questions:

* Is something seriously wrong with GiST index creation on integer[] columns?

* Why does GIN performance appear to be no better than table scans on integer[] columns?

* Why does it take 3-4x longer to create the GIN than the GiST index on tsvector? I thought that GIN was supposed to be faster to update

Hope this is helpful, and please do let me know if there are any other tests you'd like me to run against this data.

Best,

David

---

From: Tom Lane <[email-masked]>
Date: Fri, 14 Jan 2011 20:54:51 -0500

> * Why does it take 3-4x longer to create the GIN than the GiST index on tsvector? I thought that GIN was supposed to be faster to update

Hard to comment on any of this without a concrete example (including
data) to look at.  Given the bugs we've recently found in the picksplit
algorithms for other contrib modules, I wouldn't be too surprised if the
sucky GiST performance traced to a similar bug in intarray.  But I'm not
excited about devising my own test case.

One other point here is that GIN index build time is quite sensitive to
maintenance_work_mem --- what did you have that set to?

			regards, tom lane

---

From: "David E. Wheeler" <[email-masked]>
Date: Fri, 14 Jan 2011 23:37:31 -0800

> excited about devising my own test case.

I could give you access to the box in question if you'd like to poke at it. Send me a public key.

> maintenance_work_mem --- what did you have that set to?

64MB

Best,

David

---

From: "David E. Wheeler" <[email-masked]>
Date: Sun, 16 Jan 2011 22:42:32 -0800

>> excited about devising my own test case.

FWIW, it looks like we're able to fix the GiST performance by using gist__intbig_ops. Relevant thread:

  http://archives.postgresql.org/pgsql-performance/2009-03/msg00254.php

Perhaps time to revisit using gist__int_ops as the default?

Best,

David

---

From: Tom Lane <[email-masked]>
Date: Tue, 18 Jan 2011 16:39:17 -0500

> One of the reasons our client wants GIN for the integer[] column so bad is because recreating the GiST integer[] index is quite painful. Before I duped the table, I was just dropping and recreating…

I poked into this a bit, although it's really off-topic for what I was
doing in GIN, and I agree that there is something fundamentally rotten
in the gist__int_ops logic.  oprofile shows that the code is spending
all its time in g_int_compress and g_int_union during index build:

samples  %        app name                 symbol name
52747    40.2486  _int.so                  g_int_compress
27092    20.6726  libc-2.12.2.so           _wordcopy_fwd_aligned
18938    14.4506  _int.so                  compASC
18256    13.9302  postgres                 pg_qsort
5741      4.3807  no-vmlinux               /no-vmlinux
3297      2.5158  postgres                 swapfunc
864       0.6593  _int.so                  g_int_decompress
826       0.6303  _int.so                  _int_unique
700       0.5341  _int.so                  inner_int_union
617       0.4708  postgres                 med3
588       0.4487  libc-2.12.2.so           memset
371       0.2831  _int.so                  g_int_same
143       0.1091  libc-2.12.2.so           memcpy
123       0.0939  postgres                 ArrayGetNItems
67        0.0511  _int.so                  inner_int_inter
48        0.0366  postgres                 AllocSetAlloc
47        0.0359  libc-2.12.2.so           memmove
40        0.0305  postgres                 MemoryContextAllocZero

The time in g_int_compress is all on this loop:

        while (len > MAXNUMRANGE * 2)
        {
            min = 0x7fffffff;
            for (i = 2; i < len; i += 2)
                if (min > (dr[i] - dr[i - 1]))
                {
                    min = (dr[i] - dr[i - 1]);
                    cand = i;
                }
            memmove((void *) &dr[cand - 1], (void *) &dr[cand + 1], (len - cand - 1) * sizeof(int32));
            len -= 2;
        }

which is not too surprising since that's obviously O(N^2).  The other
high-percentage functions are qsort and subsidiaries, and those calls
are coming from g_int_union.  That part could probably be sped up, since
most of the calls are unioning two inputs, which could be done a lot
cheaper than this (the inputs are always presorted no?).  But there is
something really fundamentally wrong in the logic, I think, because
while poking at it with gdb I saw it union-ing fifty-thousand-element
arrays.  Surely it should get lossy before it gets to that.  I'm also
wondering how it tells the difference between lossy and non-lossy keys
--- although it's hard to tell what such spectacularly uncommented code
is supposed to be doing, it looks like the lossy case is supposed to be
pairs of values representing ranges, in which case g_int_compress is
surely doing the Wrong Thing with already-lossy inputs, and union'ing
lossy inputs is an entirely insane operation as well.

At the moment my opinion is that gist__int_ops is too broken to be
usable, and it's also too uncommented to be fixable by anyone other
than the original author.

			regards, tom lane

---

From: Tom Lane <[email-masked]>
Date: Tue, 18 Jan 2011 16:58:15 -0500

"David E. Wheeler" <[email-masked]> writes:
> These numbers are a bit crazy-making, but the upshot is that Gist is
> slow out of the gate, but with data cached, it's pretty speedy. With
> indexscan and bitmapscan disabled, these queries all took 300-400
> ms. So GIN was never better performing than a table scan.

I could not replicate that here at all --- GIN indexscans were
consistently better than seqscans for me, eg

regression=# set enable_bitmapscan TO 1;
SET
Time: 0.673 ms
regression=# explain analyze SELECT count(*) FROM listings
      WHERE features @@ '(1368799&1368800&1369043)'::query_int
        AND deleted_at IS NULL AND status = 1;
                                                              QUERY PLAN                                          
--------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=1159.20..1159.21 rows=1 width=0) (actual time=23.964..23.964 rows=1 loops=1)
   ->  Bitmap Heap Scan on listings  (cost=31.15..1158.18 rows=406 width=0) (actual time=23.014..23.876 rows=772 loops=1)
         Recheck Cond: ((features @@ '1368799 & 1368800 & 1369043'::query_int) AND (deleted_at IS NULL) AND (status = 1))
         ->  Bitmap Index Scan on idx_gin_features  (cost=0.00..31.05 rows=406 width=0) (actual time=22.913..22.913 rows=772 loops=1)
               Index Cond: (features @@ '1368799 & 1368800 & 1369043'::query_int)
 Total runtime: 24.040 ms
(6 rows)

Time: 24.968 ms
regression=# set enable_bitmapscan TO 0;
SET
Time: 0.458 ms
regression=# explain analyze SELECT count(*) FROM listings
      WHERE features @@ '(1368799&1368800&1369043)'::query_int
        AND deleted_at IS NULL AND status = 1;
                                                     QUERY PLAN                                                   
--------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=9158.24..9158.25 rows=1 width=0) (actual time=145.121..145.121 rows=1 loops=1)
   ->  Seq Scan on listings  (cost=0.00..9157.22 rows=406 width=0) (actual time=0.025..144.982 rows=772 loops=1)
         Filter: ((deleted_at IS NULL) AND (features @@ '1368799 & 1368800 & 1369043'::query_int) AND (status = 1))
 Total runtime: 145.177 ms
(4 rows)

Time: 146.228 ms

I'm noticing also that I get different rowcounts than you do, although
possibly that has something to do with the partial-index conditions,
which I'm not trying to duplicate here (all rows in my table pass those
two tests).

> * Why does it take 3-4x longer to create the GIN than the GiST index
> on tsvector?

Perhaps more maintenance_work_mem would help with that; although the
fine manual says specifically that GIN text search indexes take about
three times longer to build than equivalent GiST indexes, so maybe that
behavior is as designed.

			regards, tom lane

---

From: "David E. Wheeler" <[email-masked]>
Date: Tue, 18 Jan 2011 14:04:16 -0800

> than the original author.

That seems to jibe with your comments from last year:

  http://archives.postgresql.org/pgsql-performance/2009-03/msg00265.php

Best,

David

---

From: Tom Lane <[email-masked]>
Date: Tue, 18 Jan 2011 17:09:30 -0500

>   http://archives.postgresql.org/pgsql-performance/2009-03/msg00265.php

Well, based on what I saw just now, I believe there are one or more
actual bugs in there, not just that it's straining the design capacity
of the opclass.  I think the "lossy" aspect isn't working at all.

			regards, tom lane

---

From: "David E. Wheeler" <[email-masked]>
Date: Tue, 18 Jan 2011 15:05:07 -0800

> three times longer to build than equivalent GiST indexes, so maybe that

Okay then, thanks.

David

---

From: Tom Lane <[email-masked]>
Date: Tue, 18 Jan 2011 18:08:03 -0500

> Shall I send you data with the other two columns?:

No, I see no reason to think that has much to do with it.  I'm wondering
if your table is itself a bit bloated ...

			regards, tom lane

---

From: "David E. Wheeler" <[email-masked]>
Date: Tue, 18 Jan 2011 15:45:15 -0800

> if your table is itself a bit bloated ...

Nope. Just ran the bloat query from check_postgres.pl. Bloat is 0. Not surprising since the table was created by inserting from another table (the original with the gist indexes) and has not been updated since.

Any other ideas?

David

---

From: Tom Lane <[email-masked]>
Date: Tue, 18 Jan 2011 18:46:48 -0500

> if your table is itself a bit bloated ...

Actually ... I notice you did not show EXPLAIN ANALYZE output for your
tests.  Now I'm wondering whether you tested the right thing at all.
I got burnt that way too.  Observe:

regression=# create index idx_gin_features on listings using gin(features) WHERE deleted_at IS NULL AND status = 1;
CREATE INDEX
regression=# explain analyze SELECT count(*) FROM listings
      WHERE features @@ '(1368799&1368800&1369043)'::query_int
        AND deleted_at IS NULL AND status = 1;
                                                     QUERY PLAN                                                     
--------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=9158.24..9158.25 rows=1 width=0) (actual time=153.633..153.634 rows=1 loops=1)
   ->  Seq Scan on listings  (cost=0.00..9157.22 rows=406 width=0) (actual time=0.048..153.493 rows=772 loops=1)
         Filter: ((deleted_at IS NULL) AND (features @@ '1368799 & 1368800 & 1369043'::query_int) AND (status = 1))
 Total runtime: 153.713 ms
(4 rows)

regression=# set enable_seqscan TO 0;
SET
regression=# explain analyze SELECT count(*) FROM listings
      WHERE features @@ '(1368799&1368800&1369043)'::query_int
        AND deleted_at IS NULL AND status = 1;
                                                                   QUERY PLAN                                                                   
------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=13253.42..13253.43 rows=1 width=0) (actual time=331.990..331.990 rows=1 loops=1)
   ->  Bitmap Heap Scan on listings  (cost=4095.18..13252.40 rows=406 width=0) (actual time=164.785..331.858 rows=772 loops=1)
         Recheck Cond: ((deleted_at IS NULL) AND (status = 1))
         Filter: (features @@ '1368799 & 1368800 & 1369043'::query_int)
         ->  Bitmap Index Scan on idx_gin_features  (cost=0.00..4095.07 rows=406215 width=0) (actual time=164.045..164.045 rows=406215 loops=1)
 Total runtime: 332.169 ms
(6 rows)

The above is "using" the index, but only as a guide to where the rows
satisfying the partial-index predicate are --- note the lack of any
index condition in the indexscan node.  That's because the query_int
query is not in fact compatible with the core-provided index opclass.
We get much better results using intarray's gin__int_ops opclass:

regression=# drop index idx_gin_features;
DROP INDEX
regression=# create index idx_gin_features on listings using gin(features gin__int_ops) WHERE deleted_at IS NULL AND status = 1;
CREATE INDEX
regression=# explain analyze SELECT count(*) FROM listings
      WHERE features @@ '(1368799&1368800&1369043)'::query_int
        AND deleted_at IS NULL AND status = 1;
                                                              QUERY PLAN                                                              
--------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=1159.20..1159.21 rows=1 width=0) (actual time=23.896..23.896 rows=1 loops=1)
   ->  Bitmap Heap Scan on listings  (cost=31.15..1158.18 rows=406 width=0) (actual time=22.912..23.813 rows=772 loops=1)
         Recheck Cond: ((features @@ '1368799 & 1368800 & 1369043'::query_int) AND (deleted_at IS NULL) AND (status = 1))
         ->  Bitmap Index Scan on idx_gin_features  (cost=0.00..31.05 rows=406 width=0) (actual time=22.811..22.811 rows=772 loops=1)
               Index Cond: (features @@ '1368799 & 1368800 & 1369043'::query_int)
 Total runtime: 24.036 ms
(6 rows)

			regards, tom lane

---

From: "David E. Wheeler" <[email-masked]>
Date: Tue, 18 Jan 2011 15:53:24 -0800

> We get much better results using intarray's gin__int_ops opclass:

Ah-hah! Confirmed, thank you. I now get 23.2 ms and an index condition. Much, much better.

Thank you! And I think we can use the improved GIN indexes for this app, once 9.1 drops.

Best,

David