PostgreSQL – Unique Index Not Used with Variable Number of Values in IN Clause

postgresql

Simplified problem

I've tried to isolate and minimize the case we have on our PostgreSQL v11 database, so here it is:

We can have this simple table:

CREATE TABLE "Table" (
    id BIGSERIAL PRIMARY KEY,
    col1_text TEXT NOT NULL,
    col2_bigint BIGINT NOT NULL,
    CONSTRAINT "table_col1_col2_unique" UNIQUE (col1_text, col2_bigint)
);

We can insert one row but the amount of data doesn't seem to have an effect in this case:
INSERT INTO "Table" VALUES (default, '1', 1);

Then we have these two queries which is the same base query but with different amount of data in the IN clause:

Example1:

SELECT * FROM "Table"
    WHERE (col1_text, col2_bigint) in (
        SELECT ids.id_text, ids.id_bigint from (
            VALUES
            ('1', 1),
            ('1', 1),
            ('1', 1),   
            ('1', 1),
            ('1', 1),
            ('1', 1),
            ('1', 1),
            ('1', 1),
            ('1', 1),
            ('1', 1),
            ('1', 1),
            ('1', 1),
            ('1', 1)
        ) as ids(id_text, id_bigint)
    )

and this:

Example2:

SELECT * FROM "Table"
    WHERE (col1_text, col2_bigint) in (
        SELECT ids.id_text, ids.id_bigint from (
            VALUES
            ('1', 1),
            ('1', 1),
            ('1', 1),
            ('1', 1),
            ('1', 1)
        ) as ids(id_text, id_bigint)
    )

The explain analyze command on the first one gives the following output:

"Hash Semi Join  (cost=0.36..29.96 rows=268 width=48) (actual time=0.002..0.002 rows=0 loops=1)"
"  Hash Cond: (("Table".col1_text = "*VALUES*".column1) AND ("Table".col2_bigint = "*VALUES*".column2))"
"  ->  Seq Scan on "Table"  (cost=0.00..20.70 rows=1070 width=48) (actual time=0.002..0.002 rows=0 loops=1)"
"  ->  Hash  (cost=0.16..0.16 rows=13 width=36) (never executed)"
"        ->  Values Scan on "*VALUES*"  (cost=0.00..0.16 rows=13 width=36) (never executed)"
"Planning Time: 0.185 ms"
"Execution Time: 0.017 ms"

and for the second one we have this:

"Nested Loop  (cost=0.24..21.01 rows=268 width=48) (actual time=0.019..0.019 rows=0 loops=1)"
"  ->  HashAggregate  (cost=0.09..0.14 rows=5 width=36) (actual time=0.012..0.013 rows=1 loops=1)"
"        Group Key: "*VALUES*".column1, "*VALUES*".column2"
"        ->  Values Scan on "*VALUES*"  (cost=0.00..0.06 rows=5 width=36) (actual time=0.002..0.003 rows=5 loops=1)"
"  ->  Index Scan using table_unique_col1_col2 on "Table"  (cost=0.15..4.17 rows=1 width=48) (actual time=0.005..0.005 rows=0 loops=1)"
"        Index Cond: ((col1_text = "*VALUES*".column1) AND (col2_bigint = "*VALUES*".column2))"
"Planning Time: 0.168 ms"
"Execution Time: 0.050 ms"

(Don't mind the execution time here as the table is empty in this case, but not in the real case, see below.)

The question is why do we get this different behavior of the same query?

I would expect increase of the cost of the values scan but not to change the way it scans the original table.

What I've tried is increasing the work_mem to 32 MB (the default was 4 MB) of my instance but it didn't change the query planner.

Our real problem

Our real situation is that we have a "Table" with a unique constraint defined like in the example above and it has around 12M records and few more columns (around 10).

We also have a select query that is similar to the Example1 but in the Values section, in one scenario, it had around 58K pairs. It made our application stuck in a query timeout loop as PostgreSQL needs around 17 seconds to run the query, which was a lot more than expected.

We tried partitioning the query data (the values section) in few queries, each having around 500 pairs, and then it seems that the query planner uses the unique index, and each query runs in less than a second.

Executing the partitioned queries, cumulatively took almost half of the time (around 9s in total) compared to the runtime of the single big query (around 17s).

Can someone explain why this happens and can we expect this to be changed in some other version of postgres?
Or maybe suggest some tweak that could increase the probability of using the index?

Best Answer

PostgreSQL uses the following logic to estimate the selectivity of the IN clause (from scalararraysel in src/backend/utils/adt/selfuncs.c):

We consider three cases:

1. rightop is an Array constant: deconstruct the array, apply the
operator's selectivity function for each array element, and merge the
results in the same way that clausesel.c does for AND/OR combinations.

[...]

For generic operators, we assume the probability of success is
independent for each array element.  But for "= ANY" or "<> ALL",
if the array elements are distinct (which'd typically be the case)
then the probabilities are disjoint, and we should just sum them.

If we were being really tense we would try to confirm that the
elements are all distinct, but that would be expensive and it
doesn't seem to be worth the cycles; it would amount to penalizing
well-written queries in favor of poorly-written ones.  However, we
do protect ourselves a little bit by checking whether the
disjointness assumption leads to an impossible (out of range)
probability; if so, we fall back to the normal calculation.

Now how does that apply to your case?

We have an = ANY here (IN is translated to that), so PostgreSQL estimates the selectivity of each individual value and treats them as different, that is, it adds the results.

Assuming that the selectivity of

WHERE (col1_text, col2_bigint) = ('1', 1)

is 0.01 (it filters out 99% of the rows), the selectivity of the IN list with five elements would be 0.05, which is small enough to make an index scan look attractive.

With 13 elements, the selectivity becomes 0.13, which already warrants a sequential scan.

If there are 101 elements, PostgreSQL realizes that something is fishy, because a probability can never exceed 1. In that case, it uses 1-(1-0.01)101 (the probabilistic sum), which is about 0.64.

The problem with your test statement is that all elements of the IN list are empty, but as the comments quoted above say: If we were being really tense we would try to confirm that the elements are all distinct, but that would be expensive and it doesn't seem to be worth the cycles; it would amount to penalizing well-written queries in favor of poorly-written ones.

In your real case, one of two things could be the case:

  1. you have duplicates, so PostgreSQL mis-estimates similar to above.

  2. each estimate is a little bit off, and the error adds in the sum.

You could try running ANALYZE on the large table with a higher value of default_statistics_target, maybe that improves the estimate sufficiently.

But my real recommendation is to change the way you go about this. I may be wrong, but this looks like some kind of “poor man's join”

SELECT id
   FROM table1
   WHERE <condition>;

SELECT *
   FROM table2
   WHERE table1_id IN (<result from the first query>);

Instead, do

SELECT table2.*
   FROM table1
      JOIN table2 ON table2.table1_id = table1.id
   WHERE <consition>;
Related Question