Q:

MySql performance degrades quickly when queries have to process a large number of rows

I'm using MySql and having a situation when a given query calculates the revenue from a table of transactions. The selected transactions can span over 1 day, 1 week or 1 month.
SELECT 
revenue formula 
FROM
    product inner join
    account on key_condition1 inner join
    transaction on key_condition2
WHERE
    tx.ENTRYDATE >= '2013-06-17 00:00:00' AND tx.ENTRYDATE < '2013-07-24 00:00:00'
GROUP BY product

When I supply one week to the where statement the query runs in 3-4 seconds. When I want the entries from one month the query completes in 300 - 400 seconds if ever.
The database we're taking about is quite big. It has about 3.5 million transactions.
At first I thought that the sheer number of transactions leads to such an issue but it doesn't seem so. Per week there are 110363 entries and per month 576910. My other idea (that seems very likely) it's that because of the join the time can grow exponentially even though the join is not based on entry dates. 
My question is: is the join "at fault" for the exponential growth? For the moment the join is unavoidable but this could get fixed with some database refactoring.
Thanks for your opinion.
The results from EXPLAIN:
id,select_type,table,type,possible_keys,key,key_len,ref,rows,Extra
1,SIMPLE,LOANPRODUCT,index,PRIMARY,PRIMARY,98,NULL,1,
1,SIMPLE,LOANACCOUNT,ref,"PRIMARY,LOANACCOUNT_PRODUCTTYPEKEY",LOANACCOUNT_PRODUCTTYPEKEY,99,LOANPRODUCT.ENCODEDKEY,16559,"Using where; Using index"
1,SIMPLE,LOANTRANSACTION,ref,"LOANTRANSACTION_PARENTACCOUNTKEY,LOANTRANSACTION_REVERSALTRANSACTIONKEY,LOANTRANSACTION_ENTRYDATE",LOANTRANSACTION_PARENTACCOUNTKEY,99,LOANACCOUNT.ENCODEDKEY,7,"Using where"

A:

There could be a couple of big reasons here:

indexing
waiting for other transactions
memory constraints
caching issue

Below's what I think about each:
Indexing
I don't think it's a completely missing index since you are retrieving 5x more rows at 100x the time cost. If this were the issue, the scaling would be more or less linear with the number of rows. With no indexing, the scaling would possibly be even better than 1 if the query optimization is half way decent. However, if you have conflicting indices, then the optimizer would choose one or the other based on what it thinks is best. It's likely that the optimizer chose one for 3-4 seconds, and then the other for 300-400 seconds. 
From your EXPLAIN result, it looks like you have conflicting indices. I'm going to guess that LOANTRANSACTION_PARENTACCOUNTKEY contains key_condition2, and LOANTRANSACTION_ENTRYDATE contains ENTRYDATE. Neither one has the other column. Thus, the optimizer has to choose one or the other. You should have an index that includes both. I would put ENTRYDATE first.
I am also going to guess that this EXPLAIN is from the slower query, since it's not using index on LOANTRANSACTION to filter by ENTRYDATE. Hence, MySQL needs to read all those rows just to see if they are in the range or not. 
Waiting for Others
This is likely if other transactions are modifying the data. Try reading uncommited to see if it speeds up. If so, then this is your issue.
Memory
When you run out of memory, then all sorts of things slow down dramatically. See if 1 month scales to 2 months linearly, and if 1 week scales to .5 week linearly.
Caching
If your data is not in the cache, then that data will need to come from the disk, which is ridiculously slow compared to memory. This could very likely be your issue. If you rerun the query, the second run should be significantly faster. If your memory isn't big enough to contain the relevant rows, then your query will always be slow. See if your memory should be able to hold all the relevant tables or not.

