Database design that requires an index over two tables

Question

Using PostgreSQL (currently 9.6, but upgrades are possible), I currently have the following database layout where customers can order products, which are themselves sorted into categories (products may be in multiple categories):

Orders
id -- PRIMARY KEY
customer_id -- FOREIGN KEY (Customer - id)
product_id -> FOREIGN KEY (Product - id)

Products
id -- PRIMARY KEY

Categories
id -- PRIMARY KEY

Product_Categories
product_id -- FOREIGN KEY (Product - id)
category_id -- FOREIGN KEY (Category - id)

Data volume

Now, I have a fairly large amount of orders (~30M) and a reasonable number of categories (~1K) and customers (~10K). There is around 30K Products, with an average of 3 products by category. Products may be moved from a category to another occasionally (let's say a once per month shuffle)

Query tendencies

My problem is that I want to have the following type of query run fast: "Get all Orders for customer whose product is in Category C". That would look like:

SELECT * FROM Orders 
JOIN Product_Categories ON Orders.product_id = Product_Categories.product_id
WHERE Orders.customer_id = X AND Product_Categories.category_id = Y

Indexing considerations

The best index I can think of is an index on customer_id in Orders, supported by a secondary index on Product_Categories.product_id. This leads to the following plan (not a real plan since the design I showed above is a very large simplification of the actual case):

 - Index Scan on Orders using index on customer_id ---> Returns ~10K Rows
 - 10K Joins done by Index Lookup on the product_id index of Product_Categories (MAIN TIME CONSUMER)
 - 9990 Rows Filtered Out.
 - 10 Rows Returned

I would like to have an index over (customer_id, category_id), but I haven't been able to find a way to do this. The best solutions I can think of is to add a column categories_id INTEGER[] and then either:

1. Add a GIN index using categories_id and customer_id with the inclusion in list operator.
2. Create 1000 Partial indexes on order_id.

In both cases, I would have to synchronize categories_id with the updates in the category ↔ product association tables, which is unfortunate.

Questions

My questions are:

• Am I overthinking? Is the "filtering out 10k" rows not that bad of a problem and any solution I can think of will make the problem worse?
• Am I missing something? Can I be efficient without changing my database schema?
• Assuming I should change my database schema, what is the best way to do so?

Answer 1

If you have an index on product_categories (category_id), as well as the one you already have on orders (customer_id) then this type of query should be very fast. You can do a highly specific index scan on each table separately, then hash join the results.

https://explain.depesz.com/s/JEpZ

If that isn't fast enough for you, or you can't get it to use such a plan even when you have indexes in place, then I'm afraid you will have to give us a lot more info, like the actual query plan including timing, and what time you hope to achieve.

Answer 2

I would consider a couple of things. An order_products table which includes op_order_id and op_product_category_id fields.

In other words a record of each order "line items". Since each record is effectively a mini representation of the product, it has the product's category at the time the order is created.

So the query could be something like:

SELECT * FROM ORDERS O,  O_PRODUCTS OP
WHERE OP_CATEGORY_ID=123 AND O.O_ID=OP.OP_ORDER_ID AND
O.O_CUSTOMER_ID=456;

Don't scan a table in your query unless you definitely need fields from that table in the resulting recordset.

Indexes on the common identifier fields and any important for sorting.

Always ensure that the order of your query where clauses reduces the recordset as early as possible.

Do you need so many records in your tables? Can old records be moved to an OLAP / datawarehousing db to keep help improve performance. Also I sometimes use in memory copies of tables to improve query performance however you might want to be selective on what it contains to reduce demands on RAM.