It seems that the bulk of query time is spent on joining user's todos with projects he can acccess, the latter is large set (195098 row in my case) since it includes public and internal projects. I modified the query manually to add a predicate like SELECT "todos"."project_id" FROM todos WHERE "todos"."user_id" = 1 AND "todos"."state" = 'done' to every UNIONed SELECT, now it finishes in ~30 ms.