Tell me more ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.
up vote 21 down vote favorite
5

Does anybody knows how Google or Yahoo perform searches for keywords against very very huge amounts of data? What sort of database or technologies do they employ for this?

It takes few milliseconds, but they have more than a billion pages indexed.

share|improve this question
There is a similar question on Stack Overflow: stackoverflow.com/questions/362956/… – splattne Jun 8 '12 at 9:05
1  
There needs to be a bit of speculation since the actual algorithms are trade secrets. It still seems like this is a semantic debate as to what a "database" actually is. I think that you'll find that a lot of this discussion is based on semantic disagreement between those with a broad view of a database and a narrow view of a database. Please, let this question die in peace. – swasheck Jun 13 '12 at 14:26
@swasheck (obviously) I disagree. The poster asked how does Google return the results of a query so quickly given they have so much data. Google have told us. It's due to MapReduce. A good guess is result caching but it's not the main factor in their amazing speed. I don't want to denigrate Aaron's answer, but the poster will gain a lot of understanding how it's done by reading Google's original paper on the work. There is a lot of trade secrets too, but understanding what Google has revealed is key. – Stuart Woodward Jun 14 '12 at 21:58
To be fair @StuartWoodward I read the google developer blogs, and they don't cache search results, ever. Not according to what they've said in public. So while they do maintain a cache of the pages they've indexed, and several caches actually, meaning something akin to the archive.org site, they don't rely on the cache to provide you anything. They just maintain that for integrity sake. – jcolebrand♦ Jun 17 '12 at 2:41
2  
However, at this point the conversation here seems to be becoming inflamed, so I'm going to ask that any further non-answer-oriented or non-question-refining (none of the comments so far have been either of these) commentary be relegated to the chat room (you can always start here chat.stackexchange.com/rooms/179/the-heap or generate a new room for this question) or just left alone. Now, if you want to refine the question or provide a more authoritative answer, with source then that's fine. But no more arguing about proprietary technology. – jcolebrand♦ Jun 17 '12 at 2:42

5 Answers

up vote 17 down vote accepted

I am sure there is a combination of things:

  • serious hardware

  • lots of it - data is distributed and replicated across many nodes and different data centers

    • (actually in the Google case at least I believe they have thousands and thousands of really low-end servers)
  • a lot of common queries' results are cached, notice how they pre-populate potential searches for things you know you've never searched for before; they're predicting what you might search for and hoping they've already got your result pre-calculated and cached somewhere. In a lot of cases they do - there aren't many searches you could come up with on Google today that haven't been asked by someone before you. When they do get a new search phrase then they probably use something like free-text search - and I'd expect keywords are extracted semantically when a page is first crawled rather than trying to find keywords in the document after you've searched for them. Of course they do have to periodically invalidate those caches, re-calculating page rank, and distributing the new cached results across their cache - and I'm sure there's a lot of serious engineering behind that.
share|improve this answer
3  
Also, Google uses BigTable instead of a traditional relational database. Interesting stuff! – JHFB Jun 1 '12 at 12:37
2  
is that the sequel (er ... SQL) to this one? At any rate - it's clear that Google uses a variety of technologies to support their various requirements. Some of it is relational, some of it is not, but most things are developed in-house (BigTable, F1) and others are heavily modified (MySQL) – swasheck Jun 1 '12 at 14:59
1  
I haven't paid attention lately, but the upper range of the result set used to shrink as you paged through the results. The initial value was an estimate of the upper value. The real results aren't generated until needed. – BillThor Jun 2 '12 at 0:32
up vote 22 down vote

Pigeons.

The heart of Google's search technology is PigeonRank™, a system for ranking web pages developed by Google founders Larry Page and Sergey Brin at Stanford University:

enter image description here

Building upon the breakthrough work of B. F. Skinner, Page and Brin reasoned that low cost pigeon clusters (PCs) could be used to compute the relative value of web pages faster than human editors or machine-based algorithms. And while Google has dozens of engineers working to improve every aspect of our service on a daily basis, PigeonRank continues to provide the basis for all of our web search tools.

Why Google's patented PigeonRank™ works so well

PigeonRank's success relies primarily on the superior trainability of the domestic pigeon (Columba livia) and its unique capacity to recognize objects regardless of spatial orientation. The common gray pigeon can easily distinguish among items displaying only the minutest differences, an ability that enables it to select relevant web sites from among thousands of similar pages.

By collecting flocks of pigeons in dense clusters, Google is able to process search queries at speeds superior to traditional search engines, which typically rely on birds of prey, brooding hens or slow-moving waterfowl to do their relevance rankings.

When a search query is submitted to Google, it is routed to a data coop where monitors flash result pages at blazing speeds. When a relevant result is observed by one of the pigeons in the cluster, it strikes a rubber-coated steel bar with its beak, which assigns the page a PigeonRank value of one. For each peck, the PigeonRank increases. Those pages receiving the most pecks, are returned at the top of the user's results page with the other results displayed in pecking order.

share|improve this answer
7  
+1 From the source. Cited and everything. – swasheck Jun 1 '12 at 14:56
6  
Note: This page was posted for April Fool's Day - 2002 – dr jimbob Jun 1 '12 at 20:51
7  
Hilarious, but probably shouldn't be the highest-voted answer :-x – TehShrike Jun 2 '12 at 4:39
3  
@TehShrike well, really, being the highest-voted answer doesn't really do much except credit the poster for providing a funny and clever (though not truly helpful) answer. Even if it were the accepted answer and thus bubbled to the top, I don't think we are in danger of any newbies coming along and believing that Google runs on pigeons. – Aaron Bertrand Jun 3 '12 at 0:45
1  
I know google can't use actual pigeons. They are made obsolete by I5 processor. – Jim Thio Jun 21 '12 at 9:09
show 3 more comments
up vote 16 down vote

It's important to bear in mind a couple of things about google:

  • Their DB is the proprietary BigTable - it was custom designed BY GOOGLE to exactly fit their needs

  • Their proprietary DB is built on top of their proprietary file system - Google File System - this was designed, again BY GOOGLE, to be easily expandable using common commodity hardware. As Aaron mentioned in his answer, they have a large number of average servers instead of a small number of very powerful servers.

They store individual tables across multiple machines as a way of making access quicker - their software knows which data is on which machine and instead of thrashing through a disk to locate it can go straight to the server with the relevant info.

share|improve this answer
Pretty much. The top dogs have built their own solutions because nobody else has scaled that far before. – TehShrike Jun 2 '12 at 4:40
up vote 11 down vote
+100

Google does not use traditional relational database technology. It developed its own technology, big table and map reduce. The original research papers are here : Big Table and Map/Reduce. Also of interest is the SSTable, sorted string table.

Similar tech is now used in hadoop and the NoSQL databases.

share|improve this answer
up vote 7 down vote

Read Steven Levy's "In The Plex: How Google Thinks, Works, and Shapes Our Lives". This book is a fascinating read about all things Google and does discuss at a high level some of the technology and engineering behind search. Aaron sums it up really well in his answer and Levy's book will give you some more detail about how they do it.

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.