Indexing a database

Question

I am not so familiar with databases and now I am trying to understand the indexing mechanism.

From what I know, in a RDBMS, indexing on a column makes searching by that column faster. This is also true for the triple stores, only there indices assume you will search(for example) mostly by the subject, then by object and so on.

I am not sure about RDBMS, but on triple stores you can define more than one index, letting the store choose the best index for each query(hopefully I understood this right). Naturally, the following question appears:

Why shouldn't I add all the possible indexes to a triple store, and extending to a RDBMS, why not make indexes on each column(assuming I am not too lazy)?

Answer 1

Because, essentially, an index is an extra table, where the primary key is the field you're indexing and the only content is the primary key of your main table. So every update has to be replicated in every index that uses the field you update.

This is particularly noticable on Inserts. Imagine if every insert you did to a table had to be replicated on 20 other tables. It's going to be painfully slow.

Note that this gets even worse with compound, clustered and full-text indexes, but I don't want to complicate the issue for you yet.

Answer 2

The indexes are basically additional data structures which have to be built and stored. Building inde wastes CPU power (during writing operations) and storing it wastes disk capacity.

Why would you want to build and store indexes which you never use?

Answer 3

Only place indexes when needed. As a rule of thumb when I am developing a database schema, every table gets a PK Primary Key Clustered Index to start with. This will be the unique identifier for data in that table. In can be on 1 column or many.

After that, I usually just add Non-Clustered Unique Indexes on column(s) which I want to enforce uniqueness on.

This is the base schema. As the application gets developed and matures, we add indexes as needed based on performance concerns and how we are querying the data.

Every index added increases spaced used as well as adding additionally maintenance. So choose your indexes wisely.

Answer 4

The strength of Indexes is that they are 1) a data structure that can be quickly searched through and 2) more compact than the actual tables, allowing more of the index to fit into memory instead of being paged to disk.

If you have an index on every column, then the indexes themselves will take more space than the table they represent. If the database really does use all of the indexes, it will require more time just to swap them in and out of memory. In addition, every index has to be updated on an inert, update, or delete.

Beyond that, indexes on a single column are not even the best you can do. Most relation databases actually allow an index on multiple columns, and the order of these columns matter. For example, if I want to search a database for all people who went to Duke from classes between 1980 and 1984, then what I want is an index on (School, ClassYear). The query would not be able to use an index with the same columns, but reversed.

So to create every possible index, there are at least n! ways to arrange columns in an index. With only 5 columns, there are 120 possible indexes.

Since there are so many possible indexes, you really do have to determine what indexes are useful for your application and create only those.

Answer 5

Creating an index for every column in a table is usually a waste of space, and as others have mentioned, it can slow down insert/update operations. An index is used to speed up queries. I'd only recommend adding an index to a column if you notice poor performance when querying for values in that column.

Some databases may require an index for a table's primary key so you might not have a choice about that one. Also, if you have a very large text columns, there are specific technologies that are designed for full-text search and index, but they are not always the same kinds of index you'd use for a small numeric column.

Answer 6

To understand the answers to your questions, I think it'd be helpful to first talk a bit more about what an index is.

The classic analogy is to compare a database index to an index in a book. Y'know, like this:

Imagine that you have a cook book, and for whatever reason, recipes in the book are ordered randomly. Suppose you want to look for an Italian desert recipe. What do you do? Well, unfortunately, you're forced to scan through the book, from front cover to back cover until you find it.

Now imagine that we have an index like the one in the image above where recipes are organized alphabetically. So "chicken parmigiana" would be listed under "C". Hm, actually, that isn't helpful. You know you want an Italian desert recipe, but you don't know what letter it'd start with.

Now imagine that you have an index that is organized by cuisine. Italian, French, Indian, Chinese, Thai, etc. With this, we can go to the Italian section and look there. Woo hoo!

Another thing that'd be helpful is if we had an index organized by meal type. Breakfast, lunch, dinner, desert, appetizer, etc.

Let's relate this to software. Imagine that we have an analogous situation where you have a list of recipes and you want to find an Italian desert.

var recipes = [{
  cuisine: "french",
  mealType: "dinner",
  name: "coq au vin"
}, {
  cuisine: "thai",
  mealType: "lunch",
  name: "pad thai",
}, {
  cuisine: "italian",
  mealType: "dinner"
  name: "chicken parmigiana",
}, 
...
{
  cuisine: "italian",
  mealType: "desert",
  name: "tiramisu",
}, {
}];

Just like with the cook book, you'd have to traverse through the list to find your Italian desert. But now imagine that we have the following data structure:

var alphabeticalIndex = {
  c: [ coqAuVinPointer, chickenParmigianaPointer ],
  p: [ padThaiPointer ],
  t: [ tiramisuPointer ],
};

That doesn't help much does it. We don't know what letter to look under. How about this?

var cuisineIndex = {
  french: [ coqAuVinPointer ],
  thai: [ padThaiPointer ],
  italian: [ chickenParmigianaPointer, tiramisuPointer ],
};

Nice! That's helpful! And this is helpful too:

var mealTypeIndex = {
  lunch: [ padThaiPointer ],
  dinner: [ coqAuVinPointer, chickenParmigianaPointer ],
  desert: [ tiramisuPointer ],
};

Hopefully this illustrates why database index's help you find stuff more quickly. Perhaps it also illustrates the downside of indexes: they use up extra memory. Imagine if we had indexes for everything: expensivenessIndex, easeOfCookingIndex, popularityIndex. Actually, those seem pretty useful. If you're planning on doing a lot of lookups using the index, it's probably worth having even though it uses up extra memory. But what about something like dateOfRecipeOriginIndex? Are you ever looking up recipes that were created in the 1950s vs recipes that were created in the 1830s? Probably not. In that case, the cost of using additional memory outweighs the benefit of faster lookup speed. Similarly, in the real world, if you have a user with a mothersMaidenName property, you probably wouldn't want to create an index for mothersMaidenName since you'd never be looking up users by their mothers maiden name. On the other hand, you might want to index something like firstName.