Received: from localhost (maia-5.hub.org [200.46.204.182]) by postgresql.org (Postfix) with ESMTP id D330F9FB962 for ; Tue, 13 Feb 2007 13:09:48 -0400 (AST) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.182]) (amavisd-new, port 10024) with ESMTP id 36766-09 for ; Tue, 13 Feb 2007 13:09:26 -0400 (AST) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.4 Received: from wx-out-0506.google.com (wx-out-0506.google.com [66.249.82.234]) by postgresql.org (Postfix) with ESMTP id DA72A9FB32A for ; Tue, 13 Feb 2007 13:09:19 -0400 (AST) Received: by wx-out-0506.google.com with SMTP id i28so2193866wxd for ; Tue, 13 Feb 2007 09:09:19 -0800 (PST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:mime-version:content-type; b=pKpYv4lu/2ifvR32hhC/tudihxlsNLt80M3ThH+IOU6k40X21yCDJqEHO1P08ytQKscl6+Tdk0HY2EhAYjWK95d37hpckYu39qwuxasUYK2uE9b3R2fnqom3A0Opjbvn+4w7Lmvhe40dnmr16+Od8YlkRMHsgMOCglcGDrvCs0U= Received: by 10.90.101.19 with SMTP id y19mr19468006agb.1171386559504; Tue, 13 Feb 2007 09:09:19 -0800 (PST) Received: by 10.90.113.7 with HTTP; Tue, 13 Feb 2007 09:09:19 -0800 (PST) Message-ID: <1d4e0c10702130909g3be0a10fpf2594574c84866c9@mail.gmail.com> Date: Tue, 13 Feb 2007 18:09:19 +0100 From: "Guillaume Smet" To: "Pg Performance list" Subject: Proximity query with GIST and row estimation MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_114202_2491129.1171386559220" X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0 tagged_above=0 required=5 tests=BAYES_50, SPF_PASS X-Spam-Level: X-Archive-Number: 200702/128 X-Sequence-Number: 23182 ------=_Part_114202_2491129.1171386559220 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline Hi all, Following the work on Mark Stosberg on this list (thanks Mark!), I optimized our slow proximity queries by using cube, earthdistance (shipped with contrib) and a gist index. The result is globally very interesting apart for a specific query and we'd like to be able to fix it too to be more consistent (it's currently faster with a basic distance calculation based on acos, cos and so on but it's slow anyway). The problem is that we have sometimes very few places near a given location (small city) and sometimes a lot of them (in Paris, Bruxelles and so on - it's the case we have here). The gist index I created doesn't estimate the number of rows in the area very well. Table: lieu (100k rows) with wgslat and wgslon as numeric Table: lieugelieu (200k rows, 1k with codegelieu = 'PKG') Index: "idx_lieu_earth" gist (ll_to_earth(wgslat::double precision, wgslon::double precision)) The simplified query is: SELECT DISTINCT l.numlieu, l.nomlieu, ROUND (earth_distance(ll_to_earth(48.85957600, 2.34860800), ll_to_earth(l.wgslat, l.wgslon))) as dist FROM lieu l, lieugelieu lgl WHERE lgl.codegelieu = 'PKG' AND earth_box(ll_to_earth(48.85957600, 2.34860800), 1750) @ ll_to_earth(l.wgslat, l.wgslon) AND lgl.numlieu = l.numlieu ORDER BY dist ASC LIMIT 2; It's used to find the nearest car parks from a given location. The plan is attached plan_earthdistance_nestedloop.txt. It uses a nested loop because the row estimate is pretty bad: (cost=0.00..3.38 rows=106 width=0) (actual time=30.229..30.229 rows=5864 loops=1). If I disable the nested loop, the plan is different and faster (see plan_earthdistance_hash.txt attached). Is there any way to improve this estimation? I tried to set the statistics of wgslat and wgslon higher but it doesn't change anything (I don't know if the operator is designed to use the statistics). Any other idea to optimize this query is very welcome too. -- Guillaume ------=_Part_114202_2491129.1171386559220 Content-Type: text/plain; name=plan_earthdistance_nestedloop.txt; charset=ANSI_X3.4-1968 Content-Transfer-Encoding: base64 X-Attachment-Id: f_ey4l1k7o Content-Disposition: attachment; filename="plan_earthdistance_nestedloop.txt" ZGI9IyBleHBsYWluIGFuYWx5emUgU0VMRUNUIERJU1RJTkNUIGwubnVtbGlldSwgbC5ub21saWV1 LCBST1VORCAoZWFydGhfZGlzdGFuY2UobGxfdG9fZWFydGgoNDguODU5NTc2MDAsIDIuMzQ4NjA4 MDApLCBsbF90b19lYXJ0aChsLndnc2xhdCwgbC53Z3Nsb24pKSkgYXMgZGlzdApkYi0jIEZST00g bGlldSBsLCBsaWV1Z2VsaWV1IGxnbApkYi0jIFdIRVJFIGxnbC5jb2RlZ2VsaWV1ID0gJ1BLRycg QU5EIGVhcnRoX2JveChsbF90b19lYXJ0aCg0OC44NTk1NzYwMCwgMi4zNDg2MDgwMCksIDE3NTAp IEAgbGxfdG9fZWFydGgobC53Z3NsYXQsIGwud2dzbG9uKSBBTkQgbGdsLm51bWxpZXUgPSBsLm51 bWxpZXUgT1JERVIgQlkgZGlzdCBBU0MgTElNSVQgMjsKICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBRVUVSWSBQTEFOICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCi0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLQogTGltaXQgIChjb3N0PTYyNi44NC4uNjI2Ljg1IHJvd3M9MSB3aWR0aD01MSkgKGFj dHVhbCB0aW1lPTQ0OS4yODcuLjQ0OS4yOTggcm93cz0yIGxvb3BzPTEpCiAgIC0+ICBVbmlxdWUg IChjb3N0PTYyNi44NC4uNjI2Ljg1IHJvd3M9MSB3aWR0aD01MSkgKGFjdHVhbCB0aW1lPTQ0OS4y ODMuLjQ0OS4yOTAgcm93cz0yIGxvb3BzPTEpCiAgICAgICAgIC0+ICBTb3J0ICAoY29zdD02MjYu ODQuLjYyNi44NCByb3dzPTEgd2lkdGg9NTEpIChhY3R1YWwgdGltZT00NDkuMjc4Li40NDkuMjc5 IHJvd3M9MiBsb29wcz0xKQogICAgICAgICAgICAgICBTb3J0IEtleTogcm91bmQoc2VjX3RvX2dj KGN1YmVfZGlzdGFuY2UoJyg0MTkyNzE0Ljg2MTExNjU1LCAxNzE5NTkuNjU2NDgzNzU1LCA0ODAz Mzk0LjUyOTUxMTIzKSc6OmN1YmUsIChsbF90b19lYXJ0aCgobC53Z3NsYXQpOjpkb3VibGUgcHJl Y2lzaW9uLCAobC53Z3Nsb24pOjpkb3VibGUgcHJlY2lzaW9uKSk6OmN1YmUpKSksIGwubnVtbGll dSwgbC5ub21saWV1CiAgICAgICAgICAgICAgIC0+ICBOZXN0ZWQgTG9vcCAgKGNvc3Q9My4zOC4u NjI2LjgzIHJvd3M9MSB3aWR0aD01MSkgKGFjdHVhbCB0aW1lPTI1OC44NzcuLjQ0OC42NTEgcm93 cz03OCBsb29wcz0xKQogICAgICAgICAgICAgICAgICAgICAtPiAgQml0bWFwIEhlYXAgU2NhbiBv biBsaWV1IGwgIChjb3N0PTMuMzguLjIwMS4zNCByb3dzPTEwNiB3aWR0aD01MSkgKGFjdHVhbCB0 aW1lPTMyLjk4OC4uNjAuMTk3IHJvd3M9NTc4NiBsb29wcz0xKQogICAgICAgICAgICAgICAgICAg ICAgICAgICBSZWNoZWNrIENvbmQ6ICgnKDQxOTA5NjQuODYxMTIyMDQsIDE3MDIwOS42NTY0ODky NDUsIDQ4MDE2NDQuNTI5NTE2NzIpLCg0MTk0NDY0Ljg2MTExMTA2LCAxNzM3MDkuNjU2NDc4MjY2 LCA0ODA1MTQ0LjUyOTUwNTc0KSc6OmN1YmUgQCAobGxfdG9fZWFydGgoKHdnc2xhdCk6OmRvdWJs ZSBwcmVjaXNpb24sICh3Z3Nsb24pOjpkb3VibGUgcHJlY2lzaW9uKSk6OmN1YmUpCiAgICAgICAg ICAgICAgICAgICAgICAgICAgIC0+ICBCaXRtYXAgSW5kZXggU2NhbiBvbiBpZHhfbGlldV9lYXJ0 aCAgKGNvc3Q9MC4wMC4uMy4zOCByb3dzPTEwNiB3aWR0aD0wKSAoYWN0dWFsIHRpbWU9MzAuMjI5 Li4zMC4yMjkgcm93cz01ODY0IGxvb3BzPTEpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgIEluZGV4IENvbmQ6ICgnKDQxOTA5NjQuODYxMTIyMDQsIDE3MDIwOS42NTY0ODkyNDUsIDQ4 MDE2NDQuNTI5NTE2NzIpLCg0MTk0NDY0Ljg2MTExMTA2LCAxNzM3MDkuNjU2NDc4MjY2LCA0ODA1 MTQ0LjUyOTUwNTc0KSc6OmN1YmUgQCAobGxfdG9fZWFydGgoKHdnc2xhdCk6OmRvdWJsZSBwcmVj aXNpb24sICh3Z3Nsb24pOjpkb3VibGUgcHJlY2lzaW9uKSk6OmN1YmUpCiAgICAgICAgICAgICAg ICAgICAgIC0+ICBJbmRleCBTY2FuIHVzaW5nIGlkeF9saWV1Z2VsaWV1X2NvZGVnZWxpZXVfbnVt bGlldV9wcmluY2lwYWwgb24gbGlldWdlbGlldSBsZ2wgIChjb3N0PTAuMDAuLjQuMDAgcm93cz0x IHdpZHRoPTQpIChhY3R1YWwgdGltZT0wLjA1Mi4uMC4wNTIgcm93cz0wIGxvb3BzPTU3ODYpCiAg ICAgICAgICAgICAgICAgICAgICAgICAgIEluZGV4IENvbmQ6ICgoKGxnbC5jb2RlZ2VsaWV1KTo6 dGV4dCA9ICdQS0cnOjp0ZXh0KSBBTkQgKGxnbC5udW1saWV1ID0gIm91dGVyIi5udW1saWV1KSkK IFRvdGFsIHJ1bnRpbWU6IDQ0OS42MDcgbXMKKDEyIHJvd3MpCg== ------=_Part_114202_2491129.1171386559220 Content-Type: text/plain; name=plan_earthdistance_hash.txt; charset=ANSI_X3.4-1968 Content-Transfer-Encoding: base64 X-Attachment-Id: f_ey4l2pnp Content-Disposition: attachment; filename="plan_earthdistance_hash.txt" ZGI9IyBleHBsYWluIGFuYWx5emUgU0VMRUNUIERJU1RJTkNUIGwubnVtbGlldSwgbC5ub21saWV1 LCBST1VORCAoZWFydGhfZGlzdGFuY2UobGxfdG9fZWFydGgoNDguODU5NTc2MDAsIDIuMzQ4NjA4 MDApLCBsbF90b19lYXJ0aChsLndnc2xhdCwgbC53Z3Nsb24pKSkgYXMgZGlzdApkYi0jIEZST00g bGlldSBsLCBsaWV1Z2VsaWV1IGxnbApkYi0jIFdIRVJFIGxnbC5jb2RlZ2VsaWV1ID0gJ1BLRycg QU5EIGVhcnRoX2JveChsbF90b19lYXJ0aCg0OC44NTk1NzYwMCwgMi4zNDg2MDgwMCksIDE3NTAp IEAgbGxfdG9fZWFydGgobC53Z3NsYXQsIGwud2dzbG9uKSBBTkQgbGdsLm51bWxpZXUgPSBsLm51 bWxpZXUgT1JERVIgQlkgZGlzdCBBU0MgTElNSVQgMjsKICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBRVUVSWSBQTEFOICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCi0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLQogTGltaXQgIChjb3N0PTc4Ny4wNy4uNzg3LjA5IHJvd3M9MSB3 aWR0aD01MSkgKGFjdHVhbCB0aW1lPTE2OC42MjMuLjE2OC42MzUgcm93cz0yIGxvb3BzPTEpCiAg IC0+ICBVbmlxdWUgIChjb3N0PTc4Ny4wNy4uNzg3LjA5IHJvd3M9MSB3aWR0aD01MSkgKGFjdHVh bCB0aW1lPTE2OC42MTkuLjE2OC42Mjcgcm93cz0yIGxvb3BzPTEpCiAgICAgICAgIC0+ICBTb3J0 ICAoY29zdD03ODcuMDcuLjc4Ny4wOCByb3dzPTEgd2lkdGg9NTEpIChhY3R1YWwgdGltZT0xNjgu NjE0Li4xNjguNjE1IHJvd3M9MiBsb29wcz0xKQogICAgICAgICAgICAgICBTb3J0IEtleTogcm91 bmQoc2VjX3RvX2djKGN1YmVfZGlzdGFuY2UoJyg0MTkyNzE0Ljg2MTExNjU1LCAxNzE5NTkuNjU2 NDgzNzU1LCA0ODAzMzk0LjUyOTUxMTIzKSc6OmN1YmUsIChsbF90b19lYXJ0aCgobC53Z3NsYXQp Ojpkb3VibGUgcHJlY2lzaW9uLCAobC53Z3Nsb24pOjpkb3VibGUgcHJlY2lzaW9uKSk6OmN1YmUp KSksIGwubnVtbGlldSwgbC5ub21saWV1CiAgICAgICAgICAgICAgIC0+ICBIYXNoIEpvaW4gIChj b3N0PTIwNi4xMy4uNzg3LjA2IHJvd3M9MSB3aWR0aD01MSkgKGFjdHVhbCB0aW1lPTEwMi4wMDUu LjE2Ny45OTIgcm93cz03OCBsb29wcz0xKQogICAgICAgICAgICAgICAgICAgICBIYXNoIENvbmQ6 ICgib3V0ZXIiLm51bWxpZXUgPSAiaW5uZXIiLm51bWxpZXUpCiAgICAgICAgICAgICAgICAgICAg IC0+ICBCaXRtYXAgSGVhcCBTY2FuIG9uIGxpZXVnZWxpZXUgbGdsICAoY29zdD00LjUyLi41ODMu MjYgcm93cz00MzUgd2lkdGg9NCkgKGFjdHVhbCB0aW1lPTEuMTM3Li4zLjkwOSByb3dzPTEwOTUg bG9vcHM9MSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgUmVjaGVjayBDb25kOiAoKGNvZGVn ZWxpZXUpOjp0ZXh0ID0gJ1BLRyc6OnRleHQpCiAgICAgICAgICAgICAgICAgICAgICAgICAgIC0+ ICBCaXRtYXAgSW5kZXggU2NhbiBvbiBpZHhfbGlldWdlbGlldV9jb2RlZ2VsaWV1X251bWxpZXVf cHJpbmNpcGFsICAoY29zdD0wLjAwLi40LjUyIHJvd3M9NDM1IHdpZHRoPTApIChhY3R1YWwgdGlt ZT0xLjAzMC4uMS4wMzAgcm93cz0xMDk1IGxvb3BzPTEpCiAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgIEluZGV4IENvbmQ6ICgoY29kZWdlbGlldSk6OnRleHQgPSAnUEtHJzo6dGV4dCkK ICAgICAgICAgICAgICAgICAgICAgLT4gIEhhc2ggIChjb3N0PTIwMS4zNC4uMjAxLjM0IHJvd3M9 MTA2IHdpZHRoPTUxKSAoYWN0dWFsIHRpbWU9OTcuODA3Li45Ny44MDcgcm93cz01Nzg2IGxvb3Bz PTEpCiAgICAgICAgICAgICAgICAgICAgICAgICAgIC0+ICBCaXRtYXAgSGVhcCBTY2FuIG9uIGxp ZXUgbCAgKGNvc3Q9My4zOC4uMjAxLjM0IHJvd3M9MTA2IHdpZHRoPTUxKSAoYWN0dWFsIHRpbWU9 MzIuOTIxLi43Ni43MzYgcm93cz01Nzg2IGxvb3BzPTEpCiAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgIFJlY2hlY2sgQ29uZDogKCcoNDE5MDk2NC44NjExMjIwNCwgMTcwMjA5LjY1NjQ4 OTI0NSwgNDgwMTY0NC41Mjk1MTY3MiksKDQxOTQ0NjQuODYxMTExMDYsIDE3MzcwOS42NTY0Nzgy NjYsIDQ4MDUxNDQuNTI5NTA1NzQpJzo6Y3ViZSBAIChsbF90b19lYXJ0aCgod2dzbGF0KTo6ZG91 YmxlIHByZWNpc2lvbiwgKHdnc2xvbik6OmRvdWJsZSBwcmVjaXNpb24pKTo6Y3ViZSkKICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgLT4gIEJpdG1hcCBJbmRleCBTY2FuIG9uIGlkeF9s aWV1X2VhcnRoICAoY29zdD0wLjAwLi4zLjM4IHJvd3M9MTA2IHdpZHRoPTApIChhY3R1YWwgdGlt ZT0zMC4xNDQuLjMwLjE0NCByb3dzPTU4NjQgbG9vcHM9MSkKICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgSW5kZXggQ29uZDogKCcoNDE5MDk2NC44NjExMjIwNCwgMTcwMjA5 LjY1NjQ4OTI0NSwgNDgwMTY0NC41Mjk1MTY3MiksKDQxOTQ0NjQuODYxMTExMDYsIDE3MzcwOS42 NTY0NzgyNjYsIDQ4MDUxNDQuNTI5NTA1NzQpJzo6Y3ViZSBAIChsbF90b19lYXJ0aCgod2dzbGF0 KTo6ZG91YmxlIHByZWNpc2lvbiwgKHdnc2xvbik6OmRvdWJsZSBwcmVjaXNpb24pKTo6Y3ViZSkK IFRvdGFsIHJ1bnRpbWU6IDE2OS4xNDAgbXMKKDE2IHJvd3MpCg== ------=_Part_114202_2491129.1171386559220--