Search code examples
sqlpostgresqlindexingmaterialized-viewspostgresql-performance

Index to find records where the foreign key does not exist

Table products:

id int primary_key

Table transactions:

product_id int references products

The below SQL query is very slow:

SELECT products.* 
FROM   products 
       LEFT JOIN transactions 
              ON ( products.id = transactions.product_id ) 
WHERE  transactions.product_id IS NULL;

Out of 100 hundred million products records, there might be only 100 records where a product has no corresponding transactions.

This query is very slow as I suspect it is doing a full table scan to find those null foreign key product records.

I want to create a partial index like (pseudo-code):

CREATE INDEX products_with_no_transactions_index 
ON (Left JOIN TABLE 
    BETWEEN products AND transactions) 
WHERE transactions.product_id IS NULL;

Is the above possible and how would I go about it?

Some characteristics of this data set:

  1. Transactions are never deleted and only added.

  2. Products are never deleted but added at a rate of 100s per minute (obviously this is a made up example behind a much more complex actual use case). A small percentage of those are temporarily orphaned.

  3. I need to frequently query (up to once per minute) and need to always know what the current set of orphaned products are.

Solution

  • The best I can think of is your last idea in the comments: a MATERIALIZED VIEW:

    CREATE MATERIALIZED VIEW orphaned_products AS
SELECT *  -- or just the columns you need
FROM   products p
WHERE  NOT EXISTS (SELECT FROM transactions t WHERE t.product_id = p.id);

    Then you can use this table (a materialized view is just a special table) as drop-in replacement for the big table products in queries working with orphaned products - with obviously great impact on performance (a few 100 rows instead of 100 millions). Materialized views require Postgres 9.3, but that's what you are using according to the comments. You can implement it by hand easily in older versions.

    However, a materialized view is a snapshot and not updated dynamically. This might void any performance benefit. To update, you run the (expensive) operation:

    REFRESH MATERIALIZED VIEW orphaned_products;

    You could do that at strategically opportune points in time and have multiple subsequent queries benefit from it, depending on your requirements.

    Of course, you would have an index on orphaned_products.id, but that would not be important for a small table of a few hundred rows.

    If your model is such that transactions are never deleted, you could exploit that to great effect. Create a similar table by hand:

    CREATE TABLE orphaned_products2 AS
SELECT *  -- or just the columns you need
FROM   products p
WHERE  NOT EXISTS (SELECT FROM transactions t WHERE t.product_id = p.id);

    You can refresh that "materialized view" just like the first one by truncating and refilling it. But the point is to avoid the expensive operation. All you actually need is:

    • Add new products to orphaned_products2.
      Implement with a trigger AFTER INSERT ON products.

    • Remove products from orphaned_products2 as soon as a referencing row appears in table transactions.
      Implement with a trigger AFTER UPDATE OF product_id ON transactions. Only if your model allows transactions.products_id to be updated - which seems odd for transactions.
      And another one AFTER INSERT ON transactions.

    All comparatively cheap operations.

    If transactions can be deleted, you'd need another trigger to add orphaned products AFTER DELETE ON transactions - which would a bit be more expensive. For every deleted transaction you need to check whether that was the last referencing the related product, and add an orphan in this case. May still be a lot cheaper than to refresh the whole materialized view.

    VACUUM

    After your additional information I would also suggest custom settings for aggressive vacuuming of orphaned_products2, since it is going to produce a lot of dead rows.