Eg you have to go to quite a bit of effort to construct a knapsack problem that's hard to solve.

First, you start with an NP problem where virtually all instances are expected to be hard, like finding the pre-image to a given sha256 hash digest. Second, you sample a random instance in O(n). Third and last, you reduce this problem from the original sha256 inversion to knapsack. You can do this in polynomial time, because knapsack is NP complete.

Note for the pedantic: inverting sha256 is certainly in NP, but it's not expected to be NP complete.

Second note for the pedantic: because sha256's digest has a specific fixed size, you can technically solve any problems around it in constant time with a big lookup table. So you should replace sha256 in my example with any other problem that's expected to be hard on average.

https://www.postgresql.org/docs/17/geqo-pg-intro.html

The theory being an exhaustive search of all possible query plans is np-hard and would take too long, so you do a limited, iterative, best fit search.

My understanding is it never worked super great and would only be used if your query exceeded some high level of complexity. I distinctly remember it being removed at some point, but I see it mentioned in current docs, so I am probably wrong about that.

Anyway I wonder if, with some of the new advances in machine learning, it would be worth revisiting this approach to optimization.

Beam search approximates NP-hard solutions (make wider beam, have better approximation), is very old and it is used in SQLite query planner: https://www.sqlite.org/queryplanner-ng.html