DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=message-id:date:from:user-agent:mime-version:to:cc:subject:references:in-reply-to:content-type:sender;
	b=tZSPm0JERN5Qcdm4eQh480+noq6or2B3LttkOBRnh2dU+gJmX72gpP8X455Z23rxDF14KlTp+ZRWxWpI8xHrIGD3zsKkPuMoQLwIGv7Cg2wd7TGODFis60RkCjHh1OcBvYmZ3/ytT/EzEIzJMibZFR1gg5HHx8jAdc904Rzyv5c=
Message-ID: <47FE29AF.6010906@starsilk.net>
Date: Thu, 10 Apr 2008 08:52:31 -0600
From: Adam Gundy <adam@starsilk.net>
User-Agent: Thunderbird 2.0.0.12 (X11/20080227)
MIME-Version: 1.0
To: Richard Huxton <dev@archonet.com>
CC: pgsql-performance@postgresql.org
Subject: Re: varchar index joins not working?
References: <6f55f1270804092013n73ee1f81t2c6d72cee49655a3@mail.gmail.com>
	<47FDD3D1.9070208@archonet.com>
In-Reply-To: <47FDD3D1.9070208@archonet.com>
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature";
	micalg=sha1; boundary="------------ms020601020804060102070107"

This is a cryptographically signed message in MIME format.

--------------ms020601020804060102070107
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Richard Huxton wrote:
> Adam Gundy wrote:
>> I'm hitting an unexpected problem with postgres 8.3 - I have some
>> tables which use varchar(32) for their unique IDs which I'm attempting
>> to join using some simple SQL:
>>
>> select *
>> from group_access, groups
>> where group_access.groupid = groups.groupid and
>>          group_access.uid = '7275359408f44591d0717e16890ce335';
>>
>> there's a unique index on group_access.groupid, and a non-unique index
>> on groups.groupid. both are non-null.
> 
> What about group_access.uid - I'd have thought that + groups pkey is 
> probably the sensible combination here.

that is an index on group_access:

"group_access_pkey" PRIMARY KEY, btree (groupid, uid)

adding the (uid, groupid) index helps the small database, it will do an 
index join if forced to, but the full database still refuses to do an 
index join - it does a full index scan followed by a merge.

>>                                                         QUERY PLAN
>> -------------------------------------------------------------------------------------------------------------------------- 
>>
>>  Hash Join  (cost=8.89..41329.88 rows=119940 width=287) (actual
>> time=0.202..935.136 rows=981 loops=1)
> 
> That's because it's expecting 119,940 rows to match (rather than the 
> actual 981 you do get). If you were getting that many results this is 
> probably a sensible plan.

sure. but it's estimate is *wildly* off

>>    Hash Cond: ((groups.groupid)::text = (group_access.groupid)::text)
>>    ->  Seq Scan on groups  (cost=0.00..31696.48 rows=1123348
>> width=177) (actual time=0.011..446.091 rows=1125239 loops=1)
> 
> It's got a good idea of the total number of rows in groups.

yeah.

>>    ->  Hash  (cost=8.51..8.51 rows=30 width=110) (actual
>> time=0.148..0.148 rows=30 loops=1)
>>          ->  Seq Scan on group_access  (cost=0.00..8.51 rows=30
>> width=110) (actual time=0.014..0.126 rows=30 loops=1)
> 
> And also group_access. Oh, the seq-scan doesn't really matter here. It 
> probably *is* faster to read all 30 rows in one burst rather than go to 
> the index and then back to the table.

agreed.

>> it's running an index scan across the entire table (no condition 
>> applied) :-(
>>
>> so, just for the hell of it, I tried making groupid a char(32),
>> despite repeated assertions in this group that there's no performance
>> difference between the two:
> 
> There's no performance difference between the two.

hah. if it makes the join with char (and runs fast), or reads the whole 
table with varchar, then there *is* a performance difference - a big one!

> The char(32) thing isn't important here, what is important is that it's 
> expecting ~300 rows rather than 120,000. It's still wrong, but it's 
> close enough to make sense.

> So - the question is - why is PG expecting so many matches to your join. 

more to the point, why does it get the estimate right (or close) with 
char, but massively wrong with varchar? I've been vacuum analyzing after 
each change..

with the smaller database, and char type, it (for certain joins) still 
wants to do a seqscan because the tables are small enough, but if I 
disable seqscan, it does an index join (usually with a small time 
penalty). if I switch the types back to varchar, re-analyze, re-run, it 
*will not* do an index join!

> How many distinct values do you have in groups.groupid and 
> group_access.group_id?

for the small database (since it shows the same problem):

group_access: 280/268
groups: 2006/139

for the large database:

group_access: same
groups: 1712647/140

the groupid key is an MD5 hash, so it should be uniformly distributed. 
maybe that throws the stats? but, again, char works, varchar doesn't :-(


--------------ms020601020804060102070107
Content-Type: application/x-pkcs7-signature; name="smime.p7s"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="smime.p7s"
Content-Description: S/MIME Cryptographic Signature

MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIJAzCC
AtwwggJFoAMCAQICEDxC40TcaLz5pGwdgYqUP3wwDQYJKoZIhvcNAQEFBQAwYjELMAkGA1UE
BhMCWkExJTAjBgNVBAoTHFRoYXd0ZSBDb25zdWx0aW5nIChQdHkpIEx0ZC4xLDAqBgNVBAMT
I1RoYXd0ZSBQZXJzb25hbCBGcmVlbWFpbCBJc3N1aW5nIENBMB4XDTA4MDEyMjIwNTY1OFoX
DTA5MDEyMTIwNTY1OFowQzEfMB0GA1UEAxMWVGhhd3RlIEZyZWVtYWlsIE1lbWJlcjEgMB4G
CSqGSIb3DQEJARYRYWRhbUBzdGFyc2lsay5uZXQwggEiMA0GCSqGSIb3DQEBAQUAA4IBDwAw
ggEKAoIBAQDKsMgPTN7C3CAyNUoKepQuQnrXiEOVyA27lGOw+o5rnO1yDzKoR4YgJku89zxq
/Pk4Lc4tr61kJgh7+QopOWtvp/iDGwBEkqiHWjcDgZCwzzG0jkmwWE+6p7MTqSzJ+6EYquOV
BAtvPbnIj+QSrGG7NX/FJZubypVWFStWzvjYxHzC+at5LEeN27+6dOIcNq6z9K1rtEF49ynh
MQYuPY3oqtEpDNyk4GboG1fyI4R0+yqT9dAsIUKCQKNeTZsvyB1FW6QzxnrijE0qS6Q0S5xs
Np3txcCnR2iXvWSJvwYqIS7WIzTAxxIulEFo40JldiSGkR09YzLhkDu4/mMQt/ORAgMBAAGj
LjAsMBwGA1UdEQQVMBOBEWFkYW1Ac3RhcnNpbGsubmV0MAwGA1UdEwEB/wQCMAAwDQYJKoZI
hvcNAQEFBQADgYEAJ058YAh/XRW+46OcHqymS2d+fVhHw1DE4i3j778ameUNhW69gYHXuABU
qR2MPNsmldHciqK2BNkh4rTLXUS/Fkk7tgu7LBsYADVEKbekrNIX5kKaJUIq4M2GIKmkapKG
IfwsTbv4xRDl6uxSo/zD4IqQs/TBFZypGaIVqnSrMdowggLcMIICRaADAgECAhA8QuNE3Gi8
+aRsHYGKlD98MA0GCSqGSIb3DQEBBQUAMGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3
dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJl
ZW1haWwgSXNzdWluZyBDQTAeFw0wODAxMjIyMDU2NThaFw0wOTAxMjEyMDU2NThaMEMxHzAd
BgNVBAMTFlRoYXd0ZSBGcmVlbWFpbCBNZW1iZXIxIDAeBgkqhkiG9w0BCQEWEWFkYW1Ac3Rh
cnNpbGsubmV0MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAyrDID0zewtwgMjVK
CnqULkJ614hDlcgNu5RjsPqOa5ztcg8yqEeGICZLvPc8avz5OC3OLa+tZCYIe/kKKTlrb6f4
gxsARJKoh1o3A4GQsM8xtI5JsFhPuqezE6ksyfuhGKrjlQQLbz25yI/kEqxhuzV/xSWbm8qV
VhUrVs742MR8wvmreSxHjdu/unTiHDaus/Sta7RBePcp4TEGLj2N6KrRKQzcpOBm6BtX8iOE
dPsqk/XQLCFCgkCjXk2bL8gdRVukM8Z64oxNKkukNEucbDad7cXAp0dol71kib8GKiEu1iM0
wMcSLpRBaONCZXYkhpEdPWMy4ZA7uP5jELfzkQIDAQABoy4wLDAcBgNVHREEFTATgRFhZGFt
QHN0YXJzaWxrLm5ldDAMBgNVHRMBAf8EAjAAMA0GCSqGSIb3DQEBBQUAA4GBACdOfGAIf10V
vuOjnB6spktnfn1YR8NQxOIt4++/GpnlDYVuvYGB17gAVKkdjDzbJpXR3IqitgTZIeK0y11E
vxZJO7YLuywbGAA1RCm3pKzSF+ZCmiVCKuDNhiCppGqShiH8LE27+MUQ5ersUqP8w+CKkLP0
wRWcqRmiFap0qzHaMIIDPzCCAqigAwIBAgIBDTANBgkqhkiG9w0BAQUFADCB0TELMAkGA1UE
BhMCWkExFTATBgNVBAgTDFdlc3Rlcm4gQ2FwZTESMBAGA1UEBxMJQ2FwZSBUb3duMRowGAYD
VQQKExFUaGF3dGUgQ29uc3VsdGluZzEoMCYGA1UECxMfQ2VydGlmaWNhdGlvbiBTZXJ2aWNl
cyBEaXZpc2lvbjEkMCIGA1UEAxMbVGhhd3RlIFBlcnNvbmFsIEZyZWVtYWlsIENBMSswKQYJ
KoZIhvcNAQkBFhxwZXJzb25hbC1mcmVlbWFpbEB0aGF3dGUuY29tMB4XDTAzMDcxNzAwMDAw
MFoXDTEzMDcxNjIzNTk1OVowYjELMAkGA1UEBhMCWkExJTAjBgNVBAoTHFRoYXd0ZSBDb25z
dWx0aW5nIChQdHkpIEx0ZC4xLDAqBgNVBAMTI1RoYXd0ZSBQZXJzb25hbCBGcmVlbWFpbCBJ
c3N1aW5nIENBMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDEpjxVc1X7TrnKmVoeaMB1
BHCd3+n/ox7svc31W/Iadr1/DDph8r9RzgHU5VAKMNcCY1osiRVwjt3J8CuFWqo/cVbLrzwL
B+fxH5E2JCoTzyvV84J3PQO+K/67GD4Hv0CAAmTXp6a7n2XRxSpUhQ9IBH+nttE8YQRAHmQZ
cmC3+wIDAQABo4GUMIGRMBIGA1UdEwEB/wQIMAYBAf8CAQAwQwYDVR0fBDwwOjA4oDagNIYy
aHR0cDovL2NybC50aGF3dGUuY29tL1RoYXd0ZVBlcnNvbmFsRnJlZW1haWxDQS5jcmwwCwYD
VR0PBAQDAgEGMCkGA1UdEQQiMCCkHjAcMRowGAYDVQQDExFQcml2YXRlTGFiZWwyLTEzODAN
BgkqhkiG9w0BAQUFAAOBgQBIjNFQg+oLLswNo2asZw9/r6y+whehQ5aUnX9MIbj4Nh+qLZ82
L8D0HFAgk3A8/a3hYWLD2ToZfoSxmRsAxRoLgnSeJVCUYsfbJ3FXJY3dqZw5jowgT2Vfldr3
94fWxghOrvbqNOUQGls1TXfjViF4gtwhGTXeJLHTHUb/XV9lTzGCA2QwggNgAgEBMHYwYjEL
MAkGA1UEBhMCWkExJTAjBgNVBAoTHFRoYXd0ZSBDb25zdWx0aW5nIChQdHkpIEx0ZC4xLDAq
BgNVBAMTI1RoYXd0ZSBQZXJzb25hbCBGcmVlbWFpbCBJc3N1aW5nIENBAhA8QuNE3Gi8+aRs
HYGKlD98MAkGBSsOAwIaBQCgggHDMBgGCSqGSIb3DQEJAzELBgkqhkiG9w0BBwEwHAYJKoZI
hvcNAQkFMQ8XDTA4MDQxMDE0NTIzMVowIwYJKoZIhvcNAQkEMRYEFIKeTCtWOpybNsi9vmP2
8FxCd8jAMFIGCSqGSIb3DQEJDzFFMEMwCgYIKoZIhvcNAwcwDgYIKoZIhvcNAwICAgCAMA0G
CCqGSIb3DQMCAgFAMAcGBSsOAwIHMA0GCCqGSIb3DQMCAgEoMIGFBgkrBgEEAYI3EAQxeDB2
MGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQu
MSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwgSXNzdWluZyBDQQIQPELjRNxo
vPmkbB2BipQ/fDCBhwYLKoZIhvcNAQkQAgsxeKB2MGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQK
ExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29u
YWwgRnJlZW1haWwgSXNzdWluZyBDQQIQPELjRNxovPmkbB2BipQ/fDANBgkqhkiG9w0BAQEF
AASCAQCwi84wMCEDNCoLIl3TshGEnAyscFGRSj2XK+eGFx/RZKudNgZKka+65ZcFMWa41aLo
trvXs5+fI0sVLA8qvE37scSUq1F/HzrxurXZbT33IdQAA1ZVV98bsxXRyjaI0e+HpY3A8X9/
9qzll15gt53G9IMgEQUVn8V4zziCUi6SQzKcAYxjPynWv6PIPF1Oicfoh6eOtBQnXoM+gcO5
Tkdr49nG4kl6dhBI85hi7YAqcGbiEBvqD7FOMNsPQ2ihZW2+/Ebv4yCu1xzyQkYqGkSb767p
yfp3i9hqC6KzWinLeZGQP6ZXydaBkj3rpL8Y+m7GNuyqVtW7T/VaUa7LFFI8AAAAAAAA
--------------ms020601020804060102070107--