5 ms·

Well... - On the 2nd year of education I knew that "index is something in database, which helps to locate data faster. Like an index at the end of a book, it h

Well... - On the 2nd year of education I knew that "index is something in database, which helps to locate data faster. Like an index at the end of a book, it helps to find the right page w/o whole scan of a book". - Later, probably at 4th or 5th year I got the idea how these are implemented using B+-trees. - And even later have seen some alternative implementations. But anyways, IMO even for a senior web developer it's enough to know that index is SOME fast data structure on disc, which trades duplication and (usually) slower writes for faster lookup. And optimizer sometimes will chose index scan, sometimes won't. And to know some basic optimization techniques (like throwing ORDER BY away when data is already sorted by index).

derekp7 9y ago
I would also like developers to understand that having additional columns in an index doesn't necessarily help -- if the first column is mostly unique (such as an employee ID number) then having an additional column (on the same index) of employee name doesn't get you much. You'd need a separate index that begins with employee name. (Edit: an exception is if the entire index fits in RAM, the DB can do an in-memory full index scan vs. a full table scan). On the other hand, if the first column isn't unique, such as employee's city or state, then the DB can use the next column as a "skip" index. So an index on "state, name" will still usually improve the query time of queries against "name" (but not as much improvement as if you had a separate index beginning with "name").
- btown 9y ago
  To that point, I think it's necessary for any engineer to understand at least how tree structures work, so that this type of reasoning is intuitive. There's a tree for the first column in the index, and at each of its leaves, there's a tree for the second column. So if you have a really complicated tree on the first column, subsequent columns won't work well, because you'd need to look at many many subtrees. But if you only have a few leaves on that first tree, then the system will just explore a subtree for each one, and you'll only have a few of those to run through. You don't need to know O notation or know what kind of trees they are (much less how they're implemented) to understand that. But if you only think of a database as an Excel table and not as trees sitting on top, you'll tend to make inefficient design decisions. And at the rate that data structures are moving into the frontend, arguably everyone in the stack should know how to think in this way.
  - bjourne 9y ago
    Wouldn't it be better to have one tree containing compound keys rather than subtrees? Often trees have a lot of overhead so a tree of trees could be rather inefficient. It would also be hard to balance.
    - btown 9y ago
      Effectively this is the same; at a sufficient diversity of the first element in the compound key, you'll have almost as many tree nodes as you would if you considered them subtrees. It can be intuitively easier to think of them as subtrees, though, and that was my point; it's not necessary to know all the implementation details, just generally how the system finds data.
- kthejoker2 9y ago
  You mean adding additional key columns to the index. Adding nonkey columns to the index puts them at the leaf node so the engine doesn't have to do a key lookup back to the main table to get all the additional columns from your query. More details on covering indexes here: https://www.simple-talk.com/sql/learn-sql-server/using-covering-indexes-to-improve-query-performance/ https://www.simple-talk.com/sql/learn-sql-server/using-cover...

derekp7 9y ago

I would also like developers to understand that having additional columns in an index doesn't necessarily help -- if the first column is mostly unique (such as an employee ID number) then having an additional column (on the same index) of employee name doesn't get you much. You'd need a separate index that begins with employee name. (Edit: an exception is if the entire index fits in RAM, the DB can do an in-memory full index scan vs. a full table scan). On the other hand, if the first column isn't unique, such as employee's city or state, then the DB can use the next column as a "skip" index. So an index on "state, name" will still usually improve the query time of queries against "name" (but not as much improvement as if you had a separate index beginning with "name").

btown 9y ago
To that point, I think it's necessary for any engineer to understand at least how tree structures work, so that this type of reasoning is intuitive. There's a tree for the first column in the index, and at each of its leaves, there's a tree for the second column. So if you have a really complicated tree on the first column, subsequent columns won't work well, because you'd need to look at many many subtrees. But if you only have a few leaves on that first tree, then the system will just explore a subtree for each one, and you'll only have a few of those to run through. You don't need to know O notation or know what kind of trees they are (much less how they're implemented) to understand that. But if you only think of a database as an Excel table and not as trees sitting on top, you'll tend to make inefficient design decisions. And at the rate that data structures are moving into the frontend, arguably everyone in the stack should know how to think in this way.
- bjourne 9y ago
  Wouldn't it be better to have one tree containing compound keys rather than subtrees? Often trees have a lot of overhead so a tree of trees could be rather inefficient. It would also be hard to balance.
  - btown 9y ago
    Effectively this is the same; at a sufficient diversity of the first element in the compound key, you'll have almost as many tree nodes as you would if you considered them subtrees. It can be intuitively easier to think of them as subtrees, though, and that was my point; it's not necessary to know all the implementation details, just generally how the system finds data.
kthejoker2 9y ago
You mean adding additional key columns to the index. Adding nonkey columns to the index puts them at the leaf node so the engine doesn't have to do a key lookup back to the main table to get all the additional columns from your query. More details on covering indexes here: https://www.simple-talk.com/sql/learn-sql-server/using-covering-indexes-to-improve-query-performance/ https://www.simple-talk.com/sql/learn-sql-server/using-cover...