As I mentioned in my previous post, I'm going to be taking on a new job soon.  I'm actually going back to work for Microsoft, so it's not entirely new ;).  I'll still be living in Austin, TX, and commuting up to visit Redmond regularly.

Unfortunately, working for MS and blogging on a consultant's website is a bit confusing and perhaps a conflict of interest (or the appearance of one).  Yes, I expect that you guys are smart enough to figure it all out, but it's probably not a great long-term situation.  So, I'll have to move my ramblings back over to MSDN or somewhere like that.  I'll post up a link in a week or so once I have it all figured out.

I'd like to thank Paul and Kimberly for allowing me to blog here - they have been extremely supportive of me doing this, and I certainly appreciate it.  I hope that my content has added to their site.

What will I be doing at Microsoft?  Well, my role will be as a software architect, which is pretty much what I did previously.  I spend time trying to figure out how to make features that will help customers, make those features work well, work fast, work reliably, etc.  I will still be working on the SQL Engine, Query Processing, and whatever else comes my way that interests me.

Why not move back to Redmond?  Well, I moved away due to the climate, and I don't have any particular desire to move back.  It's obviously imperfect to work remotely, but I really *do* like building database engines.  The SQL Team was great in finding a way for me to continue working for Microsoft, and I was more than a bit flattered that they were so open in making this work for me.

I plan to leverage my position out here to talk to customers more than is often possible "inside the bubble", and I am hopeful that this will make me more effective at my job.

That's the news for today

Thanks,

Conor Cunningham

Well, I can tell you that I've been doing a few things lately.

1. I'm writing a chapter for an upcoming book - lots of interesting details like what you read here on the blog about query processing and query optimization.  It will come out around the end of the year.

2. I've been getting a new job - I'll post some details on this soon.  This has taken some more time :).

3. I've been doing some consulting work - helping people with some of the more advanced topics in SQL Server.

4. I've been getting ready to improve the sprinkler system at my house - going to try this out: http://www.smarthome.com/312cr.html

5. I'm going to try to fix my HTPC.  I have a Hauppage HDTV card that was working fine with Vista Ultimate + Media Center, and then I installed http://www.mythtv.org/ - MythTV (and me trying to futz with it) won't believe that I live in my actual timezone.  This tends to make recording things very difficult.  I believe that however it has installed Java has stored my timezone differently than windows.  Now the whole thing just doesn't work, and I'll call that "frustrating".

6. I have been on an automation crusade, trying to automate various tasks around the installation and setup of my computers.  For example, I am collecting up the registry changes to fix up the windows UI to my liking on each new machine.  I am also writing scripts to install  all of my commonly used tools.  I have determined that I am too old to continue to fight through the same silly user interfaces each time I set up a VM or new machine.

I am still interested in any questions you have, but I'll likely continue to post at a somewhat reduced rate until I get this book chapter done :).  I've got deadlines!

Happy Querying,

Conor Cunningham

http://technet.microsoft.com/en-us/magazine/cc434693.aspx

It covers some of the new features in SQL 2008 w.r.t. Data Warehousing.

Conor Cunningham

(Apologies to Star Trek).

I received a question about trigger performance, especially the do's and dont's about how they are used.

Let's first start by saying that triggers can be very useful tools to facilitate server-side programming in OLTP systems.  They are powerful ways to do things like audit changes to a table, validate business logic, or extend the features that the database server provides to you.  So, in the proper hands, these can really provide a lot of business value.

The problem with this area is that there is a great temptation to think about databases procedurally, as you would with a programming language like C++ or C#.  You can write code that looks like a procedural function call and have it get called for each insert into table!  Before you know it, non-database programmers are checking in code to your production sysem.  Suddenly, your application grinds to a halt because a trigger plan has no index or is poorly designed. 

Databases are great tools for working on SETS of rows.  You can define queries that can query the whole data efficiently.  If you do it properly, you can solve a lot of problems very easily.  So, for any given query, the startup time for a query is relatively high, but the per-row cost is optimized by lots of smart people.  I can assure you that they count instructions, worry about CPU architectures, memory access trends, cache hierarchies, and every other trick in the book to make the per-row cost of a query as low as possible.  So, it may take a few million instructions to start a query vs. a few thousand or tens of thousands to process a row in a query.

When you add a trigger, you should think that you are adding another query whenever you run the first one.  Furthermore, if you have written your application to call the database more often than necessary (say, once per row instead of batching things up as sets), then you are now adding the cost of that second query to the PER-ROW cost of the query.  That is pretty close to the definition of a "bad thing" in the dictionary...

In addition to the number of times that a trigger is called, the trigger plan itself may not be set up to run efficiently.  If the trigger enforces business logic that touches a lot of tables or rows, you need to consider what indexes to add.  I usually create an equivalent SELECT statment and run it to look at the query plan (I'd fake data and a table for the inserted table, for example).  This will help me find slow queries before the trigger is deployed - you probably want to look closely at every table scan to see if it is really necessary).

I've put together some examples that you can try to see how the system behaves under different scenarios with triggers.  I would publish some numbers to give you relative ideas about how fast things are, but I think that the current CTP of SQL Server that I am running has a few issues with memory on my machine that cause it to page wildly occassionally, so I will let you go run these on your own.  The basic idea is that things will get slower as you do more and more "bad practices" with triggers.

create table table1 (col1 int primary key identity, col2 int, col3 binary(2000), col4 binary(4000))
declare @a int
set @a=0
while @a < 20000
begin
insert into table1 (col2) values (@a/100);
set @a+=1
end
go
-- target table on which we are creating triggers
create table table2 (col1 int primary key identity, col2 int, col3 binary(2000), col4 binary(4000))

-- audit table
create table table3(col1 int, col2 binary(100))

-- try to insert 20,000 rows with no triggers defined - should be pretty fast.
begin transaction
insert into table2  select col2, col3, col4 from table1
rollback
go

-- now create a simple trigger that reads all the inserted rows and copies them to table3 (an audit table)
create trigger trig1 ON table2 FOR INSERT AS INSERT INTO table3(col1, col2) select col1, null from inserted
begin transaction
insert into table2  select col2, col3, col4 from table1
rollback
-- this will run the trigger query once with all 20,000 rows.  
go

-- here is where triggers starts to hurt.  Let's write the same query except that 
-- we read each row separately in its own query.  (This will be even worse if you remove the begin transaction
-- since each row will need to commit the log to disk).
begin transaction
declare @i int
set @i=0
while @i < 20000
begin
insert into table2  select col2, col3, col4 from table1 where col1 = @i
set @i+=1
end
rollback
-- This is a very poor use of the database - In almost every case, using a set-based approach will 
-- yield better performance.  You avoid multiple transactions.  You avoid running through a long codepath
-- to start each query.  You give the optimizer to consider more advanced plans.
go

-- let's remove trig1 for our next example
drop trigger trig1 
go

-- now let's create a trigger that copies ~100 rows every time it is called.  Furthermore, let's 
-- restrict on a non-indexed column in the source table.  This will lead to a table scan for each call.
-- This should simulate your average "bad" trigger formulation.
create trigger trig2 ON table2 FOR INSERT AS INSERT INTO table3(col1, col2) select col1, null from table1 where col2=5;
go

-- and, for fun, we'll run the one row at a time example again.
-- (go get some coffee, or whatever else you do to amuse yourself - this will take awhile.)
begin transaction
declare @i int
set @i=0
while @i < 20000
begin
insert into table2  select col2, col3, col4 from table1 where col1 = @i
set @i+=1
end
rollback

So what is a responsible DBA or database developer to do??? :)

Well, there is hope.  A few things to consider:

1. Look at that trigger - do you need it?  really?  Perhaps not.  Consider each one and make sure that you really, really need it.

2. Make sure that you call any trigger the minimum number of times.  SET STATISTICS PROFILE ON can help you see how many calls are happening for any given query. 

3. You can often pull the logic for a trigger up into the stored procedure that is calling your query.  This works if you can control all of the codepaths into the system for changes to the system - this is often the case in OLTP applications.

4. SQL Server 2005 added some neat features that help with benchmarks.  However, they are also quite useful for you if you have the time to consume them.  Look up INSERT... with OUTPUTs.  This lets you insert rows into one table and then perform an operation with the rows after the insertion (return them as a select query, insert them into another table, etc).  This is a very cool feature.  It takes quite a bit of knowledge to wrap your head around what the database system is doing to make this all work (too much blogging for this post, to be sure), but I can assure you that it is pretty fast :).

Bottom line - I recommend that you have one person at your company who is responsible to understand the schema, including things like triggers.  This means that someone can think through the tradeoffs and make reasonable decisions to avoid the most common pitfalls.

Happy Querying, folks!

Conor Cunningham

(I am still around - I've just been busy with a few personal projects of late - keep asking questions if you have them).

I received a question from a reader named Andy that was a follow-up to my questions on OUTER JOINs and WHERE clauses and ON clauses.

Upon re-reading my previous entries, I determined that I got distracted talking about the old-style join syntax instead of giving a good explanation about ON vs. WHERE _semantics_ for outer joins.

select * from cc1 left outer join cc2 on (cc1.col1=cc2.col1)

drop table cc1
create table cc1(col1 int, col2 int)
insert into cc1(col1, col2) values (1, 2)
insert into cc1(col1, col2) values (2, 3)

create table cc2(col1 int, col2 int)
insert into cc2(col1, col2) values (1, 2)

select * from cc1 left outer join cc2 on (cc1.col1=cc2.col1)

col1        col2        col1        col2
----------- ----------- ----------- -----------
1           2           1           2
2           3           NULL        NULL

(2 row(s) affected)


select * from cc1 left outer join cc2 ON (1=1) WHERE (cc1.col1=cc2.col1)

col1        col2        col1        col2
----------- ----------- ----------- -----------
1           2           1           2

(1 row(s) affected)

The question boils down to "why are these two queries returning different results?" This is a very good question.

I'll explain the what, then I'll try to explain the why/how:

In the first query, the ON clause has the predicate. This logically ties the predicate to the join. Since OUTER JOINS can return rows that do not match, the predicate is used to determine what "doesn't match".

In the second case, the join part actually tells the QP to do a full cross product.  The WHERE clause is actually not bound to the OUTER join semantics at all. This is why they return different results. 

Now let's talk "why/how".  The QP represents this second query as a tree with a filter above the join.  The QP has lots of smarts in it.  One of the thing it can determine is that the filter condition (cc1.col1=cc2.col2) actually prevents NULLs from being returned since NULL = anything is UNKNOWN in three-value logic (and therefore not TRUE and therefore not returned from the WHERE clause).  Since all NULL values from the non-outer side of the join are removed, this is logically equivalent to running an inner join because all of the extra rows for non-matching rows are actually removed.

select * from cc1 INNER join cc2 ON (1=1) WHERE (cc1.col1=cc2.col1)

If you look at the query plans, you will see that the second query is actually running an inner join because of this recognition in the QP that you don't need an outer join.  (The QP can more freely reorder inner joins, so it prefers to convert outer to inner joins where possible).

I hope that gives a better explanation as to why SQL Server returns different results for this query!

Happy Querying!

Conor

 

I had a question from a reader about contradiction detection.

The basic idea is to determine that this kind of query:

SELECT * FROM TABLE WHERE col1 > 5 and col1 < 0;

...is utterly meaningless and requires no work to be done.  It will always return zero rows.  In fact, in many cases the SQL Server QP will detect cases like this and actually remove the table from the query completely.  In its place, you have this magical "constant scan" operator, which is really just an in-memory row generator.  So, you can read from it instead of from a table.

This optimization is done in many places in the SQL Server QP, and it is great because it requires no I/O, no locks, and less CPU than actually reading from a table.

The question I had from a user had to do with cases when this optimization does NOT happen.

Since the reader sent me a perfect example, I'll just copy it up here (note - I am happy to credit readers if they would like credit, but I don't post their name unless they want me to do so).

--drop table #tmp

create table #tmp (id Int Identity(1,1) Primary key, name VarChar(250))

go

insert into #tmp(name) values(NEWID())

insert into #tmp(name) values(NEWID())

go

set statistics profile on

go

-- Execution plan create a Constant Scan

select * from #tmp

where id = 1 and id = 5

go

set statistics profile off

 

GO

 

select * from #tmp  where id = 1 and id = 5
  |--Constant Scan

--drop table tmp

create table tmp (id Int Identity(1,1) Primary key, name VarChar(250))

go

insert into tmp(name) values(NEWID())

insert into tmp(name) values(NEWID())

 

go

set statistics profile on

-- Why execution plan does not create a Constant Scan for this case?

select * from tmp

where id = 1 and id = 5

go

set statistics profile off

SELECT * FROM [tmp] WHERE [id]=@1 AND [id]=@2
  |--Clustered Index Seek(OBJECT:([t1].[dbo].[tmp].[PK__tmp__3213E83F15502E78]), SEEK:([t1].[dbo].[tmp].[id]=CONVERT_IMPLICIT(int,[@1],0)),  WHERE:([t1].[dbo].[tmp].[id]=CONVERT_IMPLICIT(int,[@2],0)) ORDERED FORWARD)

So this is interesting - in one case the constant scan is done, while in the other case it is not.... hrm.  what's up with that?

Well, some of you are familiar with autoparameterization - a feature that can take unparameterized queries, try to make them parameterized, and then avoid compilation for multiple similar simple queries.  Autoparameterization is tied to the "trivial plan" feature, meaning that the optimizer feels that there isn't really a plan choice and thus going through the complete cost-based optimization process is unnecessary.

The difference you see is based on autoparameterization and whether it happens or not.  Now, the autoparameterization rules are fairly arcane at this point - they've been around, in some form, for various releases dating back to SQL 7.0.  TempDB has a different set of rules about whether a query should be autoparameterized since these tables are globally shared.  So, in the #tmp case the table isn't being autoparameterized, the rest of the logic to simplify the query is run, and this rule detects the contradiction.

In the latter case, the query IS auto-parameterized.  The optimizer doesn't see two parameters as always being a contradiction (you could pass the same value for both parameters), and then the query is not simplified.

For what it is worth, a somewhat internal knowledge of what causes a plan to be considered trivial or not can influence whether you see one plan or the other.  For example, query hints make a plan not trivial (why hint if there is no plan choice?), and as such you could do something like this:

select * from tmp
where id = 1 and id = 5 option (maxdop 1)

This will get you the constant scan in all databases.  Adding enough rows to get the cost above the threshold for parallelism (in a parallel-enabled machine + SKU of SQL) would also do it. 

Remember, trivial plan was developed before contradiction detection, so this should be viewed in that context.  It's a bit odd, but the ecosystem developed this way and you should be aware of that when developing SQL Server apps.

I enjoy the questions - keep them coming!

Thanks,
Conor

I spent some time playing with the SQL 2008 geometry data type.  This post will cover some of the things I have learned about how it is implemented from playing with the feature.  Some of these will impact the feature's usability for some.  Others may not care.

1. late-binding of the geometry data is an interesting choice.  So one of the nice properties of a SQL query is that, for many things, the parse and bind of a query can find all sorts of compilation errors that would show up during development.  You don't have to run the query in order to see the simple mistakes, and that helps us all.  This type doesn't throw parsing errors until you try to execute the query.  That's not perfect - you have to go execute spatial queries to see whether you have typed in lots of complex data correctly or not.  I can speak from experience that I tend to mess that stuff up.

Example:

create table g1 (col1 int identity, col2 geometry)
go
insert into g1(col2) values (Geometry::STGeomFromText('LINESTRING(0 0, 10 10, 21 2)',0));
go
insert into g1(col2) values (Geometry::STGeomFromText('LINESTRING(funky chicken)',0));
go

That third query compiles just fine - running it returns an error.

2. The geography type uses some form of the .net framework.  (I'll point out that I have not enabled the CLR in my server).  Given that the ordpath type requires that the CLR be enabled, I'll guess that this means that there is a special implementation of the geometry type.

Here's the runtime errof from the previous query:

Msg 6522, Level 16, State 1, Line 1
A .NET Framework error occurred during execution of user-defined routine or aggregate "geometry":
System.FormatException: 24141: A number is expected at position 16 of the input. The input has funky.
System.FormatException:
   at Microsoft.SqlServer.Types.OpenGisWktReader.RecognizeDouble()
   at Microsoft.SqlServer.Types.OpenGisWktReader.ParsePoint()
   at Microsoft.SqlServer.Types.OpenGisWktReader.ParseLineStringText(FigureAttributes attributes)
   at Microsoft.SqlServer.Types.OpenGisWktReader.ParseLineStringTaggedText()
   at Microsoft.SqlServer.Types.OpenGisWktReader.ParseGeometryTaggedText()
   at Microsoft.SqlServer.Types.OpenGisWktReader.ReadGeometry()
   at Microsoft.SqlServer.Types.SqlGeometry.STGeomFromText(SqlChars geometryTaggedText, Int32 srid)
.
The statement has been terminated.

(I think I will be making t-shirts that say "The input has funky" on it... let me know if you want in :).

I am actually pretty happy with the error message - the only thing missing is which column caused the error.  You'll notice that "position 16" is inside of this second string being parsed by the .NET routines.  I personally do find stack traces unacceptable for general use, but the .net and java folks seem to have doubled down on this approach, so we all get to learn about their libraries even in SQL now...

This is just a seam in how it was implemented.  Be aware of this when using the type.

3. the geometry type has been (arbitrarily) given an estimated row width of about 4000 bytes.  well, this is what shows up in showplan.  So I inserted a bunch of data into this table (1.4 million rows in about 148MB).  The cost estimates don't seem to use the 4000 byte number for the row width (as it would take a long time to read 5.6GB - more than 13 seconds or so, given that is what the costing says, so I am guessing that this is just reported in showplan the same way it is costed internally).  I'm just using a heap (no indexes) for this experiment.

4. I'm waiting for maps.live.com  to make it easy for me to geocode addresses and insert them into SQL.  It has a feature to send it to some gps device, but I haven't played with it beyond learning that it didn't detect that I had blocked cookies by default ;).

5. "select col2.ToString() from g1" is a way to see something useful from that data type.  otherwise you get back binary goo...

That's all for tonight.

Thanks,

Conor Cunningham

A follow-up from my previous post.

Is COUNT(1) faster than COUNT(*)?

No, COUNT(1) is mapped into COUNT(*) early in the QP.  From the logic of my previous post, COUNT(1) is always non-null and thus is the same as just doing a COUNT(*).  Since it is semantically equivalent to COUNT(*), the QP just maps it to COUNT(*) because it makes things simpler and you can avoid special cases for things like local-global aggregation and moving group bys around joins.

You can actually look at the query plan for "SELECT COUNT(1) from Table;" and see that the output plan is COUNT(*).

You can save it a few instructions by using COUNT(*).  You will also make the ANSI SQL gods happier.

I get a lot of questions about these syntax issues - it makes sense, as this is often very interesting in traditional procedural programming languages.  In many cases, there are only very minor performance differences, if any, in the SQL language due to these.  The big differences happen because your slightly different query actually means something semantically different and thus implies a different amount of work to compute.

Please keep sending in your questions - I'm happy to answer them!

Thanks,

Conor Cunningham

So COUNT isn't an operator, but you should view this post as a "what is this operator" kind of post since I talk about how these things work and what they mean.

One of the benefits of building database engines is that all (well, most of) the syntax rules end up stuck in your head, but I know that many of these things are completely non-obvious, so I think it's worth mentioning a few things about what each of these things mean since I see them misused in lots of queries, blogs, etc.

-- Returns the count of rows from the table at the time that the query is run in the transactional isolation mode in which the query is run (usually read committed for SQL Server)
SELECT COUNT(*) FROM Table

So that example is easy enough...

SELECT COUNT(column1) FROM Table

This is actually NOT the same query as COUNT(*), in general.  It means "count the number of non-null column1 rows". 

(Now for something cool.  If you run this on a column that is non-nullable, then SQL Server converts it into the count(*) case because it is faster to run that form since it doesn't have to examine the data in each row and can instead just count rows).

SELECT COUNT(DISTINCT column1) will count the number of UNIQUE non-null column1 values.  It does not count NULL.  I don't believe SQL Server completely removes the DISTINCT operation for non-null columns in all cases.  It can in some cases.

COUNT(col) OVER (...) is a completely different beast.  It runs a count computation using the rules you've seen above but it does not collapse the rows - it adds a new column on all the rows with the computed count. 

Remember that these are semantically different operations.

Conor

I started off tonight playing with the new page compression feature.  So far I like it.  I haven't found something yet about which I want to post (which is code for "I'm still looking for the seams ;)"), but I have some other things you can try to learn a few things about how the SQL Server QP makes assumptions about various kinds of predicates in queries during cardinality estimations.

So, you may or may not know much about how the SQL Server QP figures out what plans to run.  For the uninitiated, it almost seems like some form of magic.  In some ways, it is - it's very powerful and poorly understood by many, and it usually requires very little effort by someone skilled in the area to make something amazing happen.  SQL Server merely needs to make itself sparkle when I fix a query plan and I'm set for life :).

In reality, SQL Server uses a cost-based optimizer, which means that it keeps track of all sorts of interesting statistical information, row counts, page counts, etc.  It uses all of these in formulas to come up with numbers for each plan fragment and then it weighs the relative costs of all of these to pick a plan that has the "least cost".  That sounds nice and absolute until you get to go actually try to make that work, and then you are left with all sorts of nasty questions like:

* What should the cost formulas be?
* Do the numbers need to differ based on the customer's hardware? How do we calibrate all of this stuff?  What do we do as machines get faster?
* How do I estimate how many rows are going to come back from one predicate in my WHERE clause or join in time less than running the query to figure it out?
* Same question when I have a bunch of preciates?

Eventually, the QP has to make a set of assumptions so that they can come up with a plan in a reasonable amount of time, both because customers don't like things to ever take time and because managers don't like customers to tell them about how much time something should take..  One assumption might be that, data is uniformly distributed over a data type's possible values when you don't have any better information.  This can help make it possible to come up with solutions that work well most of the time.  The problem is that estimates can be wrong, and that can cause the QP to come up with a different plan than had it had correct information to use when selecting the plan.

So, I'll show you an example here.  To be clear, I'm not saying that this is something that is "broken".  This just exposes a place where 2 different assumptions rub up against each other in a way that will SEEM odd to the outside observer.  When you consider the average customer use cases, these assumptions are not bad and work very well the vast majority of the time...

To the example:

drop table comp1
create table comp1(col1 int identity, col3 nvarchar(3000))

declare @i int 
set @i=0
while @i < 70000
begin
insert into comp1 (col3) values (N'123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890')
set @i=@i+1
end

So I create a table with the same long string in it 70,000 times. 

Then I run a query with a where clause just to get some statistics created:

select  * from comp1 where col3 like '%4567890%'
dbcc show_statistics ('comp1', col3)

Once we have all of this stuff, we can look at the estimates for two very similar queries:

select  * from comp1 where col3 like '123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890%'

select  * from comp1 where col3 like '%123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890%'

(one is LIKE 'abc%'.  The other is LIKE '%abc% where abc is the value we have inserted 70,000 times).

So, both queries will return 70,000 rows. 

Well, the abc% pattern query estimates 70,000 rows (good!).  The second query estimates 69.6985 rows.  that's a bit under ;).

Let's talk about this a bit more so you can understand why.  In the first query, there is an exact string match against a column represented in the statistics histogram.  So, the likely outcome is to take that cardinality count to determine the number of rows that will likely be returned from the query.  In this case, we expect all rows to come back.

In the second one, there is no mechanism to estimate the cardinality of ANY string of this size (SQL Server does have a feature that does smaller strings which is exposed as the "STRING INDEX" in the histogram, but you can't see the details of this object in 2005 and I haven't seen that change in 2008 either).  So, for really large strings, it is left with... guessing.

So, that 69.6985 number is an estimate that is partially based on the length of the string.  Now, the QP could try to walk through each statitistics object and try to find substrings against any existing piece of statistical data and then try to adjust its estimate.  In practice, though, the cost of doing that is expensive.  The various statistics objects are run at different times and have different sample rates, so even then they will vary somewhat.  Finally, for most cases it may just not impact the plan choice that much.  Odds are, though, that this will bite at least one of my readers at some point.  So, this is good to know - it can help you find that spot where the assumption in the QP is causing your query plan to be wrong.  This is the sort of case where you will want to consider a query hint to help the QP out.

There are more assumptions (and seams between them) in the cardinality estimation code.  I'll let you guys go hunt for them a bit to find them.

Happy Querying!
Conor Cunningham

One of the areas I managed in SQL Server had to do with the code that automatically builds statistics and uses them during query optimization to come up with a good plan.  Today I'm going to talk a bit about how statistics are built and how this works with parallelism and partitioning.

First things first.  There are two ways in which statistics are created in SQL Server:
1. You create an index.
2. You run a query that needs statistics when they do not exist and the server has "auto-create statistics" enabled.  (That's the simple definition - there are actually caveats I am skipping)

Why does creating an index also create statistics?  Well, the main cost in creating statistics is reading all the pages into memory.  The thought is that if you want to create an index, you have already paid the expensive cost and the server might as well go ahead and create the statistics object for you instead of re-reading those pages later.  So, you get these "for free" (well, almost free).

When you run a query that tries to perform an operation where cardinality estimates would be improved by having statistical information about a column, the server can try to create statistics during the compilation process.  Since compilation time needs to be kept to a minimum, these are usually done over a _sample_ of the pages to avoid making the compilation of a simple query as expensive as an index build.

So the basic plan to create an index is a singlethreaded plan that is something like this:

INSERT (New B-Tree)
  |
Sort
  |
SCAN(Heap or some index)

So during this plan's execution, there is an implicit side-effect to also create this statistics object.

For auto-stats, there is a separate query that is run.  The syntax is not public, but you can see artifacts of this if you look at the profiler and you've turned on the various auto-stats and plan outputs:

drop table stat1
create table stat1(col1 int, col2 int, col3 binary(6000))
declare @i int
set @i=0
while @i < 1000
begin
insert into stat1(col1, col2) values (rand()*1000, rand()*1000)
set @i=@i+1
end


select * from stat1 where col2 > 5

Execution Tree
--------------
Stream Aggregate(DEFINE:([Expr1004]=STATMAN([t1].[dbo].[stat1].[col2])))
  |--Sort(ORDER BY:([t1].[dbo].[stat1].[col2] ASC))
       |--Table Scan(OBJECT:([t1].[dbo].[stat1]))

What is this?  Well, this is the plan that is used to generate the statistics object.  It scans a table, sorts it (into ascending order), and then feeds it into this magical thing called statman.

Now, the details of statman are undocumented, but you can infer that it is a special internal aggregate function that is being run inside of a group by operation (stream aggregate in the plan).  This means that it is collapsing all the rows into some BLOB and then it does something with this.


Next time I hope to talk about parallel statistics build.

Happy querying!

Conor Cunningham

I've returned from a small trip and I will be preparing my next SQL post soon.

I've been struggling with slow POP3 sync behavior on my Outlook 2007/Vista 64 box, and I finally found a hammer to beat it back into submission.

The problem - I sync manually, and when I do the application becomes basically so slow as to be non-responsive.  I deleted a bunch of mail to get my mailbox down to a reasonable size (150MB) - still there.  I deleted RSS feeds, blaming XML for my woes again :).  That didn't work either.

I eventually found this:
http://support.microsoft.com/default.aspx?scid=kb;EN-US;935400

Something to do with the new Vista TCP window size algorithm not working well with "legacy" hardware.  No only is the download slow, but using Outlook becomes unbearable as well, so I can't really do anything with the application...  I didn't get timeout errors (at least not frequently), but I certainly had bad feelings about my email experience.

When I disabled the new TCP window behavior, all went back to what was expected.... Now I have to go find all those RSS feeds again :).  So here's to "netsh interface tcp set global autotuninglevel=disabled".  It worked for me, at least so far.

I think that this is a case where Microsoft has an opportunity to compare their offering to gmail and determine "hey, I wonder why people think that a webui is better - they are _so_ much slower...." well, in some cases the thick client is actually slower, and that doesn't make MS look very good.  So I hope this workaround avoids frustration for others :).

I'll also hope that MS could add something to outlook in the next service pack when it realizes that it downloads 15KB in 2 minutes from my POP3 servers.  Perhaps they can add a popup or special error in the next service pack of outlook 2007 to point people in the right direction.

My setup:
Vista x64 SP1
netgear gigabit 8 port switch
linksys wrt54g NAT
some no-name cable modem that my cable company gave to me.

Based on my previous post describing the differences between ANSI-89 and ANSI-92+ join syntaxes and recommendations, I had a follow-up question in a comment which was (paraphrased)

What do I do with non-join WHERE clauses - how should I write those?

Example:

SELECT p.FirstName + ' works in ' + d.DepartmentName AS 'Who Works Where'
FROM Person AS p
JOIN Department AS d
ON p.DepartmentID = d.DepartmentID
  AND p.JobType = 'Salaried'

(so, the question is about the filter condition on p.JobType).

Answer: it doesn't generally matter, but I'd recommend that you put it in the WHERE clause for readability.

I'll explain the why now.  A little background first:

In SQL Server (actually all QPs of any note), the SQL string is converted into an operator tree and then there's a lot of magic to rewrite that query tree into alternative forms of the query.  While some people think of this as "if I try different syntaxes, the query may execute faster", the optimizer is actually doing something at a much deeper level - it is essentially rewriting the tree using a series of rules about equivalences.  It's a lot more like doing a math proof than trying different syntaxes - it deals with associativity, commutivity, etc. (Conor bats cobwebs out of people's heads- yes, you guys did this stuff in school).  It's a big set theory algebra machine.  So, you put in a tree repesenting the syntax at one end and get a query plan out the other side.

So, I'll ask the question from a slightly different perspective and answer that too to help explain the "why":

"Does putting filters in the join condition of an inner join impact the plan choice from the optimizer?".

Answer: no - at least not in most cases. 

When the SQL Server Optimizer starts working on this query, it will do a number of things very early in the optimization process. One thing is called "simplification", and most of you can guess what will happen there.  One core task in simplication is "predicate pushdown", where the query is rewritten to push the filter conditions in WHERE clauses towards the tables on which the predicates are defined.  This mostly enables index matching later in optimization.  It also enables computed column matching.

So, these predicates are pushed down in both cases.  You lose a lot in query readability by trying this form of rewrite for very little gain.

There is one case where I'd consider doing this, but it really requires that you have uber knowledge of the QP.  However, this seems like a good challenge, so I'll explain the situation and let you guys write in if you can find an example of it:

You know that the QP uses relational algebra equivalence rules to rewrite a query tree (so A join B is equivalent to B join A, filter .a(a join b) == (select * from a where filter.a) join b, etc.

One could imagine that some of the fancier operators may not fit as easily into the relational algebra rewrite rules.  (Or, they are just so complex that the cost of trying such rewrites outweighs the benefit).

Can you find operators where (filter (OPERATOR (SCAN TABLE)) is not equivalent to (OPERATOR (filter (SCAN TABLE))? 

Obviously inner join is a bad place to start.  I'll throw out some not-so-random areas for you to try:
* updates
* xml column manipulations
* SELECT list items on objects that change semantics based on how many times they are executed in a query (rand()?  think functions)
* play with group by (this one is tricky)
* OVER clause?
* UNION/UNION ALL, INTERSECT, ...

So, there are some cases where the QP will do these rewrites, and there are some places where it can't/won't (or at least doesn't do it always).  In a few of these cases, the intent of the query can be preserved by manually rewriting the query to push the predicate "down" the query tree towards the source tables.  However, I would not recommend this unless you really know what you are doing - the query rewrite needs to be equivalent or else you may not get the right results back from your query!


Bottom line - I think that the query is far more readable with non-join predicates in the WHERE clause.  Whenever I try to optimize queries, I usually push them into this format so that I can wrap my head around what the query is trying to accomplish.


Happy querying!

Conor

I had a request from a reader that I'll answer today about when to do joins in the ON clause and when to do them in the WHERE clause.  For example:

SELECT * FROM A, B WHERE A.a = B.b

vs.

SELECT * FROM A INNER JOIN B ON (A.a = B.b)

The short answer is that both are the same (at least for inner joins), but I prefer and encourage you to use the latter format (and I will explain why).

Earlier versions of ANSI SQL did not contain the ON clause for join conditions - it used the where clause for everything.  This was fine for inner joins, but as database applications started using outer joins, there were problems that arose with this approach.  Some of you may remember the original ANSI-89-era syntax for *= and =*.  These were used on the predicates to define the behavior for an outer join.  In this case, we'll preserve non-matching rows from A in addition to the normal rows returned from a join:

SELECT * FROM A, B where A.a *= B.b
which is equvalent to:
SELECT * FROM A LEFT OUTER JOIN B on (A.a = B.b)

This "hack" worked fine until people started using multiple predicates for things and also started doing multiple outer joins in one query.  Then we were left with a big, ambiguous mess about which *=, =* applied to which join.  So, ANSI banished *= and =* and SQL Server has been threatening to follow for quite sometime.  I honestly never use the old-style join syntax, so I don't even recall the exact deprecation state.  It is dead to me already ;).

The broader concept is that predicates are "attached" to joins using the ON clause.  This is very helpful when you are trying to figure out what should happen in a query.  It helps semantically define the set of rows that should return from the join.

So, if I start nesting various inner and outer joins in a big, nasty query, all of a sudden it is very nice to have an ON clause to define what should go where.

SELECT * FROM A INNER JOIN (SELECT B.* FROM B LEFT OUTER JOIN C ON (B.col1=C.col1 and B.foo.C.bar)) AS I1 ON A.col1=I1.col1;

As applications get more complex, it is not uncommon to have 10s of tables in a query.

Internal to the SQL Server query processor (actually pretty much all query processors), there is a tree format for the query operations.  The exact representation will vary from vendor to vendor, but each one of these SQL syntax pieces transates to some set of relational operators in this query tree.  Putting your query syntactically into this format gets things much closer to the internal algebra of the query processor in addition to making things easier to read as queries get more complex.

Actually, if I were to go build my own QP, I'd seriously consider adding a query tree mechanism in addition to SQL (this concept is not new and is not mine).  OLEDB had a concept like this in the earlier public betas, for example.  Obviously the implementor would want to retain the ability to change the internal implementation, but a tree of commands is actually far easier to grok than SQL, once you get used to the idea.  Other technologies expose a graph structure to you (video codecs/transforms in windows, msbuild is an XML file representing a tree, etc).  SQL as a textual language exists historically.  It's also a nice way to write queries :).

The only other area where I get concerned is when people turn off ANSI_NULLs.  It is one of those historical features that should basically never be used.  I could imagine cases where some comparisons in joins behave differently in the ON clause vs. afterwards in an WHERE clause.  I don't want to pollute people's minds, as my attempts to go back and re-learn the quirks on this for this post left me baffled since NULL=NULL returns TRUE only for some syntax constructs.  So, I don't have a case where it is broken, but I'll leave you with the "ANSI_NULLs off is bad" message and list it as a potential reason.

Will you get wrong results if you use the old-style join syntax?  no.  The world will still turn.  So, this is really a recommendation based on style and sanity.  I would recommend that you get used to the newer style - it may help you write more powerful applications and think more like the QP.  For some applications, this might let you write more powerful features for your users.


Thanks,

Conor Cunningham

I don't know about you, but groupby is one of my favorite operators.  There are a TON of interesting optimizations that a QP considers when you start adding group by into queries, especially when you have joins and then a group by.  TPC-H benchmark wars among the large database vendors are won and lost on many such optimizations.

So, if you are doing relational OLAP (ROLAP) or are otherwise running group by queries over lots of well-normalized data, then I suggest you brush up a little on your knowledge of group by - it will help you understand when queries are behaving and when they are not.

Here's the paper I tell people to read on the subject.  It's written for the person implementing a database, but anyone who can read query plans should get the basics from the paper.  It is the basis for most of the hard-core optimizations (and tricky problems) that face all query processors today. 

The basic idea is caused by understanding that an aggregate function can be split into multiple operations and done in parts.  Some parts can be done earlier in a query, saving a lot of work.  If these results can be combined later, you might be able to speed up a query by computing these partial results early and then combining them at the end of the query.  The usual savings is that you don't have to materialize the results of a join when you only care about the aggregate over some piece of it.

Most of the core aggregate functions defined in SQL can be decomposed.  If you have a set of rows {x} := concat({y}, {z}), then
SUM({x}) == SUM({y}) + SUM({z}).
COUNT == COUNT + COUNT
MAX == MAX (MAX(), MAX())
...

Not all aggregate operations can be decomposed in this manner, but many of them can. 

If you take this concept and then apply it a query with some joins:

select sum(col1) from a join b join c

Then the idea of local-global aggregation is that you can do part of the sum before joins and pass up the SUM for each group instead of all the rows from that group. 

This idea becomes more powerful when you start throwing more complex operations into a query processor, such as partitioning or parallelism.  Often, you want to perform partial aggregations on these groups to minimize the amount of data you have to send between threads or perhaps between nodes on a NUMA machine.  All of this is the fun stuff that makes databases interesting - you can

Not every aggregate can be pushed below every join - there are rules about what can and can't be done and maintain the same results from a query.  For example, you may need to consider whether the aggregate function can handle seeing additional NULL values and return the same result or not.

If you go look at the SQL CLR user-defined aggregate definition, you'll see the exposed pieces of some of this capability in the SQL Server query optimizer.  I won't spoil all of your fun, but go take a look. 

Happy Querying!

Conor