Search results matching tag 'indexes'

March Update to Rules-Driven Maintenance

merrillaldrich — Tue, 12 Mar 2013 02:56:00 GMT

This month I have a minor update to the Rules-Driven Maintenance code I originally posted back in August 2012. This update has just two enhancements, but they are nice ones, I think:

Much improved handling for instances that use database snapshots.
Ability to do intra-day differential backups purely by setting maintenance times and limits in the policy table.

The code posted here is cumulative, and replaces entirely the original code, but please refer back to that original blog post for description, instructions and details. This update can be installed right over an existing deployment, or be installed all by itself as a complete solution but – as always – please test and be cautious.

Enjoy!

Public Release, SQL Server File Layout Viewer

merrillaldrich — Fri, 01 Mar 2013 21:36:00 GMT

Version 1.0 is Now Available!

I’ve been working off and on, as my real job permits, on this visualization tool for SQL Server data files. This is an educational or exploratory tool where you can more readily see how the individual data pages in MDF/NDF files are organized, where your tables and indexes live, what effect operations like index rebuild or index reorganize have on the physical layout of the data pages.

The viewer will scan a whole database, using only SQL and DBCC commands, and will render a color-coded representation of all the data pages represented in colored bands. Each partition of each index or heap in the database is assigned a color, so that you can see where all the bits and pieces of an object are located in the files. Above the colored bands there are grayscale or white pixels that show the page type in SQL Server (most are white, which are data pages. Unused/empty regions of the file show as gray). In the image above, for example, all the bright green areas are one index, all the purple areas are one index, and so on.

There is mouse-over functionality. If you move the mouse cursor over the graph, then details about each page populate the text fields at right, including the object and index the page belongs to, the page type, whether the page represents a fragment, where the previous and next pages are for the same object, etc.

Why?

Why create something like this? I am a visual person, and I have a theory that many issues we have in computing come down to not being able to see what’s going on. This is especially true as we learn about unfamiliar technology – we have to develop a mental model of structures like B-trees or linked lists or files in order to understand what’s happening. I hope this tool, combined with other knowledge, will help people form an accurate understanding of how data file internals work in SQL Server, faster than working purely in the abstract with tools like DBCC Page or DBCC Ind.

Instructions

Download the tool and unzip it. The package includes both an executable and the source code. If you don’t want the source, the .exe file is a standalone program and will run all on its own, so you are welcome to discard the source folder.
Validate you have the required prerequisites from the Prereq’s section below.
Locate a non-production/test database to analyze. The database can be local or on a remote server. I suggest something of a reasonable size, because scanning a really huge data set can take quite a long time.
Run SQLFileLayoutViewer.exe and select a database to scan. If the database is on a remote server, type the SQL Server name/instance name into the dialog.
Click Analyze.
Examine the resulting graph, and mouse over it with the cursor to view detailed information about each page.

Disclaimer

This is a freeware tool provided for your fun, education and entertainment. However, there is no warranty of any kind and you use it at your sole risk. The tool is free but offered under the GNU General Public License 3. If successful, and people are interested, I’ll move this work to some sort of open source project.

Prerequisites

The app requires .NET Framework 4.0 and the SQL Server management tools. I’ve tested it on Windows 7, Windows Server 2008 R2 and Windows 8. It can be run against a database on a local or remote SQL instance. I believe it will work on any database in SQL Server 2005 or later, but have not tested every possible scenario.

Risks?

I believe this tool to be relatively risk free, but I would avoid running it against live production data. The tool’s data collection is simple: it will issue a few system table selects to get things like object names, and then it will execute a DBCC PAGE statement against every page in the database. All other processing after that is done locally in the application itself. It does not modify the database.

Bugs?

I would love to hear about bugs you come across, or additional features you think would be valuable. Please contact me through this site. Note that I am a DBA first, and an amateur .NET developer a distant second, so please be gentle.

Enjoy!

Geek City: Join With Me!

Kalen Delaney — Thu, 14 Feb 2013 22:16:00 GMT

I remember one of the most surprising changes in SQL Server ~~2000~~ 2005 was how the graphical plans showed the use of a nonclustered index to seek, and the plan included something that looked like a JOIN to find rows in the base table. Here’s an example. Although I used SQL Server 2008R2, the graphical plan will be pretty similar to what it looked like back in SQL Server ~~2000~~ 2005. My code will make a copy of a table in the AdventureWorks2008 database, and then build an index on one of the columns.

USE AdventureWorks2008;
GO
IF object_id('dbo.Sales') IS NOT NULL
DROP TABLE dbo.Sales;
GO
SELECT * INTO dbo.Sales FROM Sales.SalesOrderHeader;
GO
CREATE INDEX Sales_SalesPersonID_index on dbo.Sales(SalesPersonID);
GO

Now look at the estimated graphical execution plan for this query, that searches for a particular value for the SalesPersonID column:

SELECT * FROM dbo.Sales
WHERE SalesPersonID = 280;
GO

You should see something like this:

It shows a JOIN even though there is only one table involved! What’s with that? It took me a few minutes to figure out what I was seeing, and I must admit that over the years since then I have come to appreciate this graphical representation. You’ll have a problem if you think of a JOIN as only finding matching rows between two tables, but can be solved if you realize that a JOIN can be used when finding matches between any two ROWSETS, i.e. any two sets of rows. There is a set of rows in the nonclustered index on SalesPersonID, and a set of rows in the table. The index seek finds all the index rows with a SalesPersonID value of 280, but those index rows only contain an index key value and a row pointer (RowID or RID). Because the query is requesting all the columns in the table, not just the SalesPersonID value, SQL Server must find the rows in the dbo.Sales table that have a matching value for the RowID. Internally, it is doing a join, even though there is only one table. It is joining index rows with table rows.

If the table had a clustered index, the plan would look almost exactly the same, with one difference. In SQL Server, if a table has a clustered index, nonclustered index rows do not contain RowIDs, they contain the clustered key value to be used a pointer to the row. SQL Server can take this clustered key from the nonclustered index row and look up in the clustered index to find the desired row. So I create a clustered index on SalesOrderNumber:

CREATE UNIQUE CLUSTERED INDEX Sales_ident on dbo.Sales(SalesOrderNumber);
GO

Now when I run the same query as above, I get the following plan:

The only difference in the two plans above is the icon for the lookup into the base table. One is looking up into a heap using a RowID, which is an address containing the File ID, the page number and the slot or row number on the page. The other icon represents taking a key value from the nonclustered index row and looking it up by seeking through the clustered index. If you look again at these two icons, which one looks like a picture of directly addressing a row, and which looks like a picture of following another index into the table itself?

The icon on the left is used for a RID lookup, and the icon on the right is used for a clustered index key lookup. I know that nobody asked me, but I think they got these backwards.

But wait, there’s more…

Prior to SQL Server 7, there was basically a rule of thumb with query plans that SQL Server would use one index (at most) per table per query. It could never (well, hardly ever) use two indexes on the same table in a single query. That changed in SQL Server 7 when a new algorithm called Index Intersection was introduced.

I’m going to build another index on SalesOrderDate:

CREATE INDEX Sales_OrderDate_index on dbo.Sales(OrderDate);
GO

This index will be used if I look for all orders place on July 1, 2002. The query plan for the following query is shown:

SELECT * FROM dbo.Sales
WHERE OrderDate = '2002-07-01';

We saw that the index on SalesPersonID is useful when looking for the value 280, and the index on SalesOrderDate is useful when looking for '2002-07-01'. But what if one query looks for rows that satisfy both conditions?

SELECT * FROM dbo.Sales
WHERE OrderDate = '2002-07-01'
AND SalesPersonID = 280

Here’s the plan:

We see two JOINs ! First, SQL Server finds the sets of index rows meeting each of the WHERE filter conditions and those two index row sets are joined together, using the clustered key value as the join column. Then only after SQL Server finds rows that meets both conditions, it takes the common clustered index key and uses it to find the row in the underlying table.

But wait, there’s more!

Both of these queries use a table scan, because the filter conditions are not selective enough. There are way more rows with a SalesPersonID value of 289 than there were for a value of 280, and there are more rows with an OrderDate of March 1, 2004 than there are with an OrderDate of July 1, 2002.

SELECT * FROM dbo.Sales
WHERE OrderDate = '2004-03-01' ;
GO

SELECT * FROM dbo.Sales
WHERE SalesPersonID = 289;
GO

Both of the above queries show the same plan. Because the table now has a clustered index, the plan shows a clustered index scan, but it is exactly the same work as a table scan:

However, if you look at the plan for a query that uses both filter conditions, we don’t get a clustered index scan.

SELECT * FROM dbo.Sales
WHERE OrderDate = '2004-03-01'
AND SalesPersonID = 289;

Even though each filter alone is not very restrictive, they can both be used for index intersection. The reason SQL Server usually doesn’t choose index seeks on non-restrictive filters is because the cost of then accessing the base table for all the qualifying rows can be very high. But even though each individual index returns a lot of rows, the optimizer’s estimate of the number of rows that meet BOTH conditions is very small, and therefore the number of lookups into the base table is quite small and affordable.

So, what can you learn? Just because you think an column might not be selective enough to build a nonclustered index on, don’t discount it. If that column will frequently be used in queries with multiple conditions, it just might turn out to be more useful than you thought!

So make sure you test many possible choices of indexes and combinations of indexes before you know what the best choices are.

Have fun!

~Kalen

Visualizing Data File Layout III

merrillaldrich — Tue, 29 Jan 2013 05:45:50 GMT

This is part three of a blog series illustrating a method to render the file structure of a SQL Server database into a graphic visualization.

Previous Installments:

Part 1

Part 2

Those that have been reading this series might be be thinking, “Is he going to go there?” Well, the answer is “Yes.” This is the GUID clustered index post that had to be. It’s inevitable with this tool.

If you follow SQL Server at all, you are probably aware of the long-standing debate about whether it is wise, desirable, smart, useful, or what have you, to identify rows using GUIDs. I won’t take a position on that, but I will show here, I hope objectively, a few things that the visualizer shows about file layout vs. distributed inserts, distributed inserts being one of the main challenges around using GUIDs as clustering keys. Just to recap the argument very, very briefly:

Advantages

GUID keys can be generated at the client, which saves a round-trip to the database server to create a collection of related rows.

GUID keys can make certain architectures like sharding, or peer to peer replication, or merging multiple source databases, simpler.

Disadvantages

GUID keys are wider, therefore they take more space in memory and on disk. The additional space is multiplied by their presence in both clustered and non-clustered indexes if they are a clustering key.

GUID keys don’t only take more space in RAM and on disk because of their width. They also cause distributed inserts into the clustered index – that is, new rows are added to any and all pages in the index. Each time a row has to be added, the target page must be read into memory, and at a checkpoint, the whole changed page (both existing and new rows) must be written to disk. This has two effects:

The amount of RAM and disk IO required for inserts is probably much higher, as pages with existing data must come into cache, get changed, and then be written back out again. Essentially, large parts of the table have to be rewritten to disk to append rows to pages that have data already.
The pages that store the index will individually fill up, and have to split such that half the existing rows are written back out to the “old” page and half written out to a “new” page in a different location on disk. This causes the pages to be less full, the same number of rows to require more space on disk and in RAM, and the resulting index to be massively fragmented on disk.

I am not writing to argue these points, which have I think been established by both sides of the debate, only to see if the visualizer shows these effects clearly. Most of the argument isn’t actually about these facts (they are all true, as far as I know) but rather which are more important, and I think that is the main source of debate on the issue.

Visual Example of Distributed Inserts

It’s very easy to create an example of this with a small sample database. I created one called “VizDemo2.” VizDemo2 has a slightly modified structure to illustrate what’s going on here – I need two tables that are stored separately on disk, so that they cannot interfere with one another. The simplest way to do that is with a couple of file groups containing one file each. So here’s the structure:

I created the database with a 50MB, single file, Primary file group
I added a file group FG1 with one 75MB file
I added a second file group FG2 with one 75MB file

When the database is empty, the visualizer shows only the system pages at the start of each file, as shown here:

To that database I added two sample tables identical in structure but with different clustering keys:

USE VizDemo2
GO

CREATE TABLE dbo.SampleCustomersInt  ( 
    id int identity( 1, 1 ) NOT NULL PRIMARY KEY CLUSTERED, 
    buncha char(500) default 'A', 
    big char(500) default 'B', 
    vals char(500)  default 'C'
) ON [FG1];
GO
CREATE TABLE dbo.SampleCustomersGuid  ( 
    id uniqueidentifier NOT NULL PRIMARY KEY CLUSTERED DEFAULT NEWID(), 
    buncha char(500) default 'A', 
    big char(500) default 'B', 
    vals char(500)  default 'C'
)ON [FG2];
GO

I’ll populate the two tables and we can see what the file layout looks like afterward:

INSERT dbo.SampleCustomersInt DEFAULT VALUES;
INSERT dbo.SampleCustomersGuid DEFAULT VALUES;
GO 20000

Compare

After inserts, the resulting graphic does show some facts we know to be true:

First, the data in the integer-clustered index takes about eight bands of the diagram, while storing the same data in a GUID clustered index has required about twelve bands of data pages. The database itself supports that impression with space allocation – it reports these figures:

Part of the extra space required is the width of the key, but part of it is the empty space on each page resulting from page splits. If a page that needs a new row is too full, then half the rows from that page are moved to a net-new page, half left in place, and the new row added to one or the other of the resulting pages. Afterward, they are often both partly empty.

Second, the whole graphic in the GUID clustered index area is a dark blue that the visualizer uses to show fragmentation – in fact, the object is almost perfectly fragmented, with practically no contiguous pages at all. The sequence of pages in the leaf level of the index is still a linked list, as always, but it it is physically stored in essentially random order on disk.

Does Re-Indexing Help?

The next question is whether we can combat these problems by doing huge amounts of index maintenance – if we rewrite the GUID index, will that make it take less space, or make it more efficient? The answer is, “well, sort of, temporarily.”

First, re-indexing will put the table in “GUID” order. Whether that really helps or not is debatable, perhaps. It would enable read-ahead for the index, which is otherwise clobbered by the fragmentation. Having the table in “GUID” order might or might not be of any help to performance. Second, re-indexing will make the pages denser, or less dense, depending on the fill factor applied. For the sake of demonstration, let’s re-index with the default fill factor, because I think that happens a lot out in the world, and it may tell us something:

ALTER INDEX ALL ON dbo.SampleCustomersGuid REBUILD;

After re-indexing, this is a view just of the second file group with the GUID clustered table (note that I scrolled down in the display):

The arrow shows where the data was moved from the old data pages into a new region of the file. And, sure enough, it’s not fragmented (note the lighter color) and it takes less space in the file.

That might sound good, but if this is a real database, inserts probably will continue. In the int clustered case, as we know, new data will be appended to the end of the page sequence, but in this case, new data will have to be inserted into most of the existing pages on disk. Those are all full now, and will have to be split 50/50 to create new pages for the new data, both the old and new pages will have to be written out, and the new pages by definition can’t be in index order with the existing pages.

INSERT dbo.SampleCustomersGuid DEFAULT VALUES;
GO 20000

What we get after more rows are added to the table is what a layperson might call a “hot mess:”

Here everything is fragmented – back to that dark blue – even the pages we just re-indexed a moment ago, because they all split. The table has more than doubled in size, even though we just doubled the number of rows, because the individual pages contain less data.

Would appropriate fill factor be a workaround? In some measure, yes, but it really only combats the issue. The write activity on the table, even with a low fill factor, will still be higher as more existing pages have to be flushed at checkpoints. The pages will still be less dense, and therefore take up more space on disk and in cache. In short – maybe helpful but no silver bullet.

What about Sequential GUIDs? Here I will venture my opinion. Sequential GUIDs have never made sense to me. They solve one part of this problem – the distributed insert part – but at the expense of the very things GUIDs might be good for, namely not demanding a visit to the database to generate an identifier. If you have to come to the database, you already lost this whole argument. Use an integer and solve the rest of the problem at the same time. I can only see it as a sort of band-aid for existing systems that could not be refactored, but, like a bad SUV that combines the worst properties of a car and a truck, it feels like a really poor compromise to me.

I hope this helps to illustrate some of the physical database design challenges that surround the use of GUID cluster keys. In the next installment I’m planning to demonstrate the interleaving of objects, which is one argument for multiple file groups.

Visualizing Data File Layout II

merrillaldrich — Wed, 23 Jan 2013 23:40:02 GMT

Part 2 of a blog series visually demonstrating the layout of objects on data pages in SQL Server

Part 1

In Part 1 of this series, I introduced a little demo app that renders the layout of pages in SQL Server files by object. Today I’ll put that app through its paces to show, in vivid color (well, teal, anyway) the destructive power of the famous Re-Index Then Shrink anti-pattern for index maintenance.

This one is very easy to demo, so let’s go!

First, I created a demo database VizDemo1, with a single 200 MB data file. Into that database I placed a canonical table – highly simplified for this example – clustered on an ever-increasing integer, using identity():

USE VizDemo1
GO

CREATE TABLE dbo.SampleCustomers  ( 
    id int identity( 1, 1 ) NOT NULL PRIMARY KEY CLUSTERED, 
    buncha char(500) default 'A', 
    big char(500) default 'B', 
    vals char(500)  default 'C'
);
GO

Then we populate that table with some dummy data:

INSERT dbo.SampleCustomers DEFAULT VALUES;

GO 40000

And finally, fire up the little visualizer app and process the database:

The small color bands at the top left corner of the image are the system tables and such that are in every “empty” database to make it run. The blue/green/teal area is the new table we created and populated with sample data, and the gray area represents empty regions in the file.

As expected, the table started writing into the first available space, and, because the cluster key is increasing, pages were allocated to the end of the page sequence in order, and we end up with a crazy-perfect, contiguous linked list on disk.

You can see small darker bars at intervals within the table – most of the pages in the index are “type 1” pages, which are the leaf-level/rows in the clustered index. Those bars are “type 2” index pages that have the upper level(s) of the index. The reason they are darker is that those are a disruption in the leaf level linked list, and the app shades such disruptions as a way to see fragmentation. The list has to “hop over” those pages and then continue on the other side. It’s technically fragmentation, but at this point not harmful at all – but remember that darker color that shows a break in the page order.

A side note: in the midst of the gray area you can see one orange line (and another in the sea of teal). Those are “type 11” PFS pages, which happen on a fixed interval in every file. I don’t think they ever move – they track file allocation and free space metadata. They are like rocks in the stream…

Now, what happens if we re-index this bad boy? Well, a re-index operation has to write all the pages for the object into new, blank pages in the file, and then abandon the old pages. I run:

-- This "moves" all the data toward the end of the file, into free areas
ALTER INDEX ALL ON dbo.SampleCustomers REBUILD;
GO

Then re-analyze the file. As expected, the table has “moved” toward the end of the file, and left free space toward the beginning. It’s still not fragmented, because we had enough room, and it was written in order into that new area by the rebuild:

We can see the gray area near the top is all the “abandoned” pages where the index was, and the data has all moved down into the free area. Ah, but that seems wasteful to some people, am I right? All that empty space – the file could be smaller!

Let’s see the damage that Shrink File does. Imagine that I do this:

DBCC SHRINKFILE (N'VizDemo1' , 70)
GO

First, before we shrink, let’s just scroll down and look at the end of the file:

We have two conditions – the gray part of the file is sort of OK to shrink. There’s just a lone PFS page out there, and removing that does no harm. But once we get into that blue area, the data has to be moved back up into the beginning of the file. Here’s where the problem lies, as I learned from Mr. Paul Randal – the shrink routine will move a page at a time back into that free space, starting from the end, going backward. That makes the pages land in approximately reverse order from the correct index order. Perfect fragmentation. Let’s see if this tool proves him right. Shrink, then re-analyze:

Yep, it’s not immediately apparent, perhaps, but that teal color is a darker shade that indicates every page is a fragment boundary in most of the index – perfect fragmentation! Here’s a better view:

So, how can we clean that up? Well, with a rebuild. But … we need that bigger file. In fact, practically any database in production needs this overhead of available space to be able to perform index maintenance. It’s not “wasted” space at all.

ALTER INDEX ALL ON dbo.SampleCustomers REBUILD;
GO

After the rebuild, the index is back toward the end of the file, but it’s also back in order:

Now, in light of this information, imagine nightly re-indexing on a database with … AutoShrink! <shudder>

Visualizing Data File Layout I

merrillaldrich — Tue, 22 Jan 2013 22:50:34 GMT

Part 1 of a blog series visually demonstrating the layout of objects on data pages in SQL Server

Some years ago a gentleman called Danny Gould created a free tool called Internals Viewer for SQL Server. I’m a visual sort of guy, and I always thought it would be fun and educational to make a simple visualizer, like the one he created, in order to view how objects are laid out in SQL Server files, and to use it to demonstrate how operations like re-index and shrink affect the layout of files.

To that end, and a little bit reinventing the wheel truth be told, I spent this past holiday creating a simple .NET app that renders the file layout of a database into a color-coded bitmap:

Fig 1

The app can scan the pages in a database, grab the header output from DBCC PAGE, parse that, and create a structure with a few key bits of information about every page. It then renders a bitmap from those structures showing a few things (Fig 1):

Each data object (index or table) partition is identified with a unique partition ID in SQL Server. Those IDs are used in this tool to color-code the output by object, from a color lookup table. Each color in the example screenshot represents the pages that are dedicated to a single partition of an object. This screenshot shows AdventureWorks, which doesn’t use the Enterprise Edition partitioning feature, so for this case each color represents one object – every object having exactly one partition in Standard Edition (or in databases that don’t use partitioning).

Unallocated pages are shown as gray gaps. These are regions that are part of the physical file(s), but not used to store anything.

The app flags pages at the end of any fragment of an object using a darker colored band, so it will reveal any non-contiguous structures in the data file(s). Sometimes these happen at the end of a region of the file where one object is stored, but, interestingly, sometimes these can happen in the middle – as shown in the image above where a dark band interrupts a continuous region of the same color.

The app has some very basic mouse-over capability where you can run the mouse over the image and the text fields at right will reveal information about the pages, including the object schema.table.index and partition, and also whether the page represents a fragmentation boundary.

Finally, the app shows what page types are located where in the file using the narrower white/gray/black bands. White represents data or index pages, while other shades of gray or black indicate other kinds of system pages, per Paul Randal’s excellent blog post here.

The Pixels Already Tell a Story

So, what can we learn about the sample database in this image? Here are a few things:

The part of the file shown in the bitmap is fairly dense. There aren’t big regions of unallocated space in the file. A gap in the allocated pages looks like this (enlarged):

Empty Region
Objects in the file are not contiguous, and may “hop around.” That is, if you follow the linked list of pages that compose an index, a bunch of them will be in a row, and then there will be a page that links to the next page composing the index but it’ll be in a different location in the file. I’ve called these “frag boundaries” – pages that do link to another page, but where that next logical page isn’t the next physical page in the file. In the graphic the frag boundary pages are colored with a darker dithered pattern. You can mouse over these and look in the text fields at the right in the app, and see the page they link to.

Fragment Boundaries

Sometimes the end of a fragment will be adjacent to pages from another object, but it can be the case that there’s a fragment boundary in the middle of the pages for one object – it’s just that the linked list goes up to that point in the file, but then the next page in the index (in index order) isn’t the next page in the file, even though the next page in the file is part of the same object. Imagine a page split in the “middle” of an index – the existing page with half the rows stays in place, and a new page with the other half of the rows gets created in the middle of the logical index order but possibly stored in some other location in the physical file.
Right at the very beginning of the file there’s a special sequence of metadata pages that describe the database, allocations, and so on (again, well documented by Paul Randal). In our diagram this shows up as a series of pages at top left with varying page type (the gray and white) indicators:

Database and file metadata pages

In the next installment, I’ll run some test databases through this and we can see what more severe fragmentation looks like, the effect of GUID cluster keys, shrink, and how the data moves around in a re-index operation.

Here’s a short demo video of the mouse-over working (quality is You-Tube limited):

Animated Screen Cap of Mouse-over

Update to Rules-Driven Maintenance

merrillaldrich — Wed, 16 Jan 2013 18:34:00 GMT

Back in August I posted a first version of a rules-driven solution for backups, index and statistics maintenance and integrity checks. The system in general has been working well, and has saved my team a huge amount of time and effort. We are coming to the anniversary of its use in production soon.

Today I offer an update that contains a few enhancements, performance improvements and a bug fix.

To recap, this is a system or framework to manage many small databases across many instances on many servers in a policy-based/automated way. The details about how to deploy and how to use the system are in the original post, but at a high level:

First deploy the code across a collection of servers using the included PowerShell script DeployMaintenance.ps1. That will create an administrative database on every instance (or use one that you provide) and populate it with the required tables, procedures, etc. The deployment script will also make a handful of SQL Agent jobs that handle all the maintenance on all the databases.
Visit the instances. If there is maintenance already in place, disable or remove it so as not to perform this work twice. If necessary, change or override the default preferences for this solution in the admin database for each type of maintenance. This includes the time of maintenance windows, whether to use features like differential backups or Litespeed, whether there are databases that should be treated as exceptions, with different settings, etc.
Enable the new policy jobs in SQL Agent.
Monitor to make sure things are running smoothly.

The theory behind this project is to save work configuring servers (efficiency), to ensure that the maintenance is in fact deployed and working for ALL databases in the environment (quality), to ensure that it works in a truly consistent way everywhere (consistency), and to make it so that the servers don’t have to be touched by a DBA when changes happen, such as adding or dropping databases (resiliency).

Changes

The updates in this 1.1 version include

Better reporting of errors. The jobs now write log files to the default error log location for SQL Server.
Better recovery from errors. The jobs in some cases continue on error – for example, one failed backup will not stop the backup job and leave other databases without backups.
Performance enhancements for examining backup history and system counters (mainly % log used).
One bug fix for the log backup logic on a server that uses both log shipping and Litespeed.

Disclaimers

The code for the system is posted here, and you are welcome to download it and try it out. Please note that this is not a commercial solution, and that while you may test or deploy this, you do so at your sole risk. Edits to the code almost certainly will be required for your environment. Please read, understand and test the code thoroughly before you even imagine using this in production. I do not want to cause you or your employer any pain. License for using this solution is GPL 3.0: http://opensource.org/licenses/GPL-3.0. You may use and modify this code, but not sell it.

This has been run on SQL Server versions from 2005 to 2008 R2. It probably works on 2012, but I have not tested it thoroughly.

I run only case-insensitive collation; if you are on a case-sensitive system, then you have my sympathy, and you might have to edit a few things to make this work.

There is coverage for Quest Litespeed backups in the solution; other third-party backup products could be incorporated easily, but have not been. It should be possible to follow the pattern used to handle Litespeed and extend it to any other third-party stored procedures.

If you haven’t done index maintenance for a while, and you flip this solution on you might blow up your transaction log. Be sure that you have plenty of log space and plenty of log backup space, and watch the process the first few runs. This is especially true if the combination of Standard Edition of SQL Server and the preference for Online index maintenance applies in your environment, because the maintenance process will perform index maintenance using reorganize (defrag), which produces a lot of log.

Lastly, this is a solution for the type of environment that has many small databases, not the type with a few big, performance intensive databases. Databases that are large and require detailed attention may not be suitable for a one-size-fits-all solution like this.

Geek City: Build a Big Table with a Columnstore Index

Kalen Delaney — Thu, 26 Apr 2012 18:18:00 GMT

I was looking all over to find a big table to use for my columnstore examples in my SQL Server 2012 book, and the only one I found was from someone at Microsoft and was not publicly available. When I demonstrate code in my writings, I like to have the code available for anyone to use, so that was no use.

Finally I realized I was just going to have to do it myself. I actually based the script on some work by the awesome Benjamin Nevarez (blog| twitter), but I needed to make a couple of changes to the table structure, and then the loop for adding the data took some tweeking to make sure that uniqueness was possible, in case you need to test out how the metadata changes when a columnstore index is built on a table with a unique clustered index compared to a nonunique clustered index compared to a heap.

I have just finished the chapter on indexes, and decided to make this script available. The initial table data is based on the data in Microsoft AdventureWorksDW2012 sample database that you can download here. (Note that the DW version is the first one under “Other Available Downloads”’; it’s not the one under “Recommended Download”. )

Here is the section of the script that populates most of the FactInternetSalesBIG table. (The original 60K rows were just copied from the original FactInternetSales table. Note that all the statements have to be run in a single batch because the local variable’s scope is the batch, and because the GO 9 applies to the single batch that precedes it. Of course, you can change the number of iterations to end up with a different size table. Mine ends up at just over 30 million rows. In addition to modifying the SalesOrderNumber value on each iteration, I also changed the value of the Revision column to indicate which pass through the insert loop was being executed.

-- Copy the new big table into itself 9 times
DECLARE @RevisionNumber nchar(2);
SELECT @RevisionNumber = RevisionNumber + 1 FROM RevisionNumberValue;
SELECT @RevisionNumber as RevisionNumber;
INSERT INTO dbo.FactInternetSalesBig WITH (TABLOCK)
SELECT ProductKey
,OrderDateKey
,DueDateKey
,ShipDateKey
,CustomerKey
,PromotionKey
,CurrencyKey
,SalesTerritoryKey
,SalesOrderNumber + @RevisionNumber
,SalesOrderLineNumber
,@RevisionNumber
,OrderQuantity
,UnitPrice
,ExtendedAmount
,UnitPriceDiscountPct
,DiscountAmount
,ProductStandardCost
,TotalProductCost
,SalesAmount
,TaxAmt
,Freight
,CarrierTrackingNumber
,CustomerPONumber
,OrderDate
,DueDate
,ShipDate
FROM dbo.FactInternetSalesBig;
UPDATE RevisionNumberValue SET RevisionNumber = RevisionNumber + 1;
GO 9

Make sure you have enough log space. My log grew from 1GB to just over 8GB when running the script to build the 30 million row table and columnstore index, with no clustered index.

The downloadable script has commented options to build either a clustered or nonclustered index before you build the columnstore index. I suggest building the clustered index before the columnstore index, because building the clustered index will rebuild any existing nonclustered indexes, including my columnstore index. Building the columnstore index can take a while, on my system it was about 10 minutes. (Building the original 30+ million row table took even longer.)

After I finish the chapter on partitioning, I'll have a script to partition this table, but feel free to do that yourself!

Have fun!

~Kalen

Speaking at the Charlotte Users Group

Andrew Kelly — Sat, 27 Aug 2011 00:33:55 GMT

I will be giving a presentation in between Earthquakes and Hurricanes in Charlotte NC. this Wednesday the 31st of August on Understanding Indexes in SQL Server 2008. If you are in the area please drop by and say hello. You can find out more information and register for the event here.

Andy

SQL Server, Seeks, and Binary Search

Paul White — Mon, 08 Aug 2011 20:10:27 GMT

The following table summarizes the results from my last two blog entries, showing the CPU time used when performing 5 million clustered index seeks:

In test 1, making the clustered index unique improved performance by around 40%. In test 2, making the same change reduced performance by around 70% (on 64-bit systems – more on that later). As a reminder, both tests use nested loops to join a single-column BIGINT table of numbers to itself:

In test 1, the table contains numbers from 1 to 5 million inclusive; for test 2, the table contains the even numbers from 2 to 10 million (still 5 million rows). In case you were wondering, the test 2 results are the same if we populate the table with odd numbers from 1 to 9,999,999 instead of even numbers. How can we explain these results?

Performing an Index Seek

Perhaps we need to look a bit deeper into how SQL Server performs an index seek. Most people know that SQL Server indexes are a B+ tree, so let’s work through an example of locating the row containing the value 1 million, when the table contains values from 1 to 5 million, with a unique clustered index.

Index seeks start at the index root page, which we can find in a number of ways (e.g. sys.system_internals_allocation_units). I happened to use DBCC IND to determine that the root of the index was page 117482 in file 1 (in Denali, we can use a new DMF: sys.dm_db_database_page_allocations). Anyway, whichever way you find it, we can use DBCC PAGE to look at the contents of the root page:

The col1 (key) column shows the lowest key value that can possibly be present in the lower-level page specified by Child Page Id. We can see that the lowest possible key value on page 117485 is 906305, and the next lowest key value possible is 1132881 on page 117486. So, if a row containing the value 1 million exists, the next page to look at is 117485:

We are now at level 1 of the index, and have to scroll down the output a bit further to see that the next page to look at is 119580. This page is at the leaf level of the index, and we find our target value at position 399:

Binary Search

When performing an index seek, SQL Server obviously doesn’t run DBCC PAGE and scroll down the output window to find the next page to look at like we just did. You may know that SQL Server can use binary search to locate index entries, but it’s worth taking a closer look at the index pages to see how this works in practice:

The slot array contains a series of two-byte offsets pointing to the index records. The index records are not necessarily stored in any particular order on the page; only the slot array entries are guaranteed to be in sorted order. Note that the sorted slot array entries do not contain the index keys themselves, just offsets.

Performance

When SQL Server uses binary search to locate an index entry, it starts by checking the middle element of the slot array (shown in red in the example above). It then follows that offset pointer to the index record, and compares the value it finds there with the sought value. Assuming the value is not the one we are looking for, the sorted nature of the slot array allows SQL Server to narrow the search range in half after this first comparison.

If the red index record happens to contain a value higher than the sought value, we know the value we are looking for is in that half of the slot array that sorts lower than the red entry. This process of cutting the search space in half continues until we find the record we are looking for, or until it becomes clear that the value does not exist.

The average and worst case performance of binary search is very close to log₂N comparisons to find the item of interest in a sorted list of N items. For the 476 index entries found in our test example index structure at the leaf level, that means at most 9 comparison operations. That compares well to a linear search of the sorted slot array, which might require as many as 476 comparisons if we are unlucky, 238 on average.

None of this offers any particular insight into why a binary search into a unique indexes containing only even (or odd!) numbers should be so slow. One of the advantages of binary search is that it expects to perform around the same amount of work, regardless of the distribution of the values in the index. Luckily, binary search is not the only game in town.

Linear Interpolation

As efficient as binary search is in the general case, in some cases we can do better.

When searching for the value 1 million, we know from level 1 of the index that the lowest key value that can appear on the leaf level page we are interested in is 999,601. We also know that the lowest key value on the next page is 1,000,077. From the header information on our target page, we also know there are 476 entries in the slot array on that page. Given these facts, we can make an immediate guess at which slot the value 1,000,000 ought to appear in:

expected slot = (1000077 - 999601) / 476 * (1000000 - 999601) = 399

This simple calculation takes us immediately to slot 399. As we saw earlier, slot 399 does indeed contain the value 1,000,000:

Naturally, the quality of the linear interpolation guess depends on how evenly distributed the values are within the page. To a lesser extent, it also depends on how closely the minimum key value information at level 1 of the index matches reality. In both tests shown in earlier blog entries, the values are precisely evenly distributed and the level 1 index key information is spot on.

Performance

Linear interpolation has the potential to be more efficient even than binary search, finding the target value in one comparison in this example, compared to nine comparisons for binary search. Even where the data is not perfectly distributed, there is scope for linear interpolation to be superior, simply by applying the technique repeatedly on successively narrower ranges.

A reasonable practical compromise might be to try linear interpolation two or three times, before falling back to linear or binary search on the remaining range. The advantage of linear interpolation may not seem much, but consider that SQL Server makes these comparisons for every index seek operation – when doing many millions of seeks, the difference can soon add up. It is probably not coincidence that the OLTP TPC benchmark tests perform a very great number of singleton index seeks.

Linear Regression

A natural extension to the idea of linear interpolation is to apply a linear regression (line of best fit) instead:

In the diagram, the blue dotted line represents a linear interpolation based on the values of the smallest and highest values only. The black line is obtained by a linear regression of all the data values, and results in a much better fit.

Since every straight line can be represented by a formula of the form y = mx + b, we can completely specify it by recording the values of the ‘m’ (slope) and ‘b’ (y-axis intercept) parameters. The R² value gives an idea of how good a fit the linear regression line is to the data. In the present context, the ‘y’ value represents the indexed value, and the ‘x’ value is the slot position where that value can be found. It’s easy to see that once we have a linear regression line, we can estimate the slot position for a particular sought index value by solving x = (y – b) / m.

To use linear regression in a database, we might imagine storing the ‘b’ and ‘m’ parameter values somewhere (perhaps in a compact format in the page header), and deciding whether to apply the technique based on the R² value.

What Does SQL Server Do?

All this is fine in theory, but does SQL Server really ever use anything except binary search? To see, I ran tests with a debugger attached to the SQL Server process, and stepped through the calls made while the seek test queries were running. The call stack below was obtained when running 64-bit SQL Server:

By contrast, the following call stack comes from 32-bit SQL Server:

Interestingly, SQL Server follows the same code paths (at least at the call stack level, which is the best we can do without source code) regardless of whether the index is defined as unique or not, and for all the numeric data types I tested (INT, BIGINT, REAL, FLOAT, DECIMAL with a zero scale).

The performance problem on x64 servers appears to be most pronounced when the key values have a small fixed gap between them. As we have seen, performance is very much worse on x64 servers compared with x86 versions when the table contains just even or odd numbers (i.e. with a gap of 1 between index entries). If we change the test to multiply the original entries by a factor of ten (to produce a sequence of 10, 20, 30, 40…) the performance penalty all but disappears, and the x64 unique index test is around 30% faster than the non-unique test.

Conclusions and Further Reading

From the evidence available, my best guess is that 64-bit SQL Server does use linear interpolation and/or linear regression instead of binary search under suitable conditions, but that the implementation has edge-case poor performance where the index keys are separated by a small fixed offset. It seems that we can achieve best performance by using a unique index where possible, and ensuring that keys are, as far as practicable, sequential and contiguous.

B-tree Indexes, Interpolation Search, and Skew – Microsoft Research
Interpolation Search – a log log N Search (PDF)

email: SQLkiwi@gmail.com
twitter: @SQL_Kiwi