If the data is literally not changing at all between when the query was fast to when it became slow, then likely you're experiencing a Parameter Sniffing issue. (Note this can also happen even when the data has changed, but it doesn't require the data to change for it to happen either.) This happens when parameters (such as in a stored procedure for example) are used in the query.
The reason it happens is because on the first run of the procedure when the Execution Plan is being generated, it's optimized for those first set of values supplied to the parameters of the procedure, then that query plan is cached and re-used for future runs of the same procedure (regardless of what values are passed in as parameters again).
The subsequent executions of the procedure with varying parameters might not always have the most optimal Execution Plan when the original cached plan is reused. This is dependent on a few things, bust mostly the Cardinality of your data. Generally it happens when the Cardinality of the parameters used when the Execution Plan was originally generated and cached varies a lot from the Cardinality of the values of the parameters passed in to the procedure on subsequent executions.
For example, imagine a Cars table that had 1,000,000 rows, and on 999,999 rows the Manufacturer was Honda, but in 1 row the Manufacturer was BMW. The most optimal Execution Plan to find and return the 1 row for BMW would certainly not be the same as to find and return the 999,999 rows for Honda. The uniqueness of the values within the table is the difference in Cardinality between the two values. But with a stored procedure because the Execution Plan is cached on first run, the same plan which would be sub-optimal for Honda would be used if the first time the procedure was ran BMW was passed into the parameter. (E.g. in this case, an Index Seek operation would be most performant for BMW but would be slow for Honda which would be better off with an Index Scan.)
Cardinality Estimate Issues
The previously discussed Parameter Sniffing issue is usually the result of Cardinality Estimate issues (i.e. it is a sub-problem to another problem). But you can run into Cardinality Estimate issues even without Parameter Sniffing issues.
In simplest of terms, Cardinality is the uniqueness or number of rows that exist for a specific value of a column in a Table. The Cardinality of your JOIN, WHERE, HAVING clauses' predicates impact how SQL Server's Engine chooses to find and filter down the data. This is because different operations are more performant for returning something with low Cardinality (low number of records contain that value, so it's highly unique) vs something with high Cardinality (large number of records contain that value, so not very unique).
For example, scanning the data is likely to be more performant of an operation when a large amount of records are expected to be returned for your JOIN, WHERE, HAVING clauses as opposed to seeking which is more performant for a small number of rows. Therefore different Cardinalities result in different operations for finding and filtering the data, which ultimately results in different Execution Plans.
One common thing that can cause bad Cardinality Estimates are using functions (especially non-deterministic functions) in the JOIN, WHERE, or HAVING clauses. This is because it complicates the ability of the engine to accurately determine the Cardinalities of the values of those functions during the Execution Plan generation process. Other things that can complicate your predicates are using arithmetic operators, and comparisons between different data type fields which result in implicit conversion (e.g. if one field is NVARCHAR and is compared to another that is VARCHAR).
If your queries operate on small tables or only return a small amount of data, then you may not realize you have a potential Cardinality Estimate issue. Sometimes they don't expose themselves initially until after only a small amount of data has changed in one of the underlying tables. This is definitely something you be experiencing but we wouldn't know for sure without your Execution Plans.
The other things you could be experiencing if it's not a Parameter Sniffing issue, and your data has changed between fast and slow runs, is outdated Statistics. (Though this is less likely the case unless your data is changing a lot or your server was incorrectly configured to not auto-update statistics.)
SQL Server routinely stores Statistics about the Cardinality of the values within the Table so that it can make accurate decisions on the operations to use when generating the Execution Plan. This is to try to ensure the most optimal Execution Plan is generated.
On Tables that change rather frequently, their Statistics sometimes get stale and can result in sub-optimal Execution Plans being generated for them, and therefore those Statistics need to be manually updated.
Indexes are a way of storing the data in your tables in an efficient logical data structure, a B-Tree. Without a Clustered Index the logical data structure your tables are stored in is a Heap. A Clustered Index converts that Heap into a B-Tree which is a lot more efficient for searching. The Clustered Index determines the actual ordering of your entire table itself.
Nonclustered Indexes store copies of specific fields from your table into their own B-Trees sorted on those fields themselves. They also store a reference to the Primary Key of the table in case they need to find more information from the table that isn't stored in the Nonclustered Index itself.
It is possible that if your tables were missing the appropriate indexes that your queries would be fast enough with a small amount of data but continue to slow down as the tables grew. Furthermore it is possible if you had the appropriate indexes when the queries were originally written, and someone added, changed, or removed one of those indexes, a different Execution Plan was generated that was sub-optimal. (Yes, something as simple as adding an additional index on a table can cause an existing optimal Execution Plan to no longer be used for a specific query and instead a sub-optimal plan can be used. This is on the fault of the query optimizer of the SQL Server Engine and the statistics on that table.)
Additional Resources - Specific Topics
RedGate - Execution Plan Basics - This is a great start to end overview of what is an Execution Plan, how are they created, and will help you understand their purpose and how to use them to debug performance issues. I find the Execution Plan can answer 95% of the issues someone is experiencing, and even proactively tell you about an issue that might not currently be affecting performance but can certainly affect performance in the future.
Brent Ozar - How Execution Plans Are Made - This is a good video to give a little bit of a visual with examples on how Execution Plans are formed and to help you think a little bit like the SQL Server Engine.
Brent Ozar - Watch Brent Tune Queries - This is a good video to understand the key things to look for when query tuning. You'll get a more intimate understanding of how to use the Execution Plan to help you determine what the cause of your performance problems were. You can even check for some of these things proactively after you've written a query.
Brent Ozar - Watch Brent Tune Queries (Again) - This is Brent doing basic query tuning again, so while not the exact same video the concepts are redundant (in a good way) to help you catch on to the things one should do, even proactively after you write the query, to verify its performance will hold true in the future.
SQL Server Central - Statistics And Cardinality Estimation - Cardinality Estimation is a very important thing to understand (and is slightly more complex than understanding basic things like proper indexing). This article introduces you to what it is, and what it's purpose is in SQL Server. I highly recommend looking into other resources as well (I'll continue to update my answer when I find other good ones). This is something you can also proactively check a lot of times by looking at the Execution Plan of your query right after you've written it. There's specific things you can look at in the plan like the Estimated Number of Rows vs Actual Number of Rows being far off from each other (generally a magnitude off) that indicate when you have a Cardinality Estimate issue.
Additional Resources - General
(Hardening @LadyBug1's comments into my answer for historical reference since they are great suggestions.)
These references are generally great places to learn about SQL Server, it's engine, and how to develop for your database optimally. They are of some of the most well regarded members of the SQL community:
- Brent Ozar
- Kendra Little
- Paul Randal
- Any of Aaron Bertrand's Blogs: SQLPerformance.com, SQLBlog.org, MSSQLTips.com
- Erik Darling
- Jonathan Kehayias
- Paul White
- Grant Fritchey
- RedGate's Simple Talk Blogs
If you can update your post with a specific example (query, data used for parameters, and the Execution Plan(s)) we can more definitively tell you what the issue is and point out how to determine it.