Guest User

blog

a guest
Nov 14th, 2026
22
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.62 KB | None | 0 0
  1. So you think you know indexes in databases. Do you know if deep enough to really use it to optimize db queries?
  2.  
  3.  
  4. Let understand this from first principle
  5.  
  6. A table looks like rows, but the database stores it in pages. Logically, you see individual rows. But internally, bunch of rows are put together in a single page, which is usually of 8 KB size. So
  7.  
  8. Now, let say you have a Orders table whose schema is like this
  9.  
  10. orderId BIGINT,
  11. itemId INT,
  12. date DATE,
  13. Quantity INT
  14.  
  15. let us assume that 100 rows fit on each page
  16. So, for storing 1 million rows, we would need, 10K pages.
  17.  
  18. Suppose you want to get all the rows for itemId = 101
  19.  
  20. You make query like this
  21.  
  22. SELECT *
  23. FROM Orders
  24. WHERE itemId = 101
  25.  
  26. Without a useful index,
  27.  
  28. The database engine cannot know which page contains the row where itemId is 101. So it has to search though all the rows. To get all the rows, it needs to load 10K pages from disk to memory which is quite a big operation for such simple query.
  29.  
  30. Search sequentially through all the rows of database is called a Scan.
  31.  
  32. So, even if there could be only 10 rows for itemId = 101, db still has to examine 1million rows.
  33.  
  34. So, we want to avoid scanning?
  35.  
  36. Imagine, we maintained a separate structure containing:
  37.  
  38. ItemId, Where to find the row
  39. 100, Row location A
  40. 101, Row location B
  41. 101, Row location C
  42. 102, Row location D
  43.  
  44.  
  45. This structure is ordered by itemId
  46.  
  47. Now db can locate the row for itemId 101 by fetching the row data from the location mention in the above structure.
  48.  
  49.  
  50. That is the basic idea of a nonclustered index.
  51.  
  52. One important point regarding nonclustered index is, it stores the location the corresponding row, not the row itself (althought you can includes other columns of the row, which will make the size of index bigger)
  53.  
  54. Finding an entry in the index and fetching the complete table can be two separate pieces of work.
  55.  
  56.  
  57. Now you can imagine that, the index structure could also be big for a table having many rows. This index also gets stored in to pages of 8KB, so large indexes are further splited, and this happen recursively. The index takes the shape of B+tree data structure, where each of the node of the tree is a page of 8kb size. The actual data gets stored in the leafs, and the intermediate nodes of the tree helps db to quickly search the row.
  58.  
  59.  
  60. Let us now move to the clustered index.
  61.  
  62. We have not yet talked about in what order we store the actual rows. We can leverage this order of storing rows to optimze the queries as per the use case.
  63.  
  64. So, the way we store rows also form B+ tree structure. Again like every B+ tree, the data (row’s data) gets stored in the leaves of B+ tree, and again the nodes of this tree is the pages.
  65.  
  66. So, search through a nonclustered inde can require two searches
  67.  
  68. Now, consider:
  69.  
  70. SELECT *
  71. FROM Orders
  72. WHERE itemId = 101
  73.  
  74. First it will naviate though the nonclustered index on itemId (if there is), then it will find x number of entries in the index
  75.  
  76. To get other column values like Quantity and Date (which is not present in non clustered index),
  77. It needs to fetch the values for each matched rows using the row identifier provided by the index.
  78.  
  79. Let’s suppose x rows matched for itemId = 101, then the db engine will make x fetch request to get the row data. These are called key look up.
  80.  
  81. Now, x could have been 1 or it could also have been 100k, so, the number of matching rows here is affecting the query performance a lot.
  82.  
  83. We could have been avoided it by storing the missing columns (quantity and date in this case) in the non-clustered index it self.
  84.  
  85. So in that case if we are matching large number then its better to do scan, for example, out of 1million rows, 300k matched, so even if we do scan all the rows, the total page read would be only 3K, but if we do keylook up for each of the matched 300K rows, then in worst case, we would be making 300K page fetch.
  86.  
  87.  
  88.  
  89.  
  90. ======== Part 2 =========
  91.  
  92. Query plan and statistics
  93.  
  94.  
  95. In part 2 of the blog, i want to cover what is query plan and statistics, and how db engine use it in execution of the query.
  96.  
  97. Let’s again take the same table that we took in part 1
  98.  
  99. orderId BIGINT,
  100. itemId INT,
  101. date DATE,
  102. Quantity INT
  103.  
  104.  
  105. Let’s say we have 1 million rows in this table. And the distribution is not uniform with respect to itemId. We also have clustered index on itemId
  106.  
  107. Let’s say we have 200K rows where itemId is 101, and 10 rows where itemId is 102. And other rows are uniformly distributed among itemIds.
  108.  
  109. Now, lets say we have stored procedure something like this,
  110.  
  111. CREATE STORED PROCEDURE getOrdersByItemId
  112.  
  113. SELECT * FROM Orders WHERE itemId = @itemId_param
  114.  
  115.  
  116. Now we will execute this stored procedure, getOrdersByItemId(101). DB engine will try to execute the stored procedure.
  117.  
  118. DB engine will see that we are trying to get orders data by searching through itemId, so it will try to leverage NonCustered index on it.
  119.  
  120. So, it will search the non clustered index, and it will find out 200K matching entries in non clustered index, to get the data for other columns, it will have to lookup. So in worst casse it has to make 200K page reads because is not guaranteed that the rows of same itemId will be in same page.
  121.  
  122. But there is one more way in which db engine can handle this
  123.  
  124. It will go sequential seach for all the rows. In worst case it will have to go through 10K pages. (assuming there will be 1000 rows in one page)
  125.  
  126.  
  127. In this case, reading 10K page vs 200K page, clearly it is efficient here to scan through the all pages.
  128.  
  129.  
  130. But, that’s not always the case.
  131.  
  132. For example
  133.  
  134. Let’s say user fires a query,
  135.  
  136. getOrdersByItemId (102)
  137.  
  138. Now if we search through the non clustested index, then there will be only 10 matching entries and then again we have to do 10 additional look ups to get the complete data.
  139.  
  140. If we would have followed the scan approach, then we would be scanning 10k pages, 1million rows out of which only 10 rows will match itemId 102 condition.
  141.  
  142. So, we saw that clearly no approach is better in every case.
  143.  
  144. So, the next question popping in your head should be, how does db engine know which plan should they use to search.
  145.  
  146. You can guess from here that, if db engine somehow has the info about how many rows will match the condition then, it can chose the plan based on it.
  147.  
  148. But it would be too much expensive to call COUNT query to just to count the number rows to be returned.
  149.  
  150. So, what db engine do is, it samples the data time to time and maintain statistics.
  151.  
  152. The statistics looks like this
  153.  
  154. itemId = 101, expected rows = 200k
  155. itemId = 102, expected rows = 10
  156.  
  157. If there are too many itemId, it stores the data in histograms usually with some step size.
  158. (please correct here if I am wrong)
  159.  
  160. Now, once this statics is ready, the db engine can make rational decision based on the statistics.
  161.  
  162.  
  163. Based on statistics, db engine, creates a sequence fo steps which we call query plan.
  164.  
  165. For repeated query istead of decuing quern plan on every run, it caches it.
  166.  
  167. You can face some serious issue when statistics gets stale. This happens where there is lots of read and write.
  168.  
  169.  
  170.  
  171. ========= part 3 =========
  172.  
  173. Different types of joins
  174.  
  175. Nested loop join
  176. Hash join
  177. Merge join
  178.  
  179.  
  180.  
  181. In the part 3 of the database index series blog, we will look into how indexes help in joining the tables.
  182.  
  183. Let’s again go back to the table that we have used in the last blog.
  184.  
  185. Orders table whose schema is like this
  186.  
  187. orderId BIGINT,
  188. itemId INT,
  189. date DATE,
  190. quantity INT
  191.  
  192. <insert example here of few rows>
  193.  
  194. Lets say we have one more table which is Items
  195.  
  196. itemId INT,
  197. itemName VARCHAR
  198.  
  199. <insert example here of few rows>
  200.  
  201. Now lets say we want to get table containing orderId, itemName corresponding to itemId, date and quantity
  202.  
  203. We can get it by using this query
  204.  
  205. SELECT o.orderId, i.itemName, o.date, o.quantity
  206. FROM Orders o
  207. JOIN Items i
  208. ON o.itemId = i.itemId
  209.  
  210. <insert example here of few joined rows>
  211.  
  212. Let’s understand how is this join is getting performed by the sql engine.
  213.  
  214. Lets says we have M rows in Orders table and N rows in Items table
  215.  
  216. The most obvious approach that comes to mind is
  217.  
  218. We will take a row iteratively from Orders table and try to find the itemName based on the itemId value. Again all the concepts we read for searching a row gets applied here, so to find the itemName from itemId, sql engine will try to see if there is any relevant index which can help, else it will do scan.
  219.  
  220. So, for M rows of Orders table, we will M lookups in the itemName
  221.  
  222. This approach is called nested loop join approach and it really makes sense when M is less.
  223. <insert example for this approach>
  224.  
  225. <pseudocode for it>
  226.  
  227.  
  228.  
  229. Lets think of another approach in case of M is large
  230.  
  231. If you carefully observe in the previous approach, the main bottleneck was the lookups was expensive, so if we somehow make this loopkup process fast and efficient then we will solve the problem. In the lookup, essentially we want to know the itemName from itemId, some of you might me starting to think where is this going, we have hash table data structure for exactly servicing the same purpose.
  232.  
  233. so , what we will do is, we will iternate the item table, and store the data in hashmap, for example, here the key will be itemId and value will be itemName.
  234.  
  235. Now, while joining we will iterate through the M rows of orders table and for each row we will perform the lookup for this hashmap.
  236.  
  237. This is called hash join approach
  238. So you see how this approach is suited more if we have large M.
  239.  
  240.  
  241. There is one more join approach called Merge join, which improves the efficiency further. But the criteria to do this join is there should be index to the joining column on both the tables, so that we have way to iterate the rows in sorted fashion.
  242.  
  243. Let’s see what does index on the joining column makes things favourable for joining
  244.  
  245. To understand it, imagine we have pointer at the 1st row of index structure on itemId (Orders and Items)
  246.  
  247. Let say on index on Orders table, the pointer (lets say left-pointer) is pointing to itemId 101, and in index on Items table, the pointer(right-pointer) is pointing to itemId 100.
  248.  
  249. As the index structure is sorted, we know to get to the row of itemId 101, we have move forward right-pointer.
  250.  
  251. And once we find that the itemId pointed by left-pointer is less than pointed by right-pointer, then we move forward the left-pointer. We do this till we reach the end of Orders table.
  252.  
  253. So, we saw how this is the most efficient among these three, but performing this join requires condition which is the column on which we are joining should be sorted.
  254.  
  255. <insert example here>
  256.  
  257.  
  258. Example data should be consistent
  259.  
  260.  
  261.  
  262.  
Advertisement
Add Comment
Please, Sign In to add comment