Using Non Clustered Indexes in SQL Server

In general most of us believe indexes improve performance of our select queries. But as with every other thing, this too doesn't holds true universally. They only help in their specific use cases.

Indexes are sure to take a toll on your insert, update and delete queries and may even negatively impact select queries if not created properly. To judiciously create indexes we need to understand when a particular index will be of help. Below are scenarios which may help you figure out the right kind of non clustered index for your particular use case.

To begin with, let us create a test table and populate it with some data.

Scenario 1: One non clustered index per column

Suppose we have below query on our table. To cater this query two separate indexes one each on columns "Name" and "VarField" are required. This is so because where clause in our query has two conditions joined with OR operator.

Note: If you have 10 fields in your where clause then this doesn't means you gotta create ten indexes. You should create and test and then decide on right balance. 

Create index script:

Scenario 2: Multiple key columns in single non clustered index (Composite Index)

Now suppose above query changes from OR condition to AND condition, in that case having one index comprising of both columns will be a better solution as we will get data from index in one go. If we had two different indexes one each for both fields then SQL engine would have used only one of those indexes and did a key lookup for second condition.

Create index script:

Scenario 3: Covering index

Now say we need to search on Name field and fetch value of VarField, in this case covering index comes to our rescue. Covering indexes should be created for hot columns or those fields that are accessed very frequently. If we have lot many columns and different queries fetching different set of columns then better will be to use index on where clause field only.

Create index script:

SQL Indexing is a very vast topic and I hope this will help you begin appreciating idea of making indexes judiciously and not on every other column blindly. 

Happy Coding!!

Generic MinHeap implementation

With things in complete lockdown due to coronavirus situation world over, I was getting bored this weekend. Also I hadn't added any new post here in this blog for quite some time. So thought to write a new post, kind of killing two birds with a stone :P

In today's post I am going to talk about MinHeap. 

A min-heap is a binary tree such that - the data contained in each node is less than (or equal to) the data in that node’s children. - the binary tree is complete. 

Heaps are useful when we need priority queue kind of structure. Here instead of adding a new item at the end of queue, it could be inserted further up the queue depending on their priority. This helps in a lot of scenario but lesser beings like me could tell you that I used it while solving merge n sorted array task at hacker rank but to see a real real world use case, you may check this Quora answer.

Below is my array based generic implementation of MinHeap in C#. Using array for heap makes it easy to access child/parent nodes, we can do so by using simple formulae:

    parentPosition => (currentChildPosition - 1) / 2

           leftChildPosition => 2 * currentChildPosition +1

rightChildPosition => 2 * currentChildPosition +2

	using System;
	namespace ConsoleAppVS2017
	{
	/// <summary>
	/// Array based implementation of Min Heap
	/// </summary>
	/// <typeparam name="T">T should be IComparable</typeparam>
	public class MinHeap<T> where T : IComparable<T>
	{
	//This will be used in case default contructor is called for initializing MinHeap
	private const int DefaultHeapSize = 10;
	/// <summary>
	/// Heap storage array
	/// </summary>
	private readonly T[] heap;
	/// <summary>
	/// lastItemIndex keeps track of position where new item needs be added
	/// </summary>
	private int lastItemIndex;
	/// <summary>
	/// Gives count of elements currently present in Heap
	/// </summary>
	public int Count { get { return lastItemIndex; } }
	#region Constructors
	public MinHeap() : this(DefaultHeapSize)
	{
	}
	public MinHeap(int initialSize)
	{
	//TODO: Check against predefined MaxSize and throw some checked exception
	this.heap = new T[initialSize];
	lastItemIndex = 0;
	}
	#endregion
	/// <summary>
	/// Get min element of heap without pulling it out
	/// </summary>
	/// <returns></returns>
	public T Peek()
	{
	if (lastItemIndex == 0)
	{
	throw new InvalidOperationException("Heap Empty");
	}
	return heap[0];
	}
	/// <summary>
	/// Add a new element in heap
	/// </summary>
	/// <param name="item">Item to be added</param>
	public void Push(T item)
	{
	//Validate if heap has space left for adding new element
	if (lastItemIndex == heap.Length)
	{
	//TODO: Implement Grow function and throw in case heap reaches max permissible size limit
	throw new OverflowException("Heap overflowed");
	}
	heap[lastItemIndex] = item;
	//Add element at the end of tree and increment array index pointer
	lastItemIndex++;
	//Print();
	//Console.Write("\t\t");
	//Adding a new element may break min heap property "All root elements should be smaller than their child nodes"
	HeapUp();
	//Print();
	}
	/// <summary>
	/// Remove min element of heap
	/// </summary>
	/// <returns>Min element of heap</returns>
	public T Pop()
	{
	if (lastItemIndex == 0)
	{
	throw new InvalidOperationException("Heap Empty");
	}
	T result = heap[0];
	//Print();
	//Console.Write("\t\t");
	//After removing min element we need to rebalance the tree by moving one of the child nodes up
	HeapDown();
	//Print();
	return result;
	}
	#region Private Functions
	/// <summary>
	/// Hear we begin from last item of heap and bubble it up till we find a node where both its child are bigger than it
	/// To bubble up we find Index of parent node which is equal to (index of current item - 1) / 2
	/// and swap if current item is smaller than its parent
	/// We repeat steps till heap property gets true or root node is reached
	/// </summary>
	private void HeapUp()
	{
	int itemIndex = lastItemIndex - 1;
	do
	{
	int parentIndex = (itemIndex - 1) / 2;
	if (heap[itemIndex].CompareTo(heap[parentIndex]) < 0)
	{
	Swap(itemIndex, parentIndex);
	itemIndex = parentIndex;
	}
	else
	{
	break;
	}
	}
	while (itemIndex != 0);
	}
	/// <summary>
	/// Here we move the last item of tree at top position and then rebalance tree by swapping smaller of two child nodes with root node
	/// We keep iterating till we have reached end of tree or tree gets balanced
	/// </summary>
	private void HeapDown()
	{
	lastItemIndex--;
	//Move last item at top
	heap[0] = heap[lastItemIndex];
	//replace moved item with default value, null for reference types, 0 for int, etc
	heap[lastItemIndex] = default(T);
	int currentItemIndex = 0;
	while (currentItemIndex != lastItemIndex)
	{
	int minChildIndex = FindIndexOfMinChild(currentItemIndex);
	if (minChildIndex != -1 && heap[currentItemIndex].CompareTo(heap[minChildIndex]) > 0)
	{
	Swap(currentItemIndex, minChildIndex);
	currentItemIndex = minChildIndex;
	}
	else
	{
	break;
	}
	}
	}
	/// <summary>
	/// Finds smaller of two child nodes
	/// </summary>
	/// <param name="currentItemIndex"></param>
	/// <returns>-1 if its lead node else index of smaller child or only child available</returns>
	private int FindIndexOfMinChild(int currentItemIndex)
	{
	int leftChildIndex = (2 * currentItemIndex) + 1;
	int rightChildIndex = (2 * currentItemIndex) + 2;
	//Current item is last item of heap
	if (leftChildIndex >= lastItemIndex && rightChildIndex >= lastItemIndex)
	{
	return -1;
	}
	if (leftChildIndex >= lastItemIndex && rightChildIndex < lastItemIndex)
	{
	return rightChildIndex;
	}
	if (rightChildIndex >= lastItemIndex && leftChildIndex < lastItemIndex)
	{
	return leftChildIndex;
	}
	if (heap[leftChildIndex].CompareTo(heap[rightChildIndex]) < 0)
	{
	return leftChildIndex;
	}
	else
	{
	return rightChildIndex;
	}
	}
	private void Swap(int index1, int index2)
	{
	T temp = heap[index1];
	heap[index1] = heap[index2];
	heap[index2] = temp;
	}
	private void Print()
	{
	Console.WriteLine(string.Join(",", heap));
	}
	#endregion
	}
	}

view raw .cs hosted with ❤ by GitHub

You may like to check this link for more details on heap. Stay Home, Stay Safe!