DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=message-id:date:from:user-agent:mime-version:to:cc:subject
	:references:in-reply-to:content-type:content-transfer-encoding;
	b=kDhg31p6fzdOITN0F5Oicpv5+S03JzoOVkYf7qCfRn+Xaf1wU0APH2RjduL2LZjJuR
	6iPkSEe/yQ2Auquh//3px4vCKm9EPeLaHznmWD0Enc+htZi1YZ/lvkjujtExXJUGkShY
	/QonFOb2Yi0BMAo/hWyZhFUfM1lN8deJjBH3Q=
Message-ID: <4C1BBB39.10308@gmail.com>
Date: Fri, 18 Jun 2010 20:30:17 +0200
From: Yeb Havinga <yebhavinga@gmail.com>
User-Agent: Thunderbird 2.0.0.24 (Windows/20100228)
MIME-Version: 1.0
To: Greg Smith <greg@2ndquadrant.com>
CC: Matthew Wakeling <matthew@flymine.org>,
	Robert Haas <robertmhaas@gmail.com>,
	Eliot Gable <egable+pgsql-performance@gmail.com>,
	pgsql-performance@postgresql.org
Subject: Re: B-Heaps
References: <AANLkTinsmWw4w2m2fyjord30seNfn7Ww1arKew5EttQG@mail.gmail.com>
	<alpine.DEB.2.00.1006151313370.4083@aragorn.flymine.org>
	<AANLkTik-81bRcl1tle10YvsdY1F6MwF4SFZErKOZa5LA@mail.gmail.com>
	<alpine.DEB.2.00.1006181722050.2534@aragorn.flymine.org>
	<4C1BB294.8070806@2ndquadrant.com>
In-Reply-To: <4C1BB294.8070806@2ndquadrant.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Greg Smith wrote:
> Matthew Wakeling wrote:
>> This sort of thing has been fairly well researched at an academic 
>> level, but has not been implemented in that many real world 
>> situations. I would encourage its use in Postgres.
>
> I guess, but don't forget that work on PostgreSQL is driven by what 
> problems people are actually running into.  There's a long list of 
> performance improvements sitting in the TODO list waiting for people 
> to find time to work on them, ones that we're quite certain are 
> useful.  That anyone is going to chase after any of these speculative 
> ideas from academic research instead of one of those is unlikely.  
> Your characterization of the potential speed up here is "Using a 
> proper tree inside the index page would improve the CPU usage of the 
> index lookups", which seems quite reasonable.  Regardless, when I 
> consider "is that something I have any reason to suspect is a 
> bottleneck on common workloads?", I don't think of any, and return to 
> working on one of things I already know is instead.
>
There are two different things concerning gist indexes:

1) with larger block sizes and hence, larger # entries per gist page, 
results in more generic keys of those pages. This in turn results in a 
greater number of hits, when the index is queried, so a larger part of 
the index is scanned. NB this has nothing to do with caching / cache 
sizes; it holds for every IO model. Tests performed by me showed 
performance improvements of over 200%. Since then implementing a speedup 
has been on my 'want to do list'.

2) there are several approaches to get the # entries per page down. Two 
have been suggested in the thread referred to by Matthew (virtual pages 
(but how to order these?) and tree within a page). It is interesting to 
see if ideas from Prokop's cache oblivous algorithms match with this 
problem to find a suitable virtual page format.

regards,
Yeb Havinga