Modeling combinations (options and dependencies) - Mailing list pgsql-general
From | eacil |
---|---|
Subject | Modeling combinations (options and dependencies) |
Date | |
Msg-id | WwIGBHn02EKmzqE2jtjvD9XnOmabQJ9h6iA_AZ8aG011_xGRZD5eIiu09aiFLs8GFhGGFZHrRq5Tz2ygHcpm_oA28Y220wkCIWIeSHpb1eI=@proton.me Whole thread Raw |
Responses |
Re: Modeling combinations (options and dependencies)
|
List | pgsql-general |
Hello. I am struggling for the longest time about data I can't fit into a satisfying model. I thought about giving up aboutthis project many times... Context: it's for a web server so speed is of the essence. It's an amateur project so expect cheap server. I am also morea novice than a seasoned user so please have mercy on me. Here we go, I hope I will be able to correctly explain my problem because chatgpt failed spectacularly to suggest anythingeven remotely worthwhile (yes, pretty desperate move, I know, but I am a desperate man). ------------------------------------- DATA ------------------------------------- -You have objects that are linked to many tables describing their properties, such as an object__tag table. -These objects are sold in releases. -Thing is, objects can be made of objects. I call them superobjects when they assume that container role (as objects, theycan be part of other superobjects). Multiple releases can be linked to one superobject. Yes, it's a parts scenario. -Objects can be shuffled in all sorts of unpredictable ways so it's useless to think that if one object is contained insidesome superobject A, if that superobject A will be contained inside another superobject B, superobject B will inheritall objects from superobject A. In fact, my attempt at a solution will instantiate objects to link them to superobjects. -In a superobject, multiple objects can be grouped together into a set of options. One option can be made of multiple objects(majority of the time, just one). You can choose how many options minimum and maximum (aka a range) you can choosefrom a set (majority of the time, just one). It's possible to have a NONE choice aka you don't choose any option. -Any object can have 0 (common), 1 (common), or more (very rare) dependencies. That's pretty much all. It looks like a hierarchy but it is not really one. It looks like a graph but probably not one either. It's made of multiple concepts that, alone, are difficult enough already, but now they are all grouped together and it'sgoing well over my head. In the end, I think it's about combinations with a bit of hierarchy to make everything more painful... Here is a simple "tree" representation of that data. Think of "( )" as radio buttons. Empty linebreaks are separating setsof options. X indicates mandatory nodes (unless their parent is not chosen). "(n-m)" represents the min-max range fora set of options. (x) Object 0 (it's the superobject) (1-1) Object A1 (1-1) Object A2 (1-1) Object A3 (x) Object B1 (1-1) Object C1 │ (x) Object D1 │ │ (0-1) Object E1 │ (0-1) Object E2 + Object E3 │ │ (1-2) Object F1 │ (1-2) Object F2 {requires A2} │ (1-1) Object C2 │ (x) Object G1 │ │ (x) Object E1 As you can see, a user can choose between three options A, E (with the second option being made of two objects and the thirdoption making this set optional), two options C, F. If they choose object C2, they gets objects G1 and E1 by default. Choosing object F2 forces you to have both objects C1 and A2. It's ugly to represent constraints like that but impossibleto draw in 2D properly. The reason why I said that it wasn't really a hierarchy is that you have three groups at "depth 1": object 0, object B, andobjects C with their children. These three groups are all equal to each others and their position could be swapped witheach other. Same with the children of objects C. Groups D, E, F, could be swapped with each other. When you buy a release, you have to go from the top to the bottom and go through every branch until you reach its end. Here, you could buy objects 0, A2, B1, C1, D1, E2, E3, F2. Or 0, A1, B1, C1, D1, F1. Or 0, A3, B1, C2, G1, E1. Superobjects don't have much depth to begin with, depth 6 max. Sets of options per superobject won't go probably above 10, but options themselves can go pretty high like 50. Most objects don't have dependencies to tell you. The average superobject is made of a bunch of mandatory objects and fewsets of options with few options (half of them probably being if you want the object or not). I know it's vague but the data is unpredictable with lot of exceptions and that's why I need flexibility and can't hardcodeanything. ------------------------------------- PURPOSE ------------------------------------- I don't really care at the moment as of how to render that tree above as it doesn't appear to be a big challenge. What Icare is building a performant search engine to find superobjects (and releases above them) given columns of objects (subqueries)selected through joining objects with their related tableS such as object__tag. You have to find superobjectsyou can buy, while respecting all those annoying constraints. So, if you search for a superobject containingE2 and G1, you cannot find superobject 0 because it's on different branches! Same, if you search for A1 and A2,you cannot find superobject 0 because they are in the same set of options and choosing one prevent you from choosing theother! ------------------------------------- BAD SOLUTION 1 ------------------------------------- My first thought was to create a "hierarchy". You put the three groups at depth 1 one after the other. The order doesn'tmatter. What matters is to have all possibilities the one after the other. One path of such tree would be 0-A1-B1-C1-D1-E2-E3-F1.It would be a tree representing all possible combinations. The problem is that such a tree grows exponentially. If you have 3 options, then 4, then 5, the tree will have 60 paths. If you add another one of 3 it's 180. I estimated thatyou have some freak superobjects that could spawn more than 1000 possibilities. It's insane just to check few sets ofoptions! I just need some freak exceptions I never imagined would exist to clog my database, meaning I would have to limitthe number of combinations a superobject could have to be on the safe side. And how do you even begin being efficient if it's to throw at such a hierarchy four columns of object.id to find paths thathit a combination?? If I have to check recursively hundreds of paths that do not even have a predictable order just tofind a list of superobjects, I don't see my website becoming very performant. I read a quite a "bit" on hierarchies but couldn't find anything useful. Most stuff is focused on basic cases such as findingparents or children, shortest path, subtrees, but never combinations. I also tried to flatten all of that and dived into ltree, arrays and jsonb, thinking I could use somehow that interestingcontainment property, but it was before finally getting that you can't even throw columns at such types. ------------------------------------- (NOT COMPLETELY?) BAD SOLUTION 2 ------------------------------------- It's the one I am going for at the moment (given it's the only one I found, on my own...) but it's a wasteful solution. Ittakes a lot of place and every time you want to throw another column of objects to the query, it becomes an order of magnitudeslower because the progressions of relations (and therefore joins) follows a triangle sequence (1, 3, 6, 10, 15,21, etc.) as you will see. I hesitated before explaining my solution because I don't want to divert the discussion about trying to build over it ifit's to ignore a better solution, but it's better to show that I did some homework before asking for a solution. CREATE TABLE object ( id integer NOT NULL GENERATED ALWAYS AS IDENTITY, CONSTRAINT object__pk PRIMARY KEY (id) ); CREATE TABLE superobject ( id integer NOT NULL GENERATED ALWAYS AS IDENTITY, object_id integer NOT NULL, CONSTRAINT superobject_pk PRIMARY KEY (id) ); ALTER TABLE superobject ADD CONSTRAINT superobject__object_id_fk FOREIGN KEY (object_id) REFERENCES object (id); CREATE TABLE release ( id integer NOT NULL GENERATED ALWAYS AS IDENTITY, superobject_id integer NOT NULL, CONSTRAINT release_pk PRIMARY KEY (id) ); ALTER TABLE release ADD CONSTRAINT release__superobject_id_fk FOREIGN KEY (superobject_id) REFERENCES superobject (id); CREATE TABLE instance ( id integer NOT NULL GENERATED ALWAYS AS IDENTITY , object_id integer NOT NULL, CONSTRAINT instance__pk PRIMARY KEY (id,object_id) ); ALTER TABLE instance ADD CONSTRAINT instance__object_id_fk FOREIGN KEY (object_id) REFERENCES object (id); CREATE TABLE pairing ( superobject_id integer NOT NULL, instance_a integer NOT NULL, instance_b integer NOT NULL, CONSTRAINT pairing__pk PRIMARY KEY (superobject_id,instance_a,instance_b) ); ALTER TABLE pairing ADD CONSTRAINT pairing__superobject_id_fk FOREIGN KEY (superobject_id) REFERENCES superobject (id); ALTER TABLE pairing ADD CONSTRAINT pairing__instance_a_fk FOREIGN KEY (instance_a) REFERENCES instance (id); ALTER TABLE pairing ADD CONSTRAINT pairing__instance_b_fk FOREIGN KEY (instance_b) REFERENCES instance (id); Here is a visual representation of my schema if it can help but be aware that it doesn't match exactly what I wrote aboveas it's a stripped down version: https://i.imgur.com/AUau65W.png In the table pairing, you will add for every object which object it is linked to, no matter the depth. If one has no dependency, it will have a row for every object. If one is an option, it won't have a row linking it to its fellow options or any of their sub-options. Example (instances a and b are replaced by the names of the objects for clarity): (sorry, can't format that properly in a mail) superobject_instance_a_instance_b 0___________0__________A1 0___________0__________A2 0___________0__________A3 0___________0__________B1 0___________0__________C1 0___________0__________D1 0___________0__________E1 0___________0__________E2 0___________0__________E3 0___________0__________F1 0___________0__________F2 0___________0__________C2 0___________0__________G1 0___________0__________E1 0___________A1_________0 0___________A1_________B1 0___________A1_________C1 0___________A1_________D1 0___________A1_________E1 0___________A1_________E2 0___________A1_________E3 0___________A1_________F1 0___________A1_________F2 0___________A1_________C2 0___________A1_________G1 0___________A1_________E1 0___________A2_________0 0___________A2_________B1 0___________A2_________C1 0___________A2_________D1 0___________A2_________E1 0___________A2_________E2 0___________A2_________E3 0___________A2_________F1 0___________A2_________F2 0___________A2_________C2 0___________A2_________G1 0___________A2_________E1 0___________A3_________0 ... 0___________B1_________0 ... 0___________C2_________0 0___________C2_________A1 0___________C2_________A2 0___________C2_________A3 0___________C2_________B1 0___________C2_________G1 0___________C2_________E1 0___________C1_________0 0___________C1_________A1 0___________C1_________A2 0___________C1_________A3 0___________C1_________B1 0___________C1_________D1 0___________C1_________E1 0___________C1_________E2 0___________C1_________E3 0___________C1_________F1 0___________C1_________F2 0___________D1_________0 ... etc. As you can see, it is super wasteful as you have the same relation in both directions. 0-A1 and A1-0 are identical giventhat this table has two columns semantically identical. You could search in one (instance_a -> instance_b) or the otherdirection (instance_b -> instance_a) and it would be the same. I asked on dba.stackexchange (https://dba.stackexchange.com/questions/326860/bidirectional-self-join-table)if you could split the table in half but Idon't think it's possible. The benefit is that it doesn't grow exponentially. Sure, it's closer to a quartesian product (total_of_objects * total_of_objects-1when no set of options involved) but at least it stays "reasonable". Instantiating is mandatory because if you don't make every object of a tree unique, you will get collisions. With paths A-B-C,E-B-D, D will be linked to A through A-B and B-D even though they are not. Instantiating B will prevent that. As for the queries: --FIND SUPEROBJECTS GIVEN 1 OBJECT (super fast) SELECT superobject_id FROM pairing WHERE instance_a IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <first_criterion>) GROUP BY superobject_id; --FIND SUPEROBJECTS GIVEN 2 OBJECTS (super fast) SELECT superobject_id FROM pairing WHERE instance_a IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <first_criterion>) AND instance_b IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <second_criterion>) GROUP BY superobject_id; --FIND SUPEROBJECTS GIVEN 3 OBJECTS (fast?) SELECT superobject_id FROM (SELECT p1.superobject_id, p1.instance_b AS b, p2.instance_b AS c FROM pairing p1 JOIN pairing p2 ON p1.superobject_id = p2.superobject_id and p1.instance_a = p2.instance_a WHERE p1.instance_a IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <first_criterion>) AND p1.instance_b IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <second_criterion>) AND p2.instance_b IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <third_criterion>) intersect SELECT superobject_id, instance_a AS b, instance_b AS c FROM pairing) AS results GROUP BY superobject_id It's basically a triangle. <->A<->B<->C<-> --FIND SUPEROBJECTS GIVEN 4 OBJECTS (uh oh?) SELECT first_pass.superobject_id FROM (SELECT p1.superobject_id, p1.instance_b AS b, p2.instance_b AS c, p3.instance_b ASd FROM pairing p1 JOIN pairing p2 ON p1.superobject_id = p2.superobject_id and p1.instance_a = p2.instance_a JOIN pairing p3 ON p1.superobject_id = p3.superobject_id and p1.instance_a = p3.instance_a WHERE p1.instance_a IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <first_criterion>) AND p1.instance_b IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <second_criterion>) AND p2.instance_b IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <third_criterion>) AND p3.instance_b IN (SELECT i.id FROM object o JOIN instance i ON o.id = i.object_id JOIN object__tag ot ON o.id = ot.object_idWHERE <fourth_criterion>)) AS first_pass JOIN pairing p4 ON first_pass.superobject_id = p4.superobject_id and first_pass.b = p4.instance_a and first_pass.c = p4.instance_b JOIN pairing p5 ON first_pass.superobject_id = p5.superobject_id and first_pass.b = p5.instance_a and first_pass.d = p5.instance_b JOIN pairing p6 ON first_pass.superobject_id = p6.superobject_id and first_pass.c = p6.instance_a and first_pass.d = p6.instance_b GROUP BY first_pass.superobject_id Here you have a square and its two diagonales. I am not sure it's the best way to do it. --FIND SUPEROBJECTS GIVEN 5 OBJECTS (???) something something NINE JOINS A pentacle and it's pentagram of joins... As you can see, it is already quite the beast just to find a superobject made of 4 subqueries. It doesn't look sustainableand is quite infuriating to have to build such intricate polygons from small instance_a-instance_b pieces whenthe majority of superobjects will be flat. Anyway, I hope to find some solace in your hands. ヾ(_ _*) Feel free to ask any question if something is not clear.
pgsql-general by date: