Millions of entities when logging
First thing I would look at is creating indices for your tables.  Look at the queries you are making and see if you can't optimize them with an SQL index. E.g. if you are querying against node id and user id with joins, try creating three indices, one for nid, one for id, one for nid and id.

Having the right indices can make a long running query fly.