Find outlier statistic in SQL server?
In 2016 SP2 / 2017, you can generate an actual plan, and it will tell you what statistics were used. In older versions, you could do the same, but use trace flags as Paul White describes here. But I believe you are right, updating the statistics triggers a new plan, but updating them is not what leads to better plans, its simply the new plan that's generated the first time after the stats update. you should figure out why the plan is going wrong in the first place. 

Since you mention that it is a search procedure, I'm going to guess this is a parameter sensitivity issue (seeing the procedure definition and some typical calls will help confirm). There are two thoughts here:


If the problem is due to parameter A sometimes being supplied and sometimes not, consider dynamic SQL. You build the query only with the WHERE clauses that involve supplied parameters. This lets SQL Server optimize differently for each unique combination of parameters (highly recommended to combine with the instance-level optimize for ad hoc workloads setting).
If the problem is due to parameter A sometimes leading to a small number of rows and sometimes leading to a large number of rows, consider OPTION (RECOMPILE). This forces SQL Server to re-examine the parameters every time and optimize based on how many rows this set of parameters is likely to yield. There is some overhead to recompiling but it is often worth it for the stability it brings.


If both 1 and 2 are sometimes true, consider a combination - build the statement dynamically and add OPTION (RECOMPILE) to the end.

I talk about this in a lot more depth here:


#BackToBasics : An Updated "Kitchen Sink" Example


Sure, up to date stats help, but if you're simply re-using the first plan that gets compiled after stats are updated, they're worthless. In the case where the first time you search for last name like 'S%' and the second time you search for salary &lt; 70000, the second will use the wrong index. As for filtered indexes, yes, you're definitely going to want to keep those updated manually, since they're not likely to ever fall into the 20% threshold (or the new one in place that mimics TF2371). But at least if you use dynamic SQL you will have a chance to use the filtered index plan when (and only when) it's appropriate.

Some other reading:


Why is my query suddenly slower than it was yesterday?