Attrition Calculation Performance

TLDR:

1. how to speed up the SQL calculation for attrition given it is O(n^2)
2. how to distribute the python implementation for attrition given it maintains a counter (cumulative leavers and cumulative joiners)
3. any other ideas? (influxdb? kinetica? )

I need to calculate employee attrition for every company, every month using a big table that looks like this. Startdate and enddate is the first day of the month to keep things simple as monthly attrition rate is sufficient.

peopleid | companyid | startdate  | enddate
Joe      | MSFT      | 2010-01-01 | 2015-02-01
...

I have a SQL solution (pseudo code below) that is taking a very long time, mostly due to the cross join between the calendar table and the employment history which is big.

For example, if the history table is 10B, and 50 years has 600 month in total. The cross join will yield 10e9 * 6e2 = 6e12, 6 trillion which is very expensive.

with cal as (
    select yearmonth
    from calendar
),
people_left (
    select cal.yearmonth,
        eh.companyid,
        count(distinct eh.peopleid) as peopleid_left_count
    from cal
        inner join employment_history eh on cal.yearmonth = eh.enddate_yearmonth
    group by cal.yearmonth,
        eh.companyid
),
people_avg (
    select cal.yearmonth,
        eh.companyid,
        count(distinct eh.peopleid) as peopleid_count
    from cal
        inner join employment_history eh on cal.yearmonth >= eh.startdate_yearmonth
        and cal.yearmonth <= eh.enddate_yearmonth
    group by cal.yearmonth,
        eh.companyid
)
select n.yearmonth,
    n.companyid,
    n.peopleid_left_count / d.peopleid_count as attrition -- division by zero
from people_left n
    inner join people_avg n on n.yearmonth = d.yearmonth
    and n.companyid = d.companyid;

I also implemented a python solution, here are the key steps:

1. restructure the employment history table as employment events table ( previously one job with a start and end date now got split into two records, with one for joining and the other for leaving, indexed by month for quick lookup O(1) )
2. maintain one big lookup dictionary O(1) for each company as the counters for cumulative joiners, and cumulative leavers
3. starting from month 1 and go through each month one by one till the end
4. within each month, find all the joining and leaving events, and update the counter for that company that month, calculate the churn using that month leavers divide by the difference between cumulative joiners and cumulative leavers

This is significantly faster than the SQL implementation but is it even possible to distribute the computing to speed up? the accumulation step is dependent on all previously snapshots so I cannot wrap my head around how to think in a mapreduce way.

>This is significantly faster than the SQL implementation but is it even possible to distribute the computing to speed up? the accumulation step is dependent on all previously snapshots so I cannot wrap my head around how to think in a mapreduce way.

Here are two ideas for how to approach this. The first idea is simpler, and the second idea accommodates more parallelism.

1. Different companies are independent. You could process MSFT on one core, and employees for a different company on a different core.

   This will work as long as the number of companies you need to process is larger than the number of cores you want to distribute over. I don't know whether that's true in your dataset.

2. You could split the cumulative sum step into two steps:

   1. Take in tuples of the form (company, yearmonth, join_or_leave). For each combination of company and yearmonth, sum up all tuples within one company and yearmonth and output a tuple of the form (company, yearmonth, num_joins, num_leaves). This is a non-cumulative sum, so there is no dependence between months.

      This lets you parallelize across both company and yearmonth.

      As a back of the envelope calculation, if you have 1000 companies, and 600 months, you'd end up with 600,000 tuples from this step. If you started with 20B rows (10B input * 2 events per join/leave event) then this is a 30,000x reduction in data size.

   2. Take in the previous step, and do a cumulative sum. This step is less parallel, but doesn't need to deal with as much data. (This has number of companies * number of months tuples to deal with.)

      This can also be parallelized across companies, but that may not really be useful, given the reduced data size.