0

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)
1
  • 2
    Typically an equivalent NOT EXISTS is faster than a NOT IN (plus it has the added benefit, that the NOT EXISTS doesn't have nasty surprises with NULL values) – a_horse_with_no_name Jan 17 at 19:57
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
1

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.

6
  • I have attached the plan for both queries. I see that the high cost is from the not in each unieuq_indentifier is checked again 200K records if it's in them. The other query, it is using the index to check if the epc_id is in. So yes, thanks for the explanation is not except and not in that is making a difference. its unque_identifier in is using the index and unique_identifier not in is not using the index. – coderhs Jan 17 at 19:30
  • Any suggestion on why that is happening one condition is using index and the other is not? – coderhs Jan 17 at 19:31
  • @Coderhs I'm general it stems from the estimated cost of using one query plan operation over the other which is partly dependent on the cardinality estimate. For some reason it thought not using the index was would be faster when you had the NOT IN clause, but that's a misestimation. You can read up the link in my answer on cardinality estimation for more information. I'm not an expert on PostgreSQL, so I wouldn't be able to say much otherwise without really looking into the EXPLAIN of each of your queries and researching. If you put the NOT IN clause back now is it slow again? – J.D. Jan 17 at 19:39
  • 1
    @coderhs The fact that it's a consistent issue means the fix wasn't a one-off bad plan that went away just from the query recompiling then, which is interesting. Unfortunately I don't know much else I could tell you without researching, but my link on row estimation may lead you in the right direction. – J.D. Jan 17 at 20:38
  • 1
    Thank you @jd this has definitely pointed me in the right direction. – coderhs Jan 17 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.