> is essentially a type of learned indexing, albeit not neural network based.

NN is just function approximation, why do you think that could not be a valuable part of the solution?

It seems like a dynamically adjusted/learned function approximator is a good general tool to most of these hard problems.