Post reply

Index and fragmentation

  • August 28, 2019 at 5:34 pm

    #3675175

    Hi  folks

    I know its very stupid questions but i have few doubts about sql server index and fragemnetation

    First what does indexs?? they sort data .By sort does it means physically data are shorted on disk ??? If not then what is sorted order and where ???  While in administration books its writes n as data are not physically sorted on disk while on various link on internet tells exactly opposite

    Secondly  if data are physically not sorted on disk then whats is fragmentation ??? Is nt fragmentation where logical order is different from physical i.e on disk ???  As per above and various books data on disk are not sorted even if they is index .. If that true that means there is always fragmenatation... Kindly correct me

    Third what difference between clustered index and on-clustered index ... why can be there be only one clustered index and n non clustered index ???

    clustered index means data are sorted but i can define sorting order in non-clustering  index definitions ...

     

    so what exactly is difference ???

     

    Kindly help.Any links would be appreciated

     

     

     

     

     

     

  • August 28, 2019 at 8:01 pm

    #3675194

    Very popular topic.  Start here:

    https://www.sqlservercentral.com/articles/introduction-to-indexes-part-2-%e2%80%93-the-clustered-index

    I'd go through the entire series.  Gail's VERY good.

    ----------------------------------------------------------------------------------
    Your lack of planning does not constitute an emergency on my part...unless you're my manager...or a director and above...or a really loud-spoken end-user..All right - what was my emergency again?

  • August 28, 2019 at 9:03 pm

    #3675204

    Here's a presentation by Paul Randal on the subject.  He's the guy that wrote most of the fragmentation related stuff.

    https://www.youtube.com/watch?v=p3SXxclj_vg

    --Jeff Moden

    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.

    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • August 29, 2019 at 2:19 am

    #3675269

    ... and read the following to answer most of your other questions...

    https://docs.microsoft.com/en-us/sql/relational-databases/indexes/clustered-and-nonclustered-indexes-described?view=sql-server-2017

    --Jeff Moden

    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.

    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • August 31, 2019 at 10:52 am

    #3676014

    Thanks Jeff and Matt for replies and link

    But it still doesnt ans my query.If Index are on disk physical structure as last link says so then why does various books related sql server administration tell exactly opposite that on disk data arent stored /shorted ????

    And what happens to fragmentation .. when does it comes to  picture

     

    Regards

     

  • August 31, 2019 at 5:35 pm

    #3676069

    Please read the links. This is explained in the links, especially the first one from Gail. There is a clustered index, data stored in this order, and non-clustered indexes, which only store the key columns sorted. The storage on disk is by extents, which have rows in order inside the extent, but the extents can be stored in different parts of the disk.

     

  • August 31, 2019 at 7:28 pm

    #3676076

    anoop.mig29 wrote:

    Thanks Jeff and Matt for replies and link

    But it still doesnt ans my query.If Index are on disk physical structure as last link says so then why does various books related sql server administration tell exactly opposite that on disk data arent stored /shorted ????

    And what happens to fragmentation .. when does it comes to picture

    Regards

    Ah... ok. I understand your confusion, especially when it comes to the word "sorting" and the word "data" and there's more than one definition of each depending on the context of where they're used in documentation. Let's cover a couple of definitions first just to clear up the very poor use of the words "sorting" and "data", especially as they appear in the last link that I provided.

    Setting the Stage

    To set the stage, we're not going to talk about any of the following because they're special cases, which form multiple barbed-wire lined rabbit holes that we just don't need to go down, for now.

    1. LOBs (things like VARCHAR(MAX), NVARCHAR(MAX), XML, and several of other things).
    2. ROW_OVERFLOW (occurs when you have a whole lot of variable width datatypes whose row content becomes larger than what will fit on a single 8K page for a given row).
    3. HEAPS ("tables" that have no Clustered Index).

    I also have to assume that you already know that ALL data in SQL Server lives on 8K pages.

    Simplified B-Tree Explanation

    I'll also state that I'm assuming (but will briefly restate the definition of) that you know that all indexes are stored in a "B-Tree" that has at least a "Root Page" (only one of these per B-Tree), may have multiple levels of "Intermediate Pages", and that the actual "data" for the index lives on the "Leaf Level" of the index whether it's a Clustered Index ("CI" from here on) or a Non-Clustered Index ("NCI" from here on).

    Assuming an index is large enough to have all 3 types of levels in the B-tree, the Root page contains a list of all the pages and the first index key value on each page that are in the first level of Intermediate Pages below the Root Page, each level of the Intermediate Pages (and there's always more than 1 page per level for Intermediate Pages) has a list of the pages and first key values it represents in the next level down, and the final level of Intermediate pages has a list of the Leaf Level pages and first key values it represents.

    All pages except the Root Page are "doubly linked" in that they contain the address of the page that's "logically sorted" before the page and after the page on the same level. Although there is a guarantee that the "logical order" of the before, current, and after pages will be preserved, there is absolutely NO guarantee that the pages will be in "physical order" (ascending and contiguous/gapless physical page numbers) within the MDF file, period.

    And, so, there's the first confusion that many documents about indexes instills. There are two types of "sorts"... logical (which is guaranteed) and physical (which is not) and the documentation frequently relies on the knowledge of the reader to understand which is being spoke of depending on the context in which the word "sort" is being used.

    As a bit of a sidebar, even the PHYSICAL order of rows within even a single page is NOT guaranteed. A thing called the "Slot Array" on each page controls the logical order of the rows on each page and SQL Server actually does a binary search according to the sorted "Slot Array" to find any given row for an Index Seek.

    So… on to your questions above. The first question you asked is…

    anoop.mig29 wrote:

    But it still doesnt ans my query.If Index are on disk physical structure as last link says so then why does various books related sql server administration tell exactly opposite that on disk data arent stored /shorted ????

    The point of confusion here are the definitions (and there’s more than one) of the words “sort” and “order” and the sorry fact that it depends on how people are using it in the context of what they’re writing.

    SQL Server ALWAYS stores things in indexes in the correct “sorted order” but it is rarely (so rare that you can’t actually ever count on it except in one instance that requires a whole lot of rules to be followed) the correct PHYSICAL order according to the physical page numbers within an MDF (or NDF) file and that’s what people are actually talking about in reference to your question. However, SQL Server ALWAYS stores data in indexes in the correct LOGICAL order… Period!

    For example, if you have a table full of names and the index key is based on those names and you have inserted all of the data in the index in perfect sorted order according to the index key (name column, in this case) and all the pages are as full as they can be and the table is the only table in the database and you’re the only one using the database and you’ve never updated anything in the table regarding the keys of the (for example) Clustered Index, then the LOGICAL order of the data in the Leaf Level (and all levels above it) will also be in PHYSICAL order.

    Now, let’s say that when you loaded all of that data in both perfect LOGICAL and PHYSICAL order, that you forgot to add my name (Jeff Moden) and you need to add it. Remember that each page is totally full and has no room for any more data. Also remember that SQL Server WILL store that new row on the correct page according to the LOGICAL sort order.

    Since there’s no room on the page that has been determined to be the page where the data needs to be inserted to maintain the correct Logical order, SQL Server will make a new page at the physical end of the file (in this case… it could be on an earlier page if one is “free”), move roughly have of the rows in the target page to that new page (which is NOT in physical order in this and most cases), and then finally insert the new row in the correct LOGICAL order on the original target page (or sometimes, new page). The LOGICAL SORTED ORDER is maintained but we’ve just blown the hell out of the PHYSICAL SORTED ORDER.

    So, to summarize…

    1. Documentation and the writing of blogs sometimes suck because the writers of such things get lazy and don’t explicitly state whether they’re talking about LOGICAL or PHYSICAL sort orders.
    2. LOGICAL sort order within an index is guaranteed although you cannot casually depend (there is one exception that I’ll not go into because it depends on a whole lot of rules and conditions) depend on a SELECT returning data in the correct LOGICAL order without an ORDER BY.
    3. PHYSICAL sort order is NOT guaranteed except in very rare cases (so rare that you shouldn’t depend on it) and THAT’s what people are talking about in reference to your first question.

    As to your second question of…

    anoop.mig29 wrote:

    And what happens to fragmentation .. when does it comes to picture

    First, I’m not sure which “picture” you’re talking about. But, no matter. Let’s talk about “fragmentation”.

    Logical Fragmentation

    Another fault of a lot of authors is that they only talk about “fragmentation”. In most cases, what they’re really talking about is “Logical Fragmentation”. Some people also refer to this as “external” fragmentation and I strongly recommend that they stop calling it that. I refuse to use the term because of its confusion factor. So does Paul Randal, the guy that was responsible for writing both the code for index maintenance and the official documentation about it for MS. Call it “Logical Fragmentation”… period.

    LOGICAL fragmentation has a very simple definition. Remember that each page in the Leaf Level knows the physical page number of the next page to create the correct logical order? If that “next” physical page number in the index isn’t exactly 1 larger than the “current” page number, that’s what defines LOGICAL fragmentation. The more non-contiguous pages you have, the higher the value you’ll find in the “avg_fragmentation_in_percent” column of sys.dm_db_index_physical_stats (the tool that everyone uses to measure fragmentation). And, remember, that “next” page might not even have a higher number than the “current” page. The “next” page may be physically before the current page in the file. This is why doing a “shrink file” is so bad… it can totally reverse the order of pages (I call it “index inversion”).

    Now, if you’re only doing single row lookups, LOGICAL fragmentation has absolutely no effect on performance. Single row lookups are going to start at the Root Page and make its way through the Intermediate Pages (by looking at a single page per Intermediate Page Level) and finally read the single Leaf Level Page to return the sought after row. Such single row lookups do NOT depend on the logical order matching the physical order of the pages, period, and so time spent on defragging indexes that only suffer single row lookups is a total waste, so far as performance is concerned, even if the index is totally inverted.

    If, however, you need to read some large number of pages to return all the data you want, LOGICAL fragmentation plays a very important role. In order to return the data you want, SQL Server can’t actually return the data to you directly from the harddisk (even SSDs). It must first load the data into memory, just like any other standard file system. The catch in SQL Server is that it will use a thing called “Read Aheads” because reading a large amount of data in a single batch is much more performant and efficient than reading a large amount of data a page at a time. So SQL Server will “read ahead” but only to a certain point. It only reads ahead on physically contiguous pages and then it quits. The smaller the number of pages it can “read ahead”, the more times it has to do the “read ahead” process, and the less efficient the process of reading from disk into memory becomes. The worst case is that if only one page at a time can be read.

    This is what the “fragment_count” and “avg_fragment_size_in_pages” columns of sys.dm_db_index_physical stats is all about. The “fragment_count” tells you how many times the “next” page of an index wasn’t physically contiguous and the “avg_fragment_size_in_pages” tells you the average number of physically contiguous pages there are for the fragments that are formed. The closer that the “fragment_count” is to “1”, the better off your performance will be. When the “fragment_count” equals the actual page count of the index, the “avg_fragment_size_in_pages” will become “1” and that’s absolutely the worst thing for any query other than single row queries (where is doesn’t matter at all).

    I’ll also tell you that once the pages are in RAM, LOGICAL fragmentation has virtually NO effect on performance because RAM is really good at “Random Access” (even more quickly than the best SSDs).

    So, to summarize, the ONLY time that LOGICAL fragmentation actually matters is when you do a SELECT (for example but I mean anything) that queries for data that isn’t already in memory and must be read from spinning rust or SSDs… and, yes, it can and does have a major impact on performance. That impact is reduced by the speed of SSDs but, compared to already having the data in RAM, it’s still a significant impact.

    Period. 😉

    Page Density

    A lot of people call this “physical fragmentation” or “internal fragmentation”. Again, those are confusing terms, especially to SQL Server neophytes, and I really wish people would stop using the terms and keep it simple. We don’t need to have a vocabulary test every time we talk about fragmentation especially since logical fragmentation is also and actually a form of physical fragmentation and whole lot of people also get the definition of internal and external fragmentation exactly backwards.

    If you remember the “names” table example I gave above, both LOGICAL and what people refer to as PHYSICAL fragmentation (Page Density, from here on) occurred. The LOGICAL fragmentation occurred when a new non-physically contiguous page was created to make room for the new data on the originally targeted page. There was also the problem of Page Density. At the end of inserting just one addition row, a new page was create and roughly half the data was copied from the original targeted page to the new page (this is also known as a “Bad” page split or, as Paul Randal refers to them, “Nasty” page splits). That means that both pages are left only 50% full. If you do that often enough, most of the pages that are on disk for the given index will be only 50% full, meaning that you’re actually wasting half the disk (VERY expensive if you’re using SSDs compared to spinning rust).

    Worst yet, pages on disk are loaded into memory in exactly the same format. That also means that you’re wasting 50% of your memory even if you’re only selecting 1 row at a time.

    As a bit of a sidebar, you can think of this as the index having a “natural” Fill Factor of only “50” percent, which is way too low especially if you have a relatively small amount of memory (or disk but especially memory) available.

    The Page Density is what is contained in the “avg_page_space_used_in_percent” column of sys.dm_db_index_physical_stats. Very sadly, out of the thousands of articles and answers to index questions that I’ve seen, most people don’t even refer to Page Density never mind get into any depth about why it can be really bad, why it can be good, how to tell, and what to do about it.

    So, to summarize for your second question…

    1. There are two types of fragmentation but most people only refer to LOGICAL fragmentation.
    2. LOGICAL fragmentation is simply when the guaranteed logical order doesn’t precisely match the physical order of the pages as they’re stored in the MDF/NDF files.
    3. LOGICAL fragmentation is an issue ONLY when whatever you doing reads more than one page from disk to memory. Single row reads and reads from memory (no matter how many pages) are not affected by logical fragmentation at all, even on spinning rust.
    4. Page Density is a type of fragmentation where the pages are only partially full. Sometimes, it can be a good thing because it leaves room for additional inserts on the page to prevent “Bad” page splits. This is why it’s sometimes (strong emphasis on “sometimes”) good to apply a Fill Factor to an index during an index rebuild.

    More Sidebars

    As a bit of a sidebar, if you’re casually using REORGANIZE during index maintenance to do anything but compress LOBs that actually need to be compressed (not the same as row or page compression here) because of low Page Density, you’re making a terrible mistake that is costing you dearly in the form of wasted time and CPU, wasted logging, wasted disk and memory space (Page Density), serious blocking, and you don’t even know it.

    I’ll also state that everything I’ve spoken of above also applies to the non-Leaf Levels of a B-Tree but to a much lower extent (no pun intended).

    And, to Steve's point.... everything I spoke of IS, in fact, covered in the links provided (especially the YouTube link I provided for Paul Randal's) but I absolutely DO understand the initial confusion you may have (especially based on your first question above) and wanted to explain some of the nuances that I've observed based on my own initial confusion when I first started learning about indexes.

    --Jeff Moden

    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.

    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • August 31, 2019 at 7:59 pm

    #3676080

    Ah... almost forgot...

    The word "Data" is a bit misleading and can be used in many ways based on the esoteric subject.  It's a bit like using the word "flower", which can be a part of vegetables, fruits, weeds, and, well, flower plants.

    As you know, everything stored on disk and in memory is some form of "Data".  That's not what they usually mean when it comes to SQL Server.  Sticking with what we previously talked about and limiting it all to only Clustered (CI) and Non-Clustered Indexes (NCI)...

    1. A lot of people refer to the Leaf Level and sometimes the rest of the B-Tree of a CI as the "data of the table".  The Leaf Level of a CI contains the actual "data" in the table.  In fact, the pages on the Leaf Level within many of the tools built into SQL Server identify the Leaf Level of Clustered Indexes as "Data Pages".
    2. The B-Trees of NCIs are identical to those of the CI except that they also carry the key column(s) of the CI so you can do a quick lookup on a very narrow NCI and then have it do a "lookup" in the CI to get the rest of the data. (Note that whether or not/when the Key of the CI in NCIs actually also lives in the non-Leaf Level pages of the NCI is a whole 'nuther subject that we'll not go into here, The same goes with non-unique indexes where additional hidden columns may be added even to a CI.).Even though most of the "data" on the Leaf Levels of NCIs are actually copies of the data in the CI, the pages on the Leaf Level of NCIs are referred to as "Index Pages", especially within many of the tools built into SQL Server.
    3. There are lots of different types of "data" in indexes and, like the muscles in a human body, some work in a similar fashion as the others and some don't.  Some have related tendons and some don't.  Don't let yourself get frustrated when you hear terms like "In-Row Data", "Out-of-Row Data", "Overflow-Data/pages", etc, etc.  It's going to take some time to absorb it all and it's going to take you some time to learn it all and how it can be applied, etc, etc.  The same holds true with words like "sort" and "order".  Once you get more experience, you'll be able to tell what kind of sort or order or data people are talking about just by the context that they're used in.
    4. Realize that such learning is a never ending process.  No one knows everything about any given subject.

    • This reply was modified 4 years, 7 months ago by  Jeff Moden.

    --Jeff Moden

    RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
    First step towards the paradigm shift of writing Set Based code:
    ________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

    Change is inevitable... Change for the better is not.

    Helpful Links:
    How to post code problems
    How to Post Performance Problems
    Create a Tally Function (fnTally)

  • September 2, 2019 at 1:15 pm

    #3676336

    Great explanation Jeff (as always) 🙂

    Far away is close at hand in the images of elsewhere.
    Anon.

Viewing 9 posts - 1 through 8 (of 8 total)

You must be logged in to reply to this topic. Login to reply