Thanks all for the input.
Obviously, I was doing something stupid with my original aggregation attempt, and the suggestions for creating an optimized schema are spot-on.
Unfortunately, while interesting, I cannot use a Heap or an RRD; both would ultimately remove data that might need to be included in the graph at some point. Those would probably be ideal solutions if my requirements were different.