Message-ID: <43DD85D2.5020207@modgraph-usa.com>
Date: Sun, 29 Jan 2006 19:19:46 -0800
From: "Craig A. James" <cjames@modgraph-usa.com>
User-Agent: Mozilla Thunderbird 1.0.6 (X11/20050716)
MIME-Version: 1.0
To: Mike Biamonte <mike@dbeat.com>
CC: pgsql-performance@postgresql.org
Subject: Re: Huge Data sets, simple queries
References: <007101c623a9$82207c10$0200a8c0@videobox>
In-Reply-To: <007101c623a9$82207c10$0200a8c0@videobox>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Mike Biamonte wrote:
> Does anyone have any experience with extremely large data sets?
> I'm mean hundreds of millions of rows.
> 
> The queries I need to run on my 200 million transactions are relatively
> simple:
> 
>    select month, count(distinct(cardnum)) count(*), sum(amount) from
> transactions group by month;

This may be heretical to post to a relational-database group, but sometimes a problem can be better solved OUTSIDE of the relational system.

I had a similar problem recently: I have a set of about 100,000 distinct values, each of which occurs one to several million times in the database, with an aggregate total of several hundred million occurances in the database.

Sorting this into distinct lists ("Which rows contain this value?") proved quite time consuming (just like your case), but on reflection, I realized that it was dumb to expect a general-purpose sorting algorithm to sort a list about which I had specialized knowledge.  General-purpose sorting usually takes O(N*log(N)), but if you have a small number of distinct values, you can use "bucket sorting" and sort in O(N) time, a huge improvement.  In my case, it was even more specialized -- there was a very small number of the lists that contained thousands or millions of items, but about 95% of the lists only had a few items.

Armed with this knowledge, it took me couple weeks to write a highly-specialized sorting system that used a combination of Postgres, in-memory and disk caching, and algorithms dredged up from Knuth.  The final result ran in about four hours.

The thing to remember about relational databases is that the designers are constrained by the need for generality, reliability and SQL standards.  Given any particular well-defined task where you have specialized knowledge about the data, and/or you don't care about transactional correctness, and/or you're not concerned about data loss, a good programmer can always write a faster solution.

Of course, there's a huge penalty.  You lose support, lose of generality, the application takes on complexity that should be in the database, and on and on.  A hand-crafted solution should be avoided unless there's simply no other way.

A relational database is a tool.  Although powerful, like any tool it has limitations.  Use the tool where it's useful, and use other tools when necessary.

Craig