Re: Questions about btree_gin vs btree_gist for low cardinality columns

On Sun, Jun 2, 2019 at 7:07 PM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Jeff Janes <jeff(dot)janes(at)gmail(dot)com> writes:
> > On Fri, May 24, 2019 at 11:26 AM Jeremy Finzel <finzelj(at)gmail(dot)com>
> wrote:
> >> I have been hoping for clearer direction from the community about
> >> specifically btree_gin indexes for low cardinality columns (as well as
> low
> >> cardinality multi-column indexes). In general there is very little
> >> discussion about this both online and in the docs. Rather, the emphasis
> >> for GIN indexes discussed is always on full text search of JSON
> indexing,
> >> not btree_gin indexes.
>
> I just wanted to mention that Jeremy and I had a bit of hallway-track
> discussion about this at PGCon. The core thing to note is that the GIN
> index type was designed to deal with data types that are subdividable
> and you want to search for individual component values (array elements,
> lexemes in a text document, etc). The btree_gin extension abuses this
> by just storing the whole values as if they were components. AFAIR,
> the original idea for writing both btree_gin and btree_gist was to allow
> creating a single multicolumn index that covers both subdividable and
> non-subdividable columns. The idea that btree_gin might be used on its
> own wasn't really on the radar, I don't think.

Even before 9.4 btree_gin indexes with many duplicates were still much more
compact than B-Tree, because the the value and the index tuple headers is
not repeated for each TID the way it is in B-Tree. Of course TID list
compression has made it better yet. I don't know what the original
motivation was for btree_gin, but multi-column GIN indexes never made much
sense to me anyway. What do they do that can't be done just as well by
separate single-column indexes combined through BitmapAnd and BitmapOr?

Multi-column GiST indexes can be much more useful, and so btree_gist is
useful to enable things like an index over (int, int8range).

Another possible use for btree_gin is to enable use of the fastupdate
mechanism for indexes on scalars, to speed up bulk insertion but without
having to drop the index. I've never demonstrated a realistic benefit
there, but I haven't tried very hard recently (last time I really tried was
before gin_clean_pending_list and gin_pending_list_limit were added). The
"real" solution here is something like log-structured merge trees or
fractal indexes, but fastupdate is already here.

> However, now that GIN can compress multiple index entries for the same
> component value (which has only been true since 9.4, whereas btree_gin
> is very much older than that) it seems like it does make sense to use
> btree_gin on its own for low-cardinality non-subdividable columns.
> And that means that we ought to consider non-subdividable columns as
> fully legitimate, not just a weird corner usage. So in particular
> I wonder whether it would be worth adding the scaffolding necessary
> to support index-only scan when the GIN opclass is one that doesn't
> subdivide the data values.
>

I wouldn't object to that, it just doesn't seem all that exciting. But
isn't there some aspiration towards making a next generation of B-Tree
index which will also use TID list compression, making them more compact
without resorting to GIN?

> That leaves me quibbling with some points in Jeff's otherwise excellent
> reply:
>
> > For single column using a btree_gin operator, each index entry holds the
> > entire data value. But the system doesn't know about that in any useful
> > way, so it doesn't implement index only scans, other than in the special
> > case where the value does not matter, like a 'count(*)'. Conceptually
> > perhaps this could be fixed, but I don't see it happening. Since an
> > index-only scan is usually not much good with only a single-column
> index, I
> > don't see much excitement to improve things here.
>
> I'm confused by this; surely IOS is useful even with a single-column
> index? Avoiding trips to the heap is always helpful.
>

But how realistic are the use cases? My thinking was that an IOS for:

select bid from pgbench_accounts where bid=5;

would be nice if you needed to run that query, but we already know it is 5
for each row where it is 5 so we could just do the count instead of looking
at a long column of identical values. Maybe it would be useful in joins or
something where we can't rewrite them ourselves, and the planner
can't/won't use the transitive law either.

It could be useful for disjunction in the same column, or inequality. (Or
BETWEEN if we fix the issue you mentioned below).

select bid, count(*) from pgbench_accounts where bid = 5 or bid = 7 group
by bid;

If it can be made to support IOS, perhaps it could also be made to support
ORDER BY?

> GIN indexes over btree_gin operators do not support inequality or BETWEEN
> > queries efficiently.
>
> Are you sure about that? It's set up to use the "partial match" logic,
> which is certainly pretty weird, but it does have the potential for
> handling inequalities efficiently. [ pokes at it ... ] Hm, looks like
> it does handle individual inequality conditions reasonably well, but
> it's not smart about the combination of a greater-than and a less-than
> constraint on the same column. It ends up scanning all the entries
> satisfying the one condition, plus all the entries satisfying the other,
> then intersecting those sets --- which of course comprise the whole table
> :-(. I think maybe this could be made better without a huge amount of
> work though.
>

That would be nice. I've hit the inefficient behavior of BETWEEN several
times "in the wild". Remembering that, this time I had only tested with the
BETWEEN, saw it was hitting every buffer in the index, and made unfounded
assumptions about the plain inequality case.

Cheers,

Jeff