PostgreSQL – Transform Row Data Based on Preceding Row for Cumulative Sum

I am not sure what type of performance you are looking for, but if CLR or external app is not an option, a cursor is all that is left. On my aged laptop I get through 1,000,000 rows in about 100 seconds using the following solution. The nice thing about it is that it scales linearly, so I would be looking at a little about 20 minutes to run through the entire thing. With a decent server you will be faster, but not an order of magnitude, so it would still take several minutes to complete this. If this is a one off process, you probably can afford the slowness. If you need to run this as a report or similar regularly, you might want to store the values in the same table un update them as new rows get added, e.g. in a trigger.

Anyway, here is the code:

IF OBJECT_ID('dbo.MyTable') IS NOT NULL DROP TABLE dbo.MyTable;

CREATE TABLE dbo.MyTable(
 Id INT IDENTITY(1,1) PRIMARY KEY CLUSTERED,
 v NUMERIC(5,3) DEFAULT ABS(CHECKSUM(NEWID())%100)/100.0
);


MERGE dbo.MyTable T
USING (SELECT TOP(1000000) 1 X FROM sys.system_internals_partition_columns A,sys.system_internals_partition_columns B,sys.system_internals_partition_columns C,sys.system_internals_partition_columns D)X
ON(1=0)
WHEN NOT MATCHED THEN
INSERT DEFAULT VALUES;

--SELECT * FROM dbo.MyTable

DECLARE @st DATETIME2 = SYSUTCDATETIME();
DECLARE cur CURSOR FAST_FORWARD FOR
  SELECT Id,v FROM dbo.MyTable
  ORDER BY Id;

DECLARE @id INT;
DECLARE @v NUMERIC(5,3);
DECLARE @running_total NUMERIC(6,3) = 0;
DECLARE @bucket INT = 1;

CREATE TABLE #t(
 id INT PRIMARY KEY CLUSTERED,
 v NUMERIC(5,3),
 bucket INT,
 running_total NUMERIC(6,3)
);

OPEN cur;
WHILE(1=1)
BEGIN
  FETCH NEXT FROM cur INTO @id,@v;
  IF(@@FETCH_STATUS <> 0) BREAK;
  IF(@running_total + @v > 1)
  BEGIN
    SET @running_total = 0;
    SET @bucket += 1;
  END;
  SET @running_total += @v;
  INSERT INTO #t(id,v,bucket,running_total)
  VALUES(@id,@v,@bucket, @running_total);
END;
CLOSE cur;
DEALLOCATE cur;
SELECT DATEDIFF(SECOND,@st,SYSUTCDATETIME());
SELECT * FROM #t;

GO 
DROP TABLE #t;

It drops and recreates the table MyTable, fills it with 1000000 rows and then goes to work.

The cursor copies each row into a temp table while running the calculations. At the end the select returns the calculated results. You might be a little faster if you don't copy the data around but do an in-place update instead.

If you have an option to upgrade to SQL 2012 you can look at the new window-spool supported moving window aggregates, that should give you better performance.

On a side note, if you have an assembly installed with permission_set=safe, you can do more bad stuff to a server with standard T-SQL than with the assembly, so I would keep working on removing that barrier - You have a good use case here where CLR really would help you.

For starters gid should probably be a numeric type. integer should be good enough or bigint if the key space shouldn't be big enough. Much smaller footprint, faster processing than with character data, faster and smaller indexes.

More importantly, to improve performance I suggest database normalization.

Quote:

There is a fairly regular pattern where each word appears about 1000 times.

Create a separate table for unique words:

CREATE TABLE word (
   word_id serial
 , word    text
);

Fill it with unique instances of word in your big_tbl:

INSERT INTO word (word)
SELECT DISTINCT word
FROM   big_tbl
ORDER  BY word;

ORDER BY is optional, not needed for query at hand. But it speeds up index creation and might be cheaper overall.

The table should be small in comparison: only ~ 50k rows for 50M rows in your big table.
Add indexes after filling the table:

ALTER TABLE word
    ADD CONSTRAINT word_word_uni UNIQUE (word) -- essential
  , ADD CONSTRAINT word_word_id_pkey PRIMARY KEY (word_id);  -- expendable?

If those are read-only tables, you can do without the pk. It's not relevant to the operations at hand.

Replace your big table with a much smaller new table. You may have to lock the big table to avoid concurrent writes. Concurrent reads are not a problem.

CREATE TABLE big_tbl_new AS
SELECT b.gid      -- or the suggested smaller, faster numeric replacement
     , w.word_id, b.stat
FROM   big_tbl b
JOIN   word w USING (word)
ORDER  BY word;   -- sorting by word helps query at hand

ORDER BY clusters the data (once) making the query at hand faster, because far fewer blocks have to be read (unless your data is clustered mostly already). The sort carries a cost, weigh cost and benefit once more.

DROP big_tbl;     -- make sure your new table has all data!
ALTER big_tbl_new RENAME TO big_tbl;

Recreate indexes:

ALTER TABLE big_tbl ADD CONSTRAINT big_tbl_gid_pkey PRIMARY KEY (gid);  -- expendable?
CREATE INDEX big_tbl_word_id_idx ON big_tbl (word_id);  -- essential

Your query looks like this now and should be faster:

SELECT b.*
FROM   word w
JOIN   big_tbl b USING (word_id)
WHERE  w.word = 'something';

Reorganization is meant to be a one-time operation to re-organize your data. Keep the new form and also consider keeping indexes permanently.

All of this together (including new indexes) should occupy about half of what you had before on disk, also cutting the time for creation in half (at least). Index creation should be considerably faster, the query as well. If RAM is a limiting factor, these modification pay double.

If you have to write to the table as well, it becomes more expensive (but you did not mention anything about that). You'd need to adjust your logic for DELETE / UPDATE / INSERT:
Example for INSERT: Fetch word_id for existing words or insert a new row in word returning the new word_id. Details for this:
How do I insert a row which contains a foreign key?