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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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)

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.

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.

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;

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.

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?