In his book Model Theory, Hodges remarks (rather tongue-in-cheek, if I understood him correctly) that:
Some people have hoped, when they learned of (5.3) [that "ultrapowers give arbitrarily large elementary extensions of infinite structures"] and (5.4) [the Keisler-Shelah theorem], that ultraproducts might make it possible to do model theory without all the complexities of logic. Disillusionment set in when they found themselves faced with the complexities of boolean algebra instead.
Now, I understand that the ultraproduct construction works by defining an equivalence relation using an ultrafilter in the boolean algebra of the power set of the index set $I$, so there is some relation between these two notions (ultraproducts and boolean algebras). But I don't quite get what Hodges is driving at with his remarks. How is the complexity of an ultraproduct tied with the complexity of a boolean algebra? I'd be extremely grateful if someone could provide me with a working example of an intractably complex ultraproduct construction whose intractability results from the complexity of the boolean algebra behind the construction.