pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedArray indexes, GIN?
5+ messages / 4 participants
[nested] [flat]
* Array indexes, GIN?
@ 2007-03-02 03:59 Adam L Beberg <beberg@mithral.com>
0 siblings, 2 replies; 5+ messages in thread
From: Adam L Beberg @ 2007-03-02 03:59 UTC (permalink / raw)
To: pgsql-performance
I need to cross reference 2 tables. There are O(10M) A's, each has an
ordered set of 10 of the O(100K) B's associated with it. The dominant
query will be finding the A's and their count associated with a given
list of ~1k B's i.e. if 2 of the listed B's are in A's set of 10, it's
(A,2), and we should get back ~100K rows. The good news is we only need
to run this brutal query every couple minutes, but the row updates will
flow fast.
Luckily this is PostgreSQL, so the simple solution seems to be
CREATE TABLE xref( A bigint, B bigint[10] ); -- A is primary key
which cuts down the table overhead. O(10M) rows w/array.
On the surface, looks like a job for GIN, but GIN seems undocumented,
specifically mentions it doesn't support the deletes we'll have many of
since it's designed for word searching apparently, the performance
implications are undocumented. I searched, I read, and even IRC'd, and
it seems like GIN is just not used much.
Is GIN right? Will this work at all? Will it run fast enough to function?
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Array indexes, GIN?
@ 2007-03-02 05:47 Josh Berkus <josh@agliodbs.com>
parent: Adam L Beberg <beberg@mithral.com>
1 sibling, 1 reply; 5+ messages in thread
From: Josh Berkus @ 2007-03-02 05:47 UTC (permalink / raw)
To: pgsql-performance
Adam,
> On the surface, looks like a job for GIN, but GIN seems undocumented,
> specifically mentions it doesn't support the deletes we'll have many of
> since it's designed for word searching apparently, the performance
> implications are undocumented. I searched, I read, and even IRC'd, and
> it seems like GIN is just not used much.
It's new (as of 8.2). And the authors, Oleg and Teodor, are notorious for
skimpy documetentation.
I'd start with the code in INTARRAY contrib module (also by Teodor) and bug
them on pgsql-hackers about helping you implement a GIN index for arrays.
--
Josh Berkus
PostgreSQL @ Sun
San Francisco
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Array indexes, GIN?
@ 2007-03-02 06:45 Oleg Bartunov <oleg@sai.msu.su>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 1 reply; 5+ messages in thread
From: Oleg Bartunov @ 2007-03-02 06:45 UTC (permalink / raw)
To: Josh Berkus <josh@agliodbs.com>; +Cc: pgsql-performance
On Thu, 1 Mar 2007, Josh Berkus wrote:
> Adam,
>
>> On the surface, looks like a job for GIN, but GIN seems undocumented,
>> specifically mentions it doesn't support the deletes we'll have many of
>> since it's designed for word searching apparently, the performance
>> implications are undocumented. I searched, I read, and even IRC'd, and
>> it seems like GIN is just not used much.
>
> It's new (as of 8.2). And the authors, Oleg and Teodor, are notorious for
> skimpy documetentation.
We're getting better, we have 72 pages written about new FTS :)
>
> I'd start with the code in INTARRAY contrib module (also by Teodor) and bug
> them on pgsql-hackers about helping you implement a GIN index for arrays.
GIN already has support for one dimensional arrays and intarray, particularly,
too has support of GiN.
Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Array indexes, GIN?
@ 2007-03-02 07:50 Adam L Beberg <beberg@mithral.com>
parent: Oleg Bartunov <oleg@sai.msu.su>
0 siblings, 0 replies; 5+ messages in thread
From: Adam L Beberg @ 2007-03-02 07:50 UTC (permalink / raw)
To: Oleg Bartunov <oleg@sai.msu.su>; +Cc: pgsql-performance
Oleg Bartunov wrote on 3/1/2007 10:45 PM:
> On Thu, 1 Mar 2007, Josh Berkus wrote:
>
>> Adam,
>>
>>> On the surface, looks like a job for GIN, but GIN seems undocumented,
>>> specifically mentions it doesn't support the deletes we'll have many of
>>> since it's designed for word searching apparently, the performance
>>> implications are undocumented. I searched, I read, and even IRC'd, and
>>> it seems like GIN is just not used much.
>>
>> It's new (as of 8.2). And the authors, Oleg and Teodor, are notorious
>> for
>> skimpy documetentation.
>
> We're getting better, we have 72 pages written about new FTS :)
I'm guessing FTS is not quite done since you matched 'FTS' to 'GIN' ;)
> GIN already has support for one dimensional arrays and intarray,
> particularly, too has support of GiN.
Great, so can GIN handle my situation? I'm a little unsure what to make
of "Note: There is no delete operation for ET." in particular since I'm
dealing with large numbers.
--
Adam L. Beberg
http://www.mithral.com/~beberg/
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Array indexes, GIN?
@ 2007-03-02 19:50 Jeff Davis <pgsql@j-davis.com>
parent: Adam L Beberg <beberg@mithral.com>
1 sibling, 0 replies; 5+ messages in thread
From: Jeff Davis @ 2007-03-02 19:50 UTC (permalink / raw)
To: Adam L Beberg <beberg@mithral.com>; +Cc: pgsql-performance
On Thu, 2007-03-01 at 19:59 -0800, Adam L Beberg wrote:
> On the surface, looks like a job for GIN, but GIN seems undocumented,
> specifically mentions it doesn't support the deletes we'll have many of
> since it's designed for word searching apparently, the performance
It can delete an entry for one of the keys of an index, it just can't
delete the key itself when the number of entries goes down to zero.
Because you only have O(100K) possible keys, that shouldn't be a
problem. The GIN indexes can reclaim space. If they couldn't, they
wouldn't be nearly as useful.
The time when you run into problems is when you have a huge, sparsely
populated keyspace, with a huge number of keys contained by no tuples in
the table.
However, for your application, GIN still might not be the right answer.
GIN can only return tuples which do contain some matching keys, it won't
return the number of matching keys in that tuple (that's not the job of
an index).
Let's run some numbers:
* percentage of tuples returned = 100K rows out of the 10M = 1%
* tuples per page = 8192 bytes / 32 (tuple header) + 8 (bigint) + 80
(10 bigints) = ~70. Let's say it's 50 due to some free space.
Based on those numbers, the GIN index is basically going to say "get
every other page". PostgreSQL will optimize that into a sequential scan
because it makes no sense to do a random fetch for every other page.
So, the fastest way you can do this (that I can see) is just fetch every
tuple and count the number of matches in each array. You know your data
better than I do, so replace those numbers with real ones and see if it
still makes sense.
The basic rule is that an index scan is useful only if it reduces the
number of disk pages you need to fetch enough to make up for the extra
cost of random I/O.
Regards,
Jeff Davis
^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2007-03-02 19:50 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2007-03-02 03:59 Array indexes, GIN? Adam L Beberg <beberg@mithral.com>
2007-03-02 05:47 ` Josh Berkus <josh@agliodbs.com>
2007-03-02 06:45 ` Oleg Bartunov <oleg@sai.msu.su>
2007-03-02 07:50 ` Adam L Beberg <beberg@mithral.com>
2007-03-02 19:50 ` Jeff Davis <pgsql@j-davis.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox