Solr on Heroku uses their own add-on, which starts at $20pm:

Although I don't know why it costs up front, and doesn't have a "trial" option like many of the other Heroku Add-ons, there are certain ways around it
Full Text Search
Full text search is what you're performing, and Solr is a tool to make the process much more efficient. Despite being quite DB-expensive, you can use full text searching with Heroku, depending on your DB:
MYSQL
To perform full-text searching on MYSQL, you can simply use the "LIKE" operator with %variable% as your search phrase, like this:
SELECT * FROM `table` WHERE `name` LIKE `%benjamin%`
This basically finds all the records where the name column contains "benjamin" somewhere inside it. This is quite slow
POSTGRESQL
PostgreSQL offers more power in its full text searching, but is nonetheless still quite slow & expensive. You can read more about it here, but with rails, you can use a bunch of gems which do the task for you
We recently used a gem called textacular here: http://firststop.herokuapp.com
Here is the code we used for it:
#Search
def self.search(search)
basic_search(name: search, description: search)
end
Further Reading
You can see how full text searching works here: Any reason not use PostgreSQL's built-in full text search on Heroku?
I would recommend if you're just getting the foundations established for your app. Afterwards, you can upgrade to a more dedicated solution in the form of Solr et al
Here are