So, how does immutability matter if we deal with the database -- which is what holds the state, and is obviously mutable.
I.e., you can ask to look at the entire database as it was yesterday, and run arbitrary queries against it.
You can also do speculative updates to it, in the sense of "show me the entire database as it would be if I were to have pizza for lunch".
It models this as a strictly linear succession of assertions and retractions of facts. Yesterday, `A` was true, today `A` is no longer true. While this new fact is recorded, it doesn't change the fact that yesterday, `A` was true.
What we see in reality is that append-only database is unusable without making additional "projections" or whatever you call them, databases that are ready to be queried/updated, with maybe specific denormalizations, indexes and so on.
And oh, btw, those later databases are not "imutable".
I highly recommend the talk “Domain modeling and with Datalog”[1]. It gives an explanation of how all this works, including indexing.