More “Magic Squares” Solutions

Another thought occured to me tonight while I was phased out and not doing much of note.  There is another assumption I can add in to my solution of Matthew McGiffen’s Magic Squares Puzzle that I blogged about yesterday.

  • We have the set of numbers – 1 to 9.
  • We know it has to fit a grid of 3×3.
  • We know the columns and rows and diagonals must equal.
  • Therefore, we know each row is 1/3rd of 1 + 2 + 3 + 4 … + 9.
  • Each row sums up to 15.

Now we already have the math setting up to ensure the rows and columns and diagonals all equal in the previous solution – but we can also add a predicate to the JOINs to ensure that the numbers joined into each row are never greater than 15.

This will reduce the number of JOINs and the number of rows that ever get selected to be filtered.

It also means that I don’t need the ugly UNION code from the previous example.  It is slightly slower in at around 45ms – almost double the more performant solution – but I like the way it fits together.

DECLARE @nums TABLE(n TINYINT)
DECLARE @third TINYINT

INSERT INTO @nums (n)
VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9)

SELECT @third = SUM(n) / 3.0 FROM @nums

SELECT n1.n n1, n2.n n2, n3.n n3,
       n4.n n4, n5.n n5, n6.n n6,
       n7.n n7, n8.n n8, n9.n n9
FROM @nums n1
   JOIN @nums n2 ON n2.n <> n1.n AND n1.n + n2.n <= @third
   JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n) AND n1.n + n2.n + n3.n = @third
   JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
   JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n) AND n4.n + n5.n <= @third
   JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n) AND n4.n + n5.n + n6.n = @third
   JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
   JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n) AND n7.n + n8.n <= @third
   JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n) AND n7.n + n8.n + n9.n = @third
WHERE (n1.n + n2.n + n3.n) = (n4.n + n5.n + n6.n)
   AND (n4.n + n5.n + n6.n) = (n7.n + n8.n + n9.n) 
   AND (n1.n + n2.n + n3.n) = (n1.n + n4.n + n7.n)
   AND (n1.n + n4.n + n7.n) = (n2.n + n5.n + n8.n) 
   AND (n2.n + n5.n + n8.n) = (n3.n + n6.n + n9.n)
   AND (n1.n + n2.n + n3.n) = (n1.n + n5.n + n9.n) 
   AND (n1.n + n5.n + n9.n) = (n3.n + n5.n + n7.n);

And now that I have typed that out…

Would you believe between 2 – 4ms?  Seriously.  I can’t.

DECLARE @nums TABLE(n TINYINT)
DECLARE @third TINYINT
DECLARE @n1 TINYINT, @n2 TINYINT, @n3 TINYINT, 
        @n4 TINYINT, @n5 TINYINT, @n6 TINYINT, 
        @n7 TINYINT, @n8 TINYINT, @n9 TINYINT

INSERT INTO @nums (n)
VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9)

SELECT @third = SUM(n) / 3.0 FROM @nums

SELECT TOP(1) @n1 = n1.n, @n2 = n2.n, @n3 = n3.n,
              @n4 = n4.n, @n5 = n5.n, @n6 = n6.n,
              @n7 = n7.n, @n8 = n8.n, @n9 = n9.n
FROM @nums n1
    JOIN @nums n2 ON n2.n <> n1.n AND n1.n + n2.n <= @third
    JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n) AND n1.n + n2.n + n3.n = @third
    JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
    JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n) AND n4.n + n5.n <= @third
    JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n) AND n4.n + n5.n + n6.n = @third
    JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
    JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n) AND n7.n + n8.n <= @third
    JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n) AND n7.n + n8.n + n9.n = @third
WHERE (n1.n + n2.n + n3.n) = (n4.n + n5.n + n6.n) 
   AND (n4.n + n5.n + n6.n) = (n7.n + n8.n + n9.n) 
   AND (n1.n + n2.n + n3.n) = (n1.n + n4.n + n7.n)
   AND (n1.n + n4.n + n7.n) = (n2.n + n5.n + n8.n) 
   AND (n2.n + n5.n + n8.n) = (n3.n + n6.n + n9.n)
   AND (n1.n + n2.n + n3.n) = (n1.n + n5.n + n9.n) 
   AND (n1.n + n5.n + n9.n) = (n3.n + n5.n + n7.n);
 
SELECT @n1, @n2, @n3, @n4, @n5, @n6, @n7, @n8, @n9
UNION SELECT @n7, @n4, @n1, @n8, @n5, @n2, @n9, @n6, @n3
UNION SELECT @n9, @n8, @n7, @n6, @n5, @n4, @n3, @n2, @n1
UNION SELECT @n3, @n6, @n9, @n2, @n5, @n8, @n1, @n4, @n7
UNION SELECT @n3, @n2, @n1, @n7, @n6, @n5, @n9, @n8, @n7
UNION SELECT @n1, @n4, @n7, @n2, @n5, @n8, @n3, @n6, @n9
UNION SELECT @n7, @n8, @n9, @n4, @n5, @n6, @n1, @n2, @n3
UNION SELECT @n9, @n6, @n3, @n8, @n5, @n2, @n7, @n4, @n1; 

I mentioned in the last blog post that with that brute forcing through the numbers in the JOINS gets us to the 21,814th row, and then we have 8 rotations and reflections?

Obviously, with the JOINs in this solution, the only rows that will get returned are those where the three rows add up to 15.  This returns 2,592 rows, the 179th of which matches our criteria.

So, from that test I can only surmise one thing.  I can make this even faster.  I just need to move the logic of my testing from the WHERE clause to the JOIN clauses.

This one takes around 15ms and only returns the 8 rows that match the logic we’re after.

DECLARE @nums TABLE(n TINYINT)
DECLARE @third TINYINT

INSERT INTO @nums (n)
VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9)

SELECT @third = SUM(n) / 3.0 FROM @nums

SELECT n1.n, n2.n, n3.n,
       n4.n, n5.n, n6.n,
       n7.n, n8.n, n9.n
FROM @nums n1
     JOIN @nums n2 ON n2.n <> n1.n
         AND n1.n + n2.n < @third -- ROW 1 < 15
     JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n)
         AND n1.n + n2.n + n3.n = @third -- ROW 1 = 15
     JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
         AND n1.n + n4.n < @third -- COL 1 < 15
     JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n)
         AND n4.n + n5.n < @third -- ROW 2 < 15
         AND n2.n + n5.n < @third -- COL 2 < 15
         AND n1.n + n5.n < @third -- DIAG 1 < 15
         AND n3.n + n5.n < @third -- DIAG 2 < 15
     JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n)
         AND n4.n + n5.n + n6.n = @third -- ROW 2 = 15
         AND n3.n + n6.n < @third -- COL 3 < 15
     JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
         AND n1.n + n4.n + n7.n = @third -- COL 1 = 15
         AND n3.n + n5.n + n7.n = @third -- DIAG 2 = 15
     JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n)
         AND n7.n + n8.n < @third -- ROW 3 < 15
         AND n2.n + n5.n + n8.n = @third -- COL 2 = 15
     JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n)
         AND n7.n + n8.n + n9.n = @third -- ROW 3 = 15
         AND n3.n + n6.n + n9.n = @third -- COL 3 = 15
         AND n1.n + n5.n + n9.n = @third -- DIAG 1 = 15

And if I shortcut that one to only get the first result of matching numbers, then perform the “manual” reflections and rotations?

I’m getting a total of 0 – 1ms in my execution, once it’s in the query plan cache.  Sometimes I execute and it’s zero, and sometimes I have a total of 1ms in execution time, with 0 CPU time mentioned.

DECLARE @nums TABLE(n TINYINT)
DECLARE @third TINYINT
DECLARE @n1 TINYINT, @n2 TINYINT, @n3 TINYINT,
        @n4 TINYINT, @n5 TINYINT, @n6 TINYINT,
        @n7 TINYINT, @n8 TINYINT, @n9 TINYINT

INSERT INTO @nums (n)
VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9)

SELECT @third = SUM(n) / 3.0 FROM @nums

SELECT TOP(1) @n1 = n1.n, @n2 = n2.n, @n3 = n3.n,
              @n4 = n4.n, @n5 = n5.n, @n6 = n6.n,
              @n7 = n7.n, @n8 = n8.n, @n9 = n9.n
FROM @nums n1
     JOIN @nums n2 ON n2.n <> n1.n
        AND n1.n + n2.n < @third -- ROW 1 < 15
     JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n)
        AND n1.n + n2.n + n3.n = @third -- ROW 1 = 15
     JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
        AND n1.n + n4.n < @third -- COL 1 < 15
     JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n)
        AND n4.n + n5.n < @third -- ROW 2 < 15
        AND n2.n + n5.n < @third -- COL 2 < 15
        AND n1.n + n5.n < @third -- DIAG 1 < 15
        AND n3.n + n5.n < @third -- DIAG 2 < 15
     JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n)
        AND n4.n + n5.n + n6.n = @third -- ROW 2 = 15 
        AND n3.n + n6.n < @third -- COL 3 < 15
     JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
        AND n1.n + n4.n + n7.n = @third -- COL 1 = 15
        AND n3.n + n5.n + n7.n = @third -- DIAG 2 = 15
     JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n)
        AND n7.n + n8.n < @third -- ROW 3 < 15 
        AND n2.n + n5.n + n8.n = @third -- COL 2 = 15
     JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n)
        AND n7.n + n8.n + n9.n = @third -- ROW 3 = 15
        AND n3.n + n6.n + n9.n = @third -- COL 3 = 15
        AND n1.n + n5.n + n9.n = @third; -- DIAG 1 = 15

SELECT @n1, @n2, @n3, @n4, @n5, @n6, @n7, @n8, @n9
UNION SELECT @n7, @n4, @n1, @n8, @n5, @n2, @n9, @n6, @n3
UNION SELECT @n9, @n8, @n7, @n6, @n5, @n4, @n3, @n2, @n1
UNION SELECT @n3, @n6, @n9, @n2, @n5, @n8, @n1, @n4, @n7
UNION SELECT @n3, @n2, @n1, @n7, @n6, @n5, @n9, @n8, @n7
UNION SELECT @n1, @n4, @n7, @n2, @n5, @n8, @n3, @n6, @n9
UNION SELECT @n7, @n8, @n9, @n4, @n5, @n6, @n1, @n2, @n3
UNION SELECT @n9, @n6, @n3, @n8, @n5, @n2, @n7, @n4, @n1;

 

And now, I think it’s time to don the ole straight jacket and hop into my padded cell for the night.

You know, when I posted yesterday I was quite happy with the two solutions.  I thought it was quite a good attempt – getting from a > 10 minute loop-based SQL query down to 250ms and then taking it down to a further 26ms was great for me.  I would have left it there.

And then my brain took a quiet moment, brought back the problem and thought of something I could optimise further.  Even though it took more time I preferred the solution.  And then, I just couldn’t leave it alone when I wondered about how that would go with my more performant solution… 2 – 4ms later and I knew I was onto something and I kept digging until I have something that is pretty much instant.

Seriously, if you can beat this one – let me know so I can buy you a beer! I pretty much think this is me calling it…  I am surprised how I thought I had a solution and how much improvement I could still wring from it today.  It goes to show you, there’s always another take on it. Later!

 

SQL Puzzles – Magic Squares

I love logic puzzles.  That’s not to say I’m good at them, but I enjoy problem solving enough that I went into IT as a career.

Matthew McGiffen started a series of puzzles for people wanting to improve their SQL skills over on his blog.  The first one is a magic puzzle.

magicsquare3

The basic goal is to take a 3×3 grid and put into it the numbers 1 to 9, where the columns, rows and diagonals all add up to the same result.

Have a look at Matthew’s post, and have a think of it for yourself and we’ll go over my solution 🙂

 

 

So, you’ll see in Matthew’s comments section that there are a few people who went with an iterative approach, which would be typical programming logic.  It also takes up to 10 minutes(!) to brute force all the results this way.

I have a solution in his comments, but I wanted to discuss why I came up with it.

So, I went with a Set-based approach.  SQL is great at performing on sets of data.  Tables, resultsets in a optimal matter.  I remember an Itzik Ben-Gan talk at SQL Code Camp Downunder Oz several years ago, where he went over the difference in performance between cursors and loop-based logic and set-based, and it’s stuck with me ever since.  So, the first thing I do is try to figure out a set-based approach.

Here is my initial solution, I posted on Matt’s blog.

DECLARE @nums TABLE (n TINYINT)

INSERT INTO @nums (n)
VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9)

SELECT n1.n n1, n2.n n2, n3.n n3,
       n4.n n4, n5.n n5, n6.n n6,
       n7.n n7, n8.n n8, n9.n n9
FROM @nums n1
    JOIN @nums n2 ON n2.n <> n1.n
    JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n)
    JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
    JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n)
    JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n)
    JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
    JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n)
    JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n)
WHERE (n1.n + n2.n + n3.n) = (n4.n + n5.n + n6.n) 
    AND (n4.n + n5.n + n6.n) = (n7.n + n8.n + n9.n) 
    AND (n1.n + n2.n + n3.n) = (n1.n + n4.n + n7.n)
    AND (n1.n + n4.n + n7.n) = (n2.n + n5.n + n8.n) 
    AND (n2.n + n5.n + n8.n) = (n3.n + n6.n + n9.n)
    AND (n1.n + n2.n + n3.n) = (n1.n + n5.n + n9.n) 
    AND (n1.n + n5.n + n9.n) = (n3.n + n5.n + n7.n)

That solution runs in ~250ms.  A lot better than the 10 minutes that the loop-based method takes 🙂

Can we make it better?

I was thinking about this and I came up with a solution.  We’re still brute forcing all the combinations of the numbers in that

So, basically, you have the resulting correct dataset, and you have four rotations of the data.  The rotations are where the numbers rotate 90-degrees from rows to columns, then 180-degrees (so the top row becomes the bottom row) and then 270-degrees.

There is also reflections – the correct result is the same when you swap out column 1 and column 3, so the numbers read forwards and backwards, for all four rotations.

So, we know there are 8 solutions, and if you run that SQL, you will see them.

 

Basically, if we still assume we don’t know any of the correct sequence of numbers, we still have to brute force the first solution – the initial solution without rotations or reflections, and then we can perform the rotations and reflections.

In the initial solution, we’re finding all combinations of the numbers 1 – 9.  The resultset is 362,880 rows of data.

If we find the first result, it comes in at around the 21,814th row.

So, if we take that result at 21,814 and add the 8 rows we need to calculate, then we come in significantly fewer checks than brute forcing the whole result.

DECLARE @nums TABLE(n TINYINT)
DECLARE @n1 TINYINT, @n2 TINYINT, @n3 TINYINT, 
        @n4 TINYINT, @n5 TINYINT, @n6 TINYINT, 
        @n7 TINYINT, @n8 TINYINT, @n9 TINYINT

INSERT INTO @nums (n)
VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9)

SELECT TOP(1) @n1 = n1.n, @n2 = n2.n, @n3 = n3.n,
              @n4 = n4.n, @n5 = n5.n, @n6 = n6.n,
              @n7 = n7.n, @n8 = n8.n, @n9 = n9.n
FROM @nums n1
     JOIN @nums n2 ON n2.n <> n1.n
     JOIN @nums n3 ON n3.n NOT IN (n1.n, n2.n)
     JOIN @nums n4 ON n4.n NOT IN (n1.n, n2.n, n3.n)
     JOIN @nums n5 ON n5.n NOT IN (n1.n, n2.n, n3.n, n4.n)
     JOIN @nums n6 ON n6.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n)
     JOIN @nums n7 ON n7.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n)
     JOIN @nums n8 ON n8.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n)
     JOIN @nums n9 ON n9.n NOT IN (n1.n, n2.n, n3.n, n4.n, n5.n, n6.n, n7.n, n8.n)
WHERE (n1.n + n2.n + n3.n) = (n4.n + n5.n + n6.n) 
  AND (n4.n + n5.n + n6.n) = (n7.n + n8.n + n9.n) 
  AND (n1.n + n2.n + n3.n) = (n1.n + n4.n + n7.n)
  AND (n1.n + n4.n + n7.n) = (n2.n + n5.n + n8.n) 
  AND (n2.n + n5.n + n8.n) = (n3.n + n6.n + n9.n)
  AND (n1.n + n2.n + n3.n) = (n1.n + n5.n + n9.n) 
  AND (n1.n + n5.n + n9.n) = (n3.n + n5.n + n7.n);

SELECT @n1, @n2, @n3, @n4, @n5, @n6, @n7, @n8, @n9
UNION SELECT @n7, @n4, @n1, @n8, @n5, @n2, @n9, @n6, @n3
UNION SELECT @n9, @n8, @n7, @n6, @n5, @n4, @n3, @n2, @n1
UNION SELECT @n3, @n6, @n9, @n2, @n5, @n8, @n1, @n4, @n7
UNION SELECT @n3, @n2, @n1, @n7, @n6, @n5, @n9, @n8, @n7
UNION SELECT @n1, @n4, @n7, @n2, @n5, @n8, @n3, @n6, @n9
UNION SELECT @n7, @n8, @n9, @n4, @n5, @n6, @n1, @n2, @n3
UNION SELECT @n9, @n6, @n3, @n8, @n5, @n2, @n7, @n4, @n1;

This isn’t a really elegant solution as far as they go, and I’m sure someone smarter than me knows off-hand a nice way of handling the rotations and reflections better.

It does clock in at only 26ms though.  A full order of magnitude faster than the previous.

How’d you go? Can you think of a way to improve this further? Let me know!

 

SQL Order of Execution

When thinking about SQL performance tips and where to start, I always think back to the very basics.  I’ve actually see some simple things trip up performance.  Recently.  My own.

I’m sure that SQL gurus know that SQL performs it’s operations in a standard order, and the optimizer, while incredibly impressive, is not magical at figuring out the intent of someone’s SQL, as opposed to what they actually wrote.  I think developers, and newbies, think that the optimizer is more powerful and will overlook some simpler problems.

I’m going to include a contrived example to indicate how your SQL can be effected by basic problems, and hopefully if you stumble across this it will help.

The order of execution for SQL are a lot like the BODMAS order of operations for math.

For a particular query you may have the following components and they act in this order:

1 FROM / JOIN
2 WHERE 
3 GROUP BY 
4 HAVING 
5 SELECT
6 ORDER BY 
7 TOP / OFFSET-FETCH
  1. FROM / JOIN – This tells the engine which tables you’re getting your data from.  It is very quickly worked with the WHERE clause to narrow down specific data, but one of the important parts of making good performing SQL is getting the JOIN right, and filtering correctly.
  2. WHERE – Filters which information is brought back.  If you are only filtering on one side of a JOIN then it will rely on that JOIN to bring back rows from the other side that match the JOIN.
  3. GROUP BY – If you are going to aggregate your data into a SUM, or MIN/MAX or other aggregation, it will happen at this point.
  4. HAVING – And then you can filter again by the results of the aggregation.
  5. SELECT – You are choosing specific fields to return from the sets of data you have queried.  Optimizing your SELECT to the specific data you are after can be important to memory usage and bandwidth when returning your results to the client.
  6. ORDER BY – It will then sort the data if you have asked it to.  This can be small or large depending on the size of the result-set.  If you are going to further process the data on the client, then you can get a quick performance saving by not ordering it on the server.
  7. TOP / OFFSET-FETCH – And then, if you only want a subset of the data, you are going to reduce the result-set here.  After you have done all the previous processing.

So, it becomes clear when reading this order that when you do some things can be important.  For example, if you’re going to filter your result-set, if you can do it in the WHERE clause then you are saving a lot of CPU and time doing so there, rather than aggregating the entire result-set and filtering in the HAVING, if possible.

To the contrived example!

So, here is a query that I’ve made against the StackOverflow database that Brent Ozar helpfully keeps a copy of on bittorrent.

SELECT u.Id, u.DisplayName, COUNT(*) AS PostsCount
FROM dbo.Posts p
 JOIN dbo.Users u ON p.OwnerUserId = u.Id
WHERE p.CreationDate >= '2017-01-01' AND p.CreationDate < '2017-02-01'
GROUP BY u.Id, u.DisplayName
HAVING COUNT(*) >= 293
ORDER BY PostsCount DESC;

StackOverflowTop10

It all looks pretty straightforward.  I’m going into the database and getting the users that have more than 293 posts in the month of January, 2017.  This equates to the TOP 10.

So, we’re getting the data, filtering it by the date, getting the top 10 users – so we’d expect to be reading 10 rows from the Users table, right?

Table 'Users'. Scan count 1, logical reads 39913, physical reads 0, read-ahead reads 1423, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Posts'. Scan count 1, logical reads 1257, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Except we’re not.  We’ve got 39913 page reads.

If we take a look at the query plan, we can see that it’s actually performed some optimization for us and brought the aggregation early – however, it hasn’t decided to select the top rows from the HAVING clause before performing the JOIN.

Perf1QP1

This means that if we hover over the fat arrow depicting the INNER JOIN back to the Users table we see we’re actually reading in 7.6 million users before filtering for the HAVING clause.  Well, at least it optimized the aggregation, otherwise it could be many more!

Perf1QP1b

There are many ways to optimize this JOIN to perform better.

The query actually performs better if it can optimize knowing you want the TOP 10.

SELECT u.Id, u.DisplayName, COUNT(*) AS PostsCountSELECT u.Id, u.DisplayName, COUNT(*) AS PostsCount
FROM dbo.Posts p
 JOIN dbo.Users u ON p.OwnerUserId = u.Id
WHERE p.CreationDate >= '2017-01-01' AND p.CreationDate < '2017-02-01'
GROUP BY u.Id, u.DisplayName
ORDER BY PostsCount DESC
OFFSET 0 ROWS FETCH NEXT 10 ROWS ONLY;
Table 'Users'. Scan count 0, logical reads 155, physical reads 1, read-ahead reads 57, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Posts'. Scan count 1, logical reads 1257, physical reads 4, read-ahead reads 1253, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Perf1vTop

You can separate the aggregation out to a subquery to get the results prior to the join.

SELECT u.Id, u.DisplayName, p.PostsCount
FROM (SELECT p.OwnerUserId, COUNT(*) PostsCount
   FROM dbo.Posts p
   WHERE p.CreationDate >= '2017-01-01' AND p.CreationDate < '2017-02-01'
   GROUP BY p.OwnerUserId
   HAVING COUNT(*) >= 293
 ) p JOIN dbo.Users u ON p.OwnerUserId = u.Id
ORDER BY p.PostsCount DESC;

You can separate the subquery out into a CTE, which acts like a VIEW.

WITH PostsCte AS (WITH PostsCte AS (
 SELECT p.OwnerUserId, COUNT(*) PostsCount
 FROM dbo.Posts p
 WHERE p.CreationDate >= '2017-01-01' AND p.CreationDate < '2017-02-01'
 GROUP BY p.OwnerUserId
 HAVING COUNT(*) >= 293
)

SELECT u.Id, u.DisplayName, p.PostsCount
FROM PostsCte p JOIN dbo.Users u ON p.OwnerUserId = u.Id
ORDER BY p.PostsCount DESC;

You can make the initial subquery as a separate query into a temporary table.

CREATE TABLE #posts (Id INT, PostsCount INT)

INSERT INTO #posts (Id, PostsCount)
SELECT p.OwnerUserId, COUNT(*) PostsCount
FROM dbo.Posts p
WHERE p.CreationDate >= '2017-01-01' AND p.CreationDate < '2017-02-01'
GROUP BY p.OwnerUserId
HAVING COUNT(*) >= 293

SELECT u.Id, u.DisplayName, p.PostsCount
FROM #posts p JOIN dbo.Users u ON p.Id = u.Id
ORDER BY p.PostsCount DESC

DROP TABLE #posts;

Similarly, you can use a temporary table variable.

DECLARE @posts TABLE (Id INT, PostsCount INT)

INSERT INTO @posts (Id, PostsCount)
SELECT p.OwnerUserId, COUNT(*) PostsCount
FROM dbo.Posts p
WHERE p.CreationDate >= '2017-01-01' AND p.CreationDate < '2017-02-01'
GROUP BY p.OwnerUserId
HAVING COUNT(*) >= 293

SELECT u.Id, u.DisplayName, p.PostsCount
FROM @posts p JOIN dbo.Users u ON p.Id = u.Id
ORDER BY p.PostsCount DESC;

The point here is there are several different ways to approach improving your queries, and you will find a pattern that suits over time, that is readable, and its worth paying attention to your tools to improve your performance.

The optimizer can do some work at improving performance, but having an idea of the order that things are generally done helps you know where the bottleneck of your query may be.

The difference in basic execution times for the six different queries, in CPU use is:

 SQL Server Execution Times:
 CPU time = 2359 ms, elapsed time = 2569 ms.
 CPU time = 250 ms, elapsed time = 362 ms.
 CPU time = 188 ms, elapsed time = 233 ms.
 CPU time = 203 ms, elapsed time = 260 ms.
 CPU time = 172 ms, elapsed time = 213 ms.
 CPU time = 203 ms, elapsed time = 204 ms.

Improving your performance to 1/5th the time, resources, reduces the WAITS, the locking contention and allows you to do a lot more with the hardware you’ve got.

Obviously, as mentioned earlier, this is a contrived example, and you’d do other things to improve performance such as caching of results, but it’s a reminder to keep an eye on your server, and pay attention to the small things, as they can have a big impact on your server performance.

Some further reading with better examples:

SQLBolt – SQL Lesson 12: Order of execution of a Query

Itzik Ben-Gan – Logical Query Processing: What It Is And What It Means to You