Inside Microsoft® SQL Server® 2008: T-SQL Querying

How Algorithms Scale

The jargon of database management uses the word scale in phrases such as scale out, scale up, and scalable solution. To talk about how a system or algorithm scales is to talk about how the system or algorithm is affected by changes (usually increases) in the amount of input data.

A naïve expectation about scaling is to expect this behavior: if there’s twice as much data, it will take twice as long to process the data. While some systems and algorithms behave that way, many don’t. Some tasks take the same amount of time regardless of the amount of data. For these tasks, if there’s twice as much data, it will take no longer to process the data. An example is the task of retrieving a quarter from a jar of quarters. No matter how ...