Any suggestions? I'm guessing the problem is with the absurd over-estimation on the nested loop under the sort node, but I'm not sure why it's so bad.
After looking at this some more, I'm pretty confused at both of 8.4.2's plans. They both have a Nested Loop node in them where the expected row count is a bit over 2 million, and yet the inner nodes have expected row counts of 1 and 152. I was under the impression that a nested loop between R and S would return no more than R*S?