Changing stored procedure parameter results slow stored procedure performance I have a stored procedure to fetch all users in the database. To do this it queries a view which is composed on two tables: Users (holds basic info like username) and UserPortals (maps users to certain sites). 

The only parameter that changes between executions is the 'PortalId'. 
Here is an execution plan that returns results in about 1 second
However, when changing the PortalId to a different value it takes about 21 seconds. As seen here. The slower query is for a PortalId of a newer portal so the data is presumably further towards the end of the table. Does this matter?

The interesting difference in the execution plans is that for the slower query, all rows in the Users table are scanned, however this is not the case for the faster one.

Are there any ideas on how to make the slower query faster? I assume it is an indexing problem.

Note: I have tried adding the recommended index and it actually resulted in worse performance.
One of the first things to look at in an actual execution plan, especially on the most expensive operations, is the estimated vs the actual row counts, executions, et cetera.

Often, when the estimated numbers are significantly off from the actual numbers, it indicates that the statistics for the table are out of date. This can cause the query engine to choose a bad plan. Based on what it knows about your data, the plan makes sense; however, enough of the data has changed since your statistics were last updated that the plan's not the best option for actually returning your data.

If you don't have a job that regularly updates statistics, trying updating the statistics on just this one table (or, more likely, the tables involved in this view), and see if the query speed becomes more predictable. I'd recommend setting up a statistics update job to run on a regular basis (probably at least weekly).

Note that, as the stored procedure is recompiled each time through, some time is spent calculating that optimal plan. If the speed of the stored procedure becomes more predictable, you may want to consider trying it without the WITH RECOMPILE; depending on the complexity of the query, the cost of the recompilation might be higher than the cost of using the same plan with different parameters.