Diag 1. Notice the "Table Valued function [FulltextMatch]" is inside a nested loop, with 3628 rebinds. This isn't going to end well.
Our first thought: The full text index hasn't done an incremental update; so we did a Full repopulate index... No Change in performance.
Then I finally found an article that seemed relevant: "First: Make sure that your statistics for the table's index are up to date."
So, I looked up how to do it:
#1) Check when the tables index statistics were last updated on one of the table's indexes:
DBCC SHOW_STATISTICS ( "Table_Name_Here", PK_Table_Name_Here_Index) ;
And found that the date the stats were last updated was before we had inserted our new 3000 record set into the table. ( The index stats showed there was about ~3000 fewer rows than "actual" )
#2) We updated the index stats manually via:
UPDATE STATISTICS Table_Name_Here
And now, our full-text queries are all lightning fast, regardless of any added where clause and in the execution plan, our "Actual Rebinds" on the "Table Valued function [FulltextMatch]" went back to 1.
Diag 2. "Table Valued function [FulltextMatch]" now with a rebind count of 1 ( Its not inside a nested loop any more )
And now, to answer the underlying question:
Why weren't the tables index stats recalculated after the new data was entered? We're assuming at this point that it wasn't a sufficiently large insert to trigger the stats recalculation ( we inserted around 3% new rows ).
Perhaps in this case, the table just needs to have its stats recalculated manually since its a relatively small insert, but has a really high impact on full text search speed when not completed.