[trhway]

for equality predicate you can just use hash based index, for range search the situation is of course worse, yet you can have a somewhat like a partially/probabilistically preserving order hash so that you can produce a number of candidates orders of magnitude less than the whole table scan.

[RobLach]

The mere fact that you did not need to scan the entire db means the data was not securely encrypted in the first place.

[bawolff]

But then you are not using FHE, but something with much weaker security properties.