We have a large (10,000+ lines) procedure that typically runs in 0.5-6.0 seconds depending on how much data it has to work with. Over the past month or so it has started taking 30+ seconds after we do a statistics update with FULLSCAN. When it slows down, a sp_recompile "fixes" the issue, until the nightly statistics job runs again.
By comparing the slow and fast execution plans, I have narrowed it down to a specific table/index. When it runs slow it is estimating ~300 rows will be returned from a specific index, when it runs fast it estimates 1 row. When it runs slow it uses a Table Spool after doing a seek on the index, when it runs fast it doesn't do the Table Spool.
Using DBSS SHOW_STATISTICS, I graphed out the index histogram in excel. I would normally expect the graph to be more "rolling hills", but instead, it looks like a mountain, the highest point being 2x-3x higher than most other values on the graph.
If I update statistics on it, without FULLSCAN, it looks more normal. If I then run it with FULLSCAN again it looks like I described above.
This feels like a parameter sniffing issue, and specifically related to the (seemingly) weird index distribution above.
The proc takes in a table valued parameter, can parameter sniffing occur on a table valued parameter?
EDIT: The proc also takes 12 other parameters, some of which are optional, two of which are a start and end date.
Is the histogram odd, or am I barking up the wrong tree?
I am certainly comfortable trying to adjust the query and/or try to adjust my indexing. If that is the fix that is great, at that point my question is more about the skewed histogram.
I should mention that this is a PK IDENTITY clustered index. We have two systems that talk to each other, one a legacy system, one a new home-grown system. Both systems store similar data. To keep them in sync the PK on this table in the new system is incremented when things are added to the old system, even if the data doesn't come over (a RESEED is done). So there could be some gaps in the numbering in this column. Records are rarely, if ever, deleted.
Any thoughts would be greatly appreciated. I am more than happy to gather/include more info.