Re: Debet-Credit-Balance Calculation

Oops! middink(at)indo(dot)net(dot)id ("Muhyiddin A.M Hayat") was seen spray-painting on a wall:
> everything is ok, but when record > 1000000 that query eat all my
> cpu process and take a long time, i have wait for 3 mimutes
> but query doesn't finish. (pgsql-8.0-1 running on Dual Xeon 2.8 and
> 2GB of RAM)

What you're asking for is fairly much inherently exceedingly
expensive, and that's not really a PostgreSQL issue, it would be much
the same with any database.

The cost of the balance calculation for the first row may be 1.
For row 2, it's 1+1 = 2.
For row 3, it needs the balance from #2, so cost = 2+1 = 3.

Those add up, so the cost leaps thus:
Individual costs Row Aggregate
1 1
1 + 2 = 3 4
1 + 2 + 3 = 6 10
1 + 2 + 3 + 4 = 10 20
and so forth...

The "naive" algorithm for this essentially results in the cost of the
query increasingly with O(n^3) where n is the number of elements in
the table.

You can get closer to O(n) by cacheing balances, but that will _not_
fall in an obvious way from an SQL query.

There is an easy way to do this; write a plpgsql set returning
function which adds the balance to the last column of the table. That
query will always have a cost in both time and memory proportional to
the size of the table, and the memory cost may bite you as table size
grows...
--
wm(X,Y):-write(X),write('@'),write(Y). wm('cbbrowne','gmail.com').
http://linuxdatabases.info/info/x.html
"It's like a house of cards that Godzilla has been blundering
through." -- Moon, describing how system messages work on ITS