How to model combinatorial information in RDBMS

Question

I need to model the persistence of combinatorial information. For example, suppose that the combination of 3 attributes (A, B, and C) are used to reference a given product. Besides that, supposed that a given product can belong to different combinations of A, B and C. The queries will be used to constraint the possibilities of product selection based on user requirements. Here, I'm giving a simple example, but this system is intended to combine hundreds of tables with thousands of combinations.

For now I can think in two approachs: Model1:

Table: PRODUCT_SEARCH_CONDITIONS
| key search id | attribute 1 | attribute 2 | product id |
| 1             | value 1     | value 1     | 1          |
| 2             | value 1     | value 2     | 1          |
| 3             | value 2     | value 3     | 2          |
| 4             | value 2     | value 4     | 2          |
| 5             | value 3     | value 5     | 1          |

Model2:

Table: PRODUCT_SEARCH_CONDITIONS
| key search id | product id  |
| 1             | 1           |
| 2             | 2           |
| 3             | 1           |

Table: PRODUCT_SEARCH_ATTRIBUTE_1
| key search id | attribute 1 |
| 1             | value 1     |
| 2             | value 2     |
| 3             | value 3     |

Table: PRODUCT_SEARCH_ATTRIBUTE_2
| key search id | attribute 1 |
| 1             | value 1     |
| 1             | value 2     |
| 2             | value 3     |
| 2             | value 4     |
| 3             | value 5     |

From model1, the queries and the modeling are simple, basically because I have only one table that store all possible combinations extensively. However, I have the combinatorial explosion problem because each line represents a valid combination. Indeed, if I add more variables and values, then it grows exponentially according to the valid combinations.

From model2 the queries and the modeling are more complex. However I don't need to store all possible combinations extensively, I can group valid combinations together (e.g. key search id 1 that group values of attribute 2). Besides that, the queries can also be solved more efficiently, as I can calculate the intersection between the IDs found for each attribute given the user requirements.

My question is, there exists a better modeling approach that can have the advantages of both modelings (simplicity and performance)? Or even, a specific database (or search engine) technology that better support this kind of problem?

Answer 1

You need to properly model your domain. You are modeling products. You need to model both products and product-variants where a product-variant is a particular product with specific attributes.

Both products and product-variants are entities (identified with a primary key). First consider how you'd represent that a particular product had certain variants, for all products. Then consider how you'd represent a particular product-variant, for all product-variants.

Answer 2

Every DBMS will have a hard limit on the number of columns a table can have. This will be large but it is finite. If your attribute list is huge this may be a consideration against model 1.

If all attributes must be provided for every search and all comparisons are "equals" model 1 can be efficiently indexed with a single index on all the attribute columns. If the table allows nulls, or attributes are optional in a search, or comparisons can be other than "equals" model 1 struggles. This is a well-known problem for relational databases. Ideally we could define a separate index for each attribute column and the server would compute the intersection of them, but real systems are poor at this. There are work-arounds which involve a certain amount of trial and error to get right.

With model 2 each attribute is its own table so can be indexed separately and it is likely the optimizer will use these indexes. The problem of optional run-time parameters remains. Likely SQL will be generated at run-time incurring optimization overhead for every query submitted. Further, if N search parameters are provided you're doing and N+1-way join. Optimizers tend to do progressively worse as N increases.

Where the balance between these lies will depend on the actual data distribution and also the workload. Of the two I'd tend toward model 1. Let's say there are 100 attributes, they are all integers and there are 1000 rows. That's 400kB (roughly) storage. Even with no good index the DBMS will be able to scan the table in milliseconds.

Other than relational approaches you could concatenate the attributes' values and use a text-search approach e.g. Elasticsearch. Since the comparison is of a list of search attribute values against a list of product attribute values I wonder if one of the "scientific" array-based DBMS would perform well? A graph-based approach, where each product attribute was a node, would be OK but likely no better than the relational equivalent.