Big O for zigzag merge join?

Question

What is the Big O for the zig-zag merge join algorithm?

GAE's Big Table uses it, they go into it in these videos:

• http://www.youtube.com/watch?v=AgaL6NGpkB8
• http://www.bestechvideos.com/tag/zigzag-merge-join

The reason I ask is that if I understand this example correctly, the Big O will approach O(n) for collections that contain very many matches with only one or the other, but not for both (or all three in this example).

Answer 1

Read the Performance section of Index Selection article:

The actual performance depends on the shape of the data. Specifically, the average number of entities considered for each result returned is O(S/R). This indicates that poor performance is likely when many entities match each scan, but few entities match the query as a whole (R is small and S is large).

As article notes this only affects normal indexes. If you want O(log n) speed you should define a composite index.