There was once a programmer who was attached to the court of the warlord of Wu. The warlord asked the programmer: "Which is easier to design: an accounting package or an operating system?"
"An operating system," replied the programmer.
The warlord uttered an exclamation of disbelief. "Surely an accounting package is trivial next to the complexity of an operating system," he said.
"Not so," said the programmer, "When designing an accounting package, the programmer operates as a mediator between people having different ideas: how it must operate, how its reports must appear, and how it must conform to the tax laws. By contrast, an operating system is not limited by outside appearances. When designing an operating system, the programmer seeks the simplest harmony between machine and ideas. This is why an operating system is easier to design."
Payroll is incredibly complex. You have different work rules, union bargaining units, vacation and pension accumulation difference, etc.
Local and state governments also need to track time for Federal and State reimbursement and reporting with multiple, conflicting standards.
It’s compounded by the fact that the people who truly understood how things worked (because they were there when the programs were implemented) are mostly retired now.
When you hire contractors to do this, the scope gets defined up front, and the contractor dumps anything not captured on the customer, which generally means a change order and more $.
And that's just scratching the surface of the types of problems encountered.
Statutory compliance makes payroll software complex. There can be many hundreds of rules defined by government and law (and combinations of these rules) that can affect how much money ends up in your pay packet. In addition to this the payroll software and the data held within needs to be continually kept up to date and compliant with any new rule, change of rule or removal of rules. That alone can mean many monthly updates just to keep in step with legislative changes.
I've found a good rule of thumb for complications is that projects that are governed by the law of the universe (e.g. chemistry, physics) might be super hard, at least the answer will probably be a widely agreed to pass / fail (e.g. the rocket guidance worked and the rocket did not blow up).
On the other hand, software defined by bureaucrats (e.g. payroll, regulation compliance) is going to be complicated with loopholes and journeys into minutia and logic defying requirements. Its all head space with very little logical basis. Everyone has an opinion and its all probably valid, or at least the invalid is disguised fairly well.
This is the perfect place to "confess" to something that happened to me, fresh out of college, at my first full time real job at IBM... 1996ish
I got paid for 2 weeks on my first pay check but I was technically on the job for 3 days. I thought about it, biggest paycheck I had ever had in my entire life at that point, and I decided to do the honest thing and tell my manager. He thanked me, made some calls, did whatever he did and 2 or 3 days later just told me to keep the money and not tell anyone. The effort to "fix" the problem was worth more than the problem.
So take that IBM, I got 11 days free pay from you. Enjoy that Canada!
The C3 project, someone else mentioned, is a fascinating project on payroll. It's an odd problem space, it's complex, no denying it. I've built a lot of software and have a hard time comprehending how it could take a payroll cycle to calculate payroll, I believe that the guys that worked on it were all highly intelligent though. There is this odd desire to say "oh, I could do that better" It's also staggering to think that these companies and agencies are willing to spend hundreds of millions of dollars, re-implementing this highly complex business logic rather than somehow streamlining the payroll processes.. even with unions, it's just hard to comprehend it all.
It's not free pay. Your salary accounts for the empty times when there isn't a client project to assign you to. When you do work, you are billed much higher than the pay you get.
This is what happens when non-technical bureaucrats want to design a system with full managerial control within the structure of a multi-level bureaucracy (meaning there isn't just one group of non-technical bureaucrats designing the system, there are 10 levels, and all want input, and all must approve of each others' inputs).
And this is why contractors love doing business with the Government of Canada. Bill, baby, bill.
So basically the problem isn't the inherent complexity of payroll systems, it is project management and process.
Every business process that has run for decades is complicated. Think how much bugs have been "fixed" and how many custom little things have been built. Managing users, expectations, deliverable of such things is very complicated.
You're right about the accretion of ad-hoc fixes over time. Some of these might be unnecessary when analysed with hindsight and need not be faithfully reproduced in a new component or system.
Differences in legal rules across jurisdictions, taxes, benefits, and contractual differences from person to person
Some of the things I know of. Probably a ton other exceptions.
My main takeaway is that payroll deals with people on a highly individual and highly impactful way. This is not ordering a taxi. This is stuff to do with whether you have dinner on the table or whether you can pay for your daughter's life-saving surgery.
It's interfacing with the messiest, most nonlinear, and most emotional parts of human life. You cannot simply put in a rulebook into a computer and call it a day.
It may not be simple, but it's been done before. Many, many times. That's the mind-boggling part IMHO. They're not trying to find a way to travel near light speed. They're building a payroll system.
One for-instance: taxes. Every jurisdiction (sometimes city, sometimes county, state, country) has rules that they, reasonably, expect to be followed. Not all of those rules were written by reasonable legislatures, and the aggregate code to handle all the cases tends to be large, complicated, and subject to revision.
for all the reasons many explained below I want to add into the conversation. there is nothing completely off the shelf for a large organization. now I would have expected a city wide payroll system would be easier to manage but that obviously wasn't the case.
we converted JDE to Peoplesoft AR/AP and there are still those who refuse to let us turn off the older systems. all its tables are maintained and even parallel runs are done for verification. all because out of the box isn't going to fix every organizations tweaks and needed changed to the particular business they are in; hint the burden or government regulation and tax law easily explains this.
now, not in IBM's defense, one thing I have as a take a away from being on a contract to convert from one system to another about twenty years ago looked pretty simple. then came the data inconsistencies, the sheer number of exceptions of which many were known but only to a few, and finally resistance to the new software.