I'm currently employed at AudiencePoint Inc., the industry leader in Email Send Time Optimization. AudiencePoint Send Time Optimization allows clients determine the optimal time to send a piece of correspondence to each individual on their subscriber list. To do this we need to crunch through A LOT of data. This massive amount of data is stored today in a SQL Server 2012 database running on powerful dedicated hardware. As the data and volume of operations on that data has continued to grow, we have learnt some lessons on how to scale SQL Server to keep up with the heavy demand.

One thing to note is that database operations at AudiencePoint (AP) look different from DB operations at a web based companies like StackOverflow or Amazon.com. Operations at those companies are typically transactional (OLTP) in nature; e.g. every page view requires a certain number of DB reads, new records are inserted into the DB when a question or answer is posted, etc. At AP our DB operations are typically in batches; e.g. 10 million records need to be inserted, queried, sorted, updated in batch fashion. The question becomes how do you speed up and/or scale these operations? Especially when you don't have available to you all the traditional scaling techniques used by OLTP DB applications such as caching and partitioning. Here are some of the things we learnt:

Joins are bad
And by bad, I mean slow. Especially when we are talking about large tables and more than two tables are involved. Joins combine scattered data fragments to form a single table. Therefore they are sensitive to disk seek latencies. They also generate a lot of data which may not fit into memory and have to involve the use of a swap file. Additionally, a join operation can only involve two tables at a time so when more than 2 tables are involved, it must first join the first 2 tables to create an intermediate dataset and then join that data set to the next table. This is actually a denormalization process. Therefore it's worth examining your tables and queries to see if you are overnormalized and denormalize your tables or adjust your queries like we had to do. Indexes can help improve join performance on SELECT statements but comes at a cost to INSERT operations. More on that later.


Don't put it in the DB
The fastest database operation possible is the one you don't do. No matter how fast your query operation is, not having to query for the data at all is faster. Same goes for inserts, updates or deletes. Based on the information we had at the time, we used to stuff a lot of unnecessary data into the DB and then have to query back out those millions of rows of unnecessary data. This is obviously not good for performance. In the OLTP world, unnecessary data operations are avoided by various layers of caching. If that's not available to you, then you need to think critically and work hard to avoid unnecessary DB operations. Does it need to be in the database? Why?

SQL Server performs better on subqueries than joins
Questions about the performance of joins versus the IN clause have been asked several times on StackOverflow. Two such instances can be found here: SQL Join vs. In clause and SQL Join vs. Sub-query (first link has an example). We found that SQL server performs better with sub-queries / the IN clause. This is because the IN clause precludes the necessity of a join and as we now know; Joins are bad!
On StackOverflow the common answer to the debate of joins vs. subqueries is usually "it depends on your DB engine". In our experience SQL Server (and apparently Oracle according to an SO poster) has picked a side.

Multithread your DB operations
Horizontal scaling is the holy grail of DB scaling. This is why data partitioning is so popular. In batch processing though, the tendency is to have a process repeat the same operations over and over again (hence batch). The problem with that is that if you have a SQL Server database sitting on a quad-core or octa-core server and you fire up the profiler to look at what's going on, you'll find that only one core on your SQL Server database is active while the others are just hanging around working on their tans. When we divvied up our work into smaller batches and had multiple threads doing our DB operations we saw all the other cores come to life and our performance increase by orders of magnitude. We had just achieved horizontal scaling but within one box. Snow cones for everyone!

Watch your indexes
Markus Winand explains it better; while indexes really speed up SELECT queries they have the opposite effect on INSERT (as well as UPDATE and DELETE) statements. For an insert operation on a table;

adding a single index is enough to increase the execute time by a factor of a hundred. Each additional index slows the execution down further

That's why indexes should be used deliberately, sparingly and with database usage patterns in mind. At AP we had (and probably still have) some tables where the index size is greater than the actual table size.

and finally...

Don't use SQL Server
... for things its not good at. Gotcha there?! The tendency is to try to shoehorn one solution for every problem to be solved. We've been there, done that and have learned not to do that anymore. For areas where SQL Server isn't a good fit, evaluate other solutions to pair with it. NoSQL, Graph databases, Time series databases, etc. all have their strong points and would perform better at those functions than an RDBMS. As the popular saying goes, "use the right tool for the job".

In today's short-attention-span world its important to make sure that your software product meets certain minimum speed requirements. Not doing so causes your target user to go somewhere else looking for someone who can provide the same service you offer faster and/or more conveniently. If they can find one, you've lost a potential user and your product might as well not exist when it comes to that user. Let's use web browsers as a case study. In 2009, one year after the Chrome browser launched, it had 7.1% usage compared to Firefox's 46.6% performance. Fast forward to today where Chrome's usage is 61.6% compared to Firefox's 23.6%. How did Chrome get such a leg up on FF? While being advertised on the main Google website certainly helped, their calling card was speed. Bottom line; performance matters!

If performance matters so much, we should certainly pay attention to it in the design phase of our software projects and not just leave it as an after thought. This goes against the popular notion that you should only worry about the functionality of your application and leave performance tuning until when it is needed. While it is true that premature optimization is the root of many evils, no amount of post-design performance optimization can make up for poorly designed software. Your performance requirement will differ based on user expectation, business goals and of course the work that is actually getting done. The performance expectations for pulling and presenting a record from a data store is different from performance requirements for crunching through lots of data for a machine learning problem.

Ultimately performance comes down to CPU cycles. One core can only perform one computation within one cycle. Which then implies that to speed up your software task you can; use faster hardware that can perform more cycles per second, parallelize your job so that multiple cores are working on it at the same time, or reduce the number of cycles it takes to complete your job. This post focuses on the software solutions, however, giving granular advice on how write performant software is not something that can be done in this article. What I can do is list some reasons why systems are slow and design considerations to keep in mind in order to write fast software.

Excessive memory allocation / usage:
This is especially important in managed languages like Java and C# where garbage collection is handled by the runtime. While the process of memory allocation is almost free compared to C/C++, the more memory that is allocated means that garbage collection runs longer and more frequently. In addition to that, programs that frequently need to access memory and secondary storage end up being I/O bound. CPU bound processes will always be faster than I/O bound processes because the rate at which data is transferred from main memory or secondary storage to the CPU is typically slower than the rate at which the CPU can execute instructions.

Inefficient algorithms:
Its fairly obvious that the efficiency / inefficiency of your algorithm is directly related to your software's performance. Algorithms with quadratic complexity or higher fail to scale and there's always a performance benefit in the reduction of the complexity of your algorithm. Some techniques for improving the performance of your algorithm are:
1. using a hybrid or adaptive algorithm (read links for more info),
2. avoiding unnecessary work by; caching the result of an expensive function call and returning the cached result when the same inputs occur again, providing a fast path for common cases, etc.
 It's also sometimes necessary to consider the performance of third party or framework libraries / functions and switch to a library or function with a faster algorithm if available.

Too many layers of abstraction:
While layers of abstraction are great for encapsulation, information and complexity hiding, re-use, etc. Abstractions typically add overhead. Sometimes the overhead is trivial and other times it is significant. Therefore it becomes a question of trade-offs. To gain increased performance it may be necessary to lose a layer of abstraction and along with it, both the abstraction layer's overhead as well as whatever benefits it may provide.

Bring the data closer to the computation (or vice versa):
This is closely related to my first point but takes more of a macro view. The closer the data that is being processed is, the faster the process can run. So if the data is on disk and can be brought and managed in memory effectively (maybe in chunks) we can increase performance. Another example is bulk downloading remote data and operating on it locally instead of making several individual remote calls. Hadoop solves the problem of scaling big data problems by distributing the data and sending the computation as close to the data as possible or a machine, rack or cluster level.

Task parallelization opportunities:
This one is an obvious one. While parallelization can be difficult to do properly, it can certainly yield great results in the right situations. In addition to running multiple tasks in parallel on multiple threads, look for opportunities in which instead of waiting for a long running request such as a web service or database call to return a response, your process can make the call, continue doing other things and resume its original work when the call returns. An implementation of this is the async and await keywords in C#.

Avoid / minimize bottlenecks:
The benefits of multiple threads or processes can be limited when there is a bottle neck. A bottle neck is typically a resource that cannot be accessed or modified in parallel in order to maintain its integrity. There are cases where bottlenecks can be avoided (by not sharing data / resources), but sometimes we can't get around them. In those situations the solution is to hold on to a resource lock for as little time as possible and keep the operations involving the lock as simple as possible. Bottlenecks are also prevalent in horizontal scaling situations, where the database cannot scale like the rest of the infrastructure. Database sharding is a common approach to solving that problem.

In conclusion, there are many more performance factors that this article could have covered and I only went skin deep. In future posts I'll be taking a deeper dive into these and other factors. Feel free to hit up the comments section with questions or comments.

Thanks,

Wikipedia has a good article on program optimization here: http://en.wikipedia.org/wiki/Program_optimization