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

Question

(Moved from https://softwareengineering.stackexchange.com/questions/406813/how-to-implement-fnv-1a-in-sqlite)

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 repeated queries (e.g. due to 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 a unique ID column of the table, which is a set of integers fairly close together; the other value is more like an session ID, also an integer, 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 % range;

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, which 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. For range I'll use a prime number that's greater than the expected number of rows returned by this query.

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

Inspired by comments from rwong and GrandmasterB on the previous attempt at this question before I moved it, I decided I could precompute the first iteration of FNV-1a's loop, i.e. the hash based on the unique ID column of the table. The precomputed column, fnv1a_step1, is set to

(fnvbasis ^ (ID & 0xFF)) * fnvprime

Because this value is precomputed on each row of the table separately, it can be supplied by the app and doesn't need to be expressed in SQLite; hence the use of ^ (XOR) above. Also, if ID is a string, we can compute an 8-bit hash value from it in Java or Kotlin as well. But we could even use

(fnvbasis + (RANDOM() & 0xFF)) * fnvprime

(back to using + if doing this in SQLite) because the value is only computed once, and therefore is stable even when computed from RANDOM().

The second iteration of the FNV-1a loop can be computed pretty simply in the ORDER BY clause of the query, using the current session ID, so it produces a different-but-stable ordering for each session:

ORDER BY (fnv1a_step1 + sessionId & 0xFF) * fnvprime % range;

I've implemented this in my app, and it seems to work, to my requirements. The order is stable within a session, but is different in each session.