Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TrzFK-0000iU-8N for pgsql-hackers@arkaria.postgresql.org; Sun, 06 Jan 2013 23:03:14 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.72) (envelope-from ) id 1TrzFJ-0002Rz-CL for pgsql-hackers@arkaria.postgresql.org; Sun, 06 Jan 2013 23:03:13 +0000 Received: from makus.postgresql.org ([98.129.198.125]) by malur.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TrzFI-0002Rt-2E for pgsql-hackers@postgresql.org; Sun, 06 Jan 2013 23:03:12 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by makus.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TrzFF-0006Gq-27 for pgsql-hackers@postgresql.org; Sun, 06 Jan 2013 23:03:11 +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 r06N35YV008540; Sun, 6 Jan 2013 18:03:05 -0500 (EST) From: Tom Lane To: Simon Riggs cc: Jeff Janes , pgsql-hackers Subject: Re: [PERFORM] Slow query: bitmap scan troubles In-reply-to: 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> Comments: In-reply-to Simon Riggs message dated "Sun, 06 Jan 2013 19:47:48 +0000" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0" Content-ID: <8415.1357512918.0@sss.pgh.pa.us> Date: Sun, 06 Jan 2013 18:03:05 -0500 Message-ID: <8539.1357513385@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: <8415.1357512918.1@sss.pgh.pa.us> Simon Riggs writes: > On 6 January 2013 18:58, Tom Lane wrote: >> IIRC, one of my very first attempts to deal with this was to charge >> random_page_cost per level of index descended. This was such a horrid >> overestimate that it never went anywhere. I think that reflects that in >> practical applications, the upper levels of the index tend to stay in >> cache. We could ignore I/O on that assumption and still try to model >> CPU costs of the descent, which is basically what Jeff is proposing. >> My objection to his formula is mainly that it ignores physical index >> size, which I think is important to include somehow for the reasons >> I explained in my other message. > Having a well principled approach will help bring us towards a > realistic estimate. I thought about this some more and came up with what might be a reasonably principled compromise. Assume that we know there are N leaf entries in the index (from VACUUM stats) and that we know the root page height is H (from looking at the btree metapage). (Note: H starts at zero for a single-page index.) If we assume that the number of tuples per page, P, is more or less uniform across leaf and upper pages (ie P is the fanout for upper pages), then we have N/P = number of leaf pages N/P/P = number of level 1 pages N/P^3 = number of level 2 pages N/P^(h+1) = number of level h pages Solving for the minimum P that makes N/P^(H+1) <= 1, we get P = ceil(exp(ln(N)/(H+1))) as an estimate of P given the known N and H values. 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 propose this, rather than Jeff's formula of cpu_index_tuple_cost * log2(N), as our fudge factor. The reason I like this better is that the additional factor of H/(H+1) provides the correction I want for bloated indexes: if an index is bloated, the way that reflects into the cost of any particular search is that the number of pages to be descended through is larger than otherwise. The correction is fairly small, particularly for large indexes, but that seems to be what's expected given the rest of our discussion. We could further extend this by adding some I/O charge when the index is sufficiently large, as per Simon's comments, but frankly I think that's unnecessary. Unless the fan-out factor is really awful, practical-sized indexes probably have all their upper pages in memory. What's more, per my earlier comment, when you start to think about tables so huge that that's not true it really doesn't matter if we charge another random_page_cost or two for an indexscan --- it'll still be peanuts compared to the seqscan alternative. To illustrate the behavior of this function, I've replotted my previous graph, still taking the assumed fanout to be 256 tuples/page. I limited the range of the functions to 0.0001 to 100 to keep the log-scale graph readable, but actually the H/(H+1) formulation would charge zero for indexes of less than 256 tuples. I think it's significant (and a good thing) that this curve is nowhere significantly more than the historical pre-9.2 fudge factor. Thoughts? regards, tom lane ------- =_aaaaaaaaaa0 Content-Type: image/png Content-ID: <8415.1357512918.2@sss.pgh.pa.us> Content-Description: new_fudge.png Content-Transfer-Encoding: base64 iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgBAMAAADH/8HXAAAAA3NCSVQCAgLM TMuiAAAAMFBMVEX//////1X/Vf//VVVV//9V/1VVVf9VVVWqqqqqqgCqAKqq AAAAqqoAqgAAAKoAAABJ/07MAAAALnRFWHRTb2Z0d2FyZQBnbnVwbG90IFVu aXggdmVyc2lvbiAzLjcgcGF0Y2hsZXZlbCAwNKWcDQAAE7tJREFUeJztncFy 6yoShlWxla1eoetUzV2nKvMAXXUzd53FeO/FVJ7fb5ARQpLBAhqEkAD1f06M JTeIfPkBCcu4aVgsFovFYrFYLBYrAz2a5vfRdL9H16NUdT28/t9DgGStkQD4 2zw6BrhSPcCud+BDAOx+WSY5zdUDfAweFADV3XrQlKQN6ZqQkMdip7bVNduH GKT2gQyQCllKDL/zKNw5Ao0H2SsEjCEe3fZuIVK5AnwzhzBA3xAwh6i/F9Ih Fu0M8AhZDKjqmrQC/gDzvB4BOgSJ1y/zw/DY/1w+5VaffH40n/2PVe7TGFV5 OnALAw7sRkYfzeVy6R8/5MbHpbk0DnxN8U0Y6BCkAi6Xj8F28kF47uMiAV56 gJ+9A125ywa4SQ94GXzW8/oYKPa8Pj4kwI8P4Udpz36/rtGYZQMEOgTJiIs0 3/Qjej3ZbD+lBxtnIy4a4DZD8IDvQzrw2Qd+Kn1gtQCBDkE65DL1gBd1FP6c R+FLtX3g4eeAQiUDBDoEU9ehZIBZGLBkgECHYOo6lAzQx4C3IWn75Pbd3Pof IfnYfj/j1P3N7bm/HfK1zmOUCxDoEJRQvpvvtscwAvr+1ng1zUSolXsVXmKj VSMNKhaghwEblDb7bnuAt96Bw852tNi3tFeP83tgPOxp5X9h2VaibBu3BYsF CHTIdTRbn7StoDBsPVvyYMt2YDe9LBkOlr0N4G7fI8D29qLRl6VOZ3kZ8DYi kx4cAT4dKNv1AHD8EUHt3OYn87kcWOx0FtAh14HNTekDJz8OLz8d2EoHjr3d 04FTh1hjH+hlQNmXzaOw0vk1z53fYw/4PY/C31MfKAjfbnWOwkCH+J1Ef1v8 1RLcBv30unsdpskMoJ8BfdTeLC/cnA23GeiJpEwHAh2S8CruXTjvZ9woEuB2 BgyURHdXd9UKcJ0B78rz9+F/Mz0u0UkVCRDoEFxV8F15/j5v3oXzbFlKBJhu Huvec/oRvPrkffCgodHqKhEg0CG4ruSf5j5wE8mPRHcf27AkqegusxQIMOFE 6r0n17fW95+7GGYFuOnHqgIBAh2CK4sWAJthwOgdOPSBwoF3V5byAKacyb+/ z+3zZxiF5T+XygMIdAiuLDrgwmxWcQDTGPBHvbgIUnEAgQ4JBeg4y6NVGsDN r+Le17RbRaUBBDrEz4AoIiW9q75X6msuyV1eYQC3MyA+xwwjoeuzJGeBhQEE OsTHgL3z/vn6ES67fuH166tPmusVm/5/84ViSxQz/L8SJZYFcBMDynb71Qde x5YsErzikF5H743gEEeAPWZd43HKAgh0CGHAeczAEdLXDFDuFcn1awY4/VhV FMBoAyoj7ghwYHbVAF7n11A60FlkUQCBDnG4RT9TFpB6o319Dc9FH9hIPw59 4PDaAPNa0ygMdAha9q+8zqBVEsDVV3FRlxqESgIIdAga9r3HXWoQKgjgSgMm xVcUQKBD8HWHu/Eu/yQwJ39get39hyvn7qwVBlw9TwD90d5UnFYVdHcW0CGo bhDjLvzpXTYmMCVv/f/+54+039v84FAxAMMMSJ+1/BlsJhIBaUzEPnibmrA4 JMB46Lc/LwJZTjEAgQ7B6YnPWQtIgH3SoxmSEeCUNNqPVaUADLmK8zrpUwA2 jerAIRl2ij+acCC4yikFINAhsgX7njQLgKLzG5OxD/wzd329LYfnb5uNwr6B SeRrwLUnzbAql1AhAIEOEQZcfdLsUb5FZQD0M2DCK167ygAIdMj1EHyFAPQw 4Ps/6athVBEAgQp4//nfDtUwqgSAlAHF0It7VMSkCgC+vDe+s0oACK4X34ex A/eoh1EFAHQaUJ75HWfAEgCC/aX38dSFATrkMOD7fXyCO9TDovwBgvWV+cLt QAOSALvGfw3VJLIa8P155YF7VMQiCuBvs1zFd1eBZb8yb3CkAX0cKFcyPwig xYDv+l0aB8oH4LSSuXd/uaHAuFebtjrQgB5Quma5kvmOMhtQn3fBHephl48D DwQIhn3vOr9De0CPQSRgJfMEguWu+eRvFO5QDYfyPg80tOBXfgcbMHOAsNjz yu9oA+YNcGnAxbtGRxsw75uL4HXH8m0P3KEaLmV9c9HCgEt+hxsw6yYML9uG t91wh2q4lTHAVwMa+B1vwJwBgr5petsXd6gGoXwBvhjQxC8DA2YMELQt420H uEM1KGULUDegkV8OBswXIKgb5ttecIdqkMoVoGZA88IjWRgwW4CgPF9c/0rh DtWglSlA1YAWfnkYMFeA8Hxq4ZeJATMFqBjQxi8TA2YP0MYvFwNmOp0F87O7 JSIXA+Y5naUY0BaCe9TDR1kChOmJtQHnYsA8AT4NeLeF4A7V8FOOAGF6Ym3A +RgwR4CzAa0NOCMD5ggQpid3W0RGBswQ4GxA+yePGKBLMKaOT27hDtXwVXYA JwM6+OVkwPwAgkxcnxzEHarhrdwAjgZ0rd2clQGzAwgyuTtCMH0tApQZwOIM mBtAkMndEYLpaxGivACWZ8DMAIJM7o4QTF+LIOUI0HUKk5sB8wIoW7Dz6ydw h2oEKSuAIB7sczBNhgbMCqA04N0VgulrEaicAIJ4cK7+kp8BcwI4GND9/TuY vBLBygggNEQHmKMBMwI4GPDuDMHUdVihfABCQzVgBuiShwFzbMH5AISmSANm A7BUA2YDEJoyDZjL3VnFGjCXu7OgIVcvxqQVWK08AAoDEg04TwPmAhAaqgHn asA8ABZswGwAui+C8zVgHgCBbMDZGjALgG/09wdguqNHKgeAQHWAGRswB4Bv ZAPO2IA5ACzagBkALNuAGQAs24DHA/QwIAN0iTZg1i34cIClG/BwgKUb8GiA xRvwaIDFG9AL4BCTBGD5BvQB2KUDWL4Bj3XgGzkNmL0BAwAmWMkcyAacuQE9 oSRzIJANOHsDHtqE30o3oJDPIJJqJXPagHUAlNoeoIcB82/BRwKswoAHAqzD gAfeXFSHAY+7uagSAx7XhOsw4HEAazHgYQBrMeBRAKsx4FEAqzHgQQDrMeBB AIG6G6sYAx4D8I1uwKUY8BiAcCdDcMPDJdURAGsy4DEA72QIbne0xDoC4F9k RDkGPAJgVS34iOmsmoaQI6az6jLgAU24KgMeALAyA+4PsDID7g6wNgPuDrA2 A+4NsDoD7g2wOgPuDbCqq7hB+wKsahpBal+A9RlwX4AVGnBfgBUacFeANRpw V4A1GnBPgFUacE+AtAEZoEseBiywBe8IsE4D7gewUgPuB7BSA+4GsFYD7gaw VgPuBbBaA+4FsFoD7gSwXgPuBZAOwZjyD9Q+AKucRpDaBWCd0whSu9ydVbEB d7k7q2YD7tKEKzbgLgCrNuAeAKs24A4AKz6JFkoPsN6ruEHJAVZuwPQAKzdg coBVG/DW69s3eCVAoENwXcnHqb2NEhuJHegxDVOIAW9PaaZLDBDoEFxV8F7S 3GZSWoDlGtDoNpPSAgQ6BNeUm0yk4RY6GmAmBvQ23EJJAZYwk9+GGW6hpACB jDjOgOs9pyslwBwNGN7JEXIBnGbx1y5CC2TErgbcxHALuQA+RnQrAWZiwM09 p8sJUKJb60AgI1IbMI3ndDkBPlSAoSuZH2fAxJ576rPXh+P13ybGgUCHYGiZ lNo9PNdcPkeJDaoP/G1WAtz7Km4HdBM3zXTUKPy7diVzoEMwsEiLYk+FnZrd NhpuoVTngfsYMJ3tjG4zKRVAoEMwrERdiUaJi9NtJiUCmNCASVqst+EWSnRz EdAhGFKeVIoWewkz3KsS3Vy0uQG3b7HrPacrDUCgQ9C/tHZDdOGdHKEkALcz 4JaNdhPDLXQUQKQCNmu0m3tOVxKAQEYQBtyo0abxnK4UAGMMuNHVbErP6UoB EMgImwFj0SVuriYlALjKgNFd3h7N1aQEAIGMeDVgXJcXeSocqe0BBhkwsss7 ynaKtgcIZMRswFh0h9lO0eYAvU+i13Z5x7bYhTYHCHTIf2IGjINb7EJbAyQN 2N7+G3OqconIm0RbT2eB+2XR66HvIU3KDeDW01lOA8p2GzeTn1kD3rwJg/WV uddD3yMaVTlAmwGVM+U4A+bWgrcGCKadrXa6h74HNCo7A24L0GDA9uVkOfK9 zMoBwuuO5aUG+h7PqPxacEqAppPlSANWDlBtwZZLDfQ93FLHzxsYtSVAmJ7Y p6fQ93CqMrv61bUhwNGAr8OGquAWnMF8FaENAYJ4aJ0zVOh7tEH52k7RdgAH A7on+LwNmHWj1bUdQBAjhzsE6cNc8m+0ujYD+EZP8dEGLAqd1FYAb/+ii0D3 y6U0Wl3bAGxvUbfDFNTlLbQFQDHyAl0CmndfCmy3iuIBDicu6wxY2oBhUjRA eeICdAH4sl1so9UVCXAceYMNWAm9JhLgfOICdH58Pr1UQ6+JAtjO533+Bqyh 19O1HqBy1QZ0dmxqareK1gJslcsOLwNWSa9ZDVCbNKABXv6uk16zFqB+1Qvu nP2Y8W//CpWmNQBbnZ/TgPI6I5PVYVJoBcDXOT+wZ5pGXAypUlkKBti+TlrZ DXiZOr6KDRh8d9ZyyhmsWeY3ITGkRmUp8O6shf2cPeAEsGYDhjXh1vCOB9iz TAAxpEKlKQSg6R0j1xA8AqzagCEAjW95gCPLCBADqlOe/AEa+bnPAYfHug3o D7A17gVXFgkQ/StToiInVMGVZQBYuQEjAbqnEQaAGFKbAhUHEJxZBMDaDRgH kJjHEgAxqDYFKgoguLNcTmDAKIDUROrlBAaMAghElssJDBgDkJzJ/ziBAWMA ApWFAapaAKTfSvo4QQuOAAhklg8MqkqZWg3Q483git+Le8oKcJyrFolxEVqg y8a1lSpJNoCdJCYS40rmPncjVHUPjE12gL9zYgIIdNF4boBdNycSoLaSudft MPUDdCzv3j26OTE4EOjC8QQAG3cf2Hd+Q1e4BOh3Q+CpAYrhV4weIlmuZO63 Pta5Ab5KAwhkuLgIYYCqVICeC7QxQFUqQCCjh6tgBqhKWfrJd4XAMwBctfQT kMFyGuYMANc0Ye8lKhmgqidAIGPHeUAGqGoG6P+pGgaoagYIdCzKhAGqmgAG fK6QAaoaAb4BHYpjygBVjQD/oiPnt5IYoCoJ8O1OR+L0hAGqkgBDDMgANQ0A gwzIADUNAIMMyAA1DQCBjsP5WYarJSZQEMCwtSUYoCYxnQV0GD6fngJg0HRW 4OImpwAY1ISBjkLlOQPU1AWvrsMANXXBtxMxQE1d8PJODFBTB3QMalsMUJOH ARmgSx4Lcb/cEs0ANXkARH2TAWqiAb7ek88ANdEA8WWbAWoiAS4+FMIANZEA 8XUHA9REAVx+KokBaqIA4mIPA9READR8LI4BaiIA4nIXA9TkBmj6XCYD1OQG iIZ9DFCTE6Dxg8EMUJMTIJp2MkBNLoDmT6YzQE0ugGjcywA1OQBalkZggJoY oFlbAETzbgaoyQ7QtrjJKW7O2gIgWvYzQE1WgNbVdRigJuXDhrrQluMUAFd9 2FCTfXmnUwCMb8JozcEANVkAOtYXY4CaLADRnoMBajIDdC1wxwA1mQGiIwcD 1MQAzYoD6FyikgFqMgJEVw4GqMkE0L1GKgPUZAKIzhwMUJMBILFILwPUZACI 7hwMUNMSILVKNAPUtASIRA4GqGkBkFymnAFqWgBEKgcD1PQKkF4n/8QAx+l7 kVhXMkey6BMDfMjdfWJdydzjixrODFAye4hVpC0rmSNd9JkBPh5jYlvJ3Oeb Qk4A0LaS+a9k9is9aHIgepR+AoCNow/8nftAA0Cvr6o5McBh+J1HYcNK5j4A z3Fv0crzQPTIwAB1qQC9WjAD1KUCRJ8MDFCXcnOR37ednQPgqpuL0CvDOQCu acKeX7fHAHU9AaJfBgaoawbo+32PDFDXDBA9MzBAXRNA7y8cZYC6RoBX9M3A AHWNANG7ZAaoSwIM+MZgBqhLAkT/khmgrgFgyFdWM0BdA0AMKJkB6mKAZgUB DPrSeQaoS0xnYUjJ5wAYNJ0VZMCTAAxqwhhUMgPU1QUakAG+qAs0IAN8URdo QAb4og4DS2aAukINyABf5LEQty4GqIsBmpUO4DluzmKAsWKAkWKAkWKAkWKA kWKAkWKAkWKAkWKAkWKAkWKAkWKAkWKAkWKAkWKAkWKAkWKAkWKAkWKAkVrz YUM/nQNg/ErmVp0DIDfhWDHASDHASDHASDHASDHASCUDeJJ7ixhgrBhgpBhg pBhgpBhgpBhgpBhgpBhgpLYEqIWYAYaWsjrE4/faLUSKAfqGjJPU4+Kp1pXM DWKAQp2snkhsK5nreR5zooVc6BCPUrSKhYQ8Fju1ra7ZPmR+7XdKbCuZM0An wK6bEm0l88tnoH7PoSXARzcl2krmLE+NvZ7SBzLAMInh96GOwsFvqbNYLBaL paojb896UAOONjA5jmEPWgSYjvbMJkowVkcLMX8njRZi/qU8QhTJr2dxBDzP fMiAznIt+/wKGEvQIsBwtG6+pOkay4H0EONZmh5i/KU8QrTwZvqmKpse09Uf GdCZfTEewxG0CDAd7TFNgHTTNxu5Q8yQX0qxmJQKean7gwIor/7IgPFi0XIM R9AiwHQ06Yi+YYqAX0vjU0LMv7kWYmvCWggN0Pb3fJb3sP/R1YDxYtFyDEfQ IsB0NNEf/U5Hs3lHCTHXJbQU8nKto/pAui8g+8CO6gMXAaajPWRGV3VeQmyV DSmFnKIkBxryss89wCrHsActAgxHU7LaqqOHGOsSXIp7fGCxWCwWi8Vi1az/ A/Ir3AjV34h6AAAAAElFTkSuQmCC ------- =_aaaaaaaaaa0 Content-Type: text/plain; charset="us-ascii" Content-ID: <8415.1357512918.3@sss.pgh.pa.us> Content-Description: gnuplot.txt set terminal png small color set output 'new_fudge.png' set logscale x set logscale y h(x) = (x <= 256) ? 0.0001/0.005 : (x <= 256*256) ? (1./2)*log(x)/log(2) : (x <= 256^3) ? (2./3)*log(x)/log(2) : (x <= 256^4) ? (3./4)*log(x)/log(2) : (x <= 256^5) ? (4./5)*log(x)/log(2) : (5./6)*log(x)/log(2) historical(x) = (4 * x/100000) < 100 ? 4 * x/100000 : 1/0 ninepoint2(x) = (4 * x/10000) < 100 ? 4 * x/10000 : 1/0 head(x) = 4*log(1 + x/10000) plot [10:1e9] h(x)*0.005, 0.005 * log(x)/log(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--