When does the core search module become worth using? I mean, is there any approximate number of nodes or just website pages (or any other measures of website size) when the out of the box Drupal search module is still worth using? I understand that much depends on webserver, but there should be some general guidelines. E.g., should I use the core search module if I have a Drupal website with 5K nodes?
It really depends on your situation.

You should use Drupal search core module only when you don't have any performance issues (as it's using database backend), your site is not so complex (in terms of search functionality) or you're not advanced user and you are not looking to make make your site more complex than already is.

Please note that high traffic sites running search queries against the database can affect overall performance especially when the database becomes the bottleneck. Secondly Drupal core search doesn't scale much.

Therefore using Search module from Drupal core it's not adequate when you have thousands of nodes on site. In this case you should use either Search API (with solr backend) or Apache Solr Search modules. Using Apache Solr provides advanced and accelerated search platform which features faceted search (Facet API), searching multiple sites, real-time indexing, dynamic clustering, NoSQL features, indexing attachments and many more. It's a great way to have fast access to big data on a budget. Basically Solr solutions are designed for searching the same way as Search API is designed to replace the core "Search" module.

It's also worth to mention about Elasticsearch as alternative for Solr, but it's topic for another discussion. The decision to choose whether Elasticsearch or Solr really depends on the project requirements and the decision needs to be made by experienced Drupal developer or solution architect.

In overall, Databases and Solr have complementary strengths and weaknesses, so you've to investigate these further depending on your project. However core search has a very limited functionality.

Please find the following chart which shows Drupal core's search performance vs. Solr based on its execution time.






  The results are pretty clear: Drupal core's search takes longer as you put more words in the query. This may seem fair enough, as it makes the searching more complex. But when using Solr you can't barely see any difference at all. It doesn't really matter if you search for 1 or 6 keywords. The response time for a page is almost the same.
  
  DISCLAIMER: This is not a valid test, and the result is only used here to give a glimpse of what the difference might look like. The results will most likely look different on your environment. You can see the shell scripts I used to perform the test in the document folder I pointed out earlier. All tests were performed on a system where content was using cache.


Please find the following table which is comparison Solr v.s. Relational Database:



See also:


Search API vs Apache Solr Search Integration in Drupal 7?
What are the advantages of using Apache Solr over the core search module?
Solr or database? at stackoverflow SE
Search API documentation at Drupal.org
Why use Solr? at Solr Wiki
Solr's features at Solr
Enlightening - The Dark Art of Solr Search with Drupal at annertech