Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TsGcB-0000Al-81 for pgsql-hackers@arkaria.postgresql.org; Mon, 07 Jan 2013 17:35:59 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.72) (envelope-from ) id 1TsGcA-0002fE-1o for pgsql-hackers@arkaria.postgresql.org; Mon, 07 Jan 2013 17:35:58 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TsGc9-0002f9-5v for pgsql-hackers@postgresql.org; Mon, 07 Jan 2013 17:35:57 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by magus.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TsGc8-0001E8-07 for pgsql-hackers@postgresql.org; Mon, 07 Jan 2013 17:35:56 +0000 Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.14.5/8.14.5) with ESMTP id r07HZp0W012792; Mon, 7 Jan 2013 12:35:51 -0500 (EST) From: Tom Lane To: Simon Riggs cc: Jeff Janes , pgsql-hackers Subject: Re: [PERFORM] Slow query: bitmap scan troubles In-reply-to: <8539.1357513385@sss.pgh.pa.us> References: <092a01cdd230$ff6143c0$fe23cb40$@foo.me.uk> <097601cdd249$ae338530$0a9a8f90$@foo.me.uk> <9022.1354730710@sss.pgh.pa.us> <28944.1357424296@sss.pgh.pa.us> <18164.1357498720@sss.pgh.pa.us> <8539.1357513385@sss.pgh.pa.us> Comments: In-reply-to Tom Lane message dated "Sun, 06 Jan 2013 18:03:05 -0500" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0" Content-ID: <12780.1357580129.0@sss.pgh.pa.us> Date: Mon, 07 Jan 2013 12:35:51 -0500 Message-ID: <12791.1357580151@sss.pgh.pa.us> X-Pg-Spam-Score: -1.1 (-) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-hackers Precedence: bulk Sender: pgsql-hackers-owner@postgresql.org ------- =_aaaaaaaaaa0 Content-Type: text/plain; charset="us-ascii" Content-ID: <12780.1357580129.1@sss.pgh.pa.us> I wrote: > Now, if we consider only CPU costs of index descent, we expect > about log2(P) comparisons to be needed on each of the H upper pages > to be descended through, that is we have total descent cost > cpu_index_tuple_cost * H * log2(P) > If we ignore the ceil() step as being a second-order correction, this > can be simplified to > cpu_index_tuple_cost * H * log2(N)/(H+1) I thought some more about this and concluded that the above reasoning is incorrect, because it ignores the fact that initial positioning on the index leaf page requires another log2(P) comparisons (to locate the first matching tuple if any). If you include those comparisons then the H/(H+1) factor drops out and you are left with just "cost * log2(N)", independently of the tree height. But all is not lost for including some representation of the physical index size into this calculation, because it seems plausible to consider that there is some per-page cost for descending through the upper pages. It's not nearly as much as random_page_cost, if the pages are cached, but we don't have to suppose it's zero. So that reasoning leads to a formula like cost-per-tuple * log2(N) + cost-per-page * (H+1) which is better than the above proposal anyway because we can now twiddle the two cost factors separately rather than being tied to a fixed idea of how much a larger H hurts. As for the specific costs to use, I'm now thinking that the cost-per-tuple should be just cpu_operator_cost (0.0025) not cpu_index_tuple_cost (0.005). The latter is meant to model costs such as reporting a TID back out of the index AM to the executor, which is not what we're doing at an upper index entry. I also propose setting the per-page cost to some multiple of cpu_operator_cost, since it's meant to represent a CPU cost not an I/O cost. There is already a charge of 100 times cpu_operator_cost in genericcostestimate to model "general costs of starting an indexscan". I suggest that we should consider half of that to be actual fixed overhead and half of it to be per-page cost for the first page, then add another 50 times cpu_operator_cost for each page descended through. That gives a formula of cpu_operator_cost * log2(N) + cpu_operator_cost * 50 * (H+2) This would lead to the behavior depicted in the attached plot, wherein I've modified the comparison lines (historical, 9.2, and HEAD behaviors) to include the existing 100 * cpu_operator_cost startup cost charge in addition to the fudge factor we've been discussing so far. The new proposed curve is a bit above the historical curve for indexes with 250-5000 tuples, but the value is still quite small there, so I'm not too worried about that. The people who've been complaining about 9.2's behavior have indexes much larger than that. Thoughts? regards, tom lane ------- =_aaaaaaaaaa0 Content-Type: image/png Content-ID: <12780.1357580129.2@sss.pgh.pa.us> Content-Description: new_costs.png Content-Transfer-Encoding: base64 iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgBAMAAADH/8HXAAAAA3NCSVQCAgLM TMuiAAAAMFBMVEX//////1X/Vf//VVVV//9V/1VVVf9VVVWqqqqqqgCqAKqq AAAAqqoAqgAAAKoAAABJ/07MAAAALnRFWHRTb2Z0d2FyZQBnbnVwbG90IFVu aXggdmVyc2lvbiAzLjcgcGF0Y2hsZXZlbCAwNKWcDQAAD7RJREFUeJztnU2P 6jCyhiOFZstfQeLOrC0Ns56WRr33it/P5t4tN7bzHdsxlO2Uzfuc05gP44Sn q8rB5HCaBgAAAAAAAAAO59L9fR29EyXTyXt2f8CndBH4vEDg5yiBTyXw8jqI /1jv/d/5jf/LsiMePBF2UVn8NFcGnuseQ/N09XmOzWyYy6KLcxixGUb1+Z0/ 8bwd9OnZ49kw0wPWvfEOY9/jNZehBh4l8LQdpuvzs3jlcjsoG4FddJpZ+OLu 49iAlbeHOVm7/Cz6yDibshNpGGYCf+d9ztYuEGgQth4/TZ0CUyBsd/4ubjkE ZqQIge1tbP5xVU17665em+Ymx87t7LJpr9Mo+gnN7I6O23XoPRus+7maJ0yX qmfr3ckiBI6v7Nr+trpRt67da5PN1Gds2rmv1jy9HW/pS9PemsVg47OHnlfT cyl/BWOB0xxyNRHVNe3vTV+5mbhqpW5u+nX2F/oFX03sXKegGmNOX96mW+Ng qlPf9E/ofXpDMEjgMUsKM4HXa9/8tK1J6M7BTUegDqGbEXdtJodKpxJ/7SuA HkFna9e0Y8LPBlPSjbvWDKHuvF17gd1Tl5jfiO+dyMjhEXgzL79r/nttexX6 pZ/7HDQ52f+YcqYFjrG0isDrKHA2WB9612YYYsh8egSGvuS4iPGaelX6Ff7D aDF2uoAbBPYvf3rNUwRuK5t5ensdBA6DTdWyncVxU24NFOM1XedU86tSasis 7u8/r0MNNFJGT7exBvapuJmFW1MmZ4NNATsEosn5YmdhsbnnZ32H1Jet6zWu vaWAr0DLG7nf9R3SNDeHp/74MSlVCDySkgRuMvj4N3KcBYrNPZsAjC5wvoWf 4Te2+b0tKEjg9oWkFvi7vXdDQQK3ryO+wL+m+fttflTzY2LwZycE2b6V25RA y8uQsTf61/xqZar5M1d++y3//K0wv0++b+U2Ai2JJGNv9Lcz99eZ+9Melbjh xwlbgWJ9Ry6BQ/OnN6kisMwaKFa3LWEQ/yimM2dq4K+qgc1PMwSim2IEWsKA w2EgW4HrEmgLAwj0sBZoq0Myw37sAoFEuAoUy5vWQi4pG1BP7mvAeXmv4TE+ 4K8UBQuklUC5M9B56iNtjw8wFRiSwUSBDx1l54c8Px5d05zPsun+Ng+pbqnR 9d/zzobKEBg/gzt5UplRg+hGnqVuz33s9eKk7AV2mpf0m/9agbKX9BgFmntV c36MAocfJ0wXE8TypvXNlCRtoReonZ0XAs/jY9JEoG9DXBcTxOKWNQCJh9FK Uhdoj4e+rmpgY+JR10D9mJZ5LnMWFotbKQTGgqfAVQm0ZjAEelgKtC+HyAz7 EQAEEuEpUCxu2Rc0JX0z209OxdjcxfC4/VTtgQIE2gMwaQkUnbXTXKcblgJD MpgqUNy7KOsbMTSn7m/3czfhdxovPBQg0J7BVIF3HWaqUZL6Rt0nTkMKq90Q ot+d032FMOPwF+j4SEIStyGMwK7p1OimFzg0zeLHCUuBYn4jvcCmmUegbvSd aj9UBArfOPwFOj5UlORtCF38+qavgfex9HVhqa+fSpyFxey6IwAjT8Jit4cL jqsxISWQi0CWqzELgYkyOBrcBbpOC5AZ9iMIjgLF7DoEfoCYXXdkMJO1rIa9 QFcAQqCHkBIIgR7mAl2n5skM+xEGb4HOU/Nkhv0Ig6FAMV2FwE8Q01VXBvMp gQwFhmQwBHqAQCIzgc7T42WG/QiEn0AxXYXATxDjtRIyGAKpsFtQDSmBjATy W1AtbA7hl8KTQPc/sZIZ9iMUdgLFeA0CP0KM10oogRBIhq/AMjKYncBpDnH/ M2eZYT+CgUAibAW6M5hVCWQnUAxXIPAzxHDFncEQ6EP0reebHiDQQ0AJ5DWH sBXo+a4WmWE/woFAIkwFFlMCuQkUfesJQAj0IfoWAj9EmMb3dVUyw268AS+B ASWwSIHZPlQaBPq+cE5m2I9wmH2o1Av0fuGczLAfb8BLoDCNTyCzOYSnQF8G Q6CHkBIIgR4KLIEQSIWVQGEa77fmyvS78RalCeRWAjkK9GYwBHoosQRyFFhU CWQlUJgGAj9F6MuySiAEUmEkMKQEQqCHIucQfgL9//mEzLAf78FIoNCXhZVA fgILK4GMBJY5h7ATWFoJhEAqfAQKfenNYAj0IfRlaSWQm0B/BkOgh0JLIJ9T O4zA4kogn1M7hL4sTiCfFBb6srg5hJnA8uYQNgJD5hAI9FDoHAKBZLgIFOqi wAyGQCpMBIZkMAR6KLYEshLoz2AI9CHUBQR+jlAXJZZACKTCQ2C5JRACqfAQ KNSFP4Mh0IdQF0WWQEYCdzIYAj2ElEAI9KAFllkCIZAKC4GiKTaDIZAKG4E7 GQyBHkougWwE7mQwBPqAQCKiKbcEQiAVJgL3MhgCPRRdArkI3MlgCPQBgURE ySUQAqnwELiXwaULTHqWftklkMFZ+qf9DGYskEEKCwikIYougRBI5XCBZc8h PASWXAIhkMrhAkXR70N4CCx5DjlcYOlzCAeBRZdACKRytEBR+BzCQWDRc8jR AoufQxgILLsEQiCVgwWK0ksgBFI5VmD5GQyBVA4XuJfBEOhDFF8CDxe4m8EQ 6KGCEni4wNJLIARSOVRgBSUQAqkcKbCGDIZAKkcKDMjg4gRebEYPFMi+BG4F WmylE7ibwaUJvLxsp6wmElhFCdxGoIVkAisogUcKrKIEHjkLQyCNkBJYnsCM hzF1zCEbgZdshzF1zCEHCqyjBB4qsIYSuCl5T04CZZINx+WwWbiSEgiBVNYC s70XPtVRAo9bjalkDjlQ4H4GQ6CHWkrgYTUwoASWKdAGBHo4SmAtJXD7TiRT CtcqMNskEiBQJthsfA4SWE0JhEAqBx3GVFMCj5qFIZBGSAZDoId6SuBBAgOW YioRqB9OILCaErgj8JJGYMhSTB0CE0VgRSUwTKD1pDcC1ZTAfTNpIrCiErg9 wfK1fRgCPfiXs8zXz8YWWFMJPGQxAQKJ1JTBh6zGVC3QRmSBFa0kNGwFyrib TMgmhS19In8VfEAGlyNwXfJynGBZVQk84AzVukogU4Ey6haTkv8wpqoSeMQs XFcJPEJgVSVwbzXG3Btzg5WVwPwnF53qKoH5FxMqK4EHCKyrBIYdxkR8K1db Bmf/X71qE5j9MKa2DM5+GFO5wOSHMdVlcO5ZGAKJVJfBuVdj6hdoI57A+jIY Aqmsa2Daw5j6Mngt0PadExDoY3UgbZUVTWCFGRwWgbEWEyoReJtzXT6WtgYW ksHtzc+ic9ZZmKnAtbDr/lMmcgrkmsEt5ckQ2DRvRdyanAKZZjAEUilFINcM LkfgfgCWN4fkFMg1g4sR+O/9LhDogW0JLEYg0xJIm0MyCuSawRBIJYPAGMtZ bDOYJjDfuTEBBzElziH5UphtBhciMCSDIdAD3xJYiEC2GUychHMJ5JXBny/g b2EkUNI3syDwUyEimQQmzeAMmtxkEij2u4QItH/gSN05EnkExspg4oyZgjwC Y2Xw1woU+12CBBJnzBRkERhtDv5WgdHm4G8VKPa7QKCHaBnMcA7JsqAaLYMZ CsyyoCr2uxQrMEcKx3sf/KUC470PZjiH5BAo9rtAoIeIK1lfKnC/S+hK1ncK jFcCOc4h6QVGzOAvFRjQR4YN9Z0CIy7mf6XAmJ8mcZxDkgsMCEAI9BD18+Cv FBjQR4YO9o0CY34ezHIOSSww6gkJ3ygw2hTSHv4BuoukAj+bQmwnH7Asf5qk AoMCkNeZGm+TUuA2ALeh9c/CfG1I+aHSKSC45GdDsyHZh0pKl9jvxuE7Jmik EniNfBDNloQCxX6v8gMwocDvCMBUAttvCcB0Ar8kANMJFPudagjAZAK/JQCT CRT7faoIwFQCvyYAUwn8136XOgIwkcBTwPKTfHtUlqQRKPYFPt4elCdJBJ72 P/+pJIHTCDyJfYHyzTHZkkKg2P8EspoATCHw3uwKPMv3hmRMfIH6EHBHoHxr RNZEF9gVwGZPYD0JnECgUBf+z8ArSuD4Au/60iuwKn+xBRp/XoF1+Yss8N5/ EuwTKINHK4KoAgd/PoG1vIUbiCnw9DdccwusaQLWRBR4mk6FcQqsrAA2MU/t mPlzHgbW5y/eqR1zfy6B9fmLl8LmDciAXeBDBgxUGpEELv3ZBdY2/xriCFz5 swqs018cgXexusMisFJ/MQSe7pu7NgLPtfqLIHATftvDwEeV04eBKvC+Db+1 wEe10acgCbxb9a0EVq2PInBjr7WcTH6uO/yajwWO9nz/GOZcc+0b+ETg6X7f /1cxX2GveUPgYOx/7pZpd8lDIal7VgghAvt/6dcF3n3HnlZXe9VbEiLQmPOo Oz8eX6jO8HYNHGXNkGn2rQhCBJ4hy02u/82hWiCQCAQSgUAiEEgEAolAIBEI JAKBRCCQCAQSgUAiEEgEAolAIBEIJAKBRCCQCAQSgUAiOf5Xr5rJ8r96VQ0E EoFAIhBIBAKJQCARCCQCgUQgkAgEEoFAIhBIBAKJQCARCCQCgUQgkAgEEoFA IhBIBAKJQCARCCQCgUQgkAgEEoFAIhBIBAKJQCARCCQCgUQgkAgEEoFAIhBI BAKJQCARCCQCgUQgkAgEEoFAIhBIBAKJQCARCCQCgUQgkAgEEoFAIhBIBAKJ QCARCCQCgUQgkAgEEoFAIrEEBowTaZiMm4q1x8x2pwiBwxe2PXnszkGbIgzz 7NWtBS67X6bm6erzHJvZMMs9e2OYZR/rMKtNJRnGvseLDRl1mwiEQM8eLzb0 nAt8AScOga9mJhC8j6qBrwYCP0bNwi98eyoAAAAil925pO/h+U7qp37U12nR w7q9TQ/bUNOhr+pxsW5surMbwX4gtxzGvs+LYXyGXuMbO3+Pi/utY/dC1KOe Tssetu1teliH6l/Hxeyzda8Hq2Y8+5HaYhj7Pi+H8Rm6TG/svD0ujfu3oLby 8nZa9LBub93DOlSfDMMeOTalY8qMZ/+Froax9lkMsyfwuSvw+bxc3IsX3Va6 R32dFj2s21v3sA7Vx8zrpXu4ck8p6XJXj2CP0vkwzhSeDePY1DDYy+N37OH8 jZuNTYGz38O6vXUP61BqV1RJMnvkCh1lph/PUVHeHcb3nu2yWwN9pWLcmL8G Nrs1cNPDOlQfUt49epq7h/Gcr+idYXxLhztzTLM7wTZ7U+emh2172x62oaYn Ozc2e+Dlioy3h/FPEgAAAAAAAICiGN+SLA70ZytxOXemSJ6rdnUDJ97todaw 1DvNp3nfqtWpFSS1DPCa1sIRiS7MYlG/qjksAPYrcWY9RC+XABfTGpZZe1ve OazbBf0Pod9J78qsWY4RqFdUxwhsUAuddAVO5+6iBuq4MzXQrNv51tOBE0gj AoG18f+Ilac3ue7PRgAAAABJRU5ErkJggg== ------- =_aaaaaaaaaa0 Content-Type: text/plain; charset="us-ascii" Content-ID: <12780.1357580129.3@sss.pgh.pa.us> Content-Description: gnuplot.txt set terminal png small color set output 'new_costs.png' set xlabel "Index tuples" set ylabel "Added cost" set logscale x set logscale y h(x) = (x <= 256.0) ? 0 : (x <= 256.0*256) ? 1 : (x <= 256.0*256*256) ? 2 : (x <= 256.0*256*256*256) ? 3 : (x <= 256.0*256*256*256*256) ? 4 : 5 head(x) = 4*log(1 + x/10000) + 0.25 historical(x) = 4 * x/100000 + 0.25 ninepoint2(x) = 4 * x/10000 + 0.25 plot [10:1e9][0.1:10] 0.0025*log(x)/log(2) + 0.125*(h(x)+2), head(x), historical(x), ninepoint2(x) ------- =_aaaaaaaaaa0 Content-Type: text/plain Content-Disposition: inline Content-Transfer-Encoding: 8bit MIME-Version: 1.0 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers ------- =_aaaaaaaaaa0--