Why is my PostgreSQL expression index not being used when I ORDER BY in a subquery? [duplicate]

Question

I have a query that gets about 80k rows from said table with about 3m. I only need to paginate ten rows at a time, but with ORDER BY (a+b) DESC (a and b are integer type columns.)

Right now my query's taking about 4 seconds to do this. If I ORDER BY the primary key instead, it avoids seq scans and takes 200ms, which I would be happy with.

So I created an index on (a+b) DESC.

My thinking there is that the ORDER BY and primary key both have indexes (as do all the things in the WHERE clause--and those indexes are being used just fine), so the subquery should be able to accomplish everything it needs to without a seq scan, give up 10 indexed primary keys to the outer query, which, if it needs a seq scan because of the *, only needs to find ten rows.

It didn't make a difference, anyway.

Unfortunately, I can't share full table details, but I can say that my table has 21 columns, with some text, two integer, several timestamps and even one ts_vector. Aside from the expression one there are 4 indexes: the PK (text) is btree, I have another btree text, a btree timestamp, and a gin index on the tsvector.

Further: I can also order by the indexed timestamp and the non-primary-key indexed text, and just like the primary key, this reduces query time to 200ms thanks to index usage. It's just my expression index that doesn't seem to work this way in the subquery context.

Other options, none of which seem great:

1. Add a computed column for (a+b) so the index is just on one column. If it works for ORDER BY on the pk it should work for that column, right?

2. Cheat by somehow guesstimating a happy limiter on (a+b) due to its distribution. I'm not sure how I would always know because the query inputs are dynamic, but in this case, if I add a simple AND (a+b) > 1000000, I still get ten rows back but it only takes 200ms--and uses my expression index for the WHERE clause where the seq scan would normally be. (About the not knowing, I could start doing some kind of binary-search-esque thing, trying high numbers and reducing by half until I get at least 10 rows back and then calling it a day. If I get it within less than 20 tries, I'm still ahead. But this is beyond kludgy...)

Any ideas? How can I get it to use my expression index and avoid a seq scan?

The reason I don't understand the above is that the docs (going back to 9.4 at least) explicitly put it this way:

Index expressions are relatively expensive to maintain, because the derived expression(s) must be computed for each row upon insertion and whenever it is updated. However, the index expressions are not recomputed during an indexed search, since they are already stored in the index.

So how on earth is other_column any less expensive to ORDER BY than a+b when both are indexed?

---

Regarding query plans, let's try to get to the heart of it. I've posted a follow-up question.

Answer 1

Query optimizers generally work by figuring out how to limit the number of possible rows for the query as quickly as possible, based on what it knows about the tables and their data, and the options it has on how to get to that data.

One of the factors it has to consider is how many pages it will have to load to get to the data you need. Reading pages from disk is one of the most expensive things a DBMS does, so if it can deal with fewer pages, that's generally going to be a good thing.

Your query doesn't normally include any check on a+b. So, that index will not help with the selection of the data, and there's no reason to load it in.

Once the rows to use have been identified, is it useful to use the (a+b) DESC index to sort them? I can only see two ways to do this:

1. Use the index backwards: instead of identifying rows based on values for a+b, we look through the index starting at the max value for a+b, and check each associated row to see if it's one of our candidates, stopping when we get ten rows. This requires that we load an unknown number or pages of the index, and then look up rows to see if they exist in the candidate data. Barring situations where we know almost all rows are candidates, I can't see this as being fast.

2. Calculate the a+b values for the candidate rows, and then use the index to sort: Since one of the ways to match the index against the values of a+b from the table is to sort the calculated values of a+b from the table, it would make more sense to do exactly what it sounds like the engine did: calculate a+b from the candidate rows and sort that directly, without bothering to load the index pages as well.

When you add a search criteria that involves a+b, the picture changes completely. Instead of having to use the index backwards (finding a+b values based on the rows), it actually needs to find rows based on a+b values. If it can keep the data in the sorted order while checking the other criteria, then yes, it would use that sorted order, and not have to perform a separate step to sort the data.

You should also note that, if your primary key is a clustered index, then the data is actually stored based on that value; that has an impact on how easy it is to sort by that.

Also note that the entire set of returned data has to be sorted by a+b to find the top ten a+b values.

If this query is critical, then you may be able to use variation on a covering index. Normally, this is an index that includes all the columns used in the query (whether in the SELECT list, in table joins in the FROM clause, in the WHERE clause, the ORDER BY - all the columns used).

Note that every column in the query does not necessarily have to be used as a part of the index itself. The actual index should cover enough columns to be useful in narrowing down the rows to be returned. Additional columns are generally included at the "leaf" level - they aren't used to sort the rows from the table, but the data is available in the index.

If all the columns in the query that come from this table are part of the index, or included at the leaf level, then there's no need to actually refer to the table; the covering index has all the data needed, and will normally be smaller than the full table, so we can get everything we need from the index, and load fewer pages.

It sounds like you're bringing back all the columns from the table, so a true covering index won't necessarily help much. However, an index that covers the columns except for those only in the SELECT list might work for you. By this, I mean all the columns from this table used in JOIN clauses, the WHERE clause, any GROUP BY or HAVING clauses, and (in this case) even those in the ORDER BY clause.

Using such an index, the engine could find all the rows it needs to return without referring to the actual table. Since we've included the columns from the ORDER BY clause, it should even be able to determine the 10 rows that need to be returned (thanks to your LIMIT clause). With only ten rows involved, the engine might find it faster to identify the ten rows using the index, and then to look those 10 rows up in the actual table to get the full set of values to be returned.

When a number of columns that aren't in any index it's using are involved in the identification of the actual rows to return, the engine is more likely to rely on a table scan for at least part of the query. It has to retrieve the final result set from the table, so if it thinks it will have to load more pages if it uses the index and then looks up the rows in the table, instead of going straight to the table, it might well choose to do that.

Again, please remember this is based on almost no specific information. This will work best if there are many columns (or even a few very large columns) that aren't needed in the query to identify the rows to be returned, but are only part of the ultimate SELECT list.

With respect to this statement:

However, the index expressions are not recomputed during an indexed search, since they are already stored in the index.

I think you may be generalizing it a bit too much. Without the expression index, to search for all rows where a+b >= 12000000, a+b has to be calculated for each row. By having this value indexed, we can easily identify rows where the value of a+b meets our criteria. However, this does not mean that the value of a+b is also pre-computed at the table level. If there's no way to use the index to identify our rows, then (as discussed early in this answer) the index won't be used at all. And, if the index is not used, then a+b does still have to be calculated. Indexes are designed to find specific rows based on the indexed values, not to find the indexed values based on specific rows.

Answer 2

First I'm not sure that for ORDER BY will use the index for 80,000 rows. 80k retreived, 3 million rows there.. Let's recreate it and test

CREATE TABLE foo
AS
  SELECT x::int AS a, (x%2*x)::int AS b
  FROM generate_series(1,3e6) AS gs(x);

CREATE INDEX ON foo (a,(a+b));

SELECT a FROM foo
WHERE a BETWEEN 1000000 AND 1080000
ORDER BY a+b;
                                                                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=22950.75..23151.96 rows=80483 width=8) (actual time=44.812..47.980 rows=80001 loops=1)
   Sort Key: ((a + b))
   Sort Method: quicksort  Memory: 6823kB
   ->  Bitmap Heap Scan on foo  (cost=1709.38..16392.83 rows=80483 width=8) (actual time=14.349..27.506 rows=80001 loops=1)
         Recheck Cond: ((a >= 1000000) AND (a <= 1080000))
         Heap Blocks: exact=355
         ->  Bitmap Index Scan on foo_a_expr_idx  (cost=0.00..1689.26 rows=80483 width=0) (actual time=14.294..14.294 rows=80001 loops=1)
               Index Cond: ((a >= 1000000) AND (a <= 1080000))
 Planning time: 0.148 ms
 Execution time: 52.209 ms
(10 rows)

So you can see it's stupid fast. I'm not sure what's slowing it down in your case as you didn't give us much information. But, it's not just an index scan. My guess is that the index lookup for a+b is simply not worth it. But that's a question for the lists.

Answer 3

This answer to the follow-up question works here too. The index definition's ASC/DESC + NULLS FIRST/NULLS LAST combination (whether implied or specified) must either match the query exactly or be the exact opposite.

E.g. DESC NULLS FIRST and DESC NULLS LAST are not compatible, but DESC NULLS FIRST and ASC NULLS LAST are exact opposites and the index of one can be used for the other.

So it did not have to do with it being an expression index, after all.