How to speed up query with anti-joins

Question

I have a query with 2 anti-joins (UserEmails = 1M+ rows and Subscriptions = <100k rows), 2 conditions, and a sort. I've created an index for the 2 conditions + sort, which sped up the query by 50%. Both anti-joins have indices. However, the query is too slow (4 seconds on production).

Here is the query:

SELECT
    "Users"."firstName",
    "Users"."lastName",
    "Users"."email",
    "Users"."id"
FROM
    "Users"
WHERE
    NOT EXISTS (
        SELECT
            1
        FROM
            "UserEmails"
        WHERE
            "UserEmails"."userId" = "Users". ID
    )
AND NOT EXISTS (
    SELECT
        1
    FROM
        "Subscriptions"
    WHERE
        "Subscriptions"."userId" = "Users". ID
)
AND "isEmailVerified" = TRUE
AND "emailUnsubscribeDate" IS NULL
ORDER BY
    "Users"."createdAt" DESC
LIMIT 100

Here is the explain:

Limit  (cost=1.28..177.77 rows=100 width=49) (actual time=6171.121..6171.850 rows=100 loops=1)
  ->  Nested Loop Anti Join  (cost=1.28..4665810.76 rows=2643614 width=49) (actual time=6171.119..6171.807 rows=100 loops=1)
        ->  Nested Loop Anti Join  (cost=0.86..3470216.17 rows=2707688 width=49) (actual time=0.809..6062.152 rows=28607 loops=1)
              ->  Index Scan using users_email_subscribers_idx on "Users"  (cost=0.43..1844686.50 rows=3312999 width=49) (actual time=0.055..2342.793 rows=1186607 loops=1)
              ->  Index Only Scan using "UserEmails_userId_emailId_key" on "UserEmails"  (cost=0.43..0.49 rows=1 width=4) (actual time=0.002..0.002 rows=1 loops=1186607)
                    Index Cond: ("userId" = "Users".id)
                    Heap Fetches: 1153034
        ->  Index Only Scan using "Subscriptions_userId_type_key" on "Subscriptions"  (cost=0.42..0.44 rows=1 width=4) (actual time=0.003..0.003 rows=1 loops=28607)
              Index Cond: ("userId" = "Users".id)
              Heap Fetches: 28507
Planning time: 2.346 ms
Execution time: 6171.963 ms

And here is the index that improved the speed by 50%:

CREATE INDEX  "users_email_subscribers_idx" ON "public"."Users" USING btree("createdAt" DESC) WHERE "isEmailVerified" = TRUE AND "emailUnsubscribeDate" IS NULL;

EDIT: I should also mention that the users_email_subscribers_idx is showing an Index Scan and not Index Only Scan likely because the index is being updated regularly.

Answer 1

You have huge differences between estimate number of rows by the planner and actual number of rows. It means the planer has chosen a plan based on false information.

For example, Nested Loop Anti Join (cost=0.86..3470216.17 rows=2707688 width=49) (actual time=0.809..6062.152 rows=28607 loops=1) means he estimated he would get 2 707 688 when he actually got 28 607.

Either your statistics are not accurate (and if you never tuned autovacuum settings for those huge table,I would bet on it), either you have one column that depends on another which isn't part of the key (third normal form violation).

To refresh your statictics more frequently, you can tune autovacuum settings for those big tables. I strongly suggest that you read that blog post to understand autovacuum tuning.

If your model violates the third normal form, you can either correct your model (costly but better for a long-term vision) either let the planer collect statistics on your correlated columns with create statistics (see documentation here).

Answer 2

Your best bet is probably to solve this at the application level. This looks like a query you run as part of a data-cleaning exercise. If that is so, why do you care if it takes 6 seconds to run, and why do you restrict it to 100 rows rather than reading all of them in one shot? Perhaps you could use a materialized view or some other caching mechanism. If you reject that option, read on for some "second best" options.

I should also mention that the users_email_subscribers_idx is showing an Index Scan and not Index Only Scan likely because the index is being updated regularly.

That isn't why. You need columns out of the Users table that are not contained in the index, such as firstName and id. If you created an index with all those column at the end of the column list, you would get an index only scan. That might make the query 20% faster, but isn't going to make it 99% faster.

               Heap Fetches: 1153034

You need to vacuum UserEmails more aggressively. Again, it won't be a 99% improvement, but it should help some. Autovacuum doesn't do a good job at keeping tables sufficiently vacuumed to optimize index-only scans. You can do manual vacuums. Or you can try to force autovacuum to do a better job by lowering the per-table setting of "autovacuum_vacuum_scale_factor" to zero, and then setting the per table "autovacuum_vacuum_threshold" to be in control of the vacuuming. If the table is updated randomly throughout the table, I'd set "autovacuum_vacuum_threshold" to about 1/20 of the number of blocks in the table.

How does the query perform if you experimentally set enable_nestedloop to off? This will probably give you hash anti joins, and if your version is new enough you might get parallel versions of them.