----- Original Message -----
From: "Michael Sizaki" <[EMAIL PROTECTED]>
To: <sqlite-users@sqlite.org>
Sent: Thursday, July 20, 2006 10:17 AM
Subject: [sqlite] How to calculate the sum up to a row better than O(n^2)?
Hi,
Suppose I have a database:
CREATE TABLE data (timestamp INTEGER, amount INTEGER);
INSERT INTO data VALUES(1,10);
INSERT INTO data VALUES(2,20);
INSERT INTO data VALUES(3,5);
INSERT INTO data VALUES(4,2);
...
Now I want to see the sum up to the timestamp:
SELECT
timestamp,(SELECT sum(amount)
FROM data as d
WHERE d.timestamp<=data.timestamp)
FROM data ORDER BY timestamp;
This works fine for small data sets. But it is obviously
a quadratic problem. Is there a more efficient way to do
the same thing?
It depends on your data, and what you are doing to it. BUT, if you are
simply adding new columns to your table, and not modifying any existing rows
(timestamps in any rows) -- then, you could do the following:
1) Add a new column to your table called something like "alreadyInTotal"
(defaults to 0 or Off or NotYet)
2) Keep a special value that is the "total" (could be in a different table)
3) Use the exact same query as above, but add to your WHERE " AND
alreadyInTotal=0"
4) AFTER you run the above query, add this new value to the total and then
mark all records tallied as "alreadyInTotal=1"
Obviously, there are all kinds of issues if you have multiple processes
accessing the same table.
I don't know if that is as clear as mud. Basically, keep a running total.
Know which rows have already been added to the total. Mark new rows as "in
the total", as you add them to the running total.
DanB
