Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id 618FA9FB30B for ; Fri, 2 Mar 2007 15:50:52 -0400 (AST) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-new, port 10024) with ESMTP id 10138-10 for ; Fri, 2 Mar 2007 15:50:46 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey-1.7.4 Received: from servata.com (ip-216-152-249-241.servata.com [216.152.249.241]) by postgresql.org (Postfix) with ESMTP id 289B49FB308 for ; Fri, 2 Mar 2007 15:50:47 -0400 (AST) Received: from [209.162.219.253] (helo=dogma.v10.wvs) by servata.com with esmtpa (Exim 4.50) id 1HNDm0-00029n-Ji; Fri, 02 Mar 2007 11:50:36 -0800 Subject: Re: Array indexes, GIN? From: Jeff Davis To: Adam L Beberg Cc: pgsql-performance@postgresql.org In-Reply-To: <45E7A108.9010802@mithral.com> References: <45E7A108.9010802@mithral.com> Content-Type: text/plain Date: Fri, 02 Mar 2007 11:50:38 -0800 Message-Id: <1172865038.13722.205.camel@dogma.v10.wvs> Mime-Version: 1.0 X-Mailer: Evolution 2.0.4 (2.0.4-7) Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.185 tagged_above=0 required=5 tests=AWL, BAYES_50, FORGED_RCVD_HELO, SPF_HELO_PASS X-Spam-Level: X-Archive-Number: 200703/68 X-Sequence-Number: 23473 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