pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Jeff Davis <pgsql@j-davis.com>
To: Adam L Beberg <beberg@mithral.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: Array indexes, GIN?
Date: Fri, 02 Mar 2007 11:50:38 -0800
Message-ID: <1172865038.13722.205.camel@dogma.v10.wvs> (raw)
In-Reply-To: <45E7A108.9010802@mithral.com>
References: <45E7A108.9010802@mithral.com>

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




view thread (5+ messages)

Message-ID: <1172865038.13722.205.camel@dogma.v10.wvs>
Permalink:  ../1172865038.13722.205.camel@dogma.v10.wvs/
Also on:    postgresql.org/message-id/1172865038.13722.205.camel@dogma.v10.wvs

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-performance@postgresql.org
  Cc: pgsql@j-davis.com, beberg@mithral.com
  Subject: Re: Array indexes, GIN?
  In-Reply-To: <1172865038.13722.205.camel@dogma.v10.wvs>
  References: <45E7A108.9010802@mithral.com> <1172865038.13722.205.camel@dogma.v10.wvs>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

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