@matt_uk -
Short answer: Given your data source is SQL, I think you will be fine to use the Search function so long as:
- The column your searching on is a Text data type
- The overall formula/expression does not also include any non-delegable functions.
Long answer: There is nothing that will inhibit you from using large data sets - it is certainly possible to connect your Power App to a data source which has millions of records.
However, the key concept you will need to wrap your head around is delegation.
https://learn.microsoft.com/en-us/power-apps/maker/canvas-apps/delegation-overview
As with almost everything today, PowerApps must play well with smart mobile devices. As these devices are not as powerful or have as much memory as laptops and desktops, delegation was introduced as a mechanism for reducing the processing done on the device.
The basic principle is to push (delegate) as much processing down onto the data source as is possible, and have the data source do the heavy lifting and return the results back to the app.
For example, suppose my data source is SharePoint and contains 15 million rows. I could use a Filter function to return only rows where one of the Text columns in the data source equals a specific value. This will work perfectly fine because the Filter function is delegable with SharePoint.

image ref: https://learn.microsoft.com/en-us/connectors/sharepointonline/#power-apps-delegable-functions-and-operations-for-sharepoint
However, not all data sources support delegation (Excel) and not all functions are "delegable". Let’s suppose I now want to use Search function to return specific items in a Gallery based on a string entered in a Text Input box. I could certainly use the Search function, but that will only work on the first 500 rows in the data source. This is because the Search function is not delegable with SharePoint. (note, you can increase the delegation threshold to 2000 records via the settings menu).
There are no workarounds for functions which are not delegable. You can hide any delegation warning messages with workarounds, but the delegation will persist. However, as mentioned, Filter function is delegable. If you can pre-filter your lists using the With function based on a specific criteria that will return less than 2,000 rows, you can then perform a Search function on that smaller subset of data. For example we could have population data that has 5,000 rows of people per district, but if we know that each neighbourhood within those districts will return less than 2,000 rows, it is ok to use a non-delegable function within that smaller subset using delegable Filters.
Another robust and fast alternative is to use Power Automate to return specific rows based on your search criteria back into your app.
Back to your scenario, because your data source is SQL, we know the Search is a supported delegable function with Text columns and we also know that the Search function is case insensitive.

image ref: https://learn.microsoft.com/en-us/connectors/sql/#power-apps-functions-and-operations-delegable-to-sql-server

image ref: https://learn.microsoft.com/en-us/power-platform/power-fx/reference/function-filter-lookup