Difference in speed between “not in ” and “except ” in PostgreSQL

Question

Forgive me for the vague title. I couldn't think of anything better, do feel free to suggest a better title.

---

I have been using this query in a web application with PostgreSQL for a really long time (7 Years).

asset_snapshot is the read data from a lot of IoT devices, and it truncates and reinserts data into that table every 1 minute. The maximum size (now of rows) of asset_snapshot data is 5000-10000 rows.

The aim of this query to is to return the most recent time of devices that has never been seen before.

query 1

        select *
        from location_aasset_snapshots t1
        INNER JOIN (
                    SELECT unique_identifiter, max(last_seen) as last_seen from
                    location_asset_snapshots
                    where unique_identifier not in (select unique_identifier from location_assets)
                    group by unique_identifier
                    ) t2
        on t1.unique_identifier = t2.unique_identifier and t1.last_seen = t2.last_seen

A couple of weeks ago the time to execute this query started to become 10 seconds. The reason we found that is the size of the assets table crossed to 200,000 records.

We found out that if we used except instead of not in the query retuned back to its normal speed again.

query 2:

        select *
        from location_asset_snapshots t1
        INNER JOIN (
                    SELECT unique_identifier, max(last_seen) as last_seen from
                    location_asset_snapshots
                    group by unique_identifier
                    ) t2
        on t1.unique_identifier = t2.unique_identifier and t1.last_seen = t2.last_seen
      except
      select *
        from location_asset_snapshots t1
        INNER JOIN (
                    SELECT unique_identifier, max(last_seen) as last_seen from
                    location_asset_snapshots
                    group by unique_identifier
                    ) t2
        on t1.unique_identifier = t2.unique_identifier and t1.last_seen = t2.last_seen
        where t1.unique_identifier in
        (select unique_identifier from location_assets)

Was curious to learn if there was something built in PostgreSQL that makes the second query runs faster with a growing dataset.

plan for query 1:

Hash Join  (cost=4413874.90..4413897.95 rows=2 width=90)
  Hash Cond: (((t1.unique_identifuer)::text = (location_asset_snapshots.unique_identifuer)::text) AND (t1.last_seen = (max(location_asset_snapshots.last_seen))))
  ->  Seq Scan on location_asset_snapshots t1  (cost=0.00..19.93 rows=593 width=57)
  ->  Hash  (cost=4413870.76..4413870.76 rows=276 width=33)
        ->  GroupAggregate  (cost=4413863.02..4413868.00 rows=276 width=33)
              Group Key: location_asset_snapshots.unique_identifuer
              ->  Sort  (cost=4413863.02..4413863.76 rows=296 width=33)
                    Sort Key: location_asset_snapshots.unique_identifuer
                    ->  Seq Scan on location_asset_snapshots  (cost=0.00..4413850.87 rows=296 width=33)
                          Filter: (NOT (SubPlan 1))
                          SubPlan 1
                            ->  Materialize  (cost=0.00..14344.52 rows=216768 width=25)
                                  ->  Seq Scan on location_assets  (cost=0.00..11778.68 rows=216768 width=25)

Plan for query 2:

HashSetOp Except  (cost=39.88..141.00 rows=3 width=176)
  ->  Append  (cost=39.88..140.88 rows=6 width=176)
        ->  Subquery Scan on "*SELECT* 1"  (cost=39.88..63.02 rows=3 width=94)
              ->  Hash Join  (cost=39.88..62.99 rows=3 width=90)
                    Hash Cond: (((t1.unique_identifuer)::text = (location_asset_snapshots.unique_identifuer)::text) AND (t1.last_seen = (max(location_asset_snapshots.last_seen))))
                    ->  Seq Scan on location_asset_snapshots t1  (cost=0.00..19.98 rows=598 width=57)
                    ->  Hash  (cost=32.63..32.63 rows=483 width=33)
                          ->  HashAggregate  (cost=22.97..27.80 rows=483 width=33)
                                Group Key: location_asset_snapshots.unique_identifuer
                                ->  Seq Scan on location_asset_snapshots  (cost=0.00..19.98 rows=598 width=33)
        ->  Subquery Scan on "*SELECT* 2"  (cost=40.30..77.82 rows=3 width=94)
              ->  Nested Loop  (cost=40.30..77.79 rows=3 width=90)
                    ->  Hash Join  (cost=39.88..62.99 rows=3 width=90)
                          Hash Cond: (((t1_1.unique_identifuer)::text = (location_asset_snapshots_1.unique_identifuer)::text) AND (t1_1.last_seen = (max(location_asset_snapshots_1.last_seen))))
                          ->  Seq Scan on location_asset_snapshots t1_1  (cost=0.00..19.98 rows=598 width=57)
                          ->  Hash  (cost=32.63..32.63 rows=483 width=33)
                                ->  HashAggregate  (cost=22.97..27.80 rows=483 width=33)
                                      Group Key: location_asset_snapshots_1.unique_identifuer
                                      ->  Seq Scan on location_asset_snapshots location_asset_snapshots_1  (cost=0.00..19.98 rows=598 width=33)
                    ->  Index Only Scan using for_upsert_unique_identifuer on location_assets  (cost=0.42..4.93 rows=1 width=25)
                          Index Cond: (unique_identifuer = (t1_1.unique_identifuer)::text)

Answer 1

While not an answer to your question as posed, if your ultimate goal is to improve the performance of the query then perhaps rewriting the query would be a better long term solution (basically, I'm trying to answer the question that I think lies behind the question asked).

Not knowing anything about your table structure or data, the following example is speculative but may still be of benefit. Note that, for the purpose of of this example, I've created a much larger test table (in order to amplify any differences) so YMMV, etc.

CREATE TABLE location_asset_snapshots AS
    SELECT ( random () * 1000000 )::integer AS unique_identifier,
            now () - ( ( ( random () * 1000 )::integer )::text || ' day' )::interval AS last_seen
        FROM generate_series ( 1, 100000000, 1 ) ;

SELECT 100000000
Time: 286039.624 ms (04:46.040)


CREATE TABLE location_assets AS 
    WITH x AS (
        SELECT unique_identifier
            FROM location_asset_snapshots
            WHERE random () < 0.5 
    )
    SELECT DISTINCT unique_identifier 
        FROM x ;

SELECT 1000001
Time: 90950.436 ms (01:30.950)

Attempting the original (NOT IN) query:

select count (*) from (
     select *
        from location_asset_snapshots t1
        INNER JOIN (
                    SELECT unique_identifier, max(last_seen) as last_seen from
                    location_asset_snapshots
                    where unique_identifier not in (select unique_identifier from location_assets)
                    group by unique_identifier
                    ) t2
        on t1.unique_identifier = t2.unique_identifier and t1.last_seen = t2.last_seen
) x ;        
        

For what it is worth, I cancelled the operation after having let it run for the better part of a half-hour.

Next up was testing the second (EXCEPT) query:

select count (*) from (
       select *
        from location_asset_snapshots t1
        INNER JOIN (
                    SELECT unique_identifier, max(last_seen) as last_seen from
                    location_asset_snapshots
                    group by unique_identifier
                    ) t2
        on t1.unique_identifier = t2.unique_identifier and t1.last_seen = t2.last_seen
      except
      select *
        from location_asset_snapshots t1
        INNER JOIN (
                    SELECT unique_identifier, max(last_seen) as last_seen from
                    location_asset_snapshots
                    group by unique_identifier
                    ) t2
        on t1.unique_identifier = t2.unique_identifier and t1.last_seen = t2.last_seen
        where t1.unique_identifier in
        (select unique_identifier from location_assets)
) x ;

This query did finish but still took just over 8 minutes. So, much better but still not great.

Then there is using NOT EXISTS as suggested by @a_horse_with_no_name :

select count (*) from (
    SELECT *
        FROM location_asset_snapshots t1
        INNER JOIN (
            SELECT las.unique_identifier, 
                    max ( las.last_seen ) AS last_seen 
                FROM location_asset_snapshots las
                WHERE NOT EXISTS (
                    SELECT 1
                        FROM location_assets la
                    WHERE la.unique_identifier = las.unique_identifier )
                GROUP BY las.unique_identifier
            ) t2
            ON ( t1.unique_identifier = t2.unique_identifier 
                AND t1.last_seen = t2.last_seen ) 
) x ;

This took between 30 seconds to just over a minute to run.

Another option is to rewrite the query is to make use of a LEFT OUTER JOIN as follows:

select count (*) from (
    SELECT *
        FROM location_asset_snapshots t1
        INNER JOIN (
            SELECT las.unique_identifier, 
                    max ( las.last_seen ) AS last_seen 
                FROM location_asset_snapshots las
                LEFT JOIN location_assets la
                    ON ( la.unique_identifier = las.unique_identifier )
                WHERE la.unique_identifier IS NULL
                GROUP BY las.unique_identifier
            ) t2
            ON ( t1.unique_identifier = t2.unique_identifier 
                AND t1.last_seen = t2.last_seen ) 
) x ;
                

Using the LEFT OUTER JOIN consistently took ~ 1:15 to run.

Finally, one other approach that could be taken is to use the row_number windowing function as follows:

select count (*) from (        
    SELECT * 
        FROM (
        SELECT las.*,
                row_number () OVER (
                    PARTITION BY las.unique_identifier
                    ORDER BY las.last_seen desc
                    ) AS rn
            FROM location_asset_snapshots las
            LEFT JOIN location_assets la
                ON ( la.unique_identifier = las.unique_identifier )
            WHERE la.unique_identifier IS NULL
        ) x
        WHERE rn = 1 
) y ;

Which showed performance similar to the NOT EXISTS approach.

In summary:

Approach	Time
NOT IN	> 28:00
EXCEPT	~ 8:00
NOT EXISTS	0:30 - 1:15
LEFT OUTER JOIN	~ 1:15
row_number ()	0:30 - 1:15

Answer 2

There is no inherent difference between EXCEPT vs NOT IN logically, and one is not necessarily more performant than the other. Additionally 200,000 rows is a relatively small amount of data.

You likely had a Cardinality Estimate (also known as Row Estimation) issue or your query started using a different index or index operation (e.g. scan instead of seek). When you switched to EXCEPT that likely caused a recompilation of the query plan to a more performant plan.

Without having the EXPLAIN of both queries, it's hard to say exactly what changed, but that's generally likely the two cases that you could've experienced.