Bitmap table scan cost per page formula
Hi hackers, This is Haisheng Yuan from Greenplum Database. We had some query in production showing that planner favors seqscan over bitmapscan, and the execution of seqscan is 5x slower than using bitmapscan, but the cost of bitmapscan is 2x the cost of seqscan. The statistics were updated and quite accurate. Bitmap table scan uses a formula to interpolate between random_page_cost and seq_page_cost to determine the cost per page. In Greenplum Database, the default value of random_page_cost is 100, the default value of seq_page_cost is 1. With the original cost formula, random_page_cost dominates in the final cost result, even the formula is declared to be non-linear. However, it is still more like linear, which can't reflect the real cost per page when a majority of pages are fetched. Therefore, the cost formula is updated to real non-linear function to reflect both random_page_cost and seq_page_cost for different percentage of pages fetched. Even though PostgreSQL has much smaller default value of random_page_cost (4), the same problem exists there if we change the default value. Old cost formula: cost_per_page = random_page_cost - (random_page_cost - seq_page_cost) * sqrt(pages_fetched / T); [image: Inline image 1] New cost formula: cost_per_page = seq_page_cost * pow(random_page_cost / seq_page_cost, 1 - sqrt(pages_fetched / T)); [image: Inline image 2] Below is the graph (credit to Heikki) that plots the total estimated cost of a bitmap heap scan, where table size is 1 pages, and random_page_cost=10 and seq_page_cost=1. X axis is the number of pages fetche. I.e. on the left, no pages are fetched, and on the right end, at 1, all pages are fetched. The original formula is in black, the new formula in red, and the horizontal line, in blue, shows the cost of a Seq Scan. [image: Inline image 3] Thoughts? Any better ideas? Thanks! Haisheng Yuan
Re: Bitmap table scan cost per page formula
Robert, you are right. The new formula serves Greenplum better than the original formula, because our default random page cost is much higher than Postgres. We don't want random cost always dominates in the final cost per page. ~ ~ ~ Haisheng Yuan On Wed, Dec 20, 2017 at 12:25 PM, Robert Haas wrote: > On Tue, Dec 19, 2017 at 10:25 PM, Justin Pryzby > wrote: > > In this old thread: https://www.postgresql.org/ > message-id/CAGTBQpZ%2BauG%2BKhcLghvTecm4-cGGgL8vZb5uA3% > 3D47K7kf9RgJw%40mail.gmail.com > > ..Claudio Freire wrote: > >> Correct me if I'm wrong, but this looks like the planner not > >> accounting for correlation when using bitmap heap scans. > >> > >> Checking the source, it really doesn't. > > > > ..which I think is basically right: the formula does distinguish between > the > > cases of small or large fraction of pages, but doesn't use correlation. > Our > > issue in that case seems to be mostly a failure of cost_index to account > for > > fine-scale deviations from large-scale correlation; but, if cost_bitmap > > accounted for our high correlation metric (>0.99), it might've helped > our case. > > I think this is a different and much harder problem than the one > Haisheng Yuan is attempting to fix. His data shows that the cost > curve has a nonsensical shape even when the assumption that pages are > spread uniformly is correct. That should surely be fixed. Now, being > able to figure out whether the assumption of uniform spread is correct > on a particular table would be nice too, but it seems like a much > harder problem. > > -- > Robert Haas > EnterpriseDB: http://www.enterprisedb.com > The Enterprise PostgreSQL Company >
Re: Bitmap table scan cost per page formula
Hi Jeff, The issue happens on our customer's production environment, I don't have access to their hardware. But I agree, the default value 100 is indeed a poor value. After I change the default value to 30 or less, the query starts generating plan with bitmap scan as expected. ~ ~ ~ Haisheng Yuan On Wed, Dec 20, 2017 at 9:43 PM, Jeff Janes wrote: > On Tue, Dec 19, 2017 at 11:55 AM, Haisheng Yuan wrote: > >> Hi hackers, >> >> This is Haisheng Yuan from Greenplum Database. >> >> We had some query in production showing that planner favors seqscan over >> bitmapscan, and the execution of seqscan is 5x slower than using >> bitmapscan, but the cost of bitmapscan is 2x the cost of seqscan. The >> statistics were updated and quite accurate. >> >> Bitmap table scan uses a formula to interpolate between random_page_cost >> and seq_page_cost to determine the cost per page. In Greenplum Database, >> the default value of random_page_cost is 100, the default value of >> seq_page_cost is 1. With the original cost formula, random_page_cost >> dominates in the final cost result, even the formula is declared to be >> non-linear. >> > > My first inclination would be take this as evidence that 100 is a poor > default for random_page_cost, rather than as evidence that the bitmap heap > scan IO cost model is wrong. > > Could you try the low level benchmark I posted elsewhere in the thread on > your hardware for reading 1/3 or 1/2 of the pages, in order? Maybe your > kernel/system does a better job of predicting read ahead. > > Cheers, > > Jeff >
