Well… You might have noticed that I enjoy doing small Programming challenges, like those on Dev102. So I just noticed that there is currently another “Google Code Jam” running.
So head over to http://code.google.com/codejam/contest/ and give those problems a shot & have fun
The SQL Server stores Data, lots of it. And you usually want to retrieve the data as fast as possible. So what are you going to do? You create an index on your data tables.
Well great. That’s a step in the right direction, and most likely you have improved the performance in the order of magnitudes. But what kind of index did you create and what are the differences? Is it a clustered index? Is the index covering your query? Why should it cover? What’s “new” in SQL Server 2005 or 2008? What’s a fill factor?
I wanted to cover everything in one article, but it looks like this is getting out of hand, so this will be a small series.
A table in the SQL Server can have 2 different kinds of indexes. Today we will take a closer look at the:
This index can only exist ONCE. It defines the “physical layout” of your data. Basically the clustered index is your table. All your data will be contained in the leaf nodes of a binary-tree (the clustered index).
Let’s look at the properties of a clustered index.
· Extreme performance for selecting ranges of values ( between , > , < …)
· Good performance for foreign key columns
· Grouped columns
· Columns with very distinct values (NOT primary key)
· Data that is processed sequentially
· Columns that grow constantly (e.g. DateCreated, ID,…)
· Static data (Write once, change never)
· The Clustered index will always “cover” your query, since it contains all data
· Bad for data with “random” inserts. This can cause “page splits”
· Lookup of specific Values (this can be handled better by a regular index)
· Dynamic data (Data that changes often. It will force the Serer to relocate the entire row, if the data changes)
· Might need extra space, if the index value is not constantly growing (Called “Fill Factor”).
· Must (well really should but it’s a very urgent should) be aligned with a partitioned table
What are page splits and fill factors? Those 2 terms are somewhat related to each other. I already mentioned that a clustered index will contain the data in its physical layout. So imagine a phonebook. This stores people by location & name. So it’s very easy to retrieve all “Smith in New York” (e.g. 10 pages).
But if we have a new Mr. Smith moving to NY, then we have a problem. We won’t be able to insert him into the phonebook, since there is no extra room. Instead we have to rearrange all persons and print a new phonebook. SQL Server is not that extreme, it will only process pages of data. Each data page is only 8 kb in size.
The fill factor will tell SQL Server how much of this space it should use when (re)creating an index. If we would pick the Location/Name as our clustered Index, then we know that we will most likely have some inserts/deletes/updates over time. So we will let the SQL Server know that it should keep some spare room on every page. This will allow us to insert our new Mr. Smith if he chooses to move to NY.
An important point to note is that a fill factor will only force an INITIAL amount of free space. When the index gets filled over time, since Mr. Smith is also bringing his whole clan to NY, the free space will decrease, until there is no more space left, and that will introduce the “page split”.
When a page split happens, the SQL Server will distribute the data from the page and move some of it to a new page, so there will be some room. After the new room is created, we can insert our Mr. Smith on the new, half empty page.
So you could avoid this problem by telling SQL Server to leave lots of room (e.g.: Fill factor 50%) for new data. Well… That’s not really that good either, since now we will spread the data over many more pages. And if we ask the server for “Smith in New York” again, it will now be forced to read twice as many pages (20) from the storage system to answer the same question. And the bad news is that IO is still the slowest part of your average Database…
This can be avoided, if we have a static, always increasing key on our clustered index, since the data will always be larger then the last one we inserted, we can set the fill factor to 100% and use all the space in the in the data pages.
Also a relation like order-order_items (Order_ID, Order_Position) is a good candidate for a clustered index. Since the orders don’t change often, once they are created. And the typical access is usually performed by coming from an order. And you can retrieve all related information without the need for an extra table lookup. Also all the Information will be close together, since the data is stored in the Index leave nodes. So there is no need to load any other datapages to answer the order query.
Something to note… If you create a primary key constraint on a table, SQL Server will automatically create a clustered index for you. This might not always be the optimal choice, so be aware of this.
So when should you create a clustered index? There is no right answer that can be given here. If it makes sense to keep the data together or if it will almost allways be retrieved in a “grouped” / aggregated way. So I would settle for a very general “It depends…”
That’s it for this post. I tried to keep it “simple”, so let me know if you like this style, or if you would prefer a more detailed approach with lots of SQL and DBCC statements etc…
On the next post I will take a closer at the regular indexes, covering queries and filtered index in SQL 2008.
P.s.: This is not my 1st language… So have mercy 
This weeks question on „Dev102“ is:
Given a list of n integers and another integer called m, determine (true / false) if there exist 2 numbers in that list which sum up to m.
Example: 2,6,4,9,1,12,7 and m=14 -> 2 and 12 sum up to 14, so the answer is true.
Provide the best algorithm in both manners: performance and memory to solve this puzzle. Don’t forget to mention the complexity of your solution!
So lets take a look at the different options we have…
The naïve approach would be to check every number with every other number. This would lead to N * (N-1) / 2 checks to find all possible combinations. And as you most likely guessed it, this is not the optimal approach.
So how can this be improved?
My 1st thought is again by sorting the input and the testing it more logically. I am still trying to wrap my mind around a solution that does not require me to sort the list, but it seems like this time there is no way around it.
So how would you test this more logically?
Since we now operate on a sorted list, we know that if we exceed the test for 2 given numbers in the list, then we can eliminate all further tests for that “row”. We close in from both sides until we found it.
Basically we can construct a result matrix that is also sorted, and by testing only the relevant points in this matrix we can eliminate all unneeded tests. For example the List { 5,8,11,15,23,25,29} would result in a Matrix like this:
|
i |
5 |
8 |
11 |
15 |
23 |
25 |
29 |
|
1 |
13 |
16 |
20 |
28 |
30 |
34 |
|
|
2 |
|
19 |
23 |
31 |
33 |
37 |
|
|
3 |
|
|
26 |
34 |
36 |
40 |
|
|
4 |
|
|
|
38 |
40 |
44 |
|
|
5 |
|
|
|
|
48 |
52 |
|
|
6 |
|
|
|
|
|
54 |
|
|
j -> |
2 |
3 |
4 |
5 |
6 |
7 |
|
If we start with j = max and i = 1, we could zero in on the target number quite fast.
For example if we look for 35 in the matrix (Which does not exist) we would have to do the following tests: (orange = to low, red = to high, green = eliminated since impossible)
|
5 |
8 |
11 |
15 |
23 |
25 |
|
13 |
16 |
20 |
28 |
30 |
34 |
|
|
19 |
23 |
31 |
33 |
37 |
|
|
|
26 |
34 |
36 |
40 |
|
|
|
|
38 |
40 |
44 |
|
|
|
|
|
48 |
52 |
|
|
|
|
|
|
54 |
The actual source for this problem is:
private bool findPair(int[] data, int target)
{
Array.Sort(data);
int i = 0;
int j = data.GetUpperBound(0);
while(i<j)
{
int current = data[i] + data[j];
if (current > target)
j -= 1;
else if (current < target)
i += 1;
else
return true;
}
return false;
}
You could also add an additional test at the beginning, that validates that there is a possible solution at all (checking if the 2 biggest numbers in the sorted list are bigger then the target number) But this would depend on the actual data that has to be processed. If that happens a lot, then you could even move this test to the pre-sort stage and simplify it to target < 2 * maxValueInList.
The overall complexity for this problem would be the cost of sorting + O(N).
Microsoft posted an open invitation for 2 SQL-Server 2008 exams (71-432 and 71-448).
You can take those exams for free, and if you manage to pass them, you will be given full credit for them (MSTS).
However, you will have to wait until the “real” exams are out to find out if you passed or not. So use this opertunity, and read up on all the great features in SQL2008 and go pass the exams…
So here is the Information from MS (shameless Cut&Paste) :
Below, you will find two beta exams invitations for SQL Server 2008 DBA 71-432 and SQL Server 2008 BI 71-448.
These exams will be available until July 31, 2008.
You are invited to take beta exam 71-432: TS: Microsoft SQL Server 2008, Implementation and Maintenance. You were specifically chosen to participate in this beta because of your current Microsoft Certification status or previous participation with Microsoft Learning. If you pass the beta exam, the exam credit will be added to your transcript and you will not need to take the exam in its released form. The 71-xxx identifier is used for registering for beta versions of MCP exams, when the exam is released in its final form the 70-xxx identifier is used for registration.
By participating in beta exams, you have the opportunity to provide the Microsoft Certification program with feedback about exam content, which is integral to development of exams in their released version. We depend on the contributions of experienced IT professionals and developers as we continually improve exam content and maintain the value of Microsoft certifications.
71-432: TS: Microsoft SQL Server 2008, Implementation and Maintenance counts as credit towards the following certification(s).
· Microsoft Certified Technology Specialist: SQL Server 2008, Implementation and Maintenance
Registration begins: June 5, 2008
Beta exam period runs: June 9, 2008– July 31, 2008
Receiving this invitation does not guarantee you a seat in the beta; we recommend that you register immediately. Beta exams have limited availability and are operated under a first-come-first-served basis. Once all beta slots are filled, no additional seats will be offered.
Testing is held at Prometric testing centers worldwide, although this exam may not be available in all countries (see Regional Restrictions). All testing centers will have the capability to offer this exam in its live version.
Regional Restrictions: India, Pakistan, China
You are invited to take beta exam 71-448: TS: Microsoft SQL Server 2008, Business Intelligence Development and Maintenance. You were specifically chosen to participate in this beta because of your current Microsoft Certification status or previous participation with Microsoft Learning. If you pass the beta exam, the exam credit will be added to your transcript and you will not need to take the exam in its released form. The 71-xxx identifier is used for registering for beta versions of MCP exams, when the exam is released in its final form the 70-xxx identifier is used for registration.
By participating in beta exams, you have the opportunity to provide the Microsoft Certification program with feedback about exam content, which is integral to development of exams in their released version. We depend on the contributions of experienced IT professionals and developers as we continually improve exam content and maintain the value of Microsoft certifications.
71-448: TS: Microsoft SQL Server 2008, Business Intelligence Development and Maintenance counts as credit towards the following certification(s).
· Microsoft Certified Technology Specialist: SQL Server 2008, Business Intelligence Development and Maintenance
Registration begins: June 15, 2008
Beta exam period runs: June 16, 2008– July 31, 2008
Receiving this invitation does not guarantee you a seat in the beta; we recommend that you register immediately. Beta exams have limited availability and are operated under a first-come-first-served basis. Once all beta slots are filled, no additional seats will be offered.
Testing is held at Prometric testing centers worldwide, although this exam may not be available in all countries (see Regional Restrictions). All testing centers will have the capability to offer this exam in its live version.
Regional Restrictions: India, Pakistan, China
You must register at least 24 hours prior to taking the exam.
Please use the following promotional code when registering for the exam: 943F6
Receiving this invitation does not guarantee you a seat in the beta; we recommend that you register immediately.
To register in North America, please call:
•
Prometric: (800) 755-EXAM (800-755-3926)
Outside the U.S./Canada, please contact:
•
Prometric: http://www.register.prometric.com/ClientInformation.asp
You are invited to take this beta exam at no charge.
You will be given four hours to complete the beta exam. Please plan accordingly.
Find exam preparation information: http://www.microsoft.com/learning/exams/70-432.mspx
This information was found on:
Hello World… got deleted!
So here is my 1st real post in my Blog.
This is the response to “A Programming Job Interview Challenge #8 – A Needle in a Haystack“
The question was about designing a queue that will create an alert when a certain pattern is found within the input. There are some more minor constrains, which you can check in the original post(Main constrain is that you cannot store the recieved data).
I am writing a C# implementation for this.
Explanation of the code:
The calls requires a pattern in the constructor. The pattern is then stored internally for further reference.
The main problem in this task is that we need to keep track of all possible matches that could happen. Take this pattern “A A A B” and this input “A A A A A B”. When we get the 1st A we could have a possible match. But when we get to the 4th A, the match failed. But the match that started from the 2nd and 3rd A are still in a valid state. So we have to treat each letter as a potential start for a match. And each potential match has to be evaluated separate. To keep the state of each possible match you could use all kinds of possible datastructures. I choose a generic list of enumerators. It is not the smallest possible structure I could have picked, but i think it is quite nice (you could also use an array of ints and increment each field as you need to match the next value…).
When a new chunk of data comes in, it will fetch an enumerator from the internal “pattern list”, and moves it onto the 1st position. Then it will add it to a 2nd internal List. This list will hold all “active” tests. After that is done, the class will try to validate all active pattern matches. If the match was OK, it will move the current enumerator to the next item to test. We have a positive match if we cannot move the enumerator, since we matched all items in the list.
If we fail to match a test, then we quite simply discard the current enumerator.
The maximum number of “concurrent tests” is limited to the size of the pattern. So for a 4-Element Pattern we would get a maximum of 4 concurrent tests.
The receive Function is not thread save, since we expect a lot of “sequential” input. The handling should be left to the calling function, or a thread save wrapper.
Example pattern: foo bar foo foo
Example input: foo bar foo foo bar foo foo
Result: 4-foo & 7-foo
Code:
internal class MatchingQueue<T> where T : IEquatable<T>
{private readonly List<T> target;
private readonly List<IEnumerator<T>> currentMatcher = new List<IEnumerator<T>>();
private int counter = 0;public event EventHandler<MatchingEventArgs> MatchFound;public MatchingQueue(T[] targetSequence)
{
if (targetSequence.GetUpperBound(0)<0)
throw new InvalidDataException(”Need at least 1 entry in order to match anything….”);
target = new List<T>(targetSequence);
}public void Receive(T data)
{
counter++;
IEnumerator<T> newTest = target.GetEnumerator();
currentMatcher.Add(newTest);
newTest.MoveNext();
foreach (IEnumerator<T> tester in currentMatcher.ToArray())
{
if (tester.Current.Equals(data))
{
if (!tester.MoveNext())
{
//No more tests… We have to report and remove
Report(data);
currentMatcher.Remove(tester);
}
}
else
//failed to match… Kick it
currentMatcher.Remove(tester);
}
//TODO: Foreward it to next Queue.}private void Report(T data)
{
EventHandler<MatchingEventArgs> temp = MatchFound;
if (temp != null)
temp(this, new MatchingEventArgs(data,counter));
}public class MatchingEventArgs : EventArgs
{
private readonly T match;
private readonly int counter;public MatchingEventArgs(T match, int counter)
{
this.match = match;
this.counter = counter;
}public int Counter
{
get { return counter; }
}public T Message
{
get { return match; }
}
}}
