I have a seemingly simple query that's unfortunately extremely slow.

I believe that I know why it is slow, but not how to make it fast, so I'd like to see how this could be improved.

let's call the table in question "PriceHistory", which tracks the "price" (number) for a "productId", has millions of rows, and thousands of entries per productId.

There's a btree index on productId and one on price.


Crucially (I think!) as new productId things get created, their price data stays bunched together, so there are probably millions of rows related to different productIds before getting to the first line related to a given productId.

Super slow query:

    EXPLAIN ANALYZE SELECT min(price) FROM PriceHistory WHERE productId = 'someId'
    
    Result (cost=555.25..555.26 rows=1 width=32) (actual time=100084.212..100084.213 rows=1 loops=1)
     InitPlan 1 (returns $0)
     -> Limit (cost=0.43..555.25 rows=1 width=6) (actual time=100084.209..100084.209 rows=1 loops=1)
     -> Index Scan using "PriceHistory_btree_price" on "PriceHistory" (cost=0.43..2492270.00 rows=4492 width=6) (actual time=100084.207..100084.208 rows=1 loops=1)
     Index Cond: (price IS NOT NULL)
     Filter: ((productId)::text = 'someId'::text)
     Rows Removed by Filter: 1140612
    Planning Time: 0.124 ms
    Execution Time: 100084.230 ms


Fast-ish equivalent query that forces using a better index

    > EXPLAIN ANALYZE WITH x as (SELECT price_number FROM tradingcards_live."custom$0card_prices" where "card_custom_card" = '1348695171700984260__LOOKUP__1587446850514x224832321163624450') SELECT min(price_number) from x
    Aggregate (cost=14964.82..14964.83 rows=1 width=32) (actual time=1584.004..1584.005 rows=1 loops=1)
     -> Index Scan using "PriceHistory_btree_productid" on "PriceHistory" (cost=0.56..14953.58 rows=4493 width=6) (actual time=0.909..1582.147 rows=4674 loops=1)
     Index Cond: ((productId)::text = 'someId'::text)
    Planning Time: 0.149 ms
    Execution Time: 1584.027 ms


My understanding here is that basic statistics tell postgres that the numeric index on price expects it to reach a match on productId "sooner" given how many rows match someId (in this case, 4673), and maybe that causes postgres to think that it's cheaper to scan price values up to the first match instead of matching the correct productId values, and doing the aggregation in-memory.

Is this assumption correct, and how can we make it so that the initial query automatically chooses the better index, given the data skew - "values that match column X are bunched together and not at all equally spread" ?