From: Christopher Browne <cbbrowne@acm.org>
To: pgsql-sql@postgresql.org
Subject: Re: Debet-Credit-Balance Calculation
Date: Tue, 19 Apr 2005 23:14:10 -0400
Message-ID: <m3vf6iw35p.fsf@knuth.cbbrowne.com> (raw)
References: <001c01c544ff$bb94d650$1f00a8c0@middinks>
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: cbbrowne@acm.org
Subject: Re: Debet-Credit-Balance Calculation
In-Reply-To: <m3vf6iw35p.fsf@knuth.cbbrowne.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox