Golfer22 (5/26/2013)
A subquery could run in O(k) time which is very fast. In fact, it could be merely a mathematical operation (e.g., 1+1). But it could run in O(n!) which is very slow. A subquery could be a join.Joins can be one of three types: nested loops, merge joins and hash joins. Nested loops are appropriate for small joins. Merge joins will be chosen by the database optimizer when the tables are almost in the correct order for the join.
Is there a statistic to indicate the degree or percentage of rows that are sorted in the table? Ie., the "sorted-ness" of the table? I was under the impression that the table was either sorted (ordered by a clustered key) or not, so this is a new one for me!