Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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!

share|improve this question
8  
"switching databases is not an option" well that pretty much eliminates most solutions. good luck! –  Steven A. Lowe May 25 '11 at 2:47
1  
It's hard to say without more information about what exactly you're doing with those records. Also, are you looking for 5 seconds worst case (which probably means every record examined and zero locations match)? –  Guy Sirton May 25 '11 at 3:07
2  
@Dave: How much time does the current system take? Is the current system using PostGIS? Is location_id a geography or geometry, or refers to a second table? Is the location_id column indexed? –  rwong May 25 '11 at 6:19
1  
@Thorbjørn & @Darknight - In the ideas section I list pre-calculating, which would reduce the data to one value per city per day (per category). The calculation could recur annually, or even monthly, I suppose. This was my plan if there were no other possibilities (the calculations will probably take weeks). –  Dave Jarvis May 25 '11 at 9:05
1  
@Dave, plenty of possibilities, but the question is what is relevant to you. Have you investigated where the current bottlenecks are yet? –  user1249 May 25 '11 at 9:11

8 Answers 8

up vote 12 down vote accepted

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.

share|improve this answer
    
How ever you slice and dice it - even if each row takes only 100 bytes, 1.3Billion rows = 121 GB. With all your indexes etc., I am sure this will be much more. On a single box, you are gonna be slow unless you have some serious hardware around SSD + Tonnes of ram. Cheaper way is to scale across boxes. –  Subu Subramanian May 25 '11 at 12:26
4  
@Subu, you want to go distributed? Now you have two problems... –  user1249 May 25 '11 at 12:28
    
Heh - that I agree with:) But its cheaper! –  Subu Subramanian May 25 '11 at 13:42
    
@Thorbjørn: Thank you for your time and all your help. I think I will reduce the data set to 25 million rows per category then apply indexes on the date. That should reduce the scan to ~70000 rows (per day, with a limit of two weeks for the range), which should be fairly snappy. –  Dave Jarvis May 25 '11 at 22:45
    
@Dave, you still need to know where your bottlenecks are. Learn it while you don't have to. –  user1249 May 26 '11 at 5:40

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

share|improve this answer
    
Thank you for the ideas. There are potentially 77,066 dates, and new dates will be added going forward. I have a single machine. There are 20,000 locations, yet splitting by location wouldn't help because the data to analyze spans all locations. –  Dave Jarvis May 25 '11 at 5:57
    
and how is using cloud different from th above solution ? –  Wildling May 25 '11 at 6:50
    
This is what I thought of as well. Some kind of horizontal partition so that the search can happen in parallel across all the partitions. –  davidk01 May 25 '11 at 7:45
    
Splitting on the day would probably be the most helpful, resulting in 2562 separate tables (366 days x 7 categories). –  Dave Jarvis May 26 '11 at 3:07

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.

share|improve this answer
    
Thank you for the answer. Hardware upgrades are a consideration, as per the ideas I listed. A sub-$750 USD solution would be ideal. –  Dave Jarvis May 25 '11 at 7:09

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?

share|improve this answer
    
Thank you. The seven child tables are clustered on the location, date, and category using a btree. I researched GIN indexes last year and they did not (or would not) help, as I recall. –  Dave Jarvis May 25 '11 at 7:15
2  
Indexing location based on B-Tree isn't the slightest bit useful considering the type of searches you're looking into. You need an inverted index that works with the needed operators, which in the case of Postgis usually means GIST. You might want to highlight a few of the slow queries... –  Denis de Bernardy May 25 '11 at 7:40

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.

share|improve this answer

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.

share|improve this answer
    
Thanks for the note. There are over 70,000 cities, and many different latitude/longitude values fall within a specific city area. –  Dave Jarvis May 25 '11 at 5:24
    
@Dave: can you build a voronoi diagram for cities and classify lat/lon values into tessellations? (i.e. if it sounds haphazard, let it be.) Then, during lookup, you'll search for all cities whose tessellation touches the query's lat/lon ranges. If voronoi tessellation is too slow, square boxes (e.g. 5 deg lat x 5 deg lon) might be worth trying. –  rwong May 25 '11 at 19:57

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.