It might help if you included a sample of real data, which would make it easier for us to get a feel for the characteristics of the data.

Divide and conquer. Create 10000 files. In file 0 write all job_ids that are partly or completely between 0 and 1999. In file 1 the range 2000 and 3999. And so on.

After this for any uname_id you would have to check only about 2000 items and seldom more when it overlaps into more than one range (in that case you have to check for multiple finds of the same range, but that check is easy with a result hash)

If you have to check many uname_ids at a time, you should have the uname_ids sorted. That way you need basically the same job-range (which fits easily into memory) for many consecutive checks. In that case even some preprocessing might make sense, where you create a hash with the 2000 numbers of the range as key and an array of job-ranges that include this number as data.

Naturally the 10000 files ist just one possibility, maybe 1000 files with a range of 20000 numbers or something inbetween might make more sense

What is the maximum of the coordinates?

PS:max for the coordinates in both cases is 20000000

Just to confirm: you have two datasets of 20e6 items each. Where each item is a pair of coordinates; where each coordinate pair can range from '1,2 >tag' through '19999999,20000000 >tag' ?

Yes , that is exactly the case. where the ">tag" is something that should be connected to the coordinate so that i can say, after mapping, tagX is connected to the coordinate associated with unameY

and the coordinate does not necessary need to be two consecutive numbers , but it can

Let's see. If the "coordinates" of the time intervals are in seconds, 20e6 covers about 8 months, which doesn't really tally with your "those datasets have piled up over the years".

But if they were in minutes, then it represents 39 years. Why would anyone care what user ran what job 38 years ago? They've an above average chance of being dead already.

And then there is the "rules are that even if only part of the job_id_interval crosses the uname interval, this should be reported." bit. How can a userid be responsible for a particular job if they didn't log on until the last (second|minute|lesser known time unit) of the jobs life?

And then there's that coincidence between there being 20e6 logons, 20e6 jobs; & 20e6 intervals during which those logos and job runs occurred?

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

RIP an inspiration; A true Folk's Guy

SELECT 
Jobs.Job, 
Users.User, 
Count(Users.User) AS CountOfUser

FROM Jobs LEFT JOIN Users 
     ON (
          (
              Jobs.Start <= Users.Start and 
              Jobs.Stop >= Users.Start
                                              ) or 
           (
              Jobs.Start <= Users.Stop and 
              Jobs.Stop >= Users.Stop
                                              ) or
           (
              Users.Start <= Jobs.Start and 
              Users.Stop >= Jobs.Start
                                              ) or
           (
              Users.Start <= Jobs.Stop and
              Users.Stop >= Jobs.Stop         )
       )

GROUP BY Jobs.Job, Users.User

HAVING Count(Users.User) = 1;
[download]

Job       User     CountOfUser
job_id1   uname1   1
job_id2   uname2   1
job_id3   uname2   1
job_id4   uname2   1
[download]