Same query plan, different data set, very different query duration SQL Server 2012
Do the percentages and query cost even mean anything? 


Not really--They have meaning, but they're unreliable. 


  are they referring to the estimated data from the query plan, and do not reflect the real cost? Otherwise how could the same join make up 39% of the "cost" for both, but one takes 2 seconds and one takes 47 seconds? 


Exactly--The cost is an estimate. If you look at the detail pop-up when you hover on an operator, you'll see that what you see as "Cost" in the graphical plan is actually "Estimated Operator Cost." It is based on the pre-execution estimate, and will be the same even when actual costs vary. 


  Is SQL server lying to me and the actual difference in cost is the "nested loop" for the inner join that produces the final row count even though it lists that as 0% of the cost?


It's not quite lying, but it's not reality either. Again, since these are based on estimates, they can be wrong. In particular, sometimes you'll see Cost% add up to more than 100%--another indicator it's not based on real performance.

There's a better way

IMHO, SQL Sentry Plan Explorer is the easiest way to look at the actual execution performance data. It will give you actual CPU &amp; IO information for each statement in your batch, which you can use to zero in on the most expensive parts of your batch. In this case, you can test the same statement for different customers and look at the actual execution results.

You might also want to try using SET STATISTICS IO,TIME ON and running the results through statisticsparser.com. That will give you a good sense of the IO/CPU differences between the two queries for different customers.