Re: Debet-Credit-Balance Calculation - Mailing list pgsql-sql

From Christopher Browne
Subject Re: Debet-Credit-Balance Calculation
Date
Msg-id m3vf6iw35p.fsf@knuth.cbbrowne.com
Whole thread Raw
In response to Debet-Credit-Balance Calculation  ("Muhyiddin A.M Hayat" <middink@indo.net.id>)
List pgsql-sql
Oops! middink@indo.net.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         101 + 2 + 3 + 4 = 10         20and 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


pgsql-sql by date:

Previous
From: Mihail Nasedkin
Date:
Subject: Re: Debet-Credit-Balance Calculation
Next
From: KÖPFERL Robert
Date:
Subject: Function to either return one or all records