I have rewritten the query using JOINs. I had to make one of them a FULL JOIN, but otherwise JOINs seem like a good idea. I have added the new query to the (same) gist: https://gist.github.com/valeneiko/89f8cbe26db7ca2651b47524462b5d18#file-queryoptimized-sql The query plan is much better with just a few small index scans which completes in under a millisecond: https://explain.depesz.com/s/vBdG Thank you for your help. Let me know if you have any other suggestions.
