Building an advanced multicriteria search
I think facets are a great way to do advanced searching.
Facet API is a great module that is flexible.

You can use it with core drupal search using Faceted Navigation for Search or Search API, which can use the drupal database to search.

However, due to the queries that are run in the calculation of facet data, there are performance implications of using faceted search with drupal SQL based searching.

If you have a lot of content, are using a lot of different facets, or have high traffic, I would definitely recommend using a better search engine.

Apache solr, is great and is pretty easy to get set up these days.

You main options are the Apache Solr Search Integration module and the Search API module, in conjunction with the Search API Solr search module.

Both those integrate with the facet API module.

Solr is not really shared host friendly though. Generally you will have to find a host that will provide apache solr hosting, or use a VPS or dedicated server that allows you to install solr yourself.