-2

Here's a simplification of the problem... suppose you have a bunch of socks in a drawer. Each sock has an id associated with it, but they might be different striped colors. Let's say the stripes are stored as different entries in a second table.. so for each sock with a sockid (left table) there's a stripe=red entry in table 2 and there's a stripe=blue entry in table 2 but there might be stripe=green or stripe=yellow in table 2 The 2 tables are joined by a sockid numeric identifier (indexed)

Now, let's say there are 10s or 100s of millions of socks (okay, it's a really big drawer) and you want to find all of the sockids that have a red stripe but not a blue stripe. We don't care if there are other stripes, but it must have a red stripe and it must not have a blue stripe.

Now, this is a simplification of a different schema and structure, but let's stipulate that it is currently not possible to adjust the database schema or normalize, and that there are valid reasons to arrange it this way even though there are no socks or stripes in reality, but they are representative of something that is more complicated to explain and the explanation would distract from the crux of the issue. Hence, the simplification down to stripes on socks, which is easier to understand and visualize.

I could do a construction (CTE or subselect or whatever - this is PG13 btw) where I construct a temp table with all of the socks with red stripes and all of the socks with blue stripes and then left join the two temporary tables together and omit the things that fall in both. It's straightforward to imagine and construct this query, but it could result in enormous temp tables that may both be the entire size of the original table (we have 10s of millions of socks with red stripes and are partial to red+blue stripes such that there is somebody that identifies all of the socks with red stripes without blue stripes and adds a blue stripe when one does not exist, as a separate process. All socks with red stripes but not blue stripes are constantly being updated to have blue stripes, and we must constantly search for those that and add the blue stripe.

I could also try to keep all of the blue strips in a massive array and then sockid not in blue_array, but the size of the array seems like it would also be inefficient to search for millions in a loop.

More [presumed] memory efficient than that would be to make an array_agg of the sock stripes for every sock in a lateral join, something like:

select sock.id
from socks,
lateral (
    select array_agg(stripes.color) as arr
    from stripes
    join socks on socks.id = stripes.sock_id
) as sock_stripes
where  sock_stripes.arr @> array['red'] and not sock_stripes.arr @> array['blue']

Any thoughts on scaling this up? (an important note is that after the first run of this, it's potentially possible to leverage another field that indicates the time of the last check of a socket and look for only red-striped socks that are added after that time, but that's an optimization that doesn't help us the first time)

I hope this makes sense.

3
  • I hope so too. Very kind of you to make this easier for us to understand, us being a little slow in the uptake. Oct 21, 2021 at 20:23
  • The only question I see in this question is "Any thoughts on scaling this up?". Does your current approach not perform according to your expectations? If so, what are your expectations? Did you try any of the other variants you've described and compare their execution plans?
    – mustaccio
    Oct 21, 2021 at 20:49
  • I know that creating the temporary tables and left/right joining them will not scale based upon the fact that most of the entries of 10s or 100s of millions of rows will end up in both tables, and that a CTE approach would fail abjectly. creating temporary tables will be faster but they will need indexes and the tables will also be similarly huge and proportional to the size of the entire 'socks' table. I'm in the process of trying several things but the analysis will take some time so hoping to get a jump on some extra ideas.
    – DougH
    Oct 22, 2021 at 22:42

2 Answers 2

1

Unless you have simplified your problem to the point it has become a different problem, you don't even need a join to socks as all the information you need is in stripes:

select id from stripes s where color = 'red'
 and not exists (select 1 from stripes s2 where s2.id = s.id and s2.color = 'blue')

You don't even need a separate process to add stripes:

insert into stripes (id, color)
select id, 'blue' from stripes s where color = 'red'
 and not exists (select 1 from stripes s2 where s2.id = s.id and s2.color = 'blue')
2
  • Good call, I did over-simplify in this case and there is additional information that I need from socks.
    – DougH
    Oct 22, 2021 at 22:34
  • FYI - this is working like a champ. I think it might end up being the best option. Thanks for suggesting it. (Apparently I'm not trusted enough by the 'algs' to upvote it, though.
    – DougH
    Oct 27, 2021 at 0:32
0

When a record is added that needs to be updated, store its ID in a third table. When it's updated, delete. The small size of the new table will guarantee performance, no matter how large the existing tables are.

5
  • It's a thoughtful idea, but In this case neither adding another table nor changing the schema is an option because the processes are well established. (there's a lot more going on but explaining it all is complicated and wouldn't further enhance the problem description).
    – DougH
    Oct 22, 2021 at 22:38
  • Adding a table wouldn't change a thing for the "well established" processes. The actions I propose could be executed by database triggers. If touching the schema is out of bounds, are you sure you're in the right forum? Oct 23, 2021 at 9:03
  • To elaborate, there is a bunch of software code that creates and updates the tables as part of a product. It's part of a much larger ecosystem and the way that the tables are generated and the data is populated is 'fixed'. Neither a new table nor trigger can be just introduced because it would mean major changes or other impacts and have other ramifications in the system beyond this stripped-down example. What can be changed, is how some aspects of reporting of the tables are done (e.g. the select statement to get things out).
    – DougH
    Oct 24, 2021 at 13:23
  • "we must constantly search for those that and add the blue stripe", is the blue stripe added manually? If not, you're doing more than reporting. Anyway, looking forward to a better solution. I've been confronted with a situation like you describe, the product owner couldn't find a way to handle my employer's data size. So I came up with the above, the product ran much better. Oct 24, 2021 at 15:17
  • no, there's nothing manual happening. There's actually a somewhat complicated (to explain) series of executions involving a scheduler and callback routines that generates the results (simplified to stripes) and a lot more table joining happening than in this simplistic example. The process of getting the entries in the DB is very much abstracted into a job execution framework, processing, serialization, etc. I am going to start trying to compare the 'exists' vs lateral join over the next couple of days.
    – DougH
    Oct 25, 2021 at 18:54

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.