On rereading, it seems like what may be happening is simply that the problem isn't very large (10-100,000 rows) and doesn't need to be solved very fast (a few minutes), and so the standard Prolog search strategy may have worked just fine. A good example of avoiding unnecessary over-engineering.
Without knowing the details of the problem it's hard to be sure, of course. Combinatorial explosion can make even searches involving a rather small number of choices take impractically long to finish. But that depends on the structure of the search problem.
Edit: The author says in the comments on the original post that he used SWI Prolog, which I believe doesn't do anything special in its search strategy, although it does have support for CLP.