Thanks, looks like the right indexes are being used.
I think to speed some things up we should only expand out to one :Person node in the pattern, then collect those and UNWIND them to get the desired cross product. Right now we're paying the cost for cross product expansions, which can be costly (so for 100 employees of the company, that's 100 x 100 = 10k expansions to get the cross product of 10k rows. We can get these easier by doing just the 100 expansions, collecting and UNWINDing twice to get the results we want without paying that exponential expansion cost).
Give this a try:
MATCH (p:Person)-[r:WORKED_AT]->(c:Company {comp_id:'11111'})
WITH c, collect({p:p, r:r}) as employees
UNWIND employees as emp1
UNWIND employees as emp2
WITH c, emp1, emp2
WHERE emp1.p <> emp2.p // no comparing employees to themselves
WITH c, emp1.p as p1, emp1.r as r1, emp2.p as p2, emp2.r as r2
WHERE (date(r1.`Start Date`) > date(r2.`Start Date`)) AND ((CASE WHEN r1.`End Date` = '9999-1-1' THEN date() ELSE date(r1.`End Date`) END) < (CASE WHEN r2.`End Date` = '9999-1-1' THEN date() ELSE date(r2.`End Date`) END))
RETURN p1,p2,r1,r2,c
And if you're looking for any overlap, and not the specific type of overlap in your query, then you can use the approach in this StackOverflow answer which can be logically reduced down to: DateRangesOverlap = max(start1, start2) < min(end1, end2)
That would also let us get rid of mirrored results (where we have two rows with the exact same persons to compare, but they've just switched variables, so p1 becomes p2 and p2 becomes p1).
MATCH (p:Person)-[r:WORKED_AT]->(c:Company {comp_id:'11111'})
WITH c, collect({p:p, r:r}) as employees
UNWIND employees as emp1
UNWIND employees as emp2
WITH c, emp1, emp2
WHERE id(emp1.p) < id(emp2.p) // get rid of mirrored results
WITH c, emp1.p as p1, emp1.r as r1, emp2.p as p2, emp2.r as r2
WHERE apoc.coll.max([date(r1.`Start Date`), date(r2.`Start Date`)]) < apoc.coll.min([r1.`End Date`, r2.`End Date`])
RETURN p1,p2,r1,r2,c