space filling curves

From: <shahbazc_at_gmail.com>
Date: 18 Feb 2005 01:59:09 -0800
Message-ID: <1108720749.648131.53980_at_z14g2000cwz.googlegroups.com>

I recently started reading about various ways of making various functions of a DB faster...and I keep running into space filling curves. Unfortunately, I just can't grasp the concept. Following is what I understand so far, I'll appreciate it if someone could point out any misconceptions.

>From what I've read, space filling curves allow one to 'collapse' many
dimensions into one...which is easy to manipulate (test for equality, etc.)
z-order space filling curve is formed by interleaving bits of various dimensions:
name,social security,gpa <=each must have a binary representation. after normalizing their bitstring (making sure they are of the same length...probably not necessary), combine them in the following manner: name: 1010, soc: 1100, gpa: 0001
interleaved bits: 110 010 100 001
Now sort your data according to the interleaved bits

Now, here's the part I don't understand: somehow data sorted according to this new interleaved bit string will allow me: -access to all the data in a sorted according to any key with just one pass?
That is what the descriptions seem to be implying, but clearly that is not true:
Interleave:
Decimal Binary Interleaved Interleaved Decimal

0|0|0 >> 00|00|00  000 000       0
0|0|1 >> 00|00|01  000 001       1
0|1|0 >> 00|01|00  000 010       2
...
1:2:1 >> 01|10|01  010 101       21
...
2:0:1 >> 10|00|01  100 001       33
...
2:2:0 >> 10|10|00  110 000       48

Now let's say I was doing a distinct or an aggregate on the second column and I expected it to be in order...since I applied z-order...clearly 0,0,1,2,0,2 is NOT in order! So what did I miss?

Also, it seems the hilbert curve is 'better' than z-order somehow, but I couldn't figure out how to build it. It isn't simple bit interleaving, since that gives us z-order...right? Received on Fri Feb 18 2005 - 10:59:09 CET