From: Christopher Browne <cbbrowne@acm.org>
Subject: Re: Debet-Credit-Balance Calculation
Date: Tue, 19 Apr 2005 23:14:10 -0400
Organization: cbbrowne Computing Inc
Lines: 40
Message-ID: <m3vf6iw35p.fsf@knuth.cbbrowne.com>
References: <001c01c544ff$bb94d650$1f00a8c0@middinks>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
User-Agent: Gnus/5.1007 (Gnus v5.10.7) XEmacs/21.4 (Jumbo Shrimp, linux)
Cancel-Lock: sha1:TSQghXo/addIhrweA198EL2t4Iw=
To: pgsql-sql@postgresql.org

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         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