I made an assumption on how natural ordering works and that was for the first time I've seen screwing up the ordering of records in a RocksDB database.
It's funny I used Gemini 2.0 to evaluate how natural ordering of two ULIDs. ULID is lexicographic sort friendly DUH. it was confident that the correct ordering is what natural sort should resolve to. Wrangled my head until finally starting getting code out to analyze the sort step by step and that's where it dawned on me. 4442 is going to be greater than 7CYS even though lexicographically 7CYS is greater. Natural sort will see the 7 and stop there then pick out the 4442 and then compare those. It compares numbers to numbers and alpha to alpha as it traverses the string.
I asked a bunch of question on a hybrid sort that would give me proper sorting for ULID based then UUID based, of course AI naively wants to parse the strings. Not ideal and slow imho. I figured why not just parse randomly selected segments in linear order and do natural, but again of course natural sort already kind of does this.
Messing around with the segments idea with regards to random lengths did give me the idea for why not instead compare lengths of keys and then choose the sort based on that. If the keys have the same length, choose lexicographic compare then if different lengths use natural compare. I am typically traversing according to a common prefix, so this actually works for my case since when I am traversing RocksDB keys.
I call this the Natural Lexicographic Hybrid sort. The bad part is that I have to migrate existing RocksDB databases to it since changing the comparator is a destructive operation and messes up compacted SSTs. I only worry about the idea of it possibly being an unstable sort, but we will see.