Your problem is most likely not the size itself but how queries are being done. This could be a result of non optimal code or bad DB structure.
As with all optimization you first need to find the actual bottle necks and than to decide if you fix the code, or maybe just scrap the feature.
In any case, if you care about performance or avoiding artificial limitations, you should not be hosting on a shared host but use a VPS instead.