Good news is, you can make (e.g.) a C-hook, that lets you write you app in Ruby, and your "search" code in C (or something like that). I don't know what you're doing specifically, so that may be an answer. I will say that if you're interfacing heavily with the database in this search, it is very likely that Rails is not the answer -- Rails tries to handle DB work transparently to the user, and going against that problem is not just hard, but also REALLY labor intensive. I'm told this is why twitter dropped Rails.
As far as speed goes, Ruby is about as fast as PHP at this point, although rails runs a bit slower.
Hope that helps! Feel free to ask follow-up questions.
Before deciding, please, profile your current application to measure how much time it spends doing what.
To determine what language to use, ask yourself the following question:
a) How many devs will or you want to support your application.
b) Approximately (ballpark) how many users will be sending simultaneous requests? If there are going to be 20 people logged in total, performance is not an issue.
c) How much time you have.
d) How much hardware will you be using?
e) Do you realize that doing queries from a table of 10 or 1000000 records are equivalent to the application if you return 2 rows to it? The work is in the database and will remain unchanged.
Now, many places chose RoR/PHP (and some good frameworks) as a front-end, while using a "fast" language like java or erlang for the back-end. Facebook is one such example. They use erlang to handle comet requests and php to render the front end, and I think java to do back-end messaging and so on. The front-end code just queries it.
If its a simple data application (show page, get input, query/update db, show page) then RoR is easy to make/maintain. If there are 10,000 users logged in at once, I'd think about this further. If you are a sole maintainer, RoR is nice since it makes writing and maintaining simple granted you know what you are doing.