maintaining stable row identifiers during page maintenance

Source: Dev.to

Introduction

Christmas, New Year’s, a 1‑week ski trip, time with family, the rabbit‑hole of a full re‑organization of my Obsidian vault into a Zettelkasten slip box after reading How to Take Smart Notes (link) – all of these resulted in me making far less progress on this project than I would have expected, especially during my 3‑week winter vacation. Nevertheless, there has been some progress.

I am still within the storage system, working on the slotted pages for heaps, and I have encountered a few interesting things around the way a database engine handles certain page‑maintenance operations.

Row IDs

Most systems (though here I am mainly knowledgeable about how SQL Server handles things) will use a row ID to internally identify a row.

A row ID can be considered any identifier that allows the system to uniquely identify a single row. There can be multiple places where the engine needs to store this identifier, but the best example is a non‑clustered (or secondary) index. In a non‑clustered index, each entry contains a pointer to the full row it belongs to. When retrieving rows based on that index, the row identifier is used to obtain the full row (if needed).

How SQL Server Does It

In SQL Server, row IDs used in non‑clustered indexes depend on the source table and are usually referred to as the row bookmark value (Delaney et al., 2013, p. 308):

• Clustered table – the non‑clustered indexes use the clustering key as the row identifier.
• Heap – the non‑clustered index uses a physical row locator to identify the row.

Today we focus only on heaps, as clustered tables are a whole other beast. That physical row locator (called RID by Microsoft) is an 8‑byte value comprised of three segments FileID:PageID:SlotID and can be broken down as follows:

Key point: a row ID contains the slot number of the row, and this row ID appears in all non‑clustered indexes. This leads to the concept behind this post.

Stable Slot Numbers

Because indexes use the slot ID as part of the row’s identifier, the system must guarantee that rows maintain their slot number during internal page‑maintenance operations. If rows were reassigned to other slots, every non‑clustered index would also need to be updated – a costly operation.

The most direct implication of this rule is for page compaction, but the journey to guarantee it starts with deletions.

Row Deletions

One advantage of abstracting access to rows through a slot array is that certain operations, such as deletions, become trivial. Similar to a file system, deletion from a slotted page does not require touching the actual row data; it is enough to invalidate the slot that points to that row, making the bytes belonging to the row unreachable.

In my implementation, invalidating a slot means setting both its offset and length fields to 0 while leaving the slot count in the header untouched:

initial: [(96, 100), (196, 50), (246, 50)]
slot_count = 3

// delete slot index 1 (196, 50)
after:   [(96, 100), (0, 0), (246, 50)]
slot_count = 3

Why this respects the stable slot numbers rule

• If we removed the slot from the array completely (and decremented slot_count), we would have to shift the following slots down, breaking the rule.
• If we set the slot to (0,0) but decremented slot_count, the last valid slot would become unreachable.

The rule therefore simplifies the implementation considerably. The only more complex part of deletion is a small optimization I added: if the row being deleted is physically the last on the page (i.e., it sits at the end of the data section), we can avoid leaving the page fragmented by moving the free_start pointer to the end of the previous row. In this “happy case” the can_compact flag in the header is not set, indicating that fragmentation has not started.

I initially missed this optimization in the Rust implementation (though it existed in the Java version that was open on another display). I only realized the omission while setting up insertion tests. At first I marked the scenarios as “technically possible, but not valid,” but after further thought I discovered they are actually impossible only if this optimization is implemented. You can see the comment where I marked them as impossible here:
GitHub commit comment.

Page Compaction

Page compaction is the process of internally reorganizing the records in a page to remove fragmentation. While all pages start as tightly packed arrays where rows occupy a contiguous chunk of bytes, deletions and updates can create small gaps between rows. As a result, a page’s free‑space counter may be high, yet there is no contiguous area large enough to fit a new row.

Compaction works by moving all existing rows next to each other, thus eliminating any gaps. It is usually a lazy process, performed only when an insertion cannot find a large enough fragment to accommodate the new row.

My implementation may not be the most optimal, but it works. I allocate a new byte array, copy the rows in order, and update the slot offsets accordingly. (The rest of the implementation follows the same stable‑slot‑number principles described above.)

Data Compaction Overview

The size of the data segment is calculated as free_start - header_size.
To compact the page we:

1. Iterate over the slot array.
2. For each valid slot, copy its row into a new byte array, packing the rows one after another.
3. Update the slot’s offset value to point to the row’s new location.

After processing all slots we overwrite the original data segment with the new byte array. The trailing bytes (as many as were occupied by fragments) become 0s.

Note: A more sophisticated in‑place algorithm could avoid allocating a temporary array of up to 4 KB, but that optimisation is a “nice‑to‑have” for later. The current implementation satisfies the most important requirement: stable slot numbers are preserved.

The original Java version allocated an entirely new page, copied only the valid slots, and then swapped the page’s byte array. While convenient, that approach broke the stable‑slot rule—a mistake we only discovered after discussing the process with a colleague a year later. Hence the rewrite described above.

Outro

That’s essentially it for this post, which turned out to be longer than I expected. As I mentioned at the start, progress has been slow over the past few weeks, but things should pick up now that the holidays are over.

I’ve also been building a nicer testing infrastructure. My goal is to add tests as I write the code, avoiding a massive backlog of scenarios later. I’m exploring how Rust’s features can help create helpers that make setting up any test scenario a breeze; I’ll cover that in a future post.

Another area that has kept me busy is the insertion algorithm. The Java implementation was quite chunky, so I’ve been breaking it into smaller pieces, cleaning them up, and trying to cover them with tests as thoroughly as possible.

Next steps

• Finish the work related to heap pages.
• Decide whether to stay in the storage engine (e.g., index pages and B+‑trees) or move to other modules.

I’m leaning toward the latter. This process is deliberately slow—not because of language differences, but because I’m constantly re‑examining the Java DB’s implementation details, looking for improvements and fixing shortcomings. Building a small, working prototype across all layers should make future decisions easier and help me reach an MVP faster. On a personal note, I’d love to have a functional prototype as soon as possible.

References

• Delaney, K., Beauchemin, B., Cunningham, C., Kehayias, J., Freeman, C., Nevarez, B., & Randal, P. S. (2013). Microsoft SQL Server 2012 Internals. https://www.microsoftpressstore.com/store/microsoft-sql-server-2012-internals-9780735658561