Message-ID: <46560CD0.404@emolecules.com>
Date: Thu, 24 May 2007 15:08:16 -0700
From: Craig James <craig_james@emolecules.com>
User-Agent: Thunderbird 1.5.0.10 (X11/20070221)
MIME-Version: 1.0
To: Alvaro Herrera <alvherre@commandprompt.com>
CC: pgsql-performance@postgresql.org
Subject: Re: LIKE search and performance
References: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom>
	<88daf38c0705230905u1a981102k691b47bd36011a80@mail.gmail.com>
	<4655DE75.4080506@mansionfamily.plus.com>
	<4655E64B.5050503@hagander.net>
	<4655FB8A.1040707@mansionfamily.plus.com>
	<1180040560.31471.262.camel@archimedes>
	<46560264.2020406@emolecules.com>
	<20070524214654.GR4320@alvh.no-ip.org>
In-Reply-To: <20070524214654.GR4320@alvh.no-ip.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Alvaro Herrera wrote:
 >> Just out of curiosity: Does Postgress store a duplicate of the data in the 
>> index, even for long strings?  I thought indexes only had to store the 
>> string up to the point where there was no ambiguity, for example, if I have 
>> "missing", "mississippi" and "misty", the index only needs "missin", 
>> "missis" and "mist" in the actual index.
> 
> What would happen when you inserted a new tuple with just "miss"?  You
> would need to expand all the other tuples in the index.

That's right.  This technique used by some index implementations is a tradeoff between size and update speed.  Most words in most natural languages can be distinguished by the first few characters.  The chances of having to modify more than a few surrounding nodes when you insert "miss" is small, so some implementations choose this method.  Other implementations choose to store the full string.  I was just curious which method Postgres uses.

Craig