From dkaplan@citizenhawk.com Wed Feb  27 19:47:57 2008
Received: from localhost (unknown [200.46.204.183])
	by postgresql.org (Postfix) with ESMTP id 78D422E004F
	for <pgsql-performance-postgresql.org@postgresql.org>;
	Wed, 27 Feb 2008 15:47:57 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024)
	with ESMTP id 90119-01 for
	<pgsql-performance-postgresql.org@postgresql.org>;
	Wed, 27 Feb 2008 15:47:52 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.5
Received: from smtp180.sat.emailsrvr.com (smtp180.sat.emailsrvr.com
	[66.216.121.180])
	by postgresql.org (Postfix) with ESMTP id A408B2E0058
	for <pgsql-performance@postgresql.org>;
	Wed, 27 Feb 2008 15:47:52 -0400 (AST)
Received: from relay8.relay.sat.mlsrvr.com (localhost [127.0.0.1])
	by relay8.relay.sat.mlsrvr.com (SMTP Server) with ESMTP id B631B1B4138;
	Wed, 27 Feb 2008 14:19:21 -0500 (EST)
Received: by relay8.relay.sat.mlsrvr.com (Authenticated sender:
	dkaplan-AT-typosquasher.com) with ESMTP id 801D71B400C
	for <pgsql-performance@postgresql.org>;
	Wed, 27 Feb 2008 14:19:21 -0500 (EST)
From: "Dan Kaplan" <dkaplan@citizenhawk.com>
To: <pgsql-performance@postgresql.org>
Subject: t1.col like '%t2.col%'
Date: Wed, 27 Feb 2008 11:19:22 -0800
Organization: CitizenHawk, Inc.
Message-ID: <00c001c87975$a907e2e0$1d00a8c0@dan>
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----=_NextPart_000_00C1_01C87932.9AE4A2E0"
X-Mailer: Microsoft Office Outlook 11
X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2900.3198
Thread-Index: Ach5daiqZik+LYSgQ02xij31PBaBtQ==
X-Virus-Scanned: Maia Mailguard 1.0.1
X-Spam-Status: No, hits=0.001 tagged_above=0 required=5
	tests=HTML_MESSAGE=0.001
X-Spam-Level: 
X-Archive-Number: 200802/380
X-Sequence-Number: 28922

This is a multi-part message in MIME format.

------=_NextPart_000_00C1_01C87932.9AE4A2E0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit

I've got a lot of rows in one table and a lot of rows in another table.  I
want to do a bunch of queries on their join column.  One of these is like
this: t1.col like '%t2.col%'

 

I know that always sucks.  I'm wondering how I can make it better.  First, I
should let you know that I can likely hold both of these tables entirely in
ram.  Since that's the case, would it be better to accomplish this with my
programming language?  Also you should know that in most cases, t1.col and
t2.col is 2 words or less.  I'm not sure if that matters, I mention it
because it may make tsearch2 perform badly.


------=_NextPart_000_00C1_01C87932.9AE4A2E0
Content-Type: text/html;
	charset="us-ascii"
Content-Transfer-Encoding: quoted-printable

<html xmlns:o=3D"urn:schemas-microsoft-com:office:office" =
xmlns:w=3D"urn:schemas-microsoft-com:office:word" =
xmlns=3D"http://www.w3.org/TR/REC-html40">

<head>
<meta http-equiv=3DContent-Type content=3D"text/html; =
charset=3Dus-ascii">
<meta name=3DGenerator content=3D"Microsoft Word 11 (filtered medium)">
<style>
<!--
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
	{margin:0in;
	margin-bottom:.0001pt;
	font-size:12.0pt;
	font-family:"Times New Roman";}
a:link, span.MsoHyperlink
	{color:blue;
	text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
	{color:purple;
	text-decoration:underline;}
span.EmailStyle17
	{mso-style-type:personal-compose;
	font-family:Arial;
	color:windowtext;}
@page Section1
	{size:8.5in 11.0in;
	margin:1.0in 1.25in 1.0in 1.25in;}
div.Section1
	{page:Section1;}
-->
</style>

</head>

<body lang=3DEN-US link=3Dblue vlink=3Dpurple>

<div class=3DSection1>

<p class=3DMsoNormal><font size=3D2 face=3DArial><span =
style=3D'font-size:10.0pt;
font-family:Arial'>I&#8217;ve got a lot of rows in one table and a lot =
of rows
in another table.&nbsp; I want to do a bunch of queries on their join
column.&nbsp; One of these is like this: t1.col like =
'%t2.col%'<o:p></o:p></span></font></p>

<p class=3DMsoNormal><font size=3D2 face=3DArial><span =
style=3D'font-size:10.0pt;
font-family:Arial'><o:p>&nbsp;</o:p></span></font></p>

<p class=3DMsoNormal><font size=3D2 face=3DArial><span =
style=3D'font-size:10.0pt;
font-family:Arial'>I know that always sucks.&nbsp; I&#8217;m wondering =
how I can
make it better.&nbsp; First, I should let you know that I can likely =
hold both
of these tables entirely in ram.&nbsp; Since that&#8217;s the case, =
would it be
better to accomplish this with my programming language?&nbsp; Also you =
should
know that in most cases, t1.col and t2.col is 2 words or less.&nbsp; =
I&#8217;m
not sure if that matters, I mention it because it may make tsearch2 =
perform
badly.<o:p></o:p></span></font></p>

</div>

</body>

</html>

------=_NextPart_000_00C1_01C87932.9AE4A2E0--




From oleg@sai.msu.su Thu Feb  28 05:47:30 2008
Received: from localhost (unknown [200.46.204.183])
	by postgresql.org (Postfix) with ESMTP id 24CBB2E007E
	for <pgsql-performance-postgresql.org@postgresql.org>;
	Thu, 28 Feb 2008 01:47:30 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024)
	with ESMTP id 58832-04 for
	<pgsql-performance-postgresql.org@postgresql.org>;
	Thu, 28 Feb 2008 01:47:27 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.5
Received: from sn.sai.msu.ru (sn.sai.msu.ru [195.208.220.215])
	by postgresql.org (Postfix) with ESMTP id 4FB442E0071
	for <pgsql-performance@postgresql.org>;
	Thu, 28 Feb 2008 01:47:27 -0400 (AST)
Received: from sn.sai.msu.ru (localhost [127.0.0.1])
	by sn.sai.msu.ru (8.14.1/8.12.8) with ESMTP id m1S5lMiI028417;
	Thu, 28 Feb 2008 08:47:22 +0300
Received: from localhost (megera@localhost)
	by sn.sai.msu.ru (8.14.1/8.12.8/Submit) with ESMTP id m1S5lMoM028414;
	Thu, 28 Feb 2008 08:47:22 +0300
X-Authentication-Warning: sn.sai.msu.ru: megera owned process doing -bs
Date: Thu, 28 Feb 2008 08:47:22 +0300 (MSK)
From: Oleg Bartunov <oleg@sai.msu.su>
X-X-Sender: megera@sn.sai.msu.ru
To: Dan Kaplan <dkaplan@citizenhawk.com>
cc: pgsql-performance@postgresql.org
Subject: Re: t1.col like '%t2.col%'
In-Reply-To: <00c001c87975$a907e2e0$1d00a8c0@dan>
Message-ID: <Pine.LNX.4.64.0802280833040.31180@sn.sai.msu.ru>
References: <00c001c87975$a907e2e0$1d00a8c0@dan>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
X-Virus-Scanned: Maia Mailguard 1.0.1
X-Spam-Status: No, hits=0.591 tagged_above=0 required=5 tests=AWL=-1.534,
	DNS_FROM_RFC_BOGUSMX=2.125
X-Spam-Level: 
X-Archive-Number: 200802/391
X-Sequence-Number: 28933

On Wed, 27 Feb 2008, Dan Kaplan wrote:

> I've got a lot of rows in one table and a lot of rows in another table.  I
> want to do a bunch of queries on their join column.  One of these is like
> this: t1.col like '%t2.col%'

We have an idea how to speedup wildcard search at the expense of the size - 
we have to index all permutation of the original word. Then we could
use GIN for quieries like a*b.

>
>
>
> I know that always sucks.  I'm wondering how I can make it better.  First, I
> should let you know that I can likely hold both of these tables entirely in
> ram.  Since that's the case, would it be better to accomplish this with my
> programming language?  Also you should know that in most cases, t1.col and
> t2.col is 2 words or less.  I'm not sure if that matters, I mention it
> because it may make tsearch2 perform badly.
>

contrib/pg_trgm should help you.

>

 	Regards,
 		Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83



From dkaplan@citizenhawk.com Fri Feb  29 23:52:34 2008
Received: from localhost (unknown [200.46.204.183])
	by postgresql.org (Postfix) with ESMTP id 91CBD2E0110
	for <pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 19:52:34 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024)
	with ESMTP id 57890-04 for
	<pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 19:52:31 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.5
Received: from smtp130.sat.emailsrvr.com (smtp130.sat.emailsrvr.com
	[66.216.121.130])
	by postgresql.org (Postfix) with ESMTP id B813D2E010A
	for <pgsql-performance@postgresql.org>;
	Fri, 29 Feb 2008 19:52:31 -0400 (AST)
Received: from relay3.relay.sat.mlsrvr.com (localhost [127.0.0.1])
	by relay3.relay.sat.mlsrvr.com (SMTP Server) with ESMTP id 169931D5F1C;
	Fri, 29 Feb 2008 18:52:30 -0500 (EST)
Received: by relay3.relay.sat.mlsrvr.com (Authenticated sender:
	dkaplan-AT-typosquasher.com) with ESMTP id E573C1CD177
	for <pgsql-performance@postgresql.org>;
	Fri, 29 Feb 2008 18:52:29 -0500 (EST)
From: "Dan Kaplan" <dkaplan@citizenhawk.com>
Cc: <pgsql-performance@postgresql.org>
References: <00c001c87975$a907e2e0$1d00a8c0@dan>
	<Pine.LNX.4.64.0802280833040.31180@sn.sai.msu.ru>
Subject: Re: t1.col like '%t2.col%'
Date: Fri, 29 Feb 2008 15:52:31 -0800
Organization: CitizenHawk, Inc.
Message-ID: <001401c87b2e$26386000$1d00a8c0@dan>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="US-ASCII"
Content-Transfer-Encoding: 7bit
X-Mailer: Microsoft Office Outlook 11
In-Reply-To: <Pine.LNX.4.64.0802280833040.31180@sn.sai.msu.ru>
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3198
thread-index: Ach5zZhFf2uiG79tQKSHXaW8AfpnzQBYIOMg
X-Virus-Scanned: Maia Mailguard 1.0.1
X-Spam-Status: No, hits=0.791 tagged_above=0 required=5 tests=AWL=-0.790,
	MISSING_HEADERS=1.581
X-Spam-Level: 
X-Archive-Number: 200802/407
X-Sequence-Number: 28949

I learned a little about pg_trgm here:
http://www.sai.msu.su/~megera/postgres/gist/pg_trgm/README.pg_trgm

But this seems like it's for finding similarities, not substrings.  How can
I use it to speed up t1.col like '%t2.col%'?

Thanks,
Dan

-----Original Message-----
From: pgsql-performance-owner@postgresql.org
[mailto:pgsql-performance-owner@postgresql.org] On Behalf Of Oleg Bartunov
Sent: Wednesday, February 27, 2008 9:47 PM
To: Dan Kaplan
Cc: pgsql-performance@postgresql.org
Subject: Re: [PERFORM] t1.col like '%t2.col%'

On Wed, 27 Feb 2008, Dan Kaplan wrote:

> I've got a lot of rows in one table and a lot of rows in another table.  I
> want to do a bunch of queries on their join column.  One of these is like
> this: t1.col like '%t2.col%'

We have an idea how to speedup wildcard search at the expense of the size - 
we have to index all permutation of the original word. Then we could
use GIN for quieries like a*b.

>
>
>
> I know that always sucks.  I'm wondering how I can make it better.  First,
I
> should let you know that I can likely hold both of these tables entirely
in
> ram.  Since that's the case, would it be better to accomplish this with my
> programming language?  Also you should know that in most cases, t1.col and
> t2.col is 2 words or less.  I'm not sure if that matters, I mention it
> because it may make tsearch2 perform badly.
>

contrib/pg_trgm should help you.

>

 	Regards,
 		Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
       choose an index scan if your joining column's datatypes do not
       match




From jd@commandprompt.com Fri Feb  29 23:56:13 2008
Received: from localhost (unknown [200.46.204.184])
	by postgresql.org (Postfix) with ESMTP id 0A6522E0117
	for <pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 19:56:13 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024)
	with ESMTP id 34001-07 for
	<pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 19:56:03 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.5
Received: from lists.commandprompt.com (host-159.commandprompt.net
	[207.173.203.159])
	by postgresql.org (Postfix) with ESMTP id 2C64A2E010A
	for <pgsql-performance@postgresql.org>;
	Fri, 29 Feb 2008 19:56:08 -0400 (AST)
Received: from localhost (or-69-34-217-90.sta.embarqhsd.net [69.34.217.90])
	(authenticated bits=0)
	by lists.commandprompt.com (8.13.8/8.13.8) with ESMTP id m1TNuTul029005
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
	Fri, 29 Feb 2008 15:56:30 -0800
Date: Fri, 29 Feb 2008 15:56:42 -0800
From: "Joshua D. Drake" <jd@commandprompt.com>
To: "Dan Kaplan" <dkaplan@citizenhawk.com>
Cc: <pgsql-performance@postgresql.org>
Subject: Re: t1.col like '%t2.col%'
Message-ID: <20080229155642.20ac07be@commandprompt.com>
In-Reply-To: <001401c87b2e$26386000$1d00a8c0@dan>
References: <00c001c87975$a907e2e0$1d00a8c0@dan>
	<Pine.LNX.4.64.0802280833040.31180@sn.sai.msu.ru>
	<001401c87b2e$26386000$1d00a8c0@dan>
Organization: Command Prompt, Inc.
X-Mailer: Claws Mail 3.0.2 (GTK+ 2.12.0; x86_64-pc-linux-gnu)
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: base64
X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.0
	(lists.commandprompt.com [207.173.203.159]);
	Fri, 29 Feb 2008 15:56:30 -0800 (PST)
X-Virus-Scanned: Maia Mailguard 1.0.1
X-Spam-Status: No, hits=0.541 tagged_above=0 required=5 tests=AWL=-2.255,
	MIME_BASE64_TEXT=2.796
X-Spam-Level: 
X-Archive-Number: 200802/408
X-Sequence-Number: 28950

LS0tLS1CRUdJTiBQR1AgU0lHTkVEIE1FU1NBR0UtLS0tLQ0KSGFzaDogU0hBMQ0KDQpPbiBGcmks
IDI5IEZlYiAyMDA4IDE1OjUyOjMxIC0wODAwDQoiRGFuIEthcGxhbiIgPGRrYXBsYW5AY2l0aXpl
bmhhd2suY29tPiB3cm90ZToNCg0KPiBJIGxlYXJuZWQgYSBsaXR0bGUgYWJvdXQgcGdfdHJnbSBo
ZXJlOg0KPiBodHRwOi8vd3d3LnNhaS5tc3Uuc3Uvfm1lZ2VyYS9wb3N0Z3Jlcy9naXN0L3BnX3Ry
Z20vUkVBRE1FLnBnX3RyZ20NCj4gDQo+IEJ1dCB0aGlzIHNlZW1zIGxpa2UgaXQncyBmb3IgZmlu
ZGluZyBzaW1pbGFyaXRpZXMsIG5vdCBzdWJzdHJpbmdzLg0KPiBIb3cgY2FuIEkgdXNlIGl0IHRv
IHNwZWVkIHVwIHQxLmNvbCBsaWtlICcldDIuY29sJSc/DQoNCkZhc3RlciBkaXNrcy4NCg0KTm8g
bWF0dGVyIHdoYXQsIHRoYXQgd2lsbCBzZXFzY2FuLiBTbyBpZiB5b3Ugd2FudCBpdCB0byBnbyBm
YXN0ZXIsIHlvdQ0KbmVlZCBmYXN0ZXIgaGFyZHdhcmUuDQoNClNpbmNlcmVseSwNCg0KSm9zaHVh
IEQuIERyYWtlDQoNCi0gLS0gDQpUaGUgUG9zdGdyZVNRTCBDb21wYW55IHNpbmNlIDE5OTc6IGh0
dHA6Ly93d3cuY29tbWFuZHByb21wdC5jb20vIA0KUG9zdGdyZVNRTCBDb21tdW5pdHkgQ29uZmVy
ZW5jZTogaHR0cDovL3d3dy5wb3N0Z3Jlc3FsY29uZmVyZW5jZS5vcmcvDQpEb25hdGUgdG8gdGhl
IFBvc3RncmVTUUwgUHJvamVjdDogaHR0cDovL3d3dy5wb3N0Z3Jlc3FsLm9yZy9hYm91dC9kb25h
dGUNClBvc3RncmVTUUwgU1BJIExpYWlzb24gfCBTUEkgRGlyZWN0b3IgfCAgUG9zdGdyZVNRTCBw
b2xpdGljYWwgcHVuZGl0DQoNCi0tLS0tQkVHSU4gUEdQIFNJR05BVFVSRS0tLS0tDQpWZXJzaW9u
OiBHbnVQRyB2MS40LjYgKEdOVS9MaW51eCkNCg0KaUQ4REJRRkh5SnU5QVRiL3pxZlpVVVFSQWxQ
d0FKOVhadm9Xdk5xdXVXR3l0dkpmTmxtNzlMQnZ0d0NiQndSdw0KdXFiN2ZoRDUrdzg3QnpVb1ZF
aklDRVk9DQo9ejV4UQ0KLS0tLS1FTkQgUEdQIFNJR05BVFVSRS0tLS0tDQo=



From Gregory.Williamson@digitalglobe.com Sat Mar  1 00:30:18 2008
Received: from localhost (unknown [200.46.204.184])
	by postgresql.org (Postfix) with ESMTP id 0A8492E0141
	for <pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 20:30:18 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024)
	with ESMTP id 90302-06 for
	<pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 20:30:06 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.5
Received: from copgpuniv.digitalglobe.com (ew-fw-out.digitalglobe.com
	[205.166.175.2])
	by postgresql.org (Postfix) with ESMTP id 4B1D52E0040
	for <pgsql-performance@postgresql.org>;
	Fri, 29 Feb 2008 20:30:12 -0400 (AST)
Received: from copgpuniv.digitalglobe.com (localhost.localdomain [127.0.0.1])
	by copgpuniv.digitalglobe.com (PGP Universal) with ESMTP
	id 0A99D2A03D6; Fri, 29 Feb 2008 17:30:10 -0700 (MST)
Received: from comailgate2.digitalglobe.com ([10.10.42.200])
	by copgpuniv.digitalglobe.com (PGP Universal service);
	Fri, 29 Feb 2008 17:30:10 -0700
X-PGP-Universal: processed;
	by copgpuniv.digitalglobe.com on Fri, 29 Feb 2008 17:30:10 -0700
Received: from COMAIL01.digitalglobe.com ([10.10.42.61]) by
	comailgate2.digitalglobe.com with Microsoft SMTPSVC(6.0.3790.1830);
	Fri, 29 Feb 2008 17:30:09 -0700
X-MimeOLE: Produced By Microsoft Exchange V6.5
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----_=_NextPart_001_01C87B33.677D522B"
Subject: Re: t1.col like '%t2.col%'
Date: Fri, 29 Feb 2008 17:30:08 -0700
Message-ID: 
 <8B319E5A30FF4A48BE7EEAAF609DB233015E341B@COMAIL01.digitalglobe.com>
X-MS-Has-Attach: 
X-MS-TNEF-Correlator: 
Thread-Topic: [PERFORM] t1.col like '%t2.col%'
Thread-Index: Ach7LusC7RUc+8n/QQaJbuzd6yv47gAA5csA
References: 
 <00c001c87975$a907e2e0$1d00a8c0@dan><Pine.LNX.4.64.0802280833040.31180@sn.sai.msu.ru><001401c87b2e$26386000$1d00a8c0@dan>
	<20080229155642.20ac07be@commandprompt.com>
From: "Gregory Williamson" <Gregory.Williamson@digitalglobe.com>
To: "Joshua D. Drake" <jd@commandprompt.com>,
	"Dan Kaplan" <dkaplan@citizenhawk.com>
Cc: <pgsql-performance@postgresql.org>
X-OriginalArrivalTime: 01 Mar 2008 00:30:09.0646 (UTC)
	FILETIME=[67E1D0E0:01C87B33]
X-Virus-Scanned: Maia Mailguard 1.0.1
X-Archive-Number: 200802/409
X-Sequence-Number: 28951

This is a multi-part message in MIME format.

------_=_NextPart_001_01C87B33.677D522B
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

Joshua Drake spake thusly:

> On Fri, 29 Feb 2008 15:52:31 -0800
> "Dan Kaplan" <dkaplan@citizenhawk.com> wrote:
>=20
> > I learned a little about pg_trgm here:
> > http://www.sai.msu.su/~megera/postgres/gist/pg_trgm/README.pg_trgm
> >=20
> > But this seems like it's for finding similarities, not substrings.
> > How can I use it to speed up t1.col like '%t2.col%'?
>=20
> Faster disks.
>=20
> No matter what, that will seqscan. So if you want it to go faster, you
> need faster hardware.

Word!

That said ...

Once upon a time we had a requirement to allow users to search within US =
counties for property owner name or street names by text fragment.

We used the now deprecated Full Text Indexing (FTI) with some =
handwaving. But that was in PostgreSQL 7.4 and FTI is not in the contrib =
package for some time now. See =
<http://pgfoundry.org/projects/simplefti/> ... I looked at using it in =
8.1 but my "C" chops weren't up to it, and it depended heavily on OIDs =
which we didn't want to use. Anyway, our business requirement evaporated =
so it doesn't matter to us now.

HTH,

Greg Williamson
Senior DBA
GlobeXplorer LLC, a DigitalGlobe company

Confidentiality Notice: This e-mail message, including any attachments, =
is for the sole use of the intended recipient(s) and may contain =
confidential and privileged information and must be protected in =
accordance with those provisions. Any unauthorized review, use, =
disclosure or distribution is prohibited. If you are not the intended =
recipient, please contact the sender by reply e-mail and destroy all =
copies of the original message.

(My corporate masters made me say this.)

------_=_NextPart_001_01C87B33.677D522B
Content-Type: text/html;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">
<META NAME=3D"Generator" CONTENT=3D"MS Exchange Server version =
6.5.7652.24">
<TITLE>RE: [PERFORM] t1.col like '%t2.col%'</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->

<P><FONT SIZE=3D2>Joshua Drake spake thusly:<BR>
<BR>
&gt; On Fri, 29 Feb 2008 15:52:31 -0800<BR>
&gt; &quot;Dan Kaplan&quot; &lt;dkaplan@citizenhawk.com&gt; wrote:<BR>
&gt;<BR>
&gt; &gt; I learned a little about pg_trgm here:<BR>
&gt; &gt; <A =
HREF=3D"http://www.sai.msu.su/~megera/postgres/gist/pg_trgm/README.pg_trg=
m">http://www.sai.msu.su/~megera/postgres/gist/pg_trgm/README.pg_trgm</A>=
<BR>
&gt; &gt;<BR>
&gt; &gt; But this seems like it's for finding similarities, not =
substrings.<BR>
&gt; &gt; How can I use it to speed up t1.col like '%t2.col%'?<BR>
&gt;<BR>
&gt; Faster disks.<BR>
&gt;<BR>
&gt; No matter what, that will seqscan. So if you want it to go faster, =
you<BR>
&gt; need faster hardware.<BR>
<BR>
Word!<BR>
<BR>
That said ...<BR>
<BR>
Once upon a time we had a requirement to allow users to search within US =
counties for property owner name or street names by text fragment.<BR>
<BR>
We used the now deprecated Full Text Indexing (FTI) with some =
handwaving. But that was in PostgreSQL 7.4 and FTI is not in the contrib =
package for some time now. See &lt;<A =
HREF=3D"http://pgfoundry.org/projects/simplefti/">http://pgfoundry.org/pr=
ojects/simplefti/</A>&gt; ... I looked at using it in 8.1 but my =
&quot;C&quot; chops weren't up to it, and it depended heavily on OIDs =
which we didn't want to use. Anyway, our business requirement evaporated =
so it doesn't matter to us now.<BR>
<BR>
HTH,<BR>
<BR>
Greg Williamson<BR>
Senior DBA<BR>
GlobeXplorer LLC, a DigitalGlobe company<BR>
<BR>
Confidentiality Notice: This e-mail message, including any attachments, =
is for the sole use of the intended recipient(s) and may contain =
confidential and privileged information and must be protected in =
accordance with those provisions. Any unauthorized review, use, =
disclosure or distribution is prohibited. If you are not the intended =
recipient, please contact the sender by reply e-mail and destroy all =
copies of the original message.<BR>
<BR>
(My corporate masters made me say this.)<BR>
</FONT>
</P>

</BODY>
</HTML>
------_=_NextPart_001_01C87B33.677D522B--



From jd@commandprompt.com Sat Mar  1 01:39:14 2008
Received: from localhost (unknown [200.46.204.184])
	by postgresql.org (Postfix) with ESMTP id 383622E0114
	for <pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 21:39:14 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024)
	with ESMTP id 15534-04 for
	<pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 21:39:02 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.5
Received: from lists.commandprompt.com (host-159.commandprompt.net
	[207.173.203.159])
	by postgresql.org (Postfix) with ESMTP id DA96E2E00F1
	for <pgsql-performance@postgresql.org>;
	Fri, 29 Feb 2008 21:39:09 -0400 (AST)
Received: from localhost (or-69-34-217-90.sta.embarqhsd.net [69.34.217.90])
	(authenticated bits=0)
	by lists.commandprompt.com (8.13.8/8.13.8) with ESMTP id m211csbT004041
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
	Fri, 29 Feb 2008 17:38:55 -0800
Date: Fri, 29 Feb 2008 17:39:10 -0800
From: "Joshua D. Drake" <jd@commandprompt.com>
To: "Gregory Williamson" <Gregory.Williamson@digitalglobe.com>
Cc: "Dan Kaplan" <dkaplan@citizenhawk.com>, <pgsql-performance@postgresql.org>
Subject: Re: t1.col like '%t2.col%'
Message-ID: <20080229173910.5645c6e2@commandprompt.com>
In-Reply-To: 
 <8B319E5A30FF4A48BE7EEAAF609DB233015E341B@COMAIL01.digitalglobe.com>
References: <00c001c87975$a907e2e0$1d00a8c0@dan>
	<Pine.LNX.4.64.0802280833040.31180@sn.sai.msu.ru>
	<001401c87b2e$26386000$1d00a8c0@dan>
	<20080229155642.20ac07be@commandprompt.com>
	<8B319E5A30FF4A48BE7EEAAF609DB233015E341B@COMAIL01.digitalglobe.com>
Organization: Command Prompt, Inc.
X-Mailer: Claws Mail 3.0.2 (GTK+ 2.12.0; x86_64-pc-linux-gnu)
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: base64
X-Greylist: Sender succeeded SMTP AUTH, not delayed by milter-greylist-4.0
	(lists.commandprompt.com [207.173.203.159]);
	Fri, 29 Feb 2008 17:38:55 -0800 (PST)
X-Virus-Scanned: Maia Mailguard 1.0.1
X-Spam-Status: No, hits=0.542 tagged_above=0 required=5 tests=AWL=-2.254,
	MIME_BASE64_TEXT=2.796
X-Spam-Level: 
X-Archive-Number: 200802/411
X-Sequence-Number: 28953

LS0tLS1CRUdJTiBQR1AgU0lHTkVEIE1FU1NBR0UtLS0tLQ0KSGFzaDogU0hBMQ0KDQpPbiBGcmks
IDI5IEZlYiAyMDA4IDE3OjMwOjA4IC0wNzAwDQoiR3JlZ29yeSBXaWxsaWFtc29uIiA8R3JlZ29y
eS5XaWxsaWFtc29uQGRpZ2l0YWxnbG9iZS5jb20+IHdyb3RlOg0KDQo+IEpvc2h1YSBEcmFrZSBz
cGFrZSB0aHVzbHk6DQoNCj4gV2UgdXNlZCB0aGUgbm93IGRlcHJlY2F0ZWQgRnVsbCBUZXh0IElu
ZGV4aW5nIChGVEkpIHdpdGggc29tZQ0KPiBoYW5kd2F2aW5nLiBCdXQgdGhhdCB3YXMgaW4gUG9z
dGdyZVNRTCA3LjQgYW5kIEZUSSBpcyBub3QgaW4gdGhlDQo+IGNvbnRyaWIgcGFja2FnZSBmb3Ig
c29tZSB0aW1lIG5vdy4gU2VlDQo+IDxodHRwOi8vcGdmb3VuZHJ5Lm9yZy9wcm9qZWN0cy9zaW1w
bGVmdGkvPiAuLi4gSSBsb29rZWQgYXQgdXNpbmcgaXQNCj4gaW4gOC4xIGJ1dCBteSAiQyIgY2hv
cHMgd2VyZW4ndCB1cCB0byBpdCwgYW5kIGl0IGRlcGVuZGVkIGhlYXZpbHkgb24NCj4gT0lEcyB3
aGljaCB3ZSBkaWRuJ3Qgd2FudCB0byB1c2UuIEFueXdheSwgb3VyIGJ1c2luZXNzIHJlcXVpcmVt
ZW50DQo+IGV2YXBvcmF0ZWQgc28gaXQgZG9lc24ndCBtYXR0ZXIgdG8gdXMgbm93Lg0KPiANCg0K
UmlnaHQgYnV0IHdvdWxkbid0IHRoaXMgYmUgc29sdmVkIHdpdGggdHNlYXJjaDIgYW5kIHBnX3Rn
cm0/DQoNCi0gLS0NClRoZSBQb3N0Z3JlU1FMIENvbXBhbnkgc2luY2UgMTk5NzogaHR0cDovL3d3
dy5jb21tYW5kcHJvbXB0LmNvbS8gDQpQb3N0Z3JlU1FMIENvbW11bml0eSBDb25mZXJlbmNlOiBo
dHRwOi8vd3d3LnBvc3RncmVzcWxjb25mZXJlbmNlLm9yZy8NCkRvbmF0ZSB0byB0aGUgUG9zdGdy
ZVNRTCBQcm9qZWN0OiBodHRwOi8vd3d3LnBvc3RncmVzcWwub3JnL2Fib3V0L2RvbmF0ZQ0KUG9z
dGdyZVNRTCBTUEkgTGlhaXNvbiB8IFNQSSBEaXJlY3RvciB8ICBQb3N0Z3JlU1FMIHBvbGl0aWNh
bCBwdW5kaXQNCg0KLS0tLS1CRUdJTiBQR1AgU0lHTkFUVVJFLS0tLS0NClZlcnNpb246IEdudVBH
IHYxLjQuNiAoR05VL0xpbnV4KQ0KDQppRDhEQlFGSHlMTytBVGIvenFmWlVVUVJBblJsQUowUzBq
cmM0cFNtbkJjb2JFdFp2dURrcGtXeklBQ2NEUDF0DQpDd2svajFDMnBFWFdkQU5zeVpWNWY4RT0N
Cj05R1luDQotLS0tLUVORCBQR1AgU0lHTkFUVVJFLS0tLS0NCg==



From tgl@sss.pgh.pa.us Sat Mar  1 02:10:53 2008
Received: from localhost (unknown [200.46.204.184])
	by postgresql.org (Postfix) with ESMTP id 423F52E01EE
	for <pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 22:10:53 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (mx1.hub.org [200.46.204.184]) (amavisd-maia, port 10024)
	with ESMTP id 76822-03 for
	<pgsql-performance-postgresql.org@postgresql.org>;
	Fri, 29 Feb 2008 22:10:42 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.5
Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130])
	by postgresql.org (Postfix) with ESMTP id 07B892E01EA
	for <pgsql-performance@postgresql.org>;
	Fri, 29 Feb 2008 22:10:49 -0400 (AST)
Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1])
	by sss.pgh.pa.us (8.14.2/8.14.2) with ESMTP id m212Al0X021196;
	Fri, 29 Feb 2008 21:10:47 -0500 (EST)
To: "Dan Kaplan" <dkaplan@citizenhawk.com>
cc: pgsql-performance@postgresql.org
Subject: Re: t1.col like '%t2.col%' 
In-reply-to: <001401c87b2e$26386000$1d00a8c0@dan> 
References: <00c001c87975$a907e2e0$1d00a8c0@dan>
	<Pine.LNX.4.64.0802280833040.31180@sn.sai.msu.ru>
	<001401c87b2e$26386000$1d00a8c0@dan>
Comments: In-reply-to "Dan Kaplan" <dkaplan@citizenhawk.com>
	message dated "Fri, 29 Feb 2008 15:52:31 -0800"
Date: Fri, 29 Feb 2008 21:10:47 -0500
Message-ID: <21195.1204337447@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>
X-Virus-Scanned: Maia Mailguard 1.0.1
X-Archive-Number: 200802/412
X-Sequence-Number: 28954

"Dan Kaplan" <dkaplan@citizenhawk.com> writes:
> I learned a little about pg_trgm here:
> http://www.sai.msu.su/~megera/postgres/gist/pg_trgm/README.pg_trgm

There's also real documentation in the 8.3 release:
http://www.postgresql.org/docs/8.3/static/pgtrgm.html
AFAIK pg_trgm hasn't changed much lately, so you should be able to
rely on that for recent earlier branches.

> But this seems like it's for finding similarities, not substrings.  How can
> I use it to speed up t1.col like '%t2.col%'?

The idea is to use it as a lossy index.  You make a trigram index on
t1.col and then do something like

	... where t1.col % t2.col and t1.col like ('%'||t2.col||'%');

The index gets you the %-matches and then you filter for the exact
matches with LIKE.

The similarity threshold (set_limit()) has to be set low enough that you
don't lose any desired matches, but not so low that you get everything
in the table back.  Not sure how delicate that will be.  It might be
unworkable, but surely it's worth a try.

			regards, tom lane