Signed, Unsigned, Misaligned: Lessons from Assembly to SQL
Remember how you learned counting before school?
One, two, buckle my shoe, Three, four, knock at the door, Five, six, pick up sticks, Seven, eight, lay them straight, Nine, ten, a big fat hen.
There were no negative numbers, no decimals, no fractions, and certainly no floating point numbers. Of course, one of the reasons to start with natural integers is that it’s simple and maps to your fingers. But like your fingers, most things in the real world are described by positive numbers. The number of kids in the class, your age, the weight of your bag, and the amount of money you have (kids normally don’t have debt).1
Later in life, you learn about negative numbers and fractions. The difference between two values can be negative, years in history are before Christ, and of course your account balance. So you need lots of different number types to map all the data you gather. But for most things in life, unsigned integers are the right choice. Whether it’s how much inventory is in stock, the number of rows in a table, the IP port number, the ID of a row in a database, an array index, or loop iterations: pretty much everything in real life and a lot in computing is a positive number. This holds true especially in SQL where we have NULL-value semantics, so we don’t need -1 as a special case for unknown.
This article gives an overview of how we at CedarDB handle type information and make sure that your SQL query is both fast and correct. We cover why signedness matters, from the machine instructions your CPU runs up to the columns you declare, and why a Parquet file full of unsigned integers is what finally made us expose them in SQL.
Being a compiling system, we need several type systems that interoperate to make sure sign information does not get lost on the way from SQL user input through our C++ implementation down to the generated machine code. We walk down through those layers in a follow-up post.
Everything Is a Number
Integer types are the foundation of every programming language. Whether you are a systems programmer, embedded developer, or web developer, you always need them.
They come in different flavors: signed for differences and offsets, unsigned for identifiers and addresses.
But in the end, it all boils down to ones and zeros we interpret differently depending on what we need. uint32_t, int, and float are all 4 bytes in size, as is the emoji π in UTF-8.
For example, the emoji π is stored as the 4 bytes 0xF0 0x9F 0x98 0x80 when we encode it as UTF-8.2 Read as one 32-bit value, that is 0xF09F9880. Feed those exact same bytes to different types and you get:3
| Type | Value |
|---|---|
uint32_t |
4036991104 |
int32_t |
-257976192 |
float |
β -3.95e29 |
char[4] (UTF-8) |
π |
As you can see, the same bits can mean wildly different things.
Isn’t Number Enough of a Type?
In assembly, the bedrock of programming, we notice there are no types. If you have never looked at assembly before, think of registers as named buckets of bits. There are just registers and they can store everything. The only differentiation is the size, whether it’s 8 bits, 8 bytes, or a larger vector register (x86 register overview).4
But is the fact that assembly has no types even right? How can the computer differentiate between the two comparisons if there are no types?
bool biggerSigned(const int8_t* s, int limit) {
return *s > limit;
}
bool biggerUnsigned(const uint8_t* u, unsigned limit) {
return *u > limit;
}
When looking at the assembly, we see that registers don’t have types but assembly does.
Depending on the signedness, we use different assembly instructions.
In this case, either set if less setl for the signed case, or set if below setb for the unsigned case. On x86 less and greater means signed, while below and above indicate unsigned comparisons.
; *s > limit (signed)
movsx eax, byte ptr [rdi] ; sign-extend s into register
cmp esi, eax
setl al ; set al=1 if less (signed)
; *u > limit (unsigned)
movzx eax, byte ptr [rdi] ; zero-extend u into register
cmp esi, eax
setb al ; set al=1 if below (unsigned)
Notice that the load instruction differs too: movsx sign-extends the signed value, movzx zero-extends the unsigned one.
The same holds, e.g., for division instructions or moves with either zero or sign extension.
So the type is implicitly given by choosing the right instruction.
When reading assembly, we can still infer the data type in most places, but that’s quite tedious.
Encoding the type information in the operations means that whoever or whatever writes the assembly needs to keep track of the types. While this is standard procedure for compilers, it’s quite demanding for programmers, which is one of the reasons why most people don’t program in assembly any more. Tracking types by hand opens endless room for errors. Unless, of course, you have always been curious what sqrt(π) is.5
High-Level Programming Languages
Now let’s go to the other extreme: how do high-level languages handle number types? At the bottom of the ladder, JavaScript only has support for doubles and not even integers.6 PHP at least stores integers and floats differently. Neither differentiates between signed and unsigned, a clear sign of how far removed from the hardware these languages are.
Java, R, and SQL are a step up: they distinguish between integers and floats, so you won’t accidentally mix them and get flaky results due to numeric instabilities. But signed and unsigned remain the same type here too.
Java noticed the gap about 10 years ago and added the Integer.divideUnsigned function, and for PostgreSQL you can install an extension for custom unsigned types. Some control, but not the full picture.
Systems Programming
Full control over the datatypes, however, is crucial for systems programming. If you disagree, think of the first time you had to debug code like this:
unsigned count = 10;
while (count >= 0) {
std::cout << count << '\n';
count--;
}
If you don’t immediately see the problem, think of when count >= 0 holds true and why the answer is always true!
Static type checking can do a lot of good here. It’ll warn you at compile time that your code won’t terminate.
The mirror image happens with signed values. A classic trap is a count that can go negative meeting an unsigned loop bound:
int n = count_results(); // -1 on error
for (size_t i = 0; i < n; ++i) {
process(buffer[i]);
}
Signed intuition says that if n is -1, then 0 < -1 is false, so the loop body never runs. But n is compared against size_t i, so it is implicitly converted to SIZE_MAX, which is the largest unsigned value. Now 0 < SIZE_MAX is true, and the loop you expected to skip on error instead runs far past the end of the buffer β reading out of bounds almost immediately, and, absent a crash, looping for about 200 years on a 3 GHz machine.7
Both bugs have the same root cause: the programmer’s mental model uses signed semantics, but the machine applies unsigned arithmetic. This is also precisely why SQL’s NULL is a better tool than -1 for representing missing values.
Nullability vs Unsignedness
The intent of -1 in count_results() in the previous example was to mark an invalid value, since a count cannot be negative. The only reason it’s declared an int was the error case.
Comparing nullability with unsignedness seems odd at first glance. But they have two things in common. First, strictly speaking, neither is a first class citizen of the SQL standard. Nullability is expressed as a constraint, and unsigned simply is not defined. And second, you often use them to report invalid results, as shown above.
-1 to Mark Invalid Numbers
Way before C++ had optionals, SQL had nullability. This prevents programmers from the unfortunate habit of using -1 or even worse 99998 or January 1, 17539 for invalid values.
Using negative numbers just for error codes wastes half of the number range, which is by far not the worst thing here. Imagine your unsigned data neatly stored into an int column with some -1 outliers. You cannot take an average, or sum. You always need to handle your special values.
SQL nullability gives you a better tool: instead of hijacking a valid number to mean “nothing”, you declare that the value simply does not exist. No magic constants, no corrupted aggregates, no silent bugs.
The number zero is not the same as nothing, like a tree without leaves is not the same as no tree.
Constraints in SQL
You can express unsigned numbers in plain PostgreSQL as:
CREATE TABLE inventory (
product_id INTEGER,
quantity INTEGER CHECK (quantity >= 0)
);
This gives us few advantages but big disadvantages. On the upside, we now have positive numbers in the column. But the price we pay is that we waste half of the representable range and have to evaluate the constraint for each compute step. You add two numbers, check the constraint, insert one, check the constraint. And you cannot even store larger numbers here. So it’s not worth it.
Furthermore it gives you a false sense of safety. It only guarantees that the values stored in the table are positive, not that they stay positive during a query. Subtract two quantities and you are negative again, so nothing downstream can rely on it either.
So we need both: values that may be absent (NULL), and values that are never negative (unsigned). SQL gives us only the first one.
Unsigned Types in CedarDB
The SQL standard does not define unsigned datatypes. To be fair to the standard, it also does not define how to page through a result set, so unsigned numbers are in good company here. The common workaround is constraints, but like NOT NULL, it makes more sense to implement the type properly. This gives it a wider range and avoids the overhead of constraint evaluation on every operation.
At CedarDB we believe you should store data in its most natural representation and avoid unnecessary conversions. So we expose the unsigned types we already used internally directly to the user. We used this as an opportunity to refactor our type system, making it easier to add new types and functions going forward.
The driving motivation for integration was Parquet. Parquet’s integer type carries a signedness flag right next to its bit width, and files in the wild use it for identifiers, offsets, counters, and byte sizes. If you are parsing Parquet data types, we can use the native unsigned type directly, otherwise UInt64 columns would have to be widened to 128-bit numerics just to avoid overflow. That costs memory and speed on every single value, for data that would perfectly fit into 64 bit wide registers.
Unlike in C and C++ which inherited it, unsigned does not lead to silent wrap-arounds. We check for overflow on signed and unsigned arithmetic alike, so subtracting 5 from a quantity of 3 raises an error instead of handing you 4294967294. How we do that without giving up performance is a story of its own, in our posts on overflow handling and vectorized overflow checking.
Unsigned types cast implicitly to any type that can always hold them, so mixing them with signed integers just works. Explicit casts let you convert back to unsigned whenever needed. So if you choose not to use unsigned numbers, you will never know they exist.
Using Unsigned Numbers
Everything sounds nice and easy, and using them is the same. Just declare the column with the type you want:
CREATE TABLE inventory (
product_id uint4,
quantity uint4
);
If you already worked with Parquet files following our examples, chances are high you’re already working with unsigned numbers and didn’t notice.
You can find more examples in the docs.
Making unsigned a first-class citizen throughout the whole code-generating system takes more than just adding it to the catalog. In the next blog post we go from the ground up through our type system. We will look where sign information is tracked and where it deliberately is not, why PostgreSQL’s oid is an unsigned in disguise, and what the System V ABI forgot to specify.
Want to see it in action? Load a Parquet file into CedarDB and the right unsigned types come along for free.
-
Although money is a decimal, it does not have to be. Reporting your net worth in cents is both technically correct and psychologically effective. ↩︎
-
How a character turns into bytes depends on the encoding. The same emoji is
0x00 0x01 0xF6 0x00in UTF-32BE, and Python’s'π'.encode('utf-32')even prepends a byte order mark. Some emoji are not a single codepoint at all, but a sequence glued together with zero-width joiners. This article covers the rest. ↩︎ -
Reading four bytes as one number is itself an interpretation. We use the big-endian reading here, the order we wrote the bytes in. On a little-endian machine such as x86, loading the same bytes into a
uint32_tgives you 2157486064 instead. ↩︎ -
Yes, there are different registers for integers and floats. You can also store integers in vector registers for SIMD processing, or floats in regular registers for bit tricks. ↩︎
-
It’s
NaN.sqrttakes a float, and as a float π is negative. ↩︎ -
JavaScript engines do support integers internally, but only as a storage optimization for typed arrays, not as an exposed type. ↩︎
-
Yes, that’s an em-dash I put there. I liked to use them before they became a symbol of LLM generated content and it’s time, we are taking them back. For now I just put one into the post to not overdo it. ↩︎
-
In METAR, the standard format for aviation weather reports, horizontal visibility is given in meters and caps out at four digits, so
9999means “10 km or more” rather than “9,999 meters”. See the METAR explanation in the IVAO documentation. ↩︎ -
Microsoft’s Date Data Type documentation for Dynamics NAV. The date range starts at January 1, 1753, which is the lower bound of SQL Server’s
datetime, which in turn dates back to Britain switching to the Gregorian calendar in 1752. ↩︎