From frum@ar-sd.net Wed May 23 15:28:35 2007 Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id 0E4089FA65C for ; Wed, 23 May 2007 12:28:35 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 15910-03 for ; Wed, 23 May 2007 12:28:30 -0300 (ADT) X-Greylist: delayed 00:22:16.461646 by SQLgrey-1.7.5 Received: from svr4.postgresql.org (svr4.postgresql.org [66.98.251.159]) by postgresql.org (Postfix) with ESMTP id 6D3969FA4D4 for ; Wed, 23 May 2007 12:28:30 -0300 (ADT) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.3 Received: from ar-sd.net (unknown [212.146.96.162]) by svr4.postgresql.org (Postfix) with ESMTP id 3639C5AF027 for ; Wed, 23 May 2007 15:06:12 +0000 (GMT) Received: from localhost (localhost [127.0.0.1]) by ar-sd.net (Postfix) with ESMTP id C99A4FBEB0 for ; Wed, 23 May 2007 18:06:05 +0300 (EEST) Received: from ar-sd.net ([127.0.0.1]) by localhost (ar-sd.net [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 30474-01 for ; Wed, 23 May 2007 18:05:45 +0300 (EEST) Received: from andypc (andypc.mpsro.dom [192.168.0.11]) by ar-sd.net (Postfix) with ESMTP id A0491FBE9B for ; Wed, 23 May 2007 18:05:45 +0300 (EEST) From: "Andy" To: Subject: LIKE search and performance Date: Wed, 23 May 2007 18:08:49 +0300 Message-ID: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0096_01C79D65.69A160F0" X-Mailer: Microsoft Office Outlook 11 thread-index: AcedTEI32cXEQuFWSsScI7e96csWlA== X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3028 X-Virus-Scanned: by amavisd-new at ar-sd.net X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/451 X-Sequence-Number: 24841 This is a multi-part message in MIME format. ------=_NextPart_000_0096_01C79D65.69A160F0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Hi, I have a table with varchar and text columns, and I have to search through these text in the whole table. An example would be: SELECT * FROM table WHERE name like '%john%' or street like '%srt%' Anyway, the query planner always does seq scan on the whole table and that takes some time. How can this be optimized or made in another way to be faster? I tried to make indexes on the columns but no success. PG 8.2 Regards, Andy. ------=_NextPart_000_0096_01C79D65.69A160F0 Content-Type: text/html; charset="US-ASCII" Content-Transfer-Encoding: quoted-printable

Hi,=20

I have = a table with=20 varchar and text columns, and I have to search through these text in the = whole=20 table.

An = example would=20 be:

SELECT = *=20 FROM=20 table

&nbs= p; = ; =20 WHERE name like '%john%' or street like '%srt%'

Anyway, the query=20 planner always does seq scan on the whole table and that takes some = time. How=20 can this be optimized or made in another way to be = faster?

I = tried to make=20 indexes on the columns but no success.

PG=20 8.2

Regards,

Andy.

------=_NextPart_000_0096_01C79D65.69A160F0-- From dev@archonet.com Wed May 23 15:52:24 2007 Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id 329399FBB6C for ; Wed, 23 May 2007 12:52:24 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 67614-04-3 for ; Wed, 23 May 2007 12:52:17 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.4 Received: from mail.metronet.co.uk (mail.metronet.co.uk [213.162.97.75]) by postgresql.org (Postfix) with ESMTP id 8B7B69FBB92 for ; Wed, 23 May 2007 12:52:17 -0300 (ADT) Received: from server3.office.archonet.com (84-51-143-99.archon037.adsl.metronet.co.uk [84.51.143.99]) by smtp.metronet.co.uk (MetroNet Mail) with ESMTP id B07DD76F57; Wed, 23 May 2007 16:52:12 +0100 (BST) Received: from [192.168.1.36] (dell36.office.archonet.com [192.168.1.36]) by server3.office.archonet.com (Postfix) with ESMTP id 71339274119; Wed, 23 May 2007 16:52:12 +0100 (BST) Message-ID: <4654632C.4020005@archonet.com> Date: Wed, 23 May 2007 16:52:12 +0100 From: Richard Huxton User-Agent: Thunderbird 2.0.0.0 (X11/20070326) MIME-Version: 1.0 To: Andy Cc: pgsql-performance@postgresql.org Subject: Re: LIKE search and performance References: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> In-Reply-To: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/454 X-Sequence-Number: 24844 Andy wrote: > SELECT * FROM table > WHERE name like '%john%' or street like '%srt%' > > Anyway, the query planner always does seq scan on the whole table and that > takes some time. How can this be optimized or made in another way to be > faster? > > I tried to make indexes on the columns but no success. None of the normal indexes will work for finding text in the middle of a string. If you do think of a simple way of solving this, drop a short letter explaining your idea to your local patent office followed by the Nobel prize committee. However, one of the contrib packages is "tsearch2" which is designed to do keyword searches on text for you. It'll also handle stemming (e.g. "search" will match "searching" etc.) with the right choice of dictionary. Loads of other clever stuff in it too. It's one of the optional packages with most Linux packaging systems and on the Windows one too. If you install from source see the contrib/ directory for details. -- Richard Huxton Archonet Ltd From rigmor.ukuhe@finestmedia.ee Wed May 23 16:18:35 2007 Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id EEB2D9FB5C7 for ; Wed, 23 May 2007 13:18:35 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 04312-09 for ; Wed, 23 May 2007 13:18:30 -0300 (ADT) X-Greylist: delayed 00:26:05.8095 by SQLgrey-1.7.4 Received: from svr4.postgresql.org (svr4.postgresql.org [66.98.251.159]) by postgresql.org (Postfix) with ESMTP id 93CB19FB602 for ; Wed, 23 May 2007 13:18:30 -0300 (ADT) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.3 Received: from mail.finestmedia.ee (mail.finestmedia.ee [213.180.31.2]) by svr4.postgresql.org (Postfix) with ESMTP id 057565AF02A for ; Wed, 23 May 2007 15:52:23 +0000 (GMT) Received: from [192.168.2.19] (err.fm.sise [192.168.2.19]) by mail.finestmedia.ee (Postfix) with ESMTP id 434E4492178 for ; Wed, 23 May 2007 18:52:21 +0300 (EEST) Message-ID: <46546335.5000109@finestmedia.ee> Date: Wed, 23 May 2007 18:52:21 +0300 From: Rigmor Ukuhe User-Agent: Thunderbird 1.5.0.10 (Windows/20070221) MIME-Version: 1.0 Cc: pgsql-performance@postgresql.org Subject: Re: LIKE search and performance References: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> In-Reply-To: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.001 tagged_above=0 required=5 tests=BAYES_50=0.001 X-Spam-Level: X-Archive-Number: 200705/458 X-Sequence-Number: 24848 Andy wrote: > Hi, > > I have a table with varchar and text columns, and I have to search > through these text in the whole table. > > An example would be: > SELECT * FROM table > WHERE name like '%john%' or street like '%srt%' > > Anyway, the query planner always does seq scan on the whole table and > that takes some time. How can this be optimized or made in another way > to be faster? Use tsearch2 (http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/) for full text indexing. Rigmor > > I tried to make indexes on the columns but no success. > > PG 8.2 > > Regards, > Andy. From lists@event-s.net Wed May 23 16:00:22 2007 Received: from localhost (maia-4.hub.org [200.46.204.183]) by postgresql.org (Postfix) with ESMTP id 4C3589FB37C for ; Wed, 23 May 2007 13:00:22 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 65470-06 for ; Wed, 23 May 2007 13:00:18 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from mail.pharmaline.de (mail.apoexpress.de [62.153.135.53]) by postgresql.org (Postfix) with ESMTP id 133039FB1EB for ; Wed, 23 May 2007 13:00:18 -0300 (ADT) Received: from [192.168.5.155] (68.145.108.192) by mail.pharmaline.de with ESMTP (Eudora Internet Mail Server X 3.2.10) for ; Wed, 23 May 2007 18:00:16 +0200 Mime-Version: 1.0 (Apple Message framework v752.3) In-Reply-To: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> References: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Message-Id: <532C0F0C-117B-45A1-9CA2-66CA9ECA711F@event-s.net> Content-Transfer-Encoding: 7bit From: Guido Neitzer Subject: Re: LIKE search and performance Date: Wed, 23 May 2007 10:00:18 -0600 To: PostgreSQL Performance X-Mailer: Apple Mail (2.752.3) X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/456 X-Sequence-Number: 24846 Am 23.05.2007 um 09:08 schrieb Andy: > I have a table with varchar and text columns, and I have to search > through these text in the whole table. > > An example would be: > SELECT * FROM table > WHERE name like '%john%' or street > like '%srt%' > > Anyway, the query planner always does seq scan on the whole table > and that takes some time. How can this be optimized or made in > another way to be faster? The problem is that normal indexes cannot be used for "contains" queries. If you need fulltext search capabilities you have to take a look at tsearch2 or an external search engine like Lucene. cug From alex@purefiction.net Wed May 23 16:05:32 2007 Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id 72FB19FBBA8 for ; Wed, 23 May 2007 13:05:32 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 94129-02 for ; Wed, 23 May 2007 13:05:27 -0300 (ADT) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.5 Received: from an-out-0708.google.com (an-out-0708.google.com [209.85.132.240]) by postgresql.org (Postfix) with ESMTP id D432D9FB5B0 for ; Wed, 23 May 2007 13:05:27 -0300 (ADT) Received: by an-out-0708.google.com with SMTP id c36so61326ana for ; Wed, 23 May 2007 09:05:26 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=RIq4sQgEvc3eNXIi8WLP5KV376tknx8Ne8720zfjU0UZ3il/kXwy5ijc0i8YFP13a6uuQpRZpACXvl+Q35Tf9f4KkuF4JZ2Ycr3EV+m/mbtsXrHKbvDlupNUIONiFgCBflvuCmqqDpDYdabAScoi/zuQA+sR7nLM7X0thMY0q74= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:sender:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references:x-google-sender-auth; b=ci0WzULy4qXG9qjySxvFimEabr+Yw1g9jz8yap7O6XSam7NZmP4fMJcyyWxgG59Jhl4u6T+HfsD20umrdyABnvrv3Z/irGToWUCBfvW+0q7iXEAd90n/sYFGB9Y+O3MjzKXK1QOAFAuNfvpq40JEiclm+8h+UeK62Nz43We8RnA= Received: by 10.100.95.19 with SMTP id s19mr604404anb.1179936326803; Wed, 23 May 2007 09:05:26 -0700 (PDT) Received: by 10.65.177.7 with HTTP; Wed, 23 May 2007 09:05:26 -0700 (PDT) Message-ID: <88daf38c0705230905u1a981102k691b47bd36011a80@mail.gmail.com> Date: Wed, 23 May 2007 18:05:26 +0200 From: "Alexander Staubo" To: Andy Subject: Re: LIKE search and performance Cc: pgsql-performance@postgresql.org In-Reply-To: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> X-Google-Sender-Auth: 0a482263d94c13e6 X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/457 X-Sequence-Number: 24847 On 5/23/07, Andy wrote: > An example would be: > SELECT * FROM table > WHERE name like '%john%' or street like '%srt%' > > Anyway, the query planner always does seq scan on the whole table and that > takes some time. How can this be optimized or made in another way to be > faster? There's no algorithm in existence that can "index" arbitrary substrings the way you think. The only rational way to accomplish this is to first break the text into substrings using some algorithm (eg., words delimited by whitespace and punctuation), and index the substrings individually. You can do this using vanilla PostgreSQL, and you can use Tsearch2 and/or its GIN indexes to help speed up the searches. The simplest solution would be to put all the substrings in a table, one row per substring, along with an attribute referencing the source table/row. At this point you have effectively reduced your search space: you can use a query to isolate the words in your "dictionary" that contain the substrings. So a query might be: select ... from persons where id in ( select person_id from person_words where word like '%john%'; ) The "like" search, even though it will use a sequential scan, is bound to be much faster on these small words than searching for substrings through large gobs of text in the persons table. Note that PostgreSQL *can* exploit the index for *prefix* matching, if you tell it to use the right operator class: create index persons_name_index on persons (name text_pattern_ops); or, if you're using varchars (though there is rarely any reason to): create index persons_name_index on persons (name varchar_pattern_ops); (These two may be identical internally. Check the docs.) Now you can do: select ... from persons where name like 'john%'; which will yield a query plan such as this: Index Scan using persons_name_index on persons (cost=0.00..8.27 rows=1 width=29) (actual time=0.184..0.373 rows=51 loops=1) Index Cond: ((name ~>=~ 'john'::text) AND (name ~<~ 'joho'::text)) Filter: (title ~~ 'john%'::text) Alexander. From frum@ar-sd.net Thu May 24 07:01:15 2007 Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id 278FA9FB64C for ; Thu, 24 May 2007 04:01:15 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 47167-07 for ; Thu, 24 May 2007 04:00:58 -0300 (ADT) X-Greylist: delayed 15:54:53.833718 by SQLgrey-1.7.5 Received: from ar-sd.net (unknown [212.146.96.162]) by postgresql.org (Postfix) with ESMTP id 9410E9FB666 for ; Thu, 24 May 2007 04:01:00 -0300 (ADT) Received: from localhost (localhost [127.0.0.1]) by ar-sd.net (Postfix) with ESMTP id A1425129ED; Thu, 24 May 2007 10:00:58 +0300 (EEST) Received: from ar-sd.net ([127.0.0.1]) by localhost (ar-sd.net [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 05780-03; Thu, 24 May 2007 10:00:39 +0300 (EEST) Received: from andypc (andypc.mpsro.dom [192.168.0.11]) by ar-sd.net (Postfix) with ESMTP id 5672612961; Thu, 24 May 2007 10:00:39 +0300 (EEST) From: "Andy" To: "'Rigmor Ukuhe'" Cc: Subject: Re: LIKE search and performance Date: Thu, 24 May 2007 10:03:42 +0300 Message-ID: <002101c79dd1$aa0f8ce0$0b00a8c0@mpsro.dom> MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook 11 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3028 Thread-Index: AcedVjqlqJfXNyV8QXSKnTWIF8mYGwAe1koA In-Reply-To: <46546335.5000109@finestmedia.ee> X-Virus-Scanned: by amavisd-new at ar-sd.net X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/475 X-Sequence-Number: 24865 Thank you all for the answers. I will try your suggestions and see what that brings in terms of performance. Andy. > -----Original Message----- > From: pgsql-performance-owner@postgresql.org > [mailto:pgsql-performance-owner@postgresql.org] On Behalf Of > Rigmor Ukuhe > Sent: Wednesday, May 23, 2007 6:52 PM > Cc: pgsql-performance@postgresql.org > Subject: Re: [PERFORM] LIKE search and performance > > Andy wrote: > > Hi, > > > > I have a table with varchar and text columns, and I have to search > > through these text in the whole table. > > > > An example would be: > > SELECT * FROM table > > WHERE name like '%john%' or > street like '%srt%' > > > > Anyway, the query planner always does seq scan on the whole > table and > > that takes some time. How can this be optimized or made in > another way > > to be faster? > > Use tsearch2 > (http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/) for > full text indexing. > > Rigmor > > > > > I tried to make indexes on the columns but no success. > > > > PG 8.2 > > > > Regards, > > Andy. > > > > > ---------------------------(end of > broadcast)--------------------------- > TIP 4: Have you searched our list archives? > > http://archives.postgresql.org > > From james@mansionfamily.plus.com Thu May 24 19:15:28 2007 Received: from localhost (maia-5.hub.org [200.46.204.182]) by postgresql.org (Postfix) with ESMTP id 608C59FB900 for ; Thu, 24 May 2007 16:15:28 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.182]) (amavisd-maia, port 10024) with ESMTP id 74771-06 for ; Thu, 24 May 2007 16:15:17 -0300 (ADT) X-Greylist: delayed 00:28:15.610642 by SQLgrey-1.7.5 Received: from svr4.postgresql.org (svr4.postgresql.org [66.98.251.159]) by postgresql.org (Postfix) with ESMTP id 66C749FB949 for ; Thu, 24 May 2007 16:15:18 -0300 (ADT) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.3 Received: from pih-relay04.plus.net (pih-relay04.plus.net [212.159.14.131]) by svr4.postgresql.org (Postfix) with ESMTP id 93FD95AF043 for ; Thu, 24 May 2007 18:47:02 +0000 (GMT) Received: from [80.229.150.39] (helo=mansionfamily.plus.com) by pih-relay04.plus.net with esmtp (Exim) id 1HrIKw-0002Dm-Qa for pgsql-performance@postgresql.org; Thu, 24 May 2007 19:46:59 +0100 Received: from [192.168.0.87] ([192.168.0.87]:3648) by mansionfamily.plus.com with [XMail 1.22 ESMTP Server] id for from ; Thu, 24 May 2007 19:48:23 +0100 Message-ID: <4655DE75.4080506@mansionfamily.plus.com> Date: Thu, 24 May 2007 19:50:29 +0100 From: James Mansion User-Agent: Thunderbird 2.0.0.0 (Windows/20070326) MIME-Version: 1.0 To: Alexander Staubo Cc: Andy , pgsql-performance@postgresql.org Subject: Re: LIKE search and performance References: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> <88daf38c0705230905u1a981102k691b47bd36011a80@mail.gmail.com> In-Reply-To: <88daf38c0705230905u1a981102k691b47bd36011a80@mail.gmail.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/476 X-Sequence-Number: 24866 Alexander Staubo wrote: > On 5/23/07, Andy wrote: >> An example would be: >> SELECT * FROM table >> WHERE name like '%john%' or street like >> '%srt%' >> >> Anyway, the query planner always does seq scan on the whole table and >> that >> takes some time. How can this be optimized or made in another way to be >> faster? > > There's no algorithm in existence that can "index" arbitrary > substrings the way you think. The only rational way to accomplish this > is to first break the text into substrings using some algorithm (eg., > words delimited by whitespace and punctuation), and index the > substrings individually. That seems rather harsh. If I'd put an index on each of these colomns I'd certainly expect it to use the indices - and I'm pretty sure that Sybase would. I'd expect it to scan the index leaf pages instead of the table itself - they should be much more compact and also likely to be hot in cache. Why *wouldn't* the planner do this? James From magnus@hagander.net Thu May 24 19:23:28 2007 Received: from localhost (maia-2.hub.org [200.46.204.187]) by postgresql.org (Postfix) with ESMTP id 7AD949FBF32 for ; Thu, 24 May 2007 16:23:28 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.187]) (amavisd-maia, port 10024) with ESMTP id 41725-03 for ; Thu, 24 May 2007 16:23:22 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from svr2.hagander.net (svr2.hagander.net [88.198.128.226]) by postgresql.org (Postfix) with ESMTP id 403829FB949 for ; Thu, 24 May 2007 16:23:24 -0300 (ADT) Received: from dynamic.hagander.net ([127.0.0.1]) (encrypted and authenticated) by svr2.hagander.net (Postfix) with ESMTP id 6A36CDCC985; Thu, 24 May 2007 21:23:11 +0200 (CEST) Message-ID: <4655E64B.5050503@hagander.net> Date: Thu, 24 May 2007 21:23:55 +0200 From: Magnus Hagander User-Agent: Thunderbird 2.0.0.4pre (Windows/20070520) MIME-Version: 1.0 To: James Mansion CC: Alexander Staubo , Andy , 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> In-Reply-To: <4655DE75.4080506@mansionfamily.plus.com> X-Enigmail-Version: 0.95.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/477 X-Sequence-Number: 24867 James Mansion wrote: > Alexander Staubo wrote: >> On 5/23/07, Andy wrote: >>> An example would be: >>> SELECT * FROM table >>> WHERE name like '%john%' or street like >>> '%srt%' >>> >>> Anyway, the query planner always does seq scan on the whole table and >>> that >>> takes some time. How can this be optimized or made in another way to be >>> faster? >> >> There's no algorithm in existence that can "index" arbitrary >> substrings the way you think. The only rational way to accomplish this >> is to first break the text into substrings using some algorithm (eg., >> words delimited by whitespace and punctuation), and index the >> substrings individually. > That seems rather harsh. If I'd put an index on each of these colomns > I'd certainly > expect it to use the indices - and I'm pretty sure that Sybase would. > I'd expect > it to scan the index leaf pages instead of the table itself - they > should be much > more compact and also likely to be hot in cache. If Sybase is still like SQL Server (or the other way around), it *may* end up scanning the index *IFF* the index is a clustered index. If it's a normal index, it will do a sequential scan on the table. Yes, the leaf page of the index is more compact, but you also have to scan the intermediate pages to get to the leaf pages. But again, it can be a win. On such a system. It's not a win on PostgreSQL, because of our MVCC implementation. We need to scan *both* index *and* data pages if we go down that route, in which case it's a lot faster to just scan the data pages alone. I don't really know how MSSQL deals with this now that they have MVCC-ish behavior, and I have no idea at all if sybase has anything like MVCC. > Why *wouldn't* the planner do this? The question should be why the optimizer doesn't consider it, and the executor uses it. The planner really doesn't decide that part :-) Hopefully, the answer can be found above. //Magnus From james@mansionfamily.plus.com Thu May 24 20:51:14 2007 Received: from localhost (maia-2.hub.org [200.46.204.187]) by postgresql.org (Postfix) with ESMTP id 270269FC028 for ; Thu, 24 May 2007 17:51:14 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.187]) (amavisd-maia, port 10024) with ESMTP id 69354-04 for ; Thu, 24 May 2007 17:51:06 -0300 (ADT) X-Greylist: delayed 02:04:07.771486 by SQLgrey-1.7.5 Received: from pih-relay05.plus.net (pih-relay05.plus.net [212.159.14.132]) by postgresql.org (Postfix) with ESMTP id 4FA169FC021 for ; Thu, 24 May 2007 17:51:09 -0300 (ADT) Received: from [80.229.150.39] (helo=mansionfamily.plus.com) by pih-relay05.plus.net with esmtp (Exim) id 1HrKH2-0001na-V4 for pgsql-performance@postgresql.org; Thu, 24 May 2007 21:51:05 +0100 Received: from [192.168.0.87] ([192.168.0.87]:3720) by mansionfamily.plus.com with [XMail 1.22 ESMTP Server] id for from ; Thu, 24 May 2007 21:52:29 +0100 Message-ID: <4655FB8A.1040707@mansionfamily.plus.com> Date: Thu, 24 May 2007 21:54:34 +0100 From: James Mansion User-Agent: Thunderbird 2.0.0.0 (Windows/20070326) MIME-Version: 1.0 To: Magnus Hagander CC: Alexander Staubo , Andy , 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> In-Reply-To: <4655E64B.5050503@hagander.net> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/478 X-Sequence-Number: 24868 > If Sybase is still like SQL Server (or the other way around), it *may* > end up scanning the index *IFF* the index is a clustered index. If it's > a normal index, it will do a sequential scan on the table. > > Are you sure its not covered? Have to check at work - but I'm off next week so it'll have to wait. > It's not a win on PostgreSQL, because of our MVCC implementation. We > need to scan *both* index *and* data pages if we go down that route, in > which case it's a lot faster to just scan the data pages alone. > > Why do you need to go to all the data pages - doesn't the index structure contain all the keys so you prefilter and then check to see if the *matched* items are still in view? I'll be first to admit I know zip about Postgres, but it seems odd - doesn't the index contain copies of the key values?. I suspect that I mis-spoke with 'leaf'. I really just mean 'all index pages with data', since the scan does not even need to be in index order, just a good way to get at the data in a compact way. From mark.lewis@mir3.com Thu May 24 21:02:55 2007 Received: from localhost (maia-5.hub.org [200.46.204.182]) by postgresql.org (Postfix) with ESMTP id DBA6C9FC05F for ; Thu, 24 May 2007 18:02:55 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.182]) (amavisd-maia, port 10024) with ESMTP id 22842-05 for ; Thu, 24 May 2007 18:02:48 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.4 Received: from mir3-fs.mir3.com (mail.mir3.com [65.208.188.100]) by postgresql.org (Postfix) with ESMTP id 30EEC9FC040 for ; Thu, 24 May 2007 18:02:50 -0300 (ADT) Received: MIR3-FS.mir3.com 172.16.1.11 from 172.16.2.68 172.16.2.68 via HTTP with MS-WebStorage 6.0.6249 Received: from archimedes by MIR3-FS.mir3.com; 24 May 2007 14:02:41 -0700 Subject: Re: LIKE search and performance From: Mark Lewis To: James Mansion Cc: Magnus Hagander , Alexander Staubo , Andy , pgsql-performance@postgresql.org In-Reply-To: <4655FB8A.1040707@mansionfamily.plus.com> References: <009501c79d4c$445428f0$0b00a8c0@mpsro.dom> <88daf38c0705230905u1a981102k691b47bd36011a80@mail.gmail.com> <4655DE75.4080506@mansionfamily.plus.com> <4655E64B.5050503@hagander.net> <4655FB8A.1040707@mansionfamily.plus.com> Content-Type: text/plain Content-Transfer-Encoding: 7bit Organization: MIR3, Inc. Date: Thu, 24 May 2007 14:02:40 -0700 Message-Id: <1180040560.31471.262.camel@archimedes> Mime-Version: 1.0 X-Mailer: Evolution 2.8.1 X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/479 X-Sequence-Number: 24869 On Thu, 2007-05-24 at 21:54 +0100, James Mansion wrote: > > If Sybase is still like SQL Server (or the other way around), it *may* > > end up scanning the index *IFF* the index is a clustered index. If it's > > a normal index, it will do a sequential scan on the table. > > > > > Are you sure its not covered? Have to check at work - but I'm off next > week so it'll have to wait. > > > It's not a win on PostgreSQL, because of our MVCC implementation. We > > need to scan *both* index *and* data pages if we go down that route, in > > which case it's a lot faster to just scan the data pages alone. > > > > > Why do you need to go to all the data pages - doesn't the index > structure contain all the keys so > you prefilter and then check to see if the *matched* items are still in > view? I'll be first to admit I > know zip about Postgres, but it seems odd - doesn't the index contain > copies of the key values?. > > I suspect that I mis-spoke with 'leaf'. I really just mean 'all index > pages with data', since the scan > does not even need to be in index order, just a good way to get at the > data in a compact way. PG could scan the index looking for matches first and only load the actual rows if it found a match, but that could only be a possible win if there were very few matches, because the difference in cost between a full index scan and a sequential scan would need to be greater than the cost of randomly fetching all of the matching data rows from the table to look up the visibility information. So yes it would be possible, but the odds of it being faster than a sequential scan are small enough to make it not very useful. And since it's basically impossible to know the selectivity of this kind of where condition, I doubt the planner would ever realistically want to choose that plan anyway because of its poor worst-case behavior. -- Mark From craig_james@emolecules.com Thu May 24 21:22:47 2007 Received: from localhost (maia-5.hub.org [200.46.204.182]) by postgresql.org (Postfix) with ESMTP id 267E49FBFB3 for ; Thu, 24 May 2007 18:22:47 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.182]) (amavisd-maia, port 10024) with ESMTP id 84259-03 for ; Thu, 24 May 2007 18:22:39 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from mail.emolecules.com (66-226-76-106.dedicated.abac.net [66.226.76.106]) by postgresql.org (Postfix) with ESMTP id 9EE039FBA31 for ; Thu, 24 May 2007 18:22:42 -0300 (ADT) Received: (qmail 17396 invoked by uid 2020); 24 May 2007 14:22:38 -0700 Received: from wsip-68-224-174-233.sd.sd.cox.net (HELO ?192.168.0.3?) (68.224.174.233) by 192.168.0.4 with SMTP; 24 May 2007 14:22:38 -0700 Message-ID: <46560264.2020406@emolecules.com> Date: Thu, 24 May 2007 14:23:48 -0700 From: Craig James User-Agent: Thunderbird 1.5.0.10 (X11/20070221) MIME-Version: 1.0 To: 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> In-Reply-To: <1180040560.31471.262.camel@archimedes> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/480 X-Sequence-Number: 24870 Mark Lewis wrote: > PG could scan the index looking for matches first and only load the > actual rows if it found a match, but that could only be a possible win > if there were very few matches, because the difference in cost between a > full index scan and a sequential scan would need to be greater than the > cost of randomly fetching all of the matching data rows from the table > to look up the visibility information. 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. This would make it impossible to use a full index scan for a LIKE query. Craig From alvherre@commandprompt.com Thu May 24 21:47:01 2007 Received: from localhost (maia-2.hub.org [200.46.204.187]) by postgresql.org (Postfix) with ESMTP id C39699FB9C4 for ; Thu, 24 May 2007 18:47:01 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.187]) (amavisd-maia, port 10024) with ESMTP id 96341-08 for ; Thu, 24 May 2007 18:46:55 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from lists.commandprompt.com (host-254.commandprompt.net [207.173.203.254]) by postgresql.org (Postfix) with ESMTP id 7C4A19FB927 for ; Thu, 24 May 2007 18:46:58 -0300 (ADT) Received: from perhan.alvh.no-ip.org (201-221-217-243.bk12-dsl.surnet.cl [201.221.217.243]) (authenticated bits=0) by lists.commandprompt.com (8.13.7/8.13.6) with ESMTP id l4OLkxGK016354; Thu, 24 May 2007 14:46:59 -0700 Received: by perhan.alvh.no-ip.org (Postfix, from userid 1000) id D8F7C32A14; Thu, 24 May 2007 17:46:54 -0400 (CLT) Date: Thu, 24 May 2007 17:46:54 -0400 From: Alvaro Herrera To: Craig James Cc: pgsql-performance@postgresql.org Subject: Re: LIKE search and performance Message-ID: <20070524214654.GR4320@alvh.no-ip.org> 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> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <46560264.2020406@emolecules.com> User-Agent: Mutt/1.5.13 (2006-08-11) X-Virus-Scanned: ClamAV version 0.88.5, clamav-milter version 0.88.5 on projects.commandprompt.com X-Virus-Status: Clean X-Greylist: Sender succeded SMTP AUTH authentication, not delayed by milter-greylist-1.6 (lists.commandprompt.com [192.168.2.159]); Thu, 24 May 2007 14:47:00 -0700 (PDT) X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/481 X-Sequence-Number: 24871 Craig James wrote: > Mark Lewis wrote: > > >PG could scan the index looking for matches first and only load the > >actual rows if it found a match, but that could only be a possible win > >if there were very few matches, because the difference in cost between a > >full index scan and a sequential scan would need to be greater than the > >cost of randomly fetching all of the matching data rows from the table > >to look up the visibility information. > > 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. -- Alvaro Herrera http://www.flickr.com/photos/alvherre/ "Puedes vivir solo una vez, pero si lo haces bien, una vez es suficiente" From mark@mark.mielke.cc Thu May 24 21:55:08 2007 Received: from localhost (maia-4.hub.org [200.46.204.183]) by postgresql.org (Postfix) with ESMTP id 682D79FBA47 for ; Thu, 24 May 2007 18:55:08 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 32450-03 for ; Thu, 24 May 2007 18:55:04 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.4 Received: from svr4.postgresql.org (svr4.postgresql.org [66.98.251.159]) by postgresql.org (Postfix) with ESMTP id F0FD89FBA31 for ; Thu, 24 May 2007 18:55:04 -0300 (ADT) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.3 Received: from mail.envysolutions.com (unknown [206.248.142.186]) by svr4.postgresql.org (Postfix) with ESMTP id 264005AF028 for ; Thu, 24 May 2007 21:55:04 +0000 (GMT) Received: from localhost (localhost.localdomain [127.0.0.1]) by mail.envysolutions.com (Postfix) with ESMTP id 5011E5404E; Thu, 24 May 2007 17:54:51 -0400 (EDT) X-Virus-Scanned: amavisd-new at mail.envysolutions.com Received: from mail.envysolutions.com ([127.0.0.1]) by localhost (mark.mielke.cc [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id SKCDJSeRgool; Thu, 24 May 2007 17:54:51 -0400 (EDT) Received: by mail.envysolutions.com (Postfix, from userid 500) id 2AD565404F; Thu, 24 May 2007 17:54:51 -0400 (EDT) Date: Thu, 24 May 2007 17:54:51 -0400 From: mark@mark.mielke.cc To: Mark Lewis Cc: James Mansion , Magnus Hagander , Alexander Staubo , Andy , pgsql-performance@postgresql.org Subject: Re: LIKE search and performance Message-ID: <20070524215450.GA3858@mark.mielke.cc> 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> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1180040560.31471.262.camel@archimedes> User-Agent: Mutt/1.4.2.2i X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.86 tagged_above=0 required=5 tests=AWL=-0.237, BAYES_50=0.001, FORGED_RCVD_HELO=0.135, NO_REAL_NAME=0.961 X-Spam-Level: X-Archive-Number: 200705/482 X-Sequence-Number: 24872 On Thu, May 24, 2007 at 02:02:40PM -0700, Mark Lewis wrote: > PG could scan the index looking for matches first and only load the > actual rows if it found a match, but that could only be a possible win > if there were very few matches, because the difference in cost between a > full index scan and a sequential scan would need to be greater than the > cost of randomly fetching all of the matching data rows from the table > to look up the visibility information. > So yes it would be possible, but the odds of it being faster than a > sequential scan are small enough to make it not very useful. > And since it's basically impossible to know the selectivity of this kind > of where condition, I doubt the planner would ever realistically want to > choose that plan anyway because of its poor worst-case behavior. What is a real life example where an intelligent and researched database application would issue a like or ilike query as their primary condition in a situation where they expected very high selectivity? Avoiding a poor worst-case behaviour for a worst-case behaviour that won't happen doesn't seem practical. What real life examples, that could not be implemented a better way, would behave poorly if like/ilike looked at the index first to filter? I don't understand... :-) Cheers, mark -- mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________ . . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder |\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ | | | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness bind them... http://mark.mielke.cc/ From craig_james@emolecules.com Thu May 24 22:07:10 2007 Received: from localhost (maia-2.hub.org [200.46.204.187]) by postgresql.org (Postfix) with ESMTP id DA60A9FBA47 for ; Thu, 24 May 2007 19:07:10 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.187]) (amavisd-maia, port 10024) with ESMTP id 78630-01 for ; Thu, 24 May 2007 19:07:03 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from mail.emolecules.com (66-226-76-106.dedicated.abac.net [66.226.76.106]) by postgresql.org (Postfix) with ESMTP id 5A1959FBA37 for ; Thu, 24 May 2007 19:07:07 -0300 (ADT) Received: (qmail 19083 invoked by uid 2020); 24 May 2007 15:07:06 -0700 Received: from wsip-68-224-174-233.sd.sd.cox.net (HELO ?192.168.0.3?) (68.224.174.233) by 192.168.0.4 with SMTP; 24 May 2007 15:07:06 -0700 Message-ID: <46560CD0.404@emolecules.com> Date: Thu, 24 May 2007 15:08:16 -0700 From: Craig James User-Agent: Thunderbird 1.5.0.10 (X11/20070221) MIME-Version: 1.0 To: Alvaro Herrera 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 X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/483 X-Sequence-Number: 24873 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 From lists@peufeu.com Thu May 24 22:07:14 2007 Received: from localhost (maia-2.hub.org [200.46.204.187]) by postgresql.org (Postfix) with ESMTP id 98DA09FBA47 for ; Thu, 24 May 2007 19:07:14 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.187]) (amavisd-maia, port 10024) with ESMTP id 65791-06 for ; Thu, 24 May 2007 19:07:07 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from h07.llord.com (unknown [195.140.142.194]) by postgresql.org (Postfix) with ESMTP id 211409FBA37 for ; Thu, 24 May 2007 19:07:11 -0300 (ADT) Received: from par69-8-88-161-102-87.fbx.proxad.net ([88.161.102.87] helo=apollo13) by h07.llord.com with esmtpa (Exim 4.63) (envelope-from ) id 1HrLSG-0000cR-C3; Fri, 25 May 2007 00:06:44 +0200 Date: Fri, 25 May 2007 00:09:15 +0200 To: "Mark Lewis" , "James Mansion" Subject: Re: LIKE search and performance From: PFC Cc: "Magnus Hagander" , "Alexander Staubo" , Andy , pgsql-performance@postgresql.org Content-Type: text/plain; format=flowed; delsp=yes; charset=utf-8 MIME-Version: 1.0 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> Content-Transfer-Encoding: Quoted-Printable Message-ID: In-Reply-To: <1180040560.31471.262.camel@archimedes> User-Agent: Opera Mail/9.10 (Linux) X-PopBeforeSMTPSenders: junk@peufeu.com, lists@peufeu.com, peufeu@peufeu.com, pfcaillaud@peufeu.com X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - h07.llord.com X-AntiAbuse: Original Domain - postgresql.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - peufeu.com X-Source: X-Source-Args: X-Source-Dir: X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=1.89 tagged_above=0 required=5 tests=AWL=-0.145, BAYES_20=-0.74, RCVD_IN_NJABL_SPAM=2.775 X-Spam-Level: * X-Archive-Number: 200705/484 X-Sequence-Number: 24874 > PG could scan the index looking for matches first and only load the > actual rows if it found a match, but that could only be a possible win= > if there were very few matches, because the difference in cost between= a > full index scan and a sequential scan would need to be greater than th= e > cost of randomly fetching all of the matching data rows from the table= > to look up the visibility information. If you need to do that kind of thing, ie. seq scanning a table checking= = only one column among a large table of many columns, then don't use an = index. An index, being a btree, needs to be traversed in order (or else,= a = lot of locking problems come up) which means some random accesses. So, you could make a table, with 2 columns, updated via triggers : your= = text field, and the primary key of your main table. Scanning that would = be = faster. Still, a better solution for searching in text is : - tsearch2 if you need whole words - trigrams for any substring match - xapian for full text search with wildcards (ie. John* =3D Johnny) Speed-wise those three will beat any seq scan on a large table by a hug= e = margin. From dev@archonet.com Fri May 25 08:18:49 2007 Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id 06A229FC154 for ; Fri, 25 May 2007 05:18:49 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 90325-02-2 for ; Fri, 25 May 2007 05:18:30 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.4 Received: from mail.metronet.co.uk (mail.metronet.co.uk [213.162.97.75]) by postgresql.org (Postfix) with ESMTP id B982E9FBA71 for ; Fri, 25 May 2007 05:18:32 -0300 (ADT) Received: from server3.office.archonet.com (84-51-143-99.archon037.adsl.metronet.co.uk [84.51.143.99]) by smtp.metronet.co.uk (MetroNet Mail) with ESMTP id 1820E74C39; Fri, 25 May 2007 09:13:26 +0100 (BST) Received: from [192.168.1.36] (dell36.office.archonet.com [192.168.1.36]) by server3.office.archonet.com (Postfix) with ESMTP id 7A53627410E; Fri, 25 May 2007 09:13:27 +0100 (BST) Message-ID: <46569AA5.10205@archonet.com> Date: Fri, 25 May 2007 09:13:25 +0100 From: Richard Huxton User-Agent: Thunderbird 2.0.0.0 (X11/20070326) MIME-Version: 1.0 To: mark@mark.mielke.cc Cc: Mark Lewis , James Mansion , Magnus Hagander , Alexander Staubo , Andy , 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> <20070524215450.GA3858@mark.mielke.cc> In-Reply-To: <20070524215450.GA3858@mark.mielke.cc> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/485 X-Sequence-Number: 24875 mark@mark.mielke.cc wrote: >> And since it's basically impossible to know the selectivity of this kind >> of where condition, I doubt the planner would ever realistically want to >> choose that plan anyway because of its poor worst-case behavior. > > What is a real life example where an intelligent and researched > database application would issue a like or ilike query as their > primary condition in a situation where they expected very high > selectivity? > > Avoiding a poor worst-case behaviour for a worst-case behaviour that > won't happen doesn't seem practical. But if you are also filtering on e.g. date, and that has an index with good selectivity, you're never going to use the text index anyway are you? If you've only got a dozen rows to check against, might as well just read them in. The only time it's worth considering the behaviour at all is *if* the worst-case is possible. -- Richard Huxton Archonet Ltd From mark@mark.mielke.cc Fri May 25 14:16:31 2007 Received: from localhost (maia-1.hub.org [200.46.204.191]) by postgresql.org (Postfix) with ESMTP id DC43B9FC11A for ; Fri, 25 May 2007 11:16:31 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.191]) (amavisd-maia, port 10024) with ESMTP id 10107-05 for ; Fri, 25 May 2007 11:16:28 -0300 (ADT) X-Greylist: delayed 16:21:39.418106 by SQLgrey-1.7.5 Received: from mail.envysolutions.com (unknown [206.248.142.186]) by postgresql.org (Postfix) with ESMTP id 39E939FB674 for ; Fri, 25 May 2007 11:16:28 -0300 (ADT) Received: from localhost (localhost.localdomain [127.0.0.1]) by mail.envysolutions.com (Postfix) with ESMTP id E2BC65403B; Fri, 25 May 2007 10:16:30 -0400 (EDT) X-Virus-Scanned: amavisd-new at mail.envysolutions.com Received: from mail.envysolutions.com ([127.0.0.1]) by localhost (mark.mielke.cc [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xfQo5UYKnzRV; Fri, 25 May 2007 10:16:30 -0400 (EDT) Received: by mail.envysolutions.com (Postfix, from userid 500) id B996654042; Fri, 25 May 2007 10:16:30 -0400 (EDT) Date: Fri, 25 May 2007 10:16:30 -0400 From: mark@mark.mielke.cc To: Richard Huxton Cc: Mark Lewis , James Mansion , Magnus Hagander , Alexander Staubo , Andy , pgsql-performance@postgresql.org Subject: Re: LIKE search and performance Message-ID: <20070525141630.GA12162@mark.mielke.cc> 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <46569AA5.10205@archonet.com> User-Agent: Mutt/1.4.2.2i X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.491 tagged_above=0 required=5 tests=AWL=0.135, BAYES_20=-0.74, FORGED_RCVD_HELO=0.135, NO_REAL_NAME=0.961 X-Spam-Level: X-Archive-Number: 200705/510 X-Sequence-Number: 24900 On Fri, May 25, 2007 at 09:13:25AM +0100, Richard Huxton wrote: > mark@mark.mielke.cc wrote: > >>And since it's basically impossible to know the selectivity of this kind > >>of where condition, I doubt the planner would ever realistically want to > >>choose that plan anyway because of its poor worst-case behavior. > >What is a real life example where an intelligent and researched > >database application would issue a like or ilike query as their > >primary condition in a situation where they expected very high > >selectivity? > >Avoiding a poor worst-case behaviour for a worst-case behaviour that > >won't happen doesn't seem practical. > But if you are also filtering on e.g. date, and that has an index with > good selectivity, you're never going to use the text index anyway are > you? If you've only got a dozen rows to check against, might as well > just read them in. > The only time it's worth considering the behaviour at all is *if* the > worst-case is possible. I notice you did not provide a real life example as requested. :-) This seems like an ivory tower restriction. Not allowing best performance in a common situation vs not allowing worst performance in a not-so-common situation. Cheers, mark -- mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________ . . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder |\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ | | | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness bind them... http://mark.mielke.cc/ From dev@archonet.com Fri May 25 15:35:39 2007 Received: from localhost (maia-1.hub.org [200.46.204.191]) by postgresql.org (Postfix) with ESMTP id 405479FB8E6 for ; Fri, 25 May 2007 12:35:39 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.191]) (amavisd-maia, port 10024) with ESMTP id 35193-03 for ; Fri, 25 May 2007 12:35:35 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from mail.metronet.co.uk (mail.metronet.co.uk [213.162.97.75]) by postgresql.org (Postfix) with ESMTP id E8CAF9FB6AF for ; Fri, 25 May 2007 12:35:34 -0300 (ADT) Received: from server3.office.archonet.com (84-51-143-99.archon037.adsl.metronet.co.uk [84.51.143.99]) by smtp.metronet.co.uk (MetroNet Mail) with ESMTP id 4DA9E74ADF; Fri, 25 May 2007 16:35:23 +0100 (BST) Received: from [192.168.1.36] (dell36.office.archonet.com [192.168.1.36]) by server3.office.archonet.com (Postfix) with ESMTP id A7BFF27410E; Fri, 25 May 2007 16:35:26 +0100 (BST) Message-ID: <4657023A.20209@archonet.com> Date: Fri, 25 May 2007 16:35:22 +0100 From: Richard Huxton User-Agent: Thunderbird 2.0.0.0 (X11/20070326) MIME-Version: 1.0 To: mark@mark.mielke.cc Cc: Mark Lewis , James Mansion , Magnus Hagander , Alexander Staubo , Andy , 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> In-Reply-To: <20070525141630.GA12162@mark.mielke.cc> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/517 X-Sequence-Number: 24907 mark@mark.mielke.cc wrote: > On Fri, May 25, 2007 at 09:13:25AM +0100, Richard Huxton wrote: >> mark@mark.mielke.cc wrote: >>>> And since it's basically impossible to know the selectivity of this kind >>>> of where condition, I doubt the planner would ever realistically want to >>>> choose that plan anyway because of its poor worst-case behavior. >>> What is a real life example where an intelligent and researched >>> database application would issue a like or ilike query as their >>> primary condition in a situation where they expected very high >>> selectivity? >>> Avoiding a poor worst-case behaviour for a worst-case behaviour that >>> won't happen doesn't seem practical. >> But if you are also filtering on e.g. date, and that has an index with >> good selectivity, you're never going to use the text index anyway are >> you? If you've only got a dozen rows to check against, might as well >> just read them in. >> The only time it's worth considering the behaviour at all is *if* the >> worst-case is possible. > > I notice you did not provide a real life example as requested. :-) OK - any application that allows user-built queries: Want another? Any application that has a "search by name" box - users can (and do) put one letter in and hit enter. Unfortunately you don't always have control over the selectivity of queries issued. > This seems like an ivory tower restriction. Not allowing best performance > in a common situation vs not allowing worst performance in a not-so-common > situation. What best performance plan are you thinking of? I'm assuming we're talking about trailing-wildcard matches here, rather than "contains" style matches. -- Richard Huxton Archonet Ltd From lists@peufeu.com Fri May 25 16:49:42 2007 Received: from localhost (maia-4.hub.org [200.46.204.183]) by postgresql.org (Postfix) with ESMTP id B92D69FC14E for ; Fri, 25 May 2007 13:49:42 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 67416-03 for ; Fri, 25 May 2007 13:49:39 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from h07.llord.com (unknown [195.140.142.194]) by postgresql.org (Postfix) with ESMTP id D5A319FB8DC for ; Fri, 25 May 2007 13:49:38 -0300 (ADT) Received: from par69-8-88-161-102-87.fbx.proxad.net ([88.161.102.87] helo=apollo13) by h07.llord.com with esmtpa (Exim 4.66) (envelope-from ) id 1Hrcxm-00007v-8Z; Fri, 25 May 2007 18:48:26 +0200 Date: Fri, 25 May 2007 18:51:04 +0200 To: "Richard Huxton" , mark@mark.mielke.cc Subject: Re: LIKE search and performance From: PFC Cc: "Mark Lewis" , "James Mansion" , "Magnus Hagander" , "Alexander Staubo" , Andy , pgsql-performance@postgresql.org Content-Type: text/plain; format=flowed; delsp=yes; charset=utf-8 MIME-Version: 1.0 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> <4657023A.20209@archonet.com> Content-Transfer-Encoding: Quoted-Printable Message-ID: In-Reply-To: <4657023A.20209@archonet.com> User-Agent: Opera Mail/9.10 (Linux) X-PopBeforeSMTPSenders: junk@peufeu.com, lists@peufeu.com, peufeu@peufeu.com, pfcaillaud@peufeu.com X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - h07.llord.com X-AntiAbuse: Original Domain - postgresql.org X-AntiAbuse: Originator/Caller UID/GID - [0 0] / [47 12] X-AntiAbuse: Sender Address Domain - peufeu.com X-Source: X-Source-Args: X-Source-Dir: X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=2.258 tagged_above=0 required=5 tests=AWL=-0.518, BAYES_50=0.001, RCVD_IN_NJABL_SPAM=2.775 X-Spam-Level: ** X-Archive-Number: 200705/521 X-Sequence-Number: 24911 > OK - any application that allows user-built queries: foo> > > Want another? Any application that has a "search by name" box - users = = > can (and do) put one letter in and hit enter. > > Unfortunately you don't always have control over the selectivity of = > queries issued. -*- HOW TO MAKE A SEARCH FORM -*- Imagine you have to code the search on IMDB. This is what a smart developer would do First, he uses AJAX autocompletion, so the thing is reactive. Then, he does not bother the user with a many-fields form. Instead of = forcing the user to think (users HATE that), he writes smart code. Does Google Maps have separate fields for country, city, street, zipcod= e = ? No. Because Google is about as smart as it gets. So, you parse the user query. If the user types, for instance, less than 3 letters (say, spi), he = probably wants stuff that *begins* with those letters. There is no point= = in searching for the letter "a" in a million movie titles database. So, if the user types "spi", you display "name LIKE spi%", which is = indexed, very fast. And since you're smart, you use AJAX. And you displa= y = only the most popular results (ie. most clicked on). http://imdb.com/find?s=3Dall&q=3Dspi Since 99% of the time the user wanted "spiderman" or "spielberg", you'r= e = done and he's happy. Users like being happy. If the user just types "a", you display the first 10 things that start = = with "a", this is useless but the user will marvel at your AJAX skillz. = = Then he will probably type in a few other letters. Then, if the user uses his space bar and types "spi 1980" you'll = recognize a year and display spielberg's movies in 1980. Converting your strings to phonetics is also a good idea since about 0.= 7% = of the l33T teenagers can spell stuff especially spiElberg. Only the guy who wants to know who had sex with marilyn monroe on the = 17th day of the shooting of Basic Instinct will need to use the Advanced= = search. If you detect several words, then switch to a prefix-based fulltext = search like Xapian which utterly rocks. Example : the user types "savin priv", you search for "savin*" NEAR = "priv*" and you display "saving private ryan" before he has even finishe= d = typing the second word of his query. Users love that, they feel = understood, they will click on your ads and buy your products. In all cases, search results should be limited to less than 100 to be = easy on the database. The user doesn't care about a search returning mor= e = than 10-20 results, he will just rephrase the query, and the time taken = to = fetch those thousands of records with name LIKE '%a%' will have been = utterly lost. Who goes to page 2 in google results ? BOTTOM LINE : databases don't think, you do. From mark@mark.mielke.cc Fri May 25 16:56:34 2007 Received: from localhost (maia-2.hub.org [200.46.204.187]) by postgresql.org (Postfix) with ESMTP id 569849FB674 for ; Fri, 25 May 2007 13:56:34 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.187]) (amavisd-maia, port 10024) with ESMTP id 80804-04 for ; Fri, 25 May 2007 13:56:29 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from mail.envysolutions.com (unknown [206.248.142.186]) by postgresql.org (Postfix) with ESMTP id 6B7E19FB2EA for ; Fri, 25 May 2007 13:56:30 -0300 (ADT) Received: from localhost (localhost.localdomain [127.0.0.1]) by mail.envysolutions.com (Postfix) with ESMTP id EC2A254055; Fri, 25 May 2007 12:56:33 -0400 (EDT) X-Virus-Scanned: amavisd-new at mail.envysolutions.com Received: from mail.envysolutions.com ([127.0.0.1]) by localhost (mark.mielke.cc [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id RPScAUxchthV; Fri, 25 May 2007 12:56:33 -0400 (EDT) Received: by mail.envysolutions.com (Postfix, from userid 500) id C477C54058; Fri, 25 May 2007 12:56:33 -0400 (EDT) Date: Fri, 25 May 2007 12:56:33 -0400 From: mark@mark.mielke.cc To: Richard Huxton Cc: Mark Lewis , James Mansion , Magnus Hagander , Alexander Staubo , Andy , pgsql-performance@postgresql.org Subject: Re: LIKE search and performance Message-ID: <20070525165633.GA13579@mark.mielke.cc> 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> <4657023A.20209@archonet.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <4657023A.20209@archonet.com> User-Agent: Mutt/1.4.2.2i X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.766 tagged_above=0 required=5 tests=AWL=-0.145, BAYES_40=-0.185, FORGED_RCVD_HELO=0.135, NO_REAL_NAME=0.961 X-Spam-Level: X-Archive-Number: 200705/522 X-Sequence-Number: 24912 On Fri, May 25, 2007 at 04:35:22PM +0100, Richard Huxton wrote: > >I notice you did not provide a real life example as requested. :-) > OK - any application that allows user-built queries: foo> > Want another? Any application that has a "search by name" box - users > can (and do) put one letter in and hit enter. > Unfortunately you don't always have control over the selectivity of > queries issued. The database has 10 million records. The user enters "bar" and it translates to "%bar%". You are suggesting that we expect bar to match 1 million+ records? :-) I hope not. I would define this as bad process. I would also use "LIMIT" to something like "100". > >This seems like an ivory tower restriction. Not allowing best performance > >in a common situation vs not allowing worst performance in a not-so-common > >situation. > What best performance plan are you thinking of? I'm assuming we're > talking about trailing-wildcard matches here, rather than "contains" > style matches. "Trailing-wildcard" already uses B-Tree index, does it not? I am speaking of contains, as contains is the one that was said to require a seqscan. I am questioning why it requires a seqscan. The claim was made that with MVCC, the index is insufficient to check for visibility and that the table would need to be accessed anyways, therefore a seqscan is required. I question whether a like '%bar%' should be considered a high selectivity query in the general case. I question whether a worst case should be assumed. Perhaps I question too much? :-) Cheers, mark -- mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________ . . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder |\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ | | | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness bind them... http://mark.mielke.cc/ From jd@commandprompt.com Fri May 25 17:08:10 2007 Received: from localhost (maia-2.hub.org [200.46.204.187]) by postgresql.org (Postfix) with ESMTP id 0EC879FB768 for ; Fri, 25 May 2007 14:08:10 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.187]) (amavisd-maia, port 10024) with ESMTP id 18008-03 for ; Fri, 25 May 2007 14:08:05 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from lists.commandprompt.com (host-254.commandprompt.net [207.173.203.254]) by postgresql.org (Postfix) with ESMTP id D5E019FB2EA for ; Fri, 25 May 2007 14:08:05 -0300 (ADT) Received: from [192.168.1.238] (or-76-2-4-105.dhcp.embarqhsd.net [76.2.4.105]) (authenticated bits=0) by lists.commandprompt.com (8.13.7/8.13.6) with ESMTP id l4PH6mNv016157; Fri, 25 May 2007 10:06:48 -0700 Message-ID: <465717A6.4040503@commandprompt.com> Date: Fri, 25 May 2007 10:06:46 -0700 From: "Joshua D. Drake" User-Agent: Thunderbird 2.0.0.0 (Windows/20070326) MIME-Version: 1.0 To: mark@mark.mielke.cc CC: Richard Huxton , Mark Lewis , James Mansion , Magnus Hagander , Alexander Staubo , Andy , 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> <4657023A.20209@archonet.com> <20070525165633.GA13579@mark.mielke.cc> In-Reply-To: <20070525165633.GA13579@mark.mielke.cc> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: ClamAV version 0.88.5, clamav-milter version 0.88.5 on projects.commandprompt.com X-Virus-Status: Clean X-Greylist: Sender succeded SMTP AUTH authentication, not delayed by milter-greylist-1.6 (lists.commandprompt.com [192.168.2.159]); Fri, 25 May 2007 10:06:53 -0700 (PDT) X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/523 X-Sequence-Number: 24913 mark@mark.mielke.cc wrote: > I am speaking of contains, as contains is the one that was said to > require a seqscan. I am questioning why it requires a seqscan. The > claim was made that with MVCC, the index is insufficient to check > for visibility and that the table would need to be accessed anyways, > therefore a seqscan is required. I question whether a like '%bar%' > should be considered a high selectivity query in the general case. > I question whether a worst case should be assumed. If you are doing %bar% you should be using pg_tgrm or tsearch2. J > > Perhaps I question too much? :-) > > Cheers, > mark > From dev@archonet.com Fri May 25 17:14:06 2007 Received: from localhost (maia-5.hub.org [200.46.204.182]) by postgresql.org (Postfix) with ESMTP id 4E0DA9FB60D for ; Fri, 25 May 2007 14:14:06 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.182]) (amavisd-maia, port 10024) with ESMTP id 63583-03 for ; Fri, 25 May 2007 14:14:01 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from mail.metronet.co.uk (mail.metronet.co.uk [213.162.97.75]) by postgresql.org (Postfix) with ESMTP id 7873E9FB607 for ; Fri, 25 May 2007 14:14:02 -0300 (ADT) Received: from server3.office.archonet.com (84-51-143-99.archon037.adsl.metronet.co.uk [84.51.143.99]) by smtp.metronet.co.uk (MetroNet Mail) with ESMTP id 1736174B2C; Fri, 25 May 2007 18:08:54 +0100 (BST) Received: from [192.168.1.36] (dell36.office.archonet.com [192.168.1.36]) by server3.office.archonet.com (Postfix) with ESMTP id EBA7C27410E; Fri, 25 May 2007 18:08:57 +0100 (BST) Message-ID: <46571825.30707@archonet.com> Date: Fri, 25 May 2007 18:08:53 +0100 From: Richard Huxton User-Agent: Thunderbird 2.0.0.0 (X11/20070326) MIME-Version: 1.0 To: PFC Cc: mark@mark.mielke.cc, Mark Lewis , James Mansion , Magnus Hagander , Alexander Staubo , Andy , 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> <4657023A.20209@archonet.com> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/524 X-Sequence-Number: 24914 PFC wrote: > >> OK - any application that allows user-built queries: > foo> >> >> Want another? Any application that has a "search by name" box - users >> can (and do) put one letter in and hit enter. >> >> Unfortunately you don't always have control over the selectivity of >> queries issued. > > -*- HOW TO MAKE A SEARCH FORM -*- > > Imagine you have to code the search on IMDB. > > This is what a smart developer would do All good domain-specific tips to provide users with a satisfying search-experience. None of which address the question of what plan PG should produce for: SELECT * FROM bigtable WHERE foo LIKE 's%' -- Richard Huxton Archonet Ltd From dev@archonet.com Fri May 25 17:31:09 2007 Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id F33479FB8F3 for ; Fri, 25 May 2007 14:31:09 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 79269-01-2 for ; Fri, 25 May 2007 14:30:50 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from mail.metronet.co.uk (mail.metronet.co.uk [213.162.97.75]) by postgresql.org (Postfix) with ESMTP id 5E3AE9FB768 for ; Fri, 25 May 2007 14:30:57 -0300 (ADT) Received: from server3.office.archonet.com (84-51-143-99.archon037.adsl.metronet.co.uk [84.51.143.99]) by smtp.metronet.co.uk (MetroNet Mail) with ESMTP id B1BD375F46; Fri, 25 May 2007 18:29:16 +0100 (BST) Received: from [192.168.1.36] (dell36.office.archonet.com [192.168.1.36]) by server3.office.archonet.com (Postfix) with ESMTP id AF74227410E; Fri, 25 May 2007 18:29:20 +0100 (BST) Message-ID: <46571CEC.7070202@archonet.com> Date: Fri, 25 May 2007 18:29:16 +0100 From: Richard Huxton User-Agent: Thunderbird 2.0.0.0 (X11/20070326) MIME-Version: 1.0 To: mark@mark.mielke.cc Cc: Mark Lewis , James Mansion , Magnus Hagander , Alexander Staubo , Andy , 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> <4657023A.20209@archonet.com> <20070525165633.GA13579@mark.mielke.cc> In-Reply-To: <20070525165633.GA13579@mark.mielke.cc> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/527 X-Sequence-Number: 24917 mark@mark.mielke.cc wrote: > On Fri, May 25, 2007 at 04:35:22PM +0100, Richard Huxton wrote: >>> I notice you did not provide a real life example as requested. :-) >> OK - any application that allows user-built queries: > foo> >> Want another? Any application that has a "search by name" box - users >> can (and do) put one letter in and hit enter. >> Unfortunately you don't always have control over the selectivity of >> queries issued. > > The database has 10 million records. The user enters "bar" and it > translates to "%bar%". You are suggesting that we expect bar to match > 1 million+ records? :-) I was saying that you don't know. At least, I don't know of any cheap way of gathering full substring stats or doing a full substring indexing. Even tsearch2 can't do that. > I hope not. I would define this as bad process. I would also use "LIMIT" > to something like "100". Yes, but that's not the query we're talking about is it? If possible you don't do '%bar%' searches at all. If you do, you try to restrict it further or LIMIT the results. There's nothing to discuss in these cases. >>> This seems like an ivory tower restriction. Not allowing best performance >>> in a common situation vs not allowing worst performance in a not-so-common >>> situation. >> What best performance plan are you thinking of? I'm assuming we're >> talking about trailing-wildcard matches here, rather than "contains" >> style matches. > > "Trailing-wildcard" already uses B-Tree index, does it not? Yes, it searches the btree and then checks the data for visibility. I thought that was what you felt could be worked around. It appears I was wrong. > I am speaking of contains, as contains is the one that was said to > require a seqscan. I am questioning why it requires a seqscan. Well, you seemed to be suggesting you had something better in mind. At least, that was my reading of your original post. > The > claim was made that with MVCC, the index is insufficient to check > for visibility True, for PG's implementation of MVCC. You *could* have visibility in each index, but that obviously would take more space. For a table with many indexes, that could be a *lot* more space. You also have to update all that visibilty information too. > and that the table would need to be accessed anyways, > therefore a seqscan is required. I question whether a like '%bar%' > should be considered a high selectivity query in the general case. > I question whether a worst case should be assumed. Well, the general rule-of-thumb is only about 10% for the changeover between index & seq-scan. That is, once you are reading 10% of the rows on disk (to check visibility) you might as well read them all (since you'll be reading most of the blocks anyway if the rows are randomly distributed). If you are doing SELECT * from that table then you'll want all that data you read. If you are doing SELECT count(*) then you only wanted the visibility :-( Now you and I can look at a substring and probably make a good guess how common it is (assuming we know the targets are British surnames or Japanese towns). PG needs one number - or rather, it picks one number for each length of search-string (afaik). > Perhaps I question too much? :-) Not sure it's possible to question too much :-) However, you need to provide answers occasionally too - what numbers would you pick? :-) -- Richard Huxton Archonet Ltd From lists@peufeu.com Fri May 25 17:30:21 2007 Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id E882E9FB78B for ; Fri, 25 May 2007 14:30:21 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 78479-02 for ; Fri, 25 May 2007 14:30:09 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from h07.llord.com (unknown [195.140.142.194]) by postgresql.org (Postfix) with ESMTP id B7E009FB6FA for ; Fri, 25 May 2007 14:30:06 -0300 (ADT) Received: from par69-8-88-161-102-87.fbx.proxad.net ([88.161.102.87] helo=apollo13) by h07.llord.com with esmtpa (Exim 4.66) (envelope-from ) id 1Hrdae-0002PG-R7; Fri, 25 May 2007 19:28:37 +0200 Date: Fri, 25 May 2007 19:31:16 +0200 To: "Richard Huxton" Subject: Re: LIKE search and performance From: PFC Cc: mark@mark.mielke.cc, "Mark Lewis" , "James Mansion" , "Magnus Hagander" , "Alexander Staubo" , Andy , pgsql-performance@postgresql.org Content-Type: text/plain; format=flowed; delsp=yes; charset=utf-8 MIME-Version: 1.0 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> <4657023A.20209@archonet.com> <46571825.30707@archonet.com> Content-Transfer-Encoding: 7bit Message-ID: In-Reply-To: <46571825.30707@archonet.com> User-Agent: Opera Mail/9.10 (Linux) X-PopBeforeSMTPSenders: junk@peufeu.com, lists@peufeu.com, peufeu@peufeu.com, pfcaillaud@peufeu.com X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - h07.llord.com X-AntiAbuse: Original Domain - postgresql.org X-AntiAbuse: Originator/Caller UID/GID - [0 0] / [47 12] X-AntiAbuse: Sender Address Domain - peufeu.com X-Source: X-Source-Args: X-Source-Dir: X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=2.261 tagged_above=0 required=5 tests=AWL=-0.515, BAYES_50=0.001, RCVD_IN_NJABL_SPAM=2.775 X-Spam-Level: ** X-Archive-Number: 200705/526 X-Sequence-Number: 24916 > None of which address the question of what plan PG should produce for: > SELECT * FROM bigtable WHERE foo LIKE 's%' Ah, this one already uses the btree since the '%' is at the end. My point is that a search like this will yield too many results to be useful to the user anyway, so optimizing its performance is a kind of red herring. From dev@archonet.com Fri May 25 17:32:53 2007 Received: from localhost (maia-2.hub.org [200.46.204.187]) by postgresql.org (Postfix) with ESMTP id 4D0B19FC001 for ; Fri, 25 May 2007 14:32:53 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.187]) (amavisd-maia, port 10024) with ESMTP id 03537-01-2 for ; Fri, 25 May 2007 14:32:43 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.4 Received: from mail.metronet.co.uk (mail.metronet.co.uk [213.162.97.75]) by postgresql.org (Postfix) with ESMTP id CDFE09FBF75 for ; Fri, 25 May 2007 14:32:44 -0300 (ADT) Received: from server3.office.archonet.com (84-51-143-99.archon037.adsl.metronet.co.uk [84.51.143.99]) by smtp.metronet.co.uk (MetroNet Mail) with ESMTP id BD9007580E; Fri, 25 May 2007 18:32:39 +0100 (BST) Received: from [192.168.1.36] (dell36.office.archonet.com [192.168.1.36]) by server3.office.archonet.com (Postfix) with ESMTP id C8BE42740EB; Fri, 25 May 2007 18:32:43 +0100 (BST) Message-ID: <46571DB7.2040607@archonet.com> Date: Fri, 25 May 2007 18:32:39 +0100 From: Richard Huxton User-Agent: Thunderbird 2.0.0.0 (X11/20070326) MIME-Version: 1.0 To: PFC Cc: mark@mark.mielke.cc, Mark Lewis , James Mansion , Magnus Hagander , Alexander Staubo , Andy , 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> <4657023A.20209@archonet.com> <46571825.30707@archonet.com> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/528 X-Sequence-Number: 24918 PFC wrote: >> None of which address the question of what plan PG should produce for: >> SELECT * FROM bigtable WHERE foo LIKE 's%' > > Ah, this one already uses the btree since the '%' is at the end. > My point is that a search like this will yield too many results to > be useful to the user anyway, so optimizing its performance is a kind of > red herring. At the *application level* yes. At the *query planner* level no. At the query planner level I just want it to come up with the best plan it can. The original argument was that PG's estimate of the number of matching rows was too optimistic (or pessimistic) in the case where we are doing a contains substring-search. -- Richard Huxton Archonet Ltd From stark@enterprisedb.com Fri May 25 17:58:38 2007 Received: from localhost (maia-4.hub.org [200.46.204.183]) by postgresql.org (Postfix) with ESMTP id BFE4E9FC12E for ; Fri, 25 May 2007 14:58:38 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 97579-01 for ; Fri, 25 May 2007 14:58:36 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from oxford.xeocode.com (unknown [87.127.95.194]) by postgresql.org (Postfix) with ESMTP id 6AF659FB7DF for ; Fri, 25 May 2007 14:58:35 -0300 (ADT) Received: from localhost ([127.0.0.1] helo=oxford.xeocode.com) by oxford.xeocode.com with esmtp (Exim 4.67) (envelope-from ) id 1Hre3J-0002ZQ-GW; Fri, 25 May 2007 18:58:13 +0100 From: Gregory Stark To: "Richard Huxton" Cc: , "Mark Lewis" , "James Mansion" , "Magnus Hagander" , "Alexander Staubo" , "Andy" , Subject: Re: LIKE search and performance In-Reply-To: <46571CEC.7070202@archonet.com> (Richard Huxton's message of "Fri, 25 May 2007 18:29:16 +0100") Organization: EnterpriseDB 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> <4657023A.20209@archonet.com> <20070525165633.GA13579@mark.mielke.cc> <46571CEC.7070202@archonet.com> X-Draft-From: ("nnimap+mail01.enterprisedb.com:INBOX.performance" 648) Date: Fri, 25 May 2007 18:58:13 +0100 Message-ID: <87y7jckcp6.fsf@oxford.xeocode.com> User-Agent: Gnus/5.110006 (No Gnus v0.6) Emacs/21.4 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/529 X-Sequence-Number: 24919 "Richard Huxton" writes: > Now you and I can look at a substring and probably make a good guess how common > it is (assuming we know the targets are British surnames or Japanese towns). PG > needs one number - or rather, it picks one number for each length of > search-string (afaik). I don't think that's true. Postgres calculates the lower and upper bound implied by the search pattern and then uses the histogram to estimate how selective that range is. It's sometimes surprisingly good but obviously it's not perfect. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com From dev@archonet.com Fri May 25 18:15:22 2007 Received: from localhost (maia-3.hub.org [200.46.204.184]) by postgresql.org (Postfix) with ESMTP id 2BE109FC269 for ; Fri, 25 May 2007 15:15:22 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024) with ESMTP id 40341-03 for ; Fri, 25 May 2007 15:14:59 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from mail.metronet.co.uk (mail.metronet.co.uk [213.162.97.75]) by postgresql.org (Postfix) with ESMTP id 4E6829FC279 for ; Fri, 25 May 2007 15:13:16 -0300 (ADT) Received: from server3.office.archonet.com (84-51-143-99.archon037.adsl.metronet.co.uk [84.51.143.99]) by smtp.metronet.co.uk (MetroNet Mail) with ESMTP id A30D5143968; Fri, 25 May 2007 19:13:14 +0100 (BST) Received: from [192.168.1.36] (dell36.office.archonet.com [192.168.1.36]) by server3.office.archonet.com (Postfix) with ESMTP id DA7E627410E; Fri, 25 May 2007 19:13:18 +0100 (BST) Message-ID: <4657273A.3080005@archonet.com> Date: Fri, 25 May 2007 19:13:14 +0100 From: Richard Huxton User-Agent: Thunderbird 2.0.0.0 (X11/20070326) MIME-Version: 1.0 To: Gregory Stark Cc: mark@mark.mielke.cc, Mark Lewis , James Mansion , Magnus Hagander , Alexander Staubo , Andy , 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> <20070524215450.GA3858@mark.mielke.cc> <46569AA5.10205@archonet.com> <20070525141630.GA12162@mark.mielke.cc> <4657023A.20209@archonet.com> <20070525165633.GA13579@mark.mielke.cc> <46571CEC.7070202@archonet.com> <87y7jckcp6.fsf@oxford.xeocode.com> In-Reply-To: <87y7jckcp6.fsf@oxford.xeocode.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200705/531 X-Sequence-Number: 24921 Gregory Stark wrote: > "Richard Huxton" writes: > >> Now you and I can look at a substring and probably make a good guess how common >> it is (assuming we know the targets are British surnames or Japanese towns). PG >> needs one number - or rather, it picks one number for each length of >> search-string (afaik). > > I don't think that's true. Postgres calculates the lower and upper bound > implied by the search pattern and then uses the histogram to estimate how > selective that range is. It's sometimes surprisingly good but obviously it's > not perfect. Sorry - I'm obviously picking my words badly today. I meant for the "contains" substring match. It gives different (goes away and checks...yes) predictions based on string length. So it guesses that LIKE '%aaa%' will match more than LIKE '%aaaa%'. Of course, if we were matching surnames you and I could say that this is very unlikely, but without some big statistics table I guess there's not much more PG can do. For a trailing wildcard LIKE 'aaa%' it can and does as you say convert this into something along the lines of (>= 'aaa' AND < 'aab'). Although IIRC that depends if your locale allows such (not sure, I don't really use non-C/non-English locales enough). -- Richard Huxton Archonet Ltd From james@mansionfamily.plus.com Wed Jun 6 22:27:41 2007 Received: from localhost (maia-5.hub.org [200.46.204.182]) by postgresql.org (Postfix) with ESMTP id 5F0B79FB309 for ; Wed, 6 Jun 2007 19:27:41 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.182]) (amavisd-maia, port 10024) with ESMTP id 57809-06 for ; Wed, 6 Jun 2007 19:27:28 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from ptb-relay03.plus.net (ptb-relay03.plus.net [212.159.14.214]) by postgresql.org (Postfix) with ESMTP id 242A59FB2DA for ; Wed, 6 Jun 2007 19:27:38 -0300 (ADT) Received: from [80.229.150.39] (helo=mansionfamily.plus.com) by ptb-relay03.plus.net with esmtp (Exim) id 1Hw3ya-0000Ld-0K for pgsql-performance@postgresql.org; Wed, 06 Jun 2007 23:27:36 +0100 Received: from [192.168.0.87] ([192.168.0.87]:4639) by mansionfamily.plus.com with [XMail 1.22 ESMTP Server] id for from ; Wed, 6 Jun 2007 23:21:12 +0100 Message-ID: <466733D1.1040308@mansionfamily.plus.com> Date: Wed, 06 Jun 2007 23:23:13 +0100 From: James Mansion User-Agent: Thunderbird 2.0.0.0 (Windows/20070326) MIME-Version: 1.0 To: mark@mark.mielke.cc CC: Mark Lewis , Magnus Hagander , Alexander Staubo , Andy , 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> <20070524215450.GA3858@mark.mielke.cc> In-Reply-To: <20070524215450.GA3858@mark.mielke.cc> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200706/113 X-Sequence-Number: 25146 mark@mark.mielke.cc wrote: > What is a real life example where an intelligent and researched > database application would issue a like or ilike query as their > primary condition in a situation where they expected very high > selectivity? > In my case the canonical example is to search against textual keys where the search is performed automatically if the user hs typed enough data and paused. In almost all cases the '%' trails, and I'm looking for 'starts with' in effect. usually the search will have a specified upper number of returned rows, if that's an available facility. I realise in this case that matching against the index does not allow the match count unless we check MVCC as we go, but I don't see why another thread can't be doing that. James From mark@mark.mielke.cc Thu Jun 7 03:35:05 2007 Received: from localhost (maia-4.hub.org [200.46.204.183]) by postgresql.org (Postfix) with ESMTP id 1471C9FB395 for ; Thu, 7 Jun 2007 00:35:05 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 31590-04 for ; Thu, 7 Jun 2007 00:34:59 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from svr4.postgresql.org (svr4.postgresql.org [66.98.251.159]) by postgresql.org (Postfix) with ESMTP id 89B9C9FB38E for ; Thu, 7 Jun 2007 00:34:59 -0300 (ADT) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.3 Received: from mark.mielke.cc (206-248-136-41.dsl.teksavvy.com [206.248.136.41]) by svr4.postgresql.org (Postfix) with ESMTP id 4E43E5AF02D for ; Thu, 7 Jun 2007 03:34:58 +0000 (GMT) Received: from mark.mielke.cc (localhost.localdomain [127.0.0.1]) by mark.mielke.cc (8.14.1/8.14.1) with ESMTP id l573XtCS002790; Wed, 6 Jun 2007 23:33:55 -0400 Received: (from mark@localhost) by mark.mielke.cc (8.14.1/8.14.1/Submit) id l573XqdC002789; Wed, 6 Jun 2007 23:33:52 -0400 Date: Wed, 6 Jun 2007 23:33:52 -0400 From: mark@mark.mielke.cc To: James Mansion Cc: Mark Lewis , Magnus Hagander , Alexander Staubo , Andy , pgsql-performance@postgresql.org Subject: Re: LIKE search and performance Message-ID: <20070607033352.GA2773@mark.mielke.cc> 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> <20070524215450.GA3858@mark.mielke.cc> <466733D1.1040308@mansionfamily.plus.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <466733D1.1040308@mansionfamily.plus.com> User-Agent: Mutt/1.5.14 (2007-02-12) X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.86 tagged_above=0 required=5 tests=AWL=-0.237, BAYES_50=0.001, FORGED_RCVD_HELO=0.135, NO_REAL_NAME=0.961 X-Spam-Level: X-Archive-Number: 200706/117 X-Sequence-Number: 25150 On Wed, Jun 06, 2007 at 11:23:13PM +0100, James Mansion wrote: > mark@mark.mielke.cc wrote: > >What is a real life example where an intelligent and researched > >database application would issue a like or ilike query as their > >primary condition in a situation where they expected very high > >selectivity? > In my case the canonical example is to search against textual keys > where the search is performed automatically if the user hs typed > enough data and paused. In almost all cases the '%' trails, and I'm > looking for 'starts with' in effect. usually the search will have a > specified upper number of returned rows, if that's an available > facility. I realise in this case that matching against the index > does not allow the match count unless we check MVCC as we go, but I > don't see why another thread can't be doing that. I believe PostgreSQL already considers using the index for "starts with", so this wasn't part of the discussion for me. Sorry that this wasn't clear. Cheers, mark -- mark@mielke.cc / markm@ncf.ca / markm@nortel.com __________________________ . . _ ._ . . .__ . . ._. .__ . . . .__ | Neighbourhood Coder |\/| |_| |_| |/ |_ |\/| | |_ | |/ |_ | | | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness bind them... http://mark.mielke.cc/