Is there a simple way to create a unique integer key from a two-integer composite key?

Question

For various reasons that aren't too germane to the question, I've got a table with a composite key made out of two integers and I want to create a single unique key out of those two numbers. My initial thought was to just concatenate them, but I ran into a problem quickly when I realized that a composite key of (51,1) would result in the same unique key as (5,11), namely, 511.

Does anyone have a clever way to generate an integer out of two integers such that the generated integer is unique to the pair of start integers?

Edit: After being confronted with an impressive amount of math, I'm realizing that one detail I should have included is the sizes of the keys in question. In the originating pair, the first key is currently 6 digits and will probably stay in 7 digits for the life of the system; the second key has yet to get larger than 20. Given these constraints, it looks like the problem is much less daunting.

Donohue

No DBA should let you get away with this - if need be, create a primark key column & use a unique constraint on the two columns – Kore

See Matt Ball's answer for duplicates – Kore

Answer 1

Multiply one with a high enough value

SELECT id1 * 1000000 + id2

Or use text concatenation:

SELECT CAST(CAST(id1 AS nvarchar(10)) + RIGHT('000000' + CAST(id2 AS nvarchar(10)), 6) AS int)

Or skip the integer thing and separate the IDs with something non-numeric:

SELECT CAST(id1 AS nvarchar) + ':' + CAST(id2 AS nvarchar)

Inhibitory

Answer 2

You can mathematically prove this is impossible if you want the resulting key to comprise the same number of bits as its two components. However, if you start with two 32 bit ints, and can use a 64 bit int for the result, you could obviously do something like this:

key1 << 32 | key2

SQL Syntax

SELECT key1 * POWER(2, 32) + key2

Market

This. Of course, make sure you include sanity checks on the two integers to make sure they're both 32 bits. (Assuming you're using signed integers, they'll need to be less than 2^31, or 2,147,483,648). – Radman

Sadly, I'm doing this in T-SQL and lack a bitshifting operator. – Donohue

Then fake that mother with multiplication. :-) I THINK "key1 * 2^32" accomplishes the same thing, but my math is a tad rusty. – Radman

From dbaspot.com/forums/sqlserver-programming/…, To achieve @i << @j: SELECT @i * POWER(2, @j) – Cori

+1 even though if key1 is a 32 bit integer then key1 << 32 == 0 (you should cast it to 64 bits first) – Chook

Answer 3

This has been discussed in a fair amount of detail already (as recursive said, however, the output must be comprised of more bits than the individual inputs).

Mapping two integers to one, in a unique and deterministic way

How to use two numbers as a Map key

http://en.wikipedia.org/wiki/Cantor_pairing_function#Cantor_pairing_function

Cori

Pretty complicated. Those answers lost me at "bijective". :p – Collotype

@Tchalvak: if you're not much of a math person just keep wikipedia-ing the terms you don't know! (Personally, I really enjoy "educating" myself with that kind of productive procrastination.) It boils down to pretty simple stuff; using the fancy math words just keeps definitions concise and exact. – Cori

Answer 4

You can only do it if you have an upper bound for one of the keys. Say you have key1 and key2, and up1 is a value that key1 will never reach, then you can combine the keys like this:

combined = key2 * up1 + key1;

Even if the keys could theoretically grow without limit, it's usually possible to estimate a save upper bound in practice.

Manhour

I like, cleaner than my answer was. Just have to make sure you always "encode" the keys in the predefined orders and "decode" them back in the same order. – Collotype

Answer 5

As I like the theoretical side of your question (it really is beautiful), and to contradict what many of the practical answers say, I would like to give an answer to the "math" part of your tags :)

In fact it is possible to map any two numbers (or actually any series of numbers) to a single number. This is called the Gödel number and was first published in 1931 by Kurt Gödel.

To give a quick example, with your question; say we have two variables v1 and v2. Then v3=2^v1*3^v2 would give a unique number. This number also uniquely identifies v1 and v2.

Of course the resulting number v3 may grow undesirably rapid. Please, just take this answer as a reply to the theoretical aspect in your question.

Corpulent

Answer 6

Both of the suggested solutions require some knowledge about the range of accepted keys.

To avoid making this assumption, one can riffle the digits together.

Key1 = ABC => Digits = A, B, C
Key2 = 123 => Digits = 1, 2, 3
Riffle(Key1, Key2) = A, 1, B, 2, C, 3

Zero-padding can be used when there aren't enough digits:

Key1 = 12345, Key2 = 1 => 1020304051

This method also generalizes for any number of keys.

Selfreliance

Answer 7

wrote these for mysql they work fine

CREATE FUNCTION pair (x BIGINT unsigned, y BIGINT unsigned) RETURNS BIGINT unsigned DETERMINISTIC RETURN ((x + y) * (x + y + 1)) / 2 + y;

CREATE FUNCTION reversePairX (z BIGINT unsigned) RETURNS BIGINT unsigned DETERMINISTIC RETURN (FLOOR((-1 + SQRT(1 + 8 * z))/2)) * ((FLOOR((-1 + SQRT(1 + 8 * z))/2)) + 3) / 2 - z;

CREATE FUNCTION reversePairY (z BIGINT unsigned) RETURNS BIGINT unsigned DETERMINISTIC RETURN z - (FLOOR((-1 + SQRT(1 + 8 * z))/2)) * ((FLOOR((-1 + SQRT(1 + 8 * z))/2)) + 1) / 2;

Belletrist

Answer 8

At the risk of sounding facetious:

NewKey = fn(OldKey1, OldKey2)

where fn() is a function that looks up a new autonumbered key value from a column added to your existing table.

Obviously, two integer fields can hold exponentially more values than a single integer field.

Benham

Answer 9

Why don't you just use ROW_NUMBER() or IDENTITY(int,1,1) to set new ID? Do they REALLY need to be in relation?

Claman