@Anonymous
StartsWith is definitely delegation friendly for SharePoint. Of course the limitation is the text string typed by the user cannot appear in the middle of the word. You could implement StartsWith in a ComboBox put putting this code in the Items property
Filter(your_datasource_name,StartsWith(your_column_name,ComboBox1.SearchText))
You are correct that SharePoint is not a great option if using SEARCH for more than 2,000+ records is a must. SQL or CDS would be the first choice but they carry additional expenses. My only other idea would be to somehow "pre-filter" the results so they are less than 2,000 when searched. For example: if we are searching for an employee located at an office we would filter on the office first to limit the number or employees being searched. Not ideal but it does OK in some scenarios.
Mr-Dang has a few posts about overcoming delegation by pulling records into a temporary collection. However in your case 20,000+ records might impact performance. (I've not done this yet so I cannot guide you through it. Just wanted to give you ideas.)
https://powerusers.microsoft.com/t5/Building-Power-Apps-Formerly/Overcoming-the-500-record-limit-locally/td-p/18379
If you'd like to see SEARCH be delegated in SharePoint suggest you go vote for an Idea like this one.
https://powerusers.microsoft.com/t5/Power-Apps-Ideas/Search-function-delegation-for-Sharepoint/idi-p/107429
---
Please click "Accept as Solution" if my post answered your question so that others may find it more quickly. If you found this post helpful consider giving it a "Thumbs Up."