For me it's not actually about that getCost() gets called first, but in general that getCost() is supposed to just calculate the cost, without side effects. Even if this side effect is within the specification, it's just unusual and unexpected. I would rather have a solution where getCost() only calculates the cost and the lookup is done within query(). I think we can find a solution. It's also problematic that getCost() returns 0 so that the cost is smaller than the cost of the regular jcr:uuid index. It does solve the problem, true, but it's not what I had in mind originally.
About naming: I would probably call it "TransientUUIDIndex" because it operates on the transient space. Later on, if we want to make it more generic, we could call it "TransientIndex".
What about making it explicit in the query that the result should include transient changes? So the query would be changed to "select ... from ... where [jcr:uuid] = $id including transient". Then the QueryIndex interface would be extended with a new method "boolean includesTransient". That way, if the query is "including transient", the query engine would only use indexes that do support transient changes.
I'm OK to all those changes myself later on, as I don't think they are urgent.
I wonder if both the NodeState and Root given to the query actually include the node?