Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TrunW-0004rT-G8 for pgsql-hackers@arkaria.postgresql.org; Sun, 06 Jan 2013 18:18:14 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.72) (envelope-from ) id 1TrunV-0002bi-OD for pgsql-hackers@arkaria.postgresql.org; Sun, 06 Jan 2013 18:18:13 +0000 Received: from makus.postgresql.org ([98.129.198.125]) by malur.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TrunU-0002bc-EW for pgsql-hackers@postgresql.org; Sun, 06 Jan 2013 18:18:12 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by makus.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1TrunN-0001uO-Ll for pgsql-hackers@postgresql.org; Sun, 06 Jan 2013 18:18: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 r06II34C017518; Sun, 6 Jan 2013 13:18:03 -0500 (EST) From: Tom Lane To: Jeff Janes cc: 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> Comments: In-reply-to Jeff Janes message dated "Sun, 06 Jan 2013 08:29:17 -0800" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0" Content-ID: <17417.1357495887.0@sss.pgh.pa.us> Date: Sun, 06 Jan 2013 13:18:03 -0500 Message-ID: <17517.1357496283@sss.pgh.pa.us> X-Pg-Spam-Score: -1.9 (-) 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: <17417.1357495887.1@sss.pgh.pa.us> Jeff Janes writes: > On Saturday, January 5, 2013, Tom Lane wrote: >> Jeff Janes > writes: >>> One thing which depends on the index size which, as far as I can tell, is >>> not currently being counted is the cost of comparing the tuples all the way >>> down the index. This would be proportional to log2(indextuples) * >>> cpu_index_tuple_cost, or maybe log2(indextuples) * >>> (cpu_index_tuple_cost+cpu_operator_cost), or something like that. >> Yeah, I know. I've experimented repeatedly over the years with trying >> to account explicitly for index descent costs. But every time, anything >> that looks even remotely principled turns out to produce an overly large >> correction that results in bad plan choices. I don't know exactly why >> this is, but it's true. > log2(indextuples) * cpu_index_tuple_cost should produce pretty darn small > corrections, at least if cost parameters are at the defaults. Do you > remember if that one of the ones you tried? Well, a picture is worth a thousand words, so see the attached plot of the various proposed corrections for indexes of 10 to 1e9 tuples. For purposes of argument I've supposed that the index has loading factor 256 tuples/page, and I used the default values of random_page_cost and cpu_index_tuple_cost. The red line is your proposal, the green one is mine, the blue one is current HEAD behavior. Both the blue and green lines get to values that might be thought excessively high for very large indexes, but I doubt that that really matters: if the table contains a billion rows, the cost of a seqscan will be so high that it'll hardly matter if we overshoot the cost of an index probe a bit. (Also, once the table gets that large it's debatable whether the upper index levels all fit in cache, so charging an extra random_page_cost or so isn't necessarily unrealistic.) The real problem though is at the other end of the graph: I judge that the red line represents an overcorrection for indexes of a few thousand tuples. It might also be worth noting that for indexes of a million or so tuples, we're coming out to about the same place anyway. >> One other point is that I think it is better for any such correction >> to depend on the index's total page count, not total tuple count, >> because otherwise two indexes that are identical except for bloat >> effects will appear to have identical costs. > This isn't so. A bloated index will be estimated to visit more pages than > an otherwise identical non-bloated index, and so have a higher cost. No it won't, or at least not reliably so, if there is no form of correction for index descent costs. For instance, in a probe into a unique index, we'll always estimate that we're visiting a single index tuple on a single index page. The example you show is tweaked to ensure that it estimates visiting more than one index page, and in that context the leaf-page-related costs probably do scale with bloat; but they won't if the query is only looking for one index entry. > For the bloated index, this correction might even be too harsh. If the > index is bloated by having lots of mostly-empty pages, then this seems > fair. If it is bloated by having lots of entirely empty pages that are not > even linked into the tree, then those empty ones will never be visited and > so it shouldn't be penalized. It's true that an un-linked empty page adds no cost by itself. But if there are a lot of now-empty pages, that probably means a lot of vacant space on upper index pages (which must once have held downlinks to those pages). Which means more upper pages traversed to get to the target leaf page than we'd have in a non-bloated index. Without more experimental evidence than we've got at hand, I'm disinclined to suppose that index bloat is free. > This extra bloat was one of the reasons the partial index was avoided in > "Why does the query planner use two full indexes, when a dedicated partial > index exists?" Interesting point, but it's far from clear that the planner was wrong in supposing that that bloat had significant cost. We agree that the current 9.2 correction is too large, but it doesn't follow that zero is a better value. >> So from that standpoint, >> the ln() form of the fudge factor seems quite reasonable as a crude form >> of index descent cost estimate. The fact that we're needing to dial >> it down so much reinforces my feeling that descent costs are close to >> negligible in practice. > If they are negligible, why do we really care that it use a partial index > vs a full index? TBH, in situations like the ones I'm thinking about it's not clear that a partial index is a win at all. The cases where a partial index really wins are where it doesn't index rows that you would otherwise have to visit and make a non-indexed predicate test against --- and those costs we definitely do model. However, if the planner doesn't pick the partial index if available, people are going to report that as a bug. They won't be able to find out that they're wasting their time defining a partial index if the planner won't pick it. So, between the bloat issue and the partial-index issue, I think it's important that there be some component of indexscan cost that varies according to index size, even when the same number of leaf pages and leaf index entries will be visited. It does not have to be a large component; all experience to date says that it shouldn't be very large. But there needs to be something. regards, tom lane ------- =_aaaaaaaaaa0 Content-Type: image/png Content-ID: <17417.1357495887.2@sss.pgh.pa.us> Content-Description: fudge_factor.png Content-Transfer-Encoding: base64 iVBORw0KGgoAAAANSUhEUgAAAoAAAAHgBAMAAADH/8HXAAAAA3NCSVQCAgLM TMuiAAAAMFBMVEX//////1X/Vf//VVVV//9V/1VVVf9VVVWqqqqqqgCqAKqq AAAAqqoAqgAAAKoAAABJ/07MAAAALnRFWHRTb2Z0d2FyZQBnbnVwbG90IFVu aXggdmVyc2lvbiAzLjcgcGF0Y2hsZXZlbCAwNKWcDQAAEe5JREFUeJztnc2O qzgThi1FyZZbaSn67iOb3pc0Ul8/m5ltPvwD2GAoG/xffuec4wkUhDxdZbts x81YV1dXV1dXV1dXV1dXKRqmP1/GvmPuB6lVE7yRjQMH2XVFE7hxmAB+cz9I reIAx3EYhAd+uzbCa7aBR7HwQcaDWTusaVyKwcOCGe8+rMXoYVHMgxxp0OvA Ap+7mAc50uSkayvsxPu2hcPbVPQgnubFPHcxD2IIrzOLee40D+LbPe696a0a A/h4L8X7h72nv1zy38fPavczH2TGMa63djdxl8fpOzYG8EdimIrH9MEVkp8f nSPXY8VpHOQvNV78xcOCWldrACWXqXhMrvRe/VEclQ71IykbAH+UTz7kH+7A D4nywc5dsDWA0tmm4vHgn1u8WiNZuOVDB6jOzcaSoXDgtwD3/lEAH++N1A+g MYBvhUz6oKK0eqCMa4sHqiP8ksdSA8zOR8oDp//eWh04+6M6OXvgwnZpYB5s ru1WD5wrREp1oKi9llZYq/zYevBHhOrjrV83uyVbrnsLpFPg0mqFHfRz7lFK D4TbInoATdc71NsFM4uQyhFTT+XuqjWAT1l85IvPeuIzH9zY/05/fhn7Xax+ P/ygXpy+YWsAJYjPR8JakT1XnBrH5/Ti82SK+5ObPOeDS2EFv6gxgE/pLk/T oSacH7aAmNkqn/w8f+VpeeA5/Qw+z49WnLtgYwA/8sP+/s6UhCc9dYDqHEf9 VKgnTIrTdMF0YnJgrVDu+buR+nE0BnCms3igCsW9ByoHlOaaieF8oiDlgerD rnXg7IHSvdRBYficjz3XqpCRrwM3rfDvUgeyz+KWs4Ww4S77u5zbNL8UW2Gb Puc+dE8UAJquF1gUAEZVB3hTLQIE8e9Lvvhbj7+Wg6b+gP1Nf1/Lda8/cXAu Tt+sQYASxOslP7j28WHBqTOB1/QSmOIO3ATmg6JQP5ADNQgQQBR/spgdSqCY yc1slU++Jg+Ux+QBeE3k/ubi3AXbAyjdaaL2p15KT/rTAM7nOGpQqOH1J1/x CwC4A6tCof3bCOTbNQhQ0Vk9UIXizgOVv8kXusmf4YPUPFDVWVodqDxQuZc6 KAxhPgZrVfhyrwM1R3RVPQCXVhjmOlD4Fmh2ryU45wZXvwBrhf+kp7fogRa9 kM6I9/3+5u4REYDMN9TO9NIDt8/K+cqs9vqsnIdkT2ZzsAN01Ougwe0AnXTc XekAce3jVlMHiOmMHusAUZ3j6wDP9ULcjz3n6WFXkQKIJrp8Sq974IFOWw6h XzFX1QFahdJbpvo6QIteDvjmuq8D3OmFVX3PX63pcCMyun9fuHIdZWyrNg2v E5FhZLtvrDcp1PnMVa9crh6odu1oG6CaGT7Trt/nDHDZtcP3qeqRg/ttVtkM Lrt2cE0At7t2NCefpleTewi3DRCv/Q6yNrdGxGPXjirl0HgcJb29H8iuVH6r +qSSQ+W367us6pNKl/oumsgDvBO+XMQBOoQvMmRKG6DDegVsgTppgA6tB7rA nzDA++HLRRcg3vo6fb+ELEAHfk4TblQB4vwcJyyJAnTg53gnmqmcw9iB451o pnIOza/zvSgCDMmPIsCg/OgBdOk++9yPGkCXwSuvGxIDGCj90EQLYKj0QxMp gBH4kQLoUP/5b+9BCGDw9kOIEEBALa5sj0IHYOD+3ywyACPxIwMwFj8qAB2m jy7emQbAO4s3EJEAiH/d/zI/GgABtbjMjwTAaA0IFwGADgF84+7tA4wxgqCp +Vm5KCMIq5qflYszgqCpdYCAWtzcYLVxgHEbEK62AUZuQLjaBgioxV1+bQOM 2oNWahlgvCEYTQ0DxPmF2CK+XYAOOy6G2CK+XYCAWgQI4IYBRhxDNdQqwJhj qIaciQx+5rkFmEEgfu5Evn7mmYUHcCB+jXpg/BR4kSfAOnbtSJACSznv2sHq 8kBALUIFcJshnDCAfRqR0cs8o5IFsFCD/UBALQLya3BSCQ/gkL8lrb1JJYcA Dvp+zQEEzCBkBcjaA5guBVFqDGDaCpCrMYCAGYStAFlrAJMHcGMA0wdwYwAB MwgewG0BzBDATQHMEcAtAUydgii1kwsDZhA4BZFqJxfOUgGydkI46SCqrkYA Rl4JfaJGAAJqEckBGwHosJAokgO2AdAhgGM5YBsAAbWI0oURagFgxgBuAmD0 79KcqgGAgFpEqwBZCwDTLIU+VPUAEy2FPlT1AAG1iBnA9QPM2gJz1Q4QUIuo AVw9wGyDMIsqBwiYQbwURKlugLlGUTVVDTB/ANcNMN8oqqaaJ5UAtYjvgDVP KmXvAgrVCzDnKKqmegECahG9C8NVLcAyArhegHlHUTXVChBQixQVIKsWYOZR VK631I/fVYUAzDOK+njrUgfr9EBALYIFsEbN6mxVAozeAr8RapqqBAioxZUA 3oeni2oEGHIQ5ho1TTgRlS4X9IVrwAywFOQ2NU0okWHeLcHNPIEuj6I+glHT 5ADwq0on8/jyDGCsFb0rHOAg0ZWya4frKOojJrVZLrt2DKMOML8HAnL+/f5f fHCanOrAYSwG4FEAa/VbkkGYRU6tMAdYxq4duwDeR2qiQYRZlfUDQft/e6Qm GUXVVBdAHsBIZyQxv7pm5d7/oK1DmlHUVVXMyi0+l2RbXk8VDtCo50qZBjFU LMDHvp4D9KLUAczKBHjQES5hJcxeZQG0uN0qQC9PH8AFAUTzrxJbEFYEwFO3 W5RsX2NP5QXokfYDapGFXzaAbm63qtAAzgTw4T3aVGQXUCh1KndtrK6YlTA7 pU3lHlenIwC1yBTA6UL41ihxqS0wVxKANyfCilhMfqTIAH0bW6sAtcgWwDsi A4LID2CYqZ2SA9gCcPAxP1OwCWxALTLy2xBB5zldAQac/i9zEGbRzgO9zO26 3FuxqegWhEUA6J9lnAtQi0xdaKXArXDwFQGFB3BYgIHXPQkBapE1gAN2Y4JW fIuKHYRZtAU4XOrGhK74ZpU7CLMoBMB4S6EAtcjbgrAAAGNUfLOKb0HYnsjo BTBOxbcIUIvcAXyvFX5EXsVYfgvCbgGMvQi07EGEWVuAzrlw3ODlAtSiAH4X R2Nithyzqghgb4DCQRPQq6ILyLWNWBcPTIGvlC0lcHnXgY8k/ErZUgKXbyuc 6PsXlQQw8waYxv0Kn0cytMtEQk4qXVYdXUCheJNKdwSoRSn8ygSY57cjXVOJ ADP9dqRrupzKRRSgFsUEcO4VqlZVksMplQewni6gUHkAAbUoyQERIsN3KVJ9 4bqAXbG8hLUZ41wk2rUj9+8W8BYCcBjnIpEHAmpRVACjAGVmx4s0u3ZUlMNx oavZvhIwL5J4YOlLsSzC68CvLJIABNSisAC2LLD8mq/Fnk+iGPfmoVVZAAsV NZwFqEVx/IoaTKhhJcdOV2blIqnCFsQCJONoDKAWZXWhpcrJhasM4IIAVhnA zDKg6mceToBaFOmAgZb43ldtgzCLCgFY3SDMokIAAmpRZgCXMqlU2TC+rjJa YUAtCg3gQgBW2gUUOh+N2SlOKgeYQXmDMLN2QHKMxhTwCx6vq4DRmJoDuASA DithCnbAAroxgFqUzC9/K1x3ABcAEFCLoh3QtxsTHGDtDph9Ugkwg6JbEJa9 FcYdsHB+mQFWtZjXrrzdGEAtSnfAvK0wnsMVOwizKCfA6ltgrm0dmLAbU+s8 nKkNEWTPiaAAAbWowAG3HWls97GAAKudhzOVzQPrnYczla0OBNSihgDO1wpX PA9nKhdAQC2qCGBvIqEmlZroAnLl+q1egBmUPgizKA/AqufhTGUB2EwAszwA 28jhlHIABNSiHgfMAbCZLqBQeoDV7IrlpvQAAbWopgvDlRxgWwGcASCgFpXk cEqpAda1p4mDEgNsLYCTAwTUoq4APiWiBhqmIti2Jy3lcErHRNT8yCB+w0Og bU8AtagsgM8Bfuci1LYnzbUg7BSg/NISLwJte1LjlgjnOt32ZJAzdLwItO0J oBaV8eM6rwNF6A6Btj1psAVhWCvMd35SrfDtbU+aGgVcla4fCKhFjQ6Yblau vRZEKN2sHKAWNfJLF8JttiAsGcBGWxCWDCCgFrUNIsxKA7DZAE4EsN0ATgQQ UItqHTAJwEYW89qVAGAri3ntSgAQUIt6AzhFKtfePJKuBKkcoBYVB3CCEG64 CygUHSBgBlUOwqyKDbChxbx2RQbYegDHBthyDqcUFyCgFrU7YFyAbXcBpWIC bGwxr10xAQJqUXkXhisiQAoBHBUgoBZV53BK8QC2uBTLomgAG51I3ykaQEAt muAXDWBNvyL4liIBbGBXMUdFAgioRRsBHAsgkRaYKwpAGl1oqSiTSoBaNOOA USaVKDlglBAG1KKRLgxXBIDtD+PrigAQMIM2cjil8ACbn4czFRwgrQAOD5DA PJyp0AABvUVbDhgaIKkuoFBYgCTm4UyFBQjoDZrqwnAFBUgvgAMDBPT6hnI4 pQMiw3cp3HftIDQKuOqAyMjU96tH9107KAbwMcBhVIX7rh2Avll7AXwMUP5u palw3rWDWg7Hdbxrx1eS/S4+iHsgoG/XYACf1oFfow7EAJJsQdhpK/w1WmFk 1w4qKzl2CtUPBPTSNvmFmpWjGsChZuVodgGFggAkOAizKAhAQK9rtAVhYQAS DuAwAAG9rNkADgKQbBdQKABAQK9qmF8AgGQW89p1GyCdxbx23QYI6DUtB/D9 VI5sDqd0N5Uj3QUUugkQ0CvadsC7ALsD3gQI6AVNd2G4bgGkOI+01S2AgJm3 nMMp3QFIbDGvXTcA9gDmug6Q3GJeu64DBNSYggNeB9i7gFJXAVKeRzJ0FSCg pgS6MFwXAfYAnnURIKCWzedwStcAUh8F1HQJIO15OFOXAAJqR4bfJYDE5+FM XQEImBWZCpBdAtgHYXT5z8r1QRhdF2blADWi5ID+Idy7gKZ8AfYcbiNPgP8B akKoC8PlCRBQC1oBHH7TCTo5nFJogNT4hQZILYBDAyQXwKEB0uMXFiC9AA4M kKADnhEZ1v/78i+3I+bkutBSJ0S+mtE4oOYkAxjzQLV9DN84AfnGOqMZwBhA 7npT7Io9PIQPnuzaQdEBj3ftEGc5L3Fe7OEhAJ6Y03RA1AOVkdi849ScZAvC zhuRcbOF1pk5xQAWCtUPJBrAwXbtIOuAgXbtIDiIMCsMQLr8wgAkG8AsEEDC DhgEIGUHDAGQcAvCggAkzS8AQNIBHAAg7QAOAJA4v9upHNVBmFl3UzniFSC7 HcLUA/guwO6ANwF2B7wHsDvgTYDdAe8BpN6FEboBsAcw13WA1HM4pesAOz+h ywB7AEtdBdgDWOkqwM5P6SLAHsCzLgLsDjjrGsDehV50CWAP4FWXAPYAXnUF YHdATVcAdgfUdAFgb0F0+c/K9QDWdWFWrgewIW+A3QFN+QLsgwgb+QLs/Dby BPhvnKeoWJ4AuwNuFfYr/wTVAd5UB3hTHeBNBQc4BLBweJuKHsTTvJjnzv8g xq4dbDj/vrDHU5EBaOzaoQxXc/Pdx6UYPCzMdx/WYvSwKOZBdjJ37djeppjn LuZBdjJ27VDbnny7NjoHuO7aMbjUGF2GbLt2dHnItmtHV1dXV1fXRY1YWzLq Tc/p+YP7GAaW++zOW+5jS0FPLAbrhnTrVUcfCLfYv+9keNqbUQbjUfd8PX9w H9Ngf5/dedt91GcZ9BT0zML2KMPSgTv6QLiFRdz4FLU0GG0/dfP80X0MA8t9 tudt91Ep6KCnoCcW9mxMBZt6P5sJbmH9eMNpf1oaiP0az88f3ccwsNxne952 H1sKemJhjwXpWFMmxt/hIIQNC1eA9h+pafA9/HEs54/uYxhY7rM9b7uPSkGH 4xTUsLA/7CjrRvl+Bx6oWTgOrGJ1IFohYHUg29Zx2HnbfVQKOhynoBuLowc5 /0CGhVuii2Z0x63n7rz9PqbB/j7785b74CmoYWGvJdcrDz7QxqInul1dXV1d XV1dXV2taU4mjJxBG9PrWQCiYVNuX3SAiHjSzzPPQaauAp0Yi2LjoMbzRMLa QR5oHpiSY09qkFANpYzDOmTSdaB1YEqN4pkH1cic27QESc2s5ADr7IGD8L/Z A7m6Dx7oKyeHjDpQDgWLOlCNzB3/tqeuY/UVTzfVATak/wNHLuqELOYPawAA AABJRU5ErkJggg== ------- =_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--