How to implement FNV-1(a) in SQLite?

Question

Moved

I originally posted this on SoftwareEngineering because that's where this related question was; but having looked into the Help in detail, I think my question is more on-topic for stackoverflow, and I'm moving it there. Will probably delete this question once the move is complete. Sorry I can't move the comments, which have been helpful, along with the question.

Original question

I'm trying to modify a SQLite query (in Android) to return its results in pseudorandom order. As in this question, the order needs to be stable over time (e.g. paging, screen rotation, etc.), so I can't just use ORDER BY RANDOM(). Instead I want to use a hash function that depends on a couple of input values that provide stability and sufficient uniqueness. One of these values is ROWID of the table, which is a set of integers fairly close together; the other value is more like a session ID, that remains invariant within this query.

According to this well-researched answer, FNV-1 and FNV-1a are simple hash functions with few collisions and good distribution. But as simple as they are, FNV-1 and FNV-1a both involve XOR operations, as well as looping over the bytes of input.

Looping within each row of a query is pretty awkward. One could fake it by unrolling the loop, especially if only a few bytes are involved. I could make do with two bytes, combining LSBs from the two input values (val1 & 255 and val2 & 255).

XOR isn't supported directly in SQLite. I understand A ^ B can be implemented as (A | B) - (A & B). But the repetition of values, combined with the unrolling of the loop, starts to get unwieldy. Could I just use + (ignoring overflow) instead of XOR? I don't need very high quality randomness. The order just needs to look random to a casual observer over small-integer scales.

So I'm wondering if anyone has already implemented such a thing. Given how widely used this hash function is, it seems like there would likely already be an implementation for this situation.

Here's my attempt at implementing FNV-1a:

SELECT ..... ORDER BY (((fnvbasis + val1 & 255) * fnvprime) + val2 & 255) * fnvprime;

I'm ignoring the fact that in FNV, the XOR operation (which I've replaced with +) is only supposed to affect the lowest 8 bits of the hash value. I'm also ignoring any overflow (which I hope just means the upper bits that I don't care about are lost).

For fnvbasis I'll use 16777619, and for fnvprime I'll use 2166136261. These are the specified values for 32 bit input, since I don't see a specified value for 16 bit input.

So is this a reasonable way to approximate FNV-1a in a SQLite query? Is there a better, existing implementation? I.e. will it actually produce an ordering that looks pretty random to a casual user, despite my mutilating the operations of the real FNV-1a?

Answer 1

I would do this: "calculate the pseudo-random order separately, and store it separately." Now you can JOIN by that table of randomly-ordered keys and thus obtain the selected sequence any number of times. The order will remain stable until you change it by recalculating the content of the randomization-table.

You could also in this way easily have an arbitrary number of separate generations of the random ordering, just by adding a new column to the table.