Fixing javascript variable leaks

Today I happended to have a look at my application's window object and was shocked to see that 'i' was defined on it! I doggedly started searching my code to see where the leak had perpetrated itself from. After an hour of debugging, which included using Google's online closure compiler (Thanks Sandy!!) and jslint, I came up with nothing.

It struck me that it could be some of the js-libraries that I was using that were causing the leak, and not my code. I tried doing a binary-search on the js-includes, but that didn't work since the code wouldn't even run without most of those includes. At this point I really didn't know how to even go about trying to fix it!!

A few hacky thoughts later, I decided to introduce this code in my application:

var _iv = setInterval(function() {
  if (typeof window.i != "undefined") {
    clearInterval(_iv);
  }
}, 10);

Of course, this relied on the fact that I had inserted a verbiage of console.log() statements in my code at various points (It actually helped to have them!!)

This bit of hackery at least helped me determine that the error happened after a certain set of statements (functions) had executed. From here, it was manual work, checking every function and callback (yes) in my code as well as any library that I was using.

After about 30 minutes, I was able to trace the leak to embed.ly's jQuery library. I also discovered that the fb-complete jQuery library I was using had this leak, but it wasn't the one responsible for the specific instance of the variable 'i' that I was seeing then.

When to use events & when to use callbacks?

With the recent spate of javascript programming that I've been subject to, I've found myself asking this question quite often to myself "Should I use callbacks here or should I use events (jQuery trigger & bind)?"

I've found this initial approximation quite useful till now: "If the operation that will follow depends upon the exact instance of this operation, then wrap the state in a closure and use a callback. Otherwise, use events." The advantage of using events is that:
1. You need not think of all the actions that could result in this event handler being called.
2. You need not tell anyone that this particular event handler needs to be invoked. Everyone just publishes some data (like a tweet) and all those interested (followers) just gobble that data up.
3. You can dynamically attach event handlers. So, if some component in the system suddenly decided to react to certain events, it can just plonk itself into to the listeners queue for that event.

jQuery goes one step further and allows you to trigger (and bind) events on specific DOM nodes only!! And then it goes a step further and lets you define an event namespace to try and prevent event name conflicts.

SQL Query optimization - Part-8 (Indexes Schmindexes)

The "Why are my queries slow despite indexes on all columns" Edition.

Consider the following table:

CREATE TABLE florist_orders(
 order_id INT NOT NULL PRIMARY KEY AUTO_INCREMENT, 
 basket_color INT (1) NOT NULL, -- This can be either 0, 1, 2 or 3
 num_roses INT NOT NULL, 
 num_sunflowers INT NOT NULL, 
 num_daisies INT NOT NULL, 
 processed INT(1) NOT NULL DEFAULT 0, 
 created TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

Let's assume that the packaging for every basket of a different color is done by a diffrent person. Additionally, baskets packaging also differs based on the maximum number of flowers of each type. If there is more than 1 of any type, the packaging differs from when there is at most 1 of each type of flower. Each packager wants to check the orders that she needs to process.

The following query works fine:

SELECT * FROM florist_orders
WHERE
 basked_color = 2 AND
 processed = 0 AND
 (num_roses > 1 OR num_sunflowers > 1 OR num_daisies > 1)
ORDER BY created ASC -- Process older orders first to avoid starvation
;

However, as the size of the florist_orders tables gorws, you realize that each query is taking too long. Why is this? You have an index on every column and yet queries are slow?

You decide to create composite indexes. As a first attempt, you create an index on

(basket_color, processed, num_roses, num_sunflowers, num_daisies)

but notice that it hasn't really affected the query's execution time. Additionally, EXPLAIN says that no indexes are being used!! What to do now?

To solve this issue, you would need to modify your table and make it friendly for this specific query. These are the steps you would need to take:

1. Add a column named num_flowers which is set to MAX(num_roses, num_sunflowers, num_daisies) on every INSERT and UPDATE via TRIGGERS.
2. Then, create an index on:

   (basket_color, processed, num_flowers)

3. Modify your query to read:

   SELECT * FROM florist_orders
   WHERE
    basked_color = 2 AND
    processed = 0 AND
    num_flowers > 1
   ORDER BY created ASC -- Process older orders first to avoid starvation
   ;

This should pretty much fix any speed issues with the aforementioned query and ensure that all queries remain responsive. This trick will work ONLY if all the flowers are being checked to be greater than the SAME number.

Firefox, I love you!!

The day was saved by Firefox's page cache. I typed in a reply on a forum thread, clicked "post reply" and then closed the tab, only to realize that I wasn't logged in and that a login dialog had popped up just as I had closed the tab. I right-clicked the tab-list and clicked "Undo Closed Tab" and poof!! the complete tab with all its state was there, awaiting my credentials!!

Awesome stuff Firefox... I love you!!

Peer-2-Peer systems at their best!!

Recently, the skype network went down. You can read all about it here.

However, the exciting take away from this is (quoting from the link above) "In order to restore Skype functionality, the Skype engineering and operations team introduced hundreds of instances of the Skype software into the P2P network to act as dedicated supernodes, which we nick-named “mega-supernodes,” to provide enough temporary supernode capacity to accelerate the recovery of the peer-to-peer cloud."

Which is exactly my idea of how a self-healing peer-2-peer system should behave. Introducing more nodes into the mix should ideally help solve scaling and availability issues, which is exactly what the Skype team did. I would like to congratulate them for that!!

Practical SVD for the curious reader

Let's see an example of how SVD can be used perform seemingly daunting tasks.
Consider that we are implementing a rating system for a contest and we want to know player that may have similar skill. Additionally we would like to know the hardness of the tasks in the contest since they are not known apriori.

We build a a matrix that holds player number on the y-axis and task number on the x-axis. Let us suppose that we roughly know the first 3 problems to be easy, the next 3 to be of medium difficulty and the next 3 to be hard. The built matrix would look like this:

# 0  1  2  3  4  5  6  7  8
[ 1, 1, 1, 0, 0, 0, 0, 0, 0 ], #0
[ 1, 1, 1, 1, 0, 0, 1, 0, 0 ], #1
[ 1, 0, 0, 0, 0, 1, 1, 1, 0 ], #2
[ 1, 1, 1, 1, 1, 1, 0, 0, 0 ], #3
[ 1, 0, 1, 1, 0, 0, 1, 1, 1 ], #4
[ 1, 0, 1, 0, 0, 0, 0, 0, 0 ], #5
[ 1, 0, 0, 1, 1, 1, 0, 0, 0 ], #6
[ 1, 0, 0, 1, 1, 1, 1, 1, 1 ], #7

Now, we compute the SVD of this matrix and keep only the best 4 feature sets.

We get [U=]

[[-0.22828916 -0.50341088  0.06758431 -0.27577721]
 [-0.3796649  -0.38290566  0.21189598  0.16725752]
 [-0.29514798  0.33343393  0.18247298 -0.80693185]
 [-0.4283514  -0.28592541 -0.50767041  0.05970937]
 [-0.42379852  0.09624233  0.5690528   0.38393312]
 [-0.18451958 -0.30010945  0.12296957 -0.24683212]
 [-0.31511921  0.15603403 -0.56486439  0.03629706]
 [-0.46924257  0.53231036 -0.03863212  0.17781851]]

We get [S=]

[[ 4.86583872  0.          0.          0.        ]
 [ 0.          2.40125574  0.          0.        ]
 [ 0.          0.          2.02979097  0.        ]
 [ 0.          0.          0.          1.29857912]]

We get [V=]

[[-0.55984867 -0.14756061  0.02109021 -0.38852126]
 [-0.21297571 -0.48817872 -0.11242051 -0.03758748]
 [-0.33799385 -0.57307894  0.22851232  0.06799022]
 [-0.41435336  0.0482063  -0.16268579  0.63532176]
 [-0.24923004  0.16758689 -0.54742924  0.21086504]
 [-0.3098872   0.30644504 -0.45753181 -0.41053094]
 [-0.32221659  0.24115755  0.45560831 -0.06000612]
 [-0.24418998  0.40061814  0.35121531 -0.18880653]
 [-0.18353282  0.26176     0.26131788  0.43258946]]

Next, we need to compute U*S and V*S.
What is the significance of these matrices?
The matrix U*S will allow us to find user that are similar in skill to each other.
The matrix V*S will allow us to determine problems that have been misclassified or are actually similar in difficulty to each other.

After computing the U*S and V*S matrices, we will take the row-wise sum of squared differences (SOSD)and check the pairs of rows that have the least such difference. These are the rows that are of interest to us.

We get [SOSD(U*S)=]

[(0, 1, 1.0430999999999999),
 (0, 2, 4.6740000000000004),
 (0, 3, 2.7736000000000001),
 (0, 4, 4.7484000000000002),
 (0, 5, 0.29770000000000002),
 (0, 6, 4.4981999999999998),
 (0, 7, 7.9534000000000002),
 (1, 2, 4.7319000000000004),
 (1, 3, 2.2631000000000001),
 (1, 4, 1.9745999999999999),
 (1, 5, 1.2628999999999999),
 (1, 6, 4.2881999999999998),
 (1, 7, 5.2785000000000002),
 (2, 3, 5.8609),
 (2, 4, 3.7233999999999998),
 (2, 5, 3.1476999999999999),
 (2, 6, 3.6909999999999998),
 (2, 7, 2.7824),
 (3, 4, 5.7964000000000002),
 (3, 5, 3.2058),
 (3, 6, 1.4441999999999999),
 (3, 7, 4.8299000000000003),
 (4, 5, 3.7522000000000002),
 (4, 6, 5.8014999999999999),
 (4, 7, 2.7383999999999999),
 (5, 6, 3.6880000000000002),
 (5, 7, 6.3265000000000002),
 (6, 7, 2.5535000000000001)]

Analysis of SOSD(U*S): User #0 & user #5 seem to be skilled similarly. Similarly, the following pairs of users also seem to be of similar calibre: (0, 1), (0, 5), (1, 4), (1, 5), (3, 6), (4, 7), (6, 7)
Some of this analysis may seem questionable especially considering that we designated the last 3 problems to be hard. How are user #1 & #4 similar if this is the case?
Let's look at the V*S matrix.

We get [SOSD(V*S)=]

[(0, 1, 3.7989000000000002),
 (0, 2, 2.7381000000000002),
 (0, 3, 2.629),
 (0, 4, 4.7946),
 (0, 5, 3.6124999999999998),
 (0, 6, 3.1680999999999999),
 (0, 7, 4.6081000000000003),
 (0, 8, 5.6936999999999998),
 (1, 2, 0.9093),
 (1, 3, 3.3931),
 (1, 4, 3.3944000000000001),
 (1, 5, 4.5884),
 (1, 6, 4.6798999999999999),
 (1, 7, 5.5022000000000002),
 (1, 8, 4.2117000000000004),
 (2, 3, 3.5369999999999999),
 (2, 4, 5.8647999999999998),
 (2, 5, 6.8044000000000002),
 (2, 6, 4.0688000000000004),
 (2, 7, 5.8483000000000001),
 (2, 8, 4.8121),
 (3, 4, 1.6414),
 (3, 5, 2.8456000000000001),
 (3, 6, 2.806),
 (3, 7, 3.6351),
 (3, 8, 2.3344),
 (4, 5, 0.88270000000000004),
 (4, 6, 4.4261999999999997),
 (4, 7, 3.9102999999999999),
 (4, 8, 2.931),
 (5, 6, 3.6707999999999998),
 (5, 7, 2.931),
 (5, 8, 3.7172000000000001),
 (6, 7, 0.36359999999999998),
 (6, 8, 1.0225),
 (7, 8, 0.88270000000000004)]

The following pairs of problems seem to be equally difficult/easy: (3, 4), (1, 2), (4, 5), (6, 8), (7, 8), (6, 7)
You can immediately see a clique of (6, 7, 8) which were all originally designated as hard problems!
Similarly, (3, 4, 5) seem to be related and so do (1, 2). The reason that problems #0 can not be classified by the system could be that since it has been solved by everyone, not much can be said conclusively about it.
You would have noticed that users #1 & #4 have both solved problems #0, #2, #3 & #6. As it turns out, it seems that the features (as deduced by the system) have given a higher weightage to one or more of these problems, which is why users #1 & #4 have been clustered together.

SVD 101

I've been trying to find out more about SVD (Singular Value Decomposition) in the last few days, and here is what I have come up with (links marked with a star[*] MUST be READ). I'll try updating it as and when possible.

1. http://www.funpecrp.com.br/GMR/year2007/vol4-6/xm0017_full_text.html
2. http://www.cs.um.edu.mt/~csaw/CSAW04/Proceedings/09.pdf
3. http://www.math.umn.edu/~lerman/math5467/svd.pdf
4. http://www.seobook.com/lsi/tdm.htm
5. http://web.mit.edu/snikolov/www/topicweb_verbose.pdf
6. http://www.cs.carleton.edu/cs_comps/0607/recommend/recommender/svd.html
7. http://en.wikipedia.org/wiki/Latent_semantic_indexing
8. * http://web.ics.purdue.edu/~park283/wp-content/uploads/2010/10/Singular_Value_Decomposition_Tutorial.pdf
9. http://web.mit.edu/be.400/www/SVD/Singular_Value_Decomposition.htm
10. http://www.miislita.com/information-retrieval-tutorial/singular-value-decomposition-fast-track-tutorial.pdf
11. http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-1-understanding.html
12. http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-2-computing-singular-values.html
13. http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-3-full-svd.html
14. * http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-4-lsi-how-to-calculations.html
15. * http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-5-lsi-keyword-research-co-occurrence.html (explains the significance of the U & V matrices)
16. * http://www.dcs.shef.ac.uk/~genevieve/lsa_tutorial.htm (Thanks to Shashank Singh for this link)

SVD can be used to:

1. Determine Document Similarity
2. Determine User similarity in a competition (or in a rating-based system such as movie recommendations)
3. Perform Image compression
4. Perform Principal Component Analysis
5. and much more...

You can use the following tools to compute the SVD of a matrix:

1. SciLab
2. NumPy (SciPy)

Suggest more recipients (in a chat conference)

If you don't already know, gmail has had a feature called Suggest more recipients for a while now.

From the link above, "Gmail will suggest people you might want to include based on the groups of people you email most often. So if you always email your mom, dad, and sister together, and you start composing a message to your mom and dad, Gmail will suggest adding your sister. Enter at least two recipients and any suggestions will show up like this."

I am planning on extending this even for the chat conversation start page in the chat client that I'm working on. So, if you start entering JIDs of people you want to chat with, the client should automatically suggest more participants.

Thanks to Sandy for the providing the link to gmail blog!!

Update (02/01/2011): This feature is now implemented and part of the dev. versions.

Debugging PHP's $_REQUEST

The $_REQUEST page in the PHP manual, says that "$_REQUEST is an associative array that by default contains the contents of $_GET, $_POST and $_COOKIE. The variables in $_REQUEST are provided to the script via the GET, POST, and COOKIE input mechanisms and therefore could be modified by the remote user and cannot be trusted. The presence and order of variables listed in this array is defined according to the PHP variables_order configuration directive."

I was under the impression that $_REQUEST would only contain data from the $_GET and the $_POST variables. In my application, I was setting cookies that had the same key as one of the GET parameters that I was expecting. The script was hence getting data set by the cookie and not the GET parameter!! I went half mad trying to debug this and was suspecting some caching issue. Things got queerer when changing some of the GET parameters worked, but others refused to budge from their original value!! You can imagine the perplexing situation I was in. Thankfully, though it dawned on me to check the PHP manual to see what the $_REQUEST was supposed to contain and I was able to fix my code to use $_GET.

Since then, I have come across this very useful page which mentions the exact problem I had and also says why one should avoid using $_REQUEST.

Shortest Slowest path

A few weeks ago, I had was presented with a question: "You are given an n X n matrix. Each cell has a non-negative integer that denotes the cost of landing on that cell. Start from the top-left corner, compute the cost of the least-cost-path to reach the bottom-right corner of the matrix such that the sum of all costs incurred during the traversal is the least. Additionally, you are allowed to move only down or right."

Of course, this is just a slight variation of Dijkstra's Shortest Path problem, but I was surprised at the first solution that came to mind. I was trying really hard to not use Dijkstra's shortest path algorithm to solve this problem. I landed up linearizing all the n² cells into n² vertices in a graph and applied the Floyd-Warshall algorithm on the resulting matrix (of having side n²). Hence, the total complexity shot up to a whooping O(n⁶) (n being the side of the original matrix). If I had used a standard BFS or Dijkstra's algorithm, I would have been able to solve it with a runtime complexity of O(n² log(n)).

However, this was a very interesting exercise in functional programming since I was able to piece together a solution by chaining solutions to existing problems. The composition looks something like this:
Solution(matrix) = FloydWarshall(Linearize(matrix))

Dyslexia Friendly

I made my home page Dyslexia Friendly today. Click here to find out more.

Help on selected text

Today, I've added this new feature that I call "Help on selected text."

If you select any word or phrase on my blog, a small window will pop-up that will ask you to if you want more information on the selected phrase. If you click on the More Info link, you will be shown some more information if it is available. Pictures if available will also be shown. I am using Duck Duck Go's API to fetch this information. If nothing is found, an appropriate message will be displayed. If you select a block of text that is greater than 60 characters in length, it will be ignored and no prompt for more information will be shown.

Let me know if you find it useful or want to integrate it on your site!!

Update: Sandy suggested making the opacity of the box depend upon the distance of the mouse pointer from the info-box. Implemented this.

Update: A separate page documenting this widget, providing samples and examples has been put up here.

Update: My homepage: http://dhruvbird.com/ is now enabled with the zero-click plugin!!

TDDB: What I would do differently if I were to re-implement it

Working on TDDB was a lot of fun (for all of us) and we learnt a lot!! Probably much more than what we initially thought. From not knowing anything about databases to implementing our own meant that we really hit the jackpot in terms on learning stuff and being hand-on. Watching theory and practice collide head on is something we experienced then!!

If I were to work on TDDB from scratch all over again, these are the things I would do differently:

1. Use HTTP for the transport layer. We implemented our own protocol for the transport. We got to learn a lot while doing so. However, since there's such a huge eco-system already built around HTTP, it would make sense to use it. Another advantage of using HTTP is that making clients in various languages (and even a client for the browser) is much less of an issue.
2. Use sqlite/MySQL/postgreSQL/BerkeleyDB or some other underlying DB for the actual storage. We implemented our own disk format and transaction subsystem instead of using something already available. We learnt a HELLUVA LOT while doing so. However, if I were to do it again, I'd go with something I can just build on. I would need to implement the query parser, the optimizer, the execution engine and the lock manager though since for a distributed DB, these things would define the system.
3. In general, use as many existing systems and build on them rather than implementing your own. While the latter approach means that one can learn much more, it also means that some of the "interesting" things won't get as much time and thought as they should.
4. Research the common use-cases more thoroughly. I think we just scratched the surface of use-cases when it came to distributed query processing and I think that there is a much wider audience for such a system. Exploring this in more detail is something I hope to do in the future.

Interesting problem (string based)

Find the longest prefix of a string that is a palindrome.
O(n²) is easy, but you need come up with something that's O(n).

Hint: KMP

The psychological effects of a bad API

It makes everyone sick and your developers lose their creativity and grapple with the API rather than solving interesting problems and innovating.

Anyone can code, but only the fearless can be great

I personally think that every programming task needs to be approached from the perspective of being completely bug-free. When you write code, think that it is going to be deployed on a rocket or a space-craft and that the lives of a few hundred depend on the robustness of the code. Of course, you can cut yourself some slack by making practical simplifying assumptions about the specific task at hand, but I'd rather programmers started with the strictest requirements and then loosened them rather than the other way around (which seems to be happening more often these days).

Library v/s Framework

I sort of dislike frameworks (except for the ones that actually make your life easier). Libraries on the other hand are really great things!! Frameworks say: "This is all you are allowed to do and these are the ways you could do it. Additionally, I allow you the freedom of doing this insignificant operation in any way you see fit." On the other hand, libraries say: "If this is the input you feed me, this is the output you shall get. It's up to you to feed me the input and then you are free to do whatever you wish with the output I give you."

This change of mindset makes a world of difference while writing applications that do different things or just things differently from what the "framework" architect thought to be "the" way of doing things.

Django is a GOOD framework. It goes a long way to obviate all the mundane tasks, but at the same time provides a rich library-like interface to many convenience functions. IMHO, the Library way is the functional way where you can compose a complex operation from many small operations chained or composed together. A framework on the other hand reminds me of OO and something like the a template method pattern. Now, I really like the template method pattern when it is used minimally and with care. However, using this pattern for everything you do is just brainless. In the same way, frameworks aren't the solution to all design related problems.

jQuery is an awesome library. It's been true to its slogan of "Write less, do more". It's literally packed with a lot of convenience functions that lets you create really nice looking and functional UIs and web-applications without breaking a sweat. I think it gels in very well with the javascript and DOM eco-system. It doesn't try to be different and OOish (like Dojo) which is where I think it scores.

Frameworks cramp creativity whereas Libraries liberate the artist within the programmer. I hear a lot of people say "tell, don't ask", but I would say "ask and you shall be told."

SQL Query optimization - Part-7

(The you need referential integrity for more than referential integrity edition)

Why do we tag our blog posts with well, tags, so that people can glean meaningful information from these terse blocks of text. A post tagged with vacation or tutorial says so much about the blog post. Similarly, hinting the DB that a certain column has a similar looking entry in some other table means a lot to the execution planner. Yes, I'm talking about Foreign Key references.

If it finds such a hint, it can infer that:

1. Every value in this column has some unique value in the column that it refers to.
2. Since it is pointing to a UNIQUE column, joining a column from this table will match exactly 1 row from the table to which it refers to. Hence, while NATURAL JOINing the 2 tables, the execution engine can stop when it finds one match.
3. A Foreign Key constraint forces you to make the referenced column UNIQUE. This means that a WHERE clause on that column will never match more than one row and the optimizer can take advantage of that. If such a query occurs as a subquery, then the optimizer can evaluate the sub-query first and replace the sub-query with a single constant which is the result of the inner query's execution.

All these optimizations can significantly reduce your query's execution time.

SQL Query optimization - Part-6 (How NATURAL JOINs work)

(The devil lies in the details edition)

To show how JOINing in databases works, we'll take up a very simple example and make some simplifying assumptions (which are true) about databases & indexes so that we can reason clearly about certain concepts and yet still understand the key insights required for comprehending how NATURAL JOINs work.

Let's assume that we have 2 tables X & Y that we want to join on a column named 'c'.
SELECT * FROM X JOIN Y ON X.c=Y.c WHERE <condition>

For the sake of simplicity, we shall draw parallels between the tables X & Y and 2 arrays AX & AY that are in-memory. Also let the size of the table X & Y be sA & sY. We shall consider a few cases and try to analyze how JOINing would work in these scenarios:

1. No index on 'c' in either table: The DB is forced to perform a O(sX.sY) operation by running code that looks like a nested loop. Hence, this type of join is called a nested loop join. This is the most expensive type of join and must be avoided if the tables X & Y are very large.
2. B-Tree index on 'c' only in table X: (This case is symmetrical to a B-Tree index being present on 'c' only in table Y -- but not really). This case is akin to one of the arrays being sorted and the other being unsorted. Here, the execution engine can loop over the table that doesn't have an index (the unsorted array in our analogy) and for each element, lookup the corresponding value in the table with the index (sorted array lookup using binary search). The cost for joining is O(sX.log sY) or O(sY.log sX). This is why which table has the index is important and the 2 cases aren't exactly symmetrical. It is advisable to have an index on the larger table -- to keep the linear component in the complexity as low as possible.
3. Hash index on 'c' only in table X: (This case is symmetrical to a Hash index being present on 'c' only in table Y -- but not really). Again, this case is similar to the one above and depending up on whether table X or table Y has an index, the JOIN complexity will be either O(sY) or O(sX) respectively. Again, it is advisable to have an index on the larger table.
4. Hash index on 'c' in both tables: This case isn't much different from the previous case except for the fact that the execution planner can decide whether to iterate over table X or table Y depending up on which table has a fewer number of rows.
5. B-Tree index on 'c' in both tables: This is a very interesting and common case and is similar to the problem of trying to find the intersection of 2 sorted arrays AX & AY. It should be clear that the complexity of doing so is O(sX + sY). This bound is NOT tight and may be as low as theta(min(sX, sY)). Hence, it should be clear that some of the join strategies above can (in theory) be faster than this one. However, the execution planner may not always choose to use both indexes if it has heuristic data that suggests that iterating over one of the tables would be much cheaper (say because it contains only 2 rows). This join is most commonly referred to as the Merge Join because it looks like you are merging 2 arrays.

SQL Query optimization - Part-5 (Motivation)

(The better late than never edition)

I'm sure many of you have worked on web-apps (you know stuff like wikipedia, gmail, facebook, codechef, reddit, digg, duckduckgo or even your personal web-site which has some dymnamic/interactive content). I'm sure that out of these many, many of you have worked on sites that get traffic to the tune of a few hundred visitors per second. I'm sure you know how painstaking it is to run such a site and keep it up and running and responsive for all its users. Lots of things like the web-server, DB, file system, OS, etc... need to be tweaked and tuned and retro-fitted to suit the needs of the things around it.

The one place (in my experience) that can easily introduce bottlenecks is the DB (database). That's because it is something that is a real work-horse and is programmed by you (the application writer), who may not know what food it likes. It's very easy to write a query that runs 10x slower than what it really should be running and not notice this for a very long time.

Imagine the time you get slashdotted and need to support 5000 requests instead of the customary 50 requests/second. Don't you wish your DB doesn't just die due to the load?? Well, if you are one such person who is pedantic about the performance of your database, you are thinking right!

You will mostly learn how to optimize your DB through experimentation, but since others have been burned before, you might as well stay and take advantage of their experiences.