It Happened on Halloween
Churning, churning, churning… continuously updating innocently standing rows. The UPDATE operation, though built by its makers to do good, was set loose to wreak havoc on a multitude of payroll records. It was only supposed to allocate 10% pay increases to employees that had a yearly salary of less than $25,000. But no. That wasn’t enough for the beast. It plowed through the records, disseminating raises. It ran over and over the database until every last employee was assigned a yearly salary of $25,000.
The updated rows tried to stay ahead of it, tried to stay out of the way – but to no avail. The hungry query still hunted every row within its parameters, pulled it in, changed it, altered it forever, and then left it in the same path where it could again fall prey. The brute would not be satisfied until the company that created it was gushing dollars from the wound of its hacking bite.
It would have been a quiet Friday afternoon. But was Halloween. A monster was loosed, and nothing could be done to right the wrong until Monday morning.
That was 1976. And to this day, engineers and developers are still looking for the best strategies to defeat the Halloween Problem.
What is It, Really?
The most concise definition of the problem comes from a Microsoft® blog, The “Halloween Problem” for XML APIs: “Halloween protection is needed to prevent a situation where the physical location of a row within a table changes due to an UPDATE operation. As a result, the same row may be revisited multiple times within the context of a single logical operation, which should not occur.” [2]
The incident on that fateful Halloween day occurred when the update operation kept searching for payroll data rows of a minimum value, found them, and then updated them multiple times until they all maxed-out at $25,000.
This is really a problem for developers to address, so database users might not have heard about it, and probably don’t need to be looking under the bed for it. However, because such database errors can be far-reaching and costly, companies must be vigilant in their watch.
Who are the Heroes?
The Halloween Problem does raise its head as a not-completely-contained animal. Many companies are still working on solutions. An InnovationQ® concept query, taken from the above quotation (i.e., protection is needed to prevent a situation where the physical location of a row within a table changes due to an UPDATE operation) and given a publication date filter of one year, produced a results list of 1,101 US patents and applications of good relevance. That is a good body of work on a similar problem in one year.
So, who is doing all this work? Who are the monster-hunters?
Given the top 1,500 relevant results, it looks like IBM is generating the most patents and applications in this area.
Figure 1: For the query: protection is needed to prevent a situation where the physical location of a row within a table changes due to an UPDATE operation, IBM is the top producer of relevant work in the past year.
The quantity of patents and applications does not necessarily mean the most relevant is among them. When the same 1,500 results are sorted by relevance, the German-based SAP comes out on top.
Figure 2: Companies at the top of the list have the patents or applications with the highest relevance to the query
Also considering the most recent work along with the most relevant, SAP has an application in the #1 spot from September of 2018: US20180253468 In-memory row storage durability. The novel architecture addresses extreme Online Transaction Processing (xOLTP) performance, as its use is growing, and aims to build a controlled environment in which to provide accelerated database access and processing. It recognizes the need to manage transactions and sequences of operations between rows.
Oracle has a granted patent in the #2 spot from May of 2018: US9965535 Client-side handling of transient duplicates for row-level replication. Here, the inventors directly face the challenge of databases going wrong while updating rows. The method seeks to ensure that row changes only execute when it is “safe” to do so, effectively avoiding constraint violations and promoting successful updates.
Happy Halloween?
For 42 years, engineers and developers have turned inventors in a quest to finally put the full Halloween Problem down. As recently as last month, they are still introducing data processing approaches to do so. As we become more dependent on the nature of electronics, as we increasingly and trustingly invite the Internet of Things into our homes, offices, and automobiles, and share our data with solicitors across the globe, we hope that the Halloween Problem is solved and the heroes at SAP, IBM, Oracle, and others, continue to watch for monsters.
References
[1] https://en.wikipedia.org/wiki/Halloween_Problem
[2] https://blogs.msdn.microsoft.com/mikechampion/2006/07/20/the-halloween-problem-for-xml-apis/
[3] InnovationQ search. https://iq.ip.com/discover