The sad state of foldcase and string comparisons
perl11.org
perl11.org
I've been trying to get some ideas together about how to get around these issues. The Unicode Comparison Algorithm doesn't clearly define how to do incremental comparison (for string sorting, or traversing a trie etc.), but it seems that ICU already does some optimizations, such as discarding the longest common prefix in its strcmp via binary comparison, and then only converting the distinguishing character position.
While we're at it here's a proposal for normalized keys in pg: https://wiki.postgresql.org/wiki/Key_normalization .