Where on earth do you get the idea that he does? It is not the complexity of the algorithm but the straightforward nature of a theta join.

I really wouldn't dismiss Itzik Ben Gan's writings too lightly. He is easily up there in the top 10 of SQL Server gurus, and very possibly the very top T-SQL expert on the planet.

pootle flump ur codings are working excelent.

Yeah, that sounds a bit defensive doesn't it?

Point is, he isn't arguing a general case here but a very specific one. A theta join like yours is will involve half the number of rows a Cartesian product would involve.
There is a calculable and exponential increase in the number of rows processed.

pootle flump ur codings are working excelent.

Here's a quote from the paper:
I'm not dismissing Mr. Ben Gan's expertise, far from it. I'm just saying that reading twice the rows does not necessarily take twice the time. The number of rows read may be growing exponentially as data accumulate, but query run time does not have to, and in my experience often does not.

Beg your pardon. I thought you were referring to complexity of the query algorithm, not the plan.

For set based processors the processing of each successive row has a lower cost of the previous one. Under normal circumstances, reading twice as many rows results in twice as many rows being processed. And normally we notice little difference in processing normal queries as the data accumulates.

The point here though is that number of rows read <> the number of rows processed. In this specific case the addition of a single, average row in your inner table results in N/2 more rows being processed (the N being the number of rows in your outer table).

I am happy to script up some benchmarks if you are sufficiently motivated to put your observations up against Ben Gan's

pootle flump ur codings are working excelent.

May be it's a terminology issue, but for me "reading" and "processing" here means the same thing. I understand perfectly what you (and Ben Gan) say, but still I'm a bit uncomfortable with the perfect exponent on the benchmark diagram. I'm going to run some tests for myself when there's a slow day in my schedule.


Not table, partition {as in "OVER (PARTITION BY...)"}. In the example that kicked off this thread we were aggregating data by customer ID. The formula, of course, still stands.