How to efficiently iterate a supervised model over the Cartesian product of very large number of records?
This problem is called record linkage and there are methods to avoid iterating the whole cartesian product. The main method I know was called "blocking" and consists in doing a first "rough" pass to create groups of matching candidates (the "blocks"). For example you can create groups which contain at least X n-grams in common. This can be done through one linear iteration through all the entities, storing them in every applicable bin based on their n-grams (an entity can be stored in several bins). I assume that some kind of clustering could also be used to generate the groups of similar entities. Then you end up with multiple groups of smaller size, and you run the cartesian product comparison on every group individually. This can greatly reduce the complexity.

note: I was working on this maybe 10 years ago so there might be more recent approaches.