Scanning a billion rows in an ultra-fast database

Question

Background

A local database contains nearly 1.3 billion unique rows. Each row is indirectly associated with a specific latitude and longitude (location). Each row has a date stamp.

Use Case

The problem is as follows:

1. The user sets a starting/ending date, and a range of values (e.g., 100 to 105).
2. The system gathers all the rows that match the given date, grouped by location.
3. The system performs determines the locations that, during those dates, have a statistical likelihood of falling into the given range of values.
4. The system displays all matching locations to the user.

This is a problem of speed and scale.

Question

What is the least expensive solution architecture you can imagine that would allow such a system to retrieve results for users in under five seconds?

Current System

The environment is currently:

• PostgreSQL 8.4 (upgrade is possible; switching databases is not an option)
• R and PL/R
• XFS
• WD VelociRaptor
• 8 GB RAM (Corsair G.Skill; 1.3 GHz)
• Quad core GenuineIntel 7 (2.8 GHz)
• Ubuntu 10.10

Hardware upgrades are acceptable.

Update - Database Structure

The billions of rows are in a table resembling:

id | taken | location_id | category | value1 | value2 | value3

• id - Primary key
• taken - Date assigned to the row
• location_id - Reference to the latitude/longitude
• category - A description of the data
• value1 .. 3 - The other values the user can query

The taken column is typically consecutive dates per location_id, sometimes each location has data from 1800 to 2010 (about 77,000 dates, many of them duplicated as each location has data in the same date range).

There are seven categories and the tables are already split by category (using child tables). Each category contains ~190 million rows. In the near future, the number of rows per category will exceed a billion.

There are approximately 20,000 locations and 70,000 cities. The locations are correlated to city by latitude and longitude. Assigning each location to a particular city means finding the city's boundaries, which is not a trivial task.

Ideas

Some ideas I have include:

• Find a cloud service to host the database.
• Create an SSD raid stripe (great video).
• Create a table that amalgamates all the locations by city (pre-calculation).

Thank you!

Answer 1

The most important thing is to be absolutely certain where the bottleneck is now for a given number of representative requests as you cannot switch databases.

If you do full table scans, you need appropriate indexes.

If you wait on I/O you need more memory for caching (Jeff Atwood recently mentioned that 24 Gb systems were reachable on desktop systems).

If you wait on CPU you need to see if your calculations can be optimized.

This requires a pointy DBA-hat and a Operating System-hat, but is worth it to ensure you are barking up the right tree.

Answer 2

How about partitioning the table into multiple pieces located on different hosts based on date stamp? This is horizontally scalable, and as long as you have enough number of boxes, you could write a small aggregation engine on top of these setups.

If you see that the date stamp is changing too much, then you could partition based on the locations - again horizontally scalable. (Hopefully they don't add many more of latitudes/longitudes!)

Answer 3

Worst case scenario is date range covers all the dates in your database.

You're looking to read 1.3 billion records and do some sort of analysis on each record vs. the entered values, on one physical machine, in less than 5 seconds. The outcome can be all locations or none - you know nothing in advance.

Given these parameters I would say likely impossible.

Just look at your hard drive: the Max Sustained rate is less than 150MB/s. Reading 1.3 billion records will take more than 5 seconds. CPU-wise you're not going to be able to do any sort of statistical analysis on 1.3 billion records in 5 seconds.

Your only hope (tm :-) ) is finding some sort of lookup function based on the values entered by the user that will narrow the search down (by a few orders of magnitude). You can calculate this lookup function offline. Without knowing more about the exact match criteria I don't think anyone can tell you how to do that but an example would be to partition the range of values into some discrete interval and create a lookup that gives you all the records in that interval. As long as the interval is small enough you can do real work in it, e.g. pruning away entries that don't match the user entered value. Basically trading space for time.

It may be possible to hold onto all the records (or at least the important part) in memory. Probably not in 8GB. This will at least eliminate the disk I/O portion though even the memory bandwidth may be insufficient to scan through everything in 5 seconds. At any rate, this is another technique for speeding up these sorts of applications (combine with my previous suggestion).

You mention using a cloud service. Yes if you pay for enough CPU and IO muscle and partition your database across many servers you can brute force/divide and conquer it.

Answer 4

I second rwong's comment to the question: PostgreSQL offers appropriate indexes types and tools (GIST indexes, GIN indexes, Postgis, Geometrical types) in such a way that geodata and datetime-related data should be searchable along those criterias without much issues.

If your queries on these criterias take seconds, it probably means no such indexes are being used. Can you confirm that you've investigated these as appropriate?

Answer 5

Given you use PostgreSQL and latitude/longitude data, you should definitely use PostGIS as well, that way you can add a GiST spatial index to your database to help speed things up.

I have a such a table (with 350k rows) with a configuration much smaller than yours (2 core and barely 2Gb RAM) yet searches take less than one second.

Answer 6

Maybe you could break a relational model like Essbase did with their OLAP architecture: Essbase Wikipedia

What I mean is create one table per city, thus ending up with 1000+ tables. Not one table like you suggested, but many. Index each table by date and location. Many tables, many indexes --> faster.

Answer 7

As far as your idea of finding a cloud service to host the database, have you come across SimpleGeo yet? They just cut the ribbon on a Storage service that's apparently "specifically tuned to store and query location data really, really fast" - although the cost to store and query against more than billion rows might make this approach unfeasible.

Answer 8

you are expecting a bicycle to run on the highway. currently you are looking for a solution to tackle this problem only, you are not foreseeing the problem what if u have 2 billion records? scalability must be addressed. answer is simple use object databases. e.g Intersystems cache

and believe you me I'm not from intersystems ;-)