Category Archives: Hekaton

Hekaton, Internals

Halloween Protection

Leave a comment

I thought it would be appropriate today, on the 40th anniversary of discovery of the problem, to address the issue of Halloween protection. Describing the problem is nothing new, of course, but nonetheless, I thought it would be interesting to illustrate in my own words.

Reportedly, the Halloween problem was identified on October 31, 1976 by three researchers, and the name stuck. Imagine that we have a table of employees with salary information. We’ll create such a table and make the employee name the primary key and the clustering key, and then put a nonclustered index on salary. Here is such a table with some random data.

create table Employee
(
	FirstName nvarchar(40) not null,
	Salary money not null,
	constraint pk_Employee primary key clustered (FirstName)
);
 
create nonclustered index ix_Employee__Salary on Employee (Salary);
 
insert Employee (FirstName, Salary)
values ('Hector', 22136), ('Hannah', 21394), ('Frank', 28990), ('Eleanor', 29832), ('Maria', 28843),
       ('Maxine', 23603), ('Sylvia', 26332), ('Jeremy', 20230), ('Michael', 27769), ('Dean', 24496);

The task at hand is to give all employees with a salary of less than 25,000 a 10% raise. This can be accomplished with a simple query.

update Employee
set Salary = Salary * 1.10
where Salary < 25000.00;

Now imagine that the SQL Server optimizer decides to use the nonclustered index to identify the rows to update. The index initially contains this data (bearing in mind that the index implicitly contains the clustering key).

employeencidx

Without Halloween protection, we can imagine that SQL walks through the rows in the index and makes the updates. So the Jeremy row is updated first, and the new salary is 22,253.

employeeafterjeremyupdate

However, the index is keyed by Salary and should be sorted on that column, so SQL Server will need to move the row in the index to the appropriate location.

employeeafterjeremyupdateandindexmove

Next, SQL updates the Hannah row and moves it within the index.

employeeafterhannahupdateandindexmove

And then for Hector:

employeeafterhectorupdateandindexmove

However, at this point, the next row is Jeremy again. So the database updates the Jeremy row for a second time.

employeeafterjeremyupdateandindexmove2

Hannah again.

employeeafterhannahupdateandindexmove2

Then Maxine.

employeeaftermaxineupdateandindexmove

Finally Hector for a second time, followed by Jeremy for a third time, and then Dean.

employeeafterhectorjeremydeanupdateandindexmove

At this point the next row is for Hannah again. However, her salary is greater than or equal to 25,000 and therefore doesn’t qualify for update based on the query predicate. Since none of the remaining rows meet the WHERE clause condition, processing stops and query execution is complete.

That, in a nutshell, is the Halloween problem: some rows get process multiple times as a result of the row being physically moved within the index being used to process the query. For comparison, the (incorrect) results described the above processing are on the left, and the correct results are on the right.

employeeupdatefinalresultsincorrect employeeupdatefinalresultscorrect

In this particular case, the process results in every employee having a salary of at least 25,000. However, imagine if the query didn’t have the WHERE clause but still chose to use the Salary index to process. The result would be an infinite loop where each employee’s salary would be repeatedly increased by 10% until an overflow condition occurred.

So how does SQL Server protect against the Halloween problem? There are a variety of mechanisms in place for this very purpose.

  • SQL Server may choose an alternate index. In fact, this is precisely what SQL will do in our example by reading from the clustered index to drive the updates. Because the clustered index isn’t sorted by Salary in any way, updates during the processing phase don’t affect the row location and the problem does not arise. This separation of the read and write portion avoids the problem.

    halloweenalternateindexselection

  • But what if scanning the clustered index is a relatively expensive operation. When I load 1,000,000 rows into the Employee table and only 5 employees have salaries below 25,000, SQL Server will naturally favor the nonclustered index.

    halloweennonclusteredindexselection

    Note particularly the highlighted Sort operator. Sort is a blocking operation, that is, the entire input set must be read (and then sorted) before any output is generated. Once again, this separates the read and write phases of query processing.

  • Suppose that the Salary index is the only means of access the data. For instance, if I drop the nonclustered Salary index and the primary key on the table, and then create a clustered index on Salary, SQL Server is forced to use the Salary index. In this case, SQL Server will insert an eager spool into the plan, once again separating the reading and writing.

    halloweeneagerspool

  • Memory-optimized (Hekaton) tables avoid the Halloween problem by their very nature. Rows in a memory table are read-only, and “updates” to the row cause the current version of the row to be invalidated a new version of the rows to be written. Once again, read and write separation happens, in this case organically.

I don’t intend this to be a comprehensive list of protections in SQL Server, but it covers the most common scenarios.

To me, the key takeaway here is that Halloween protection is an integral and crucial aspect of query processing that the optimizer simply must take into account. This most certainly affects the plan generation processes and likely adds overhead to the plan to ensure correct results.

Hekaton, SQL Server 2014

Hekaton concurrent updates: Large vs. small transactions

Leave a comment

Here is another experiment that I performed with In-Memory OLTP (Hekaton) on CTP2 of SQL Server 2014.  I started by creating a table and a sequence:

create table Employee
(
	EmployeeId bigint not null
		primary key nonclustered hash with (bucket_count = 20000000),
	Salary money
) with (memory_optimized = on, durability = schema_only);
 
CREATE SEQUENCE EmployeeSequence AS BIGINT
START WITH 1 INCREMENT BY 1;

Next, I added about 10 million records into the table. The EmployeeId was generated from the sequence object and the Salary was a random value from 25,000 to 75,000:

with Records as (select top (216) status from master.dbo.spt_values)
insert	Employee (EmployeeId, Salary)
select	next value for EmployeeSequence as EmployeeId,
	cast(cast(25000.00 + 50000.00 * (abs(cast(binary_checksum(newid()) as int)))
		* 1.0 / 2147483648.0 as int)as money) as Salary
from	Records r1 cross join Records r2 cross join Records r3;

The first few rows looked like this:

EmployeesTop10

I don’t know enough about the internals of Hekaton to be sure how the records in the Employee table are accessed during a table scan (or if there is a deterministic way that they are accessed), but I am making the guess that it happens in EmployeeId order. I set up the following queries in two separate connections:

Connection 1 – Give all employees a 5% raise:

update Employee
set Salary *= 1.05;

Connection 2 – Set a specific salary for a specific employee:

update Employee
set Salary = 80000.00
where EmployeeId = 9999999;

Before running anything, row 9,999,999 looked like this:

Employee9999999Before

I then fired off the query in connection 1 and as quickly as possible switched to connection 2 and executed the statement there. Query 2 completed quickly. The first query ran for a few seconds and then generated an error:

Msg 41302, Level 16, State 110, Line 1
The current transaction attempted to update a record that has been updated since this transaction started. The transaction was aborted.
The statement has been terminated.

The bottom line is that even though query 1 started first and almost surely had done far more work (in terms of number of updates done before it hits the record for employee 9,999,999), nonetheless it gets the short end of the stick and is the “victim” in this case.  At this point, the target employee has this value:

Employee9999999After

This behavior of simply killing off the second transaction involved in a concurrent update in such a fashion is the price that is paid for having no locking.  My concern is that it will limit the usefulness of Hekaton tables for OLTP purposes. I can certainly envision a scenario where a batch update repeatedly fails because small one-off updates taking place across the same set of records will repeatedly cause the larger transaction be to terminated. And batch updates are just a part of life, at least in my experience, for most OLTP systems. That being said, I still envision great utility in using the In-Memory tables in situations where concurrent updates won’t be likely, such as for staging tables.

Hekaton, SQL Server 2014

Hekaton error message is slightly misleading

Leave a comment

Let’s take a look at the error message that we receive when we do a concurrent update on an In-Memory OLTP (Hekaton) table. I start by opening a connection and running:

begin transaction
 
update CheckingAccount with (snapshot)
set    Balance = 100.00
where  OwnerId = 123;

This update runs fine. Now, after this first statement completes, I open a second connection and run another update against the same table:

update CheckingAccount
set    Balance = 200.00
where  OwnerId = 123;

Since I have an open transaction in the first connection that has updated the same row, I expect the second attempt to fail. It does, and the error message is:

Msg 41302, Level 16, State 110, Line 1
The current transaction attempted to update a record that has been updated since this transaction started. The transaction was aborted.
The statement has been terminated.

The wording of this error message is a bit misleading, however. Clearly the first update did not happen after the second transaction started, particularly given that the second connection had not yet even been established at that time!

Hekaton, SQL Server 2014

Hekaton – Classic deadlock scenario

Leave a comment

Ever since CTP2 was released a few weeks back, I have become interested in the new In-Memory OLTP (aka Hekaton) feature currently being constructed for SQL Server 2014.  Once I learned that Hekaton uses lock-free structures, one of the first things I started to wonder about is how Hekaton handles a classic deadlock scenario.  After downloading and installing the CTP, I created a Hekaton-enabled database and then added a couple of tables:

create table CheckingAccount
(
       OwnerId int not null primary key nonclustered hash with (bucket_count = 1000),
       Balance money
) with (memory_optimized = on, durability = schema_and_data);
 
create table SavingsAccount
(
       OwnerId int not null primary key nonclustered hash with (bucket_count = 1000),
       Balance money
) with (memory_optimized = on, durability = schema_and_data);
 
insert CheckingAccount (OwnerId, Balance) values (123, 1000.00);
insert SavingsAccount (OwnerId, Balance) values (123, 2000.00);

Now in connection 1, I run the following:

begin transaction
 
update SavingsAccount with (snapshot)
set           Balance -= 300.00
where  OwnerId = 123;

In connection 2:

begin transaction
 
update CheckingAccount with (snapshot)
set           Balance -= 200.00
where  OwnerId = 123;

Back in connection 1:

update CheckingAccount with (snapshot)
set           Balance += 300.00
where  OwnerId = 123;

Msg 41302, Level 16, State 110, Line 1
The current transaction attempted to update a record that has been updated since this transaction started. The transaction was aborted.
Msg 3998, Level 16, State 1, Line 1
Uncommittable transaction is detected at the end of the batch. The transaction is rolled back.
The statement has been terminated.

So right there we have the answer to how Hekaton handles this scenario: the second attempt at an update on the same row causes the transaction to fail.

Completing the scenario, switch back to connection 2 and run:

update SavingsAccount with (snapshot)
set           Balance += 200.00
where  OwnerId = 123;
 
commit transaction

Now check the state of the tables:

select ca.OwnerId, ca.Balance CheckingBalance, sa.Balance SavingsBalance
from CheckingAccount ca inner join SavingsAccount sa
on ca.OwnerId = sa.OwnerId where ca.OwnerId = 123;

hekaton-consistency
So the tables are transactionally consistent. Bear in mind that in the classic version of this scenario (using disk-based tables), connection 2 would have been chose as the deadlock victim. It’s OK that in this world the opposite is the case because the rules of consistency don’t dictate who is the “winner” and who is the “loser,” only that end result “balances out.”