Skip site navigation (1) Skip section navigation (2)

Re: LIKE optimization and locale

From: Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)us>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Peter Eisentraut <peter_e(at)gmx(dot)net>, PostgreSQL-development <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: LIKE optimization and locale
Date: 2000-11-26 20:43:48
Message-ID: 200011262043.PAA13975@candle.pha.pa.us (view raw or flat)
Thread:
Lists: pgsql-hackers
> The core problem is: given a string "foo", find a string "fop" that
> is greater than any possible extension "foobar" of "foo".  We need
> not find the least such string (else it would indeed be a hard
> problem), just a reasonably close upper bound.  The algorithm we have
> in 7.0.* increments the last byte(s) of "foo" until it finds
> something greater than "foo".  That handles collation orders that are
> different from numerical order, but it still breaks down in the cases
> Peter mentions.

This increment seems sub-optimal.

> 
> One variant I've been wondering about is to test a candidate bound
> string against not only "foo", but all single-character extensions of
> "foo", ie, "foo\001" through "foo\255".  That would catch situations
> like the one most recently complained of, where the last character
> of the proposed bound string is just a noise-character in dictionary
> order.  But I'm afraid it's still not good enough to catch all cases
> ... and it doesn't generalize to MULTIBYTE very well anyway.

This was my suggestion, to test all 255 chars and find the lowest that
is greater than the target, but I see that multi-byte would be a
problem.  Oh, well.  I hoped some postmaster-generated lookup table
could fix this.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman(at)candle(dot)pha(dot)pa(dot)us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

In response to

pgsql-hackers by date

Next:From: Trond Eivind =?iso-8859-1?q?Glomsr=d8d?=Date: 2000-11-26 21:12:00
Subject: Re: OK, that's one LOCALE bug report too many...
Previous:From: The Hermit HackerDate: 2000-11-26 20:19:03
Subject: Re: when will PostgreSQL 7.1?

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group