Improve execution time of query in PostgreSQL with multiple joins

Question

I'm having the trouble with the following query due to the growing size of the database ( websites is around a million rows, misspelled goes up to a couple millions )

It can reach up to 165 seconds in run time, I was wondering if there was a way to improve this without having to add additional columns to the tables, maybe using some king of index ?

SELECT contacturl, url 
FROM websites 
WHERE contactable = true
  AND websites.contacted = false 
  AND url IN (
    SELECT url
    FROM scans
    WHERE scanid IN (
      SELECT distinct(scanid)
      FROM misspelled
      WHERE word = ?
    )
  )
;

Edit : As requested, the output of the explain analyze :

Edit (1) : After Checking the explain statement output, this sing select seems to be taking most of the time :

select distinct(scanid) from misspelled where word = ?

Answer 1

Try going with an EXISTS test. First, let's be explicit about where the columns are coming from, also you don't need col = TRUE and col = FALSE on bools. You can simply say WHERE col or WHERE NOT col, I think that's a bit cleaner.

SELECT w.contacturl, w.url 
FROM websites AS w
WHERE w.contactable
  AND NOT w.contacted
  AND w.url IN (
    SELECT s.url
    FROM scans AS s
    WHERE s.scanid IN (
      SELECT distinct(m.scanid)
      FROM misspelled AS m
      WHERE m.word = ?
    )
  )
;

Now, with EXISTS,

SELECT w.contacturl, w.url 
FROM websites AS w
WHERE w.contactable
  AND NOT w.contacted 
  AND EXISTS (
    SELECT 1
    FROM scans AS s
    WHERE s.scanid IN (
      SELECT distinct(m.scanid)
      FROM misspelled AS m
      WHERE m.word = ?
    )
    AND w.url = s.url
  )
;

But you can do even better. DISTINCT just reduces duplicates for IN. With EXISTS duplicates are simply ignored.

SELECT w.contacturl, w.url 
FROM websites AS w
WHERE w.contactable
  AND NOT w.contacted 
  AND EXISTS (
    SELECT 1
    FROM scans AS s
    WHERE w.url = s.url
    AND EXISTS (
      SELECT 1
      FROM misspelled AS m
      WHERE m.scanid = s.scanid
      AND m.word = ?
    )
  )
;

That should be a lot faster, normally.

Answer 2

Replacing the IN with JOIN might do the trick.

WITH s1 AS
  (SELECT DISTINCT scanid
   FROM misspelled
   WHERE word = ?),
     s2 AS
  (SELECT url
   FROM scans
   JOIN s1 USING (scanid))
SELECT contacturl,
       url
FROM websites
JOIN s2 USING (url)
WHERE contactable = TRUE
  AND websites.contacted = FALSE;

Probably need many indexes:

• word ON mispelled
• url ON websites
• contactable AND contacted ON websites

AND without CTEs (although I am not sure if it will improve performance):

SELECT contacturl,
       url
FROM websites
JOIN
  (SELECT url
   FROM scans
   JOIN
     (SELECT DISTINCT scanid
      FROM misspelled
      WHERE word = ?) s1 USING (scanid)) s2 USING (url)
WHERE contactable = TRUE
  AND websites.contacted = FALSE;