I agree, it looks as a database problem. The time to execute a DB query is really not proportional to the number of matching results, but on the complexity of what it has to do to fetch these results. You are not saying enough to elicit a really useful answer.
Comment on Re^2: fetchall_arrayref({}) call freezing