Selectivity Factor - Block Selectivity

Hello everyone.

I was just reading through an article on Indexes, and as I was reading it I realized that I had a mistake in my earlier post where I had claimed that Row selectivity is an important factor to consider while deciding on Indexes. As you know , Indexes are only helpful if they help in reducing the number of IO(physical or logical). Lets consider the case of Oracle. In Oracle, data in a table is stored in blocks. Lets assume a case where each block hold only 100 rows of a table. If there 1000 rows in a table, then assume that these are stored in 10 different blocks. In this case, even if a filter has a low selectivity (say 10%), having an index will result in 10 IOs per block(for 10 rows in each ). If Oracle had decided to do a Full Table scan, then it would have resulted in just 10 IOs as a whole. My point here is, instead of taking Row selectivity as a decision making parameter, Indexing decisions have to be based on something known as Block selectivity. A simple definition of Block selectivity is :

Block selectivity = P/Ptotal
where P = Number of blocks which have atleast 1 row which qualifies the filter condition.
Ptotal = Total number of blocks below the high water mark of the table.

The lesser the block selectivity for a field, the better the performance will be if the field is indexed. One way to ensure a good block selectivity is to physically cluster the data along this field. A good clustering factor will ensure that the rows with same value for this field are physically close and in a lesser number of blocks. On the other hand , if these rows were spread across almost the entire set of blocks, then an Index may prove as an overhead as each block would have to be visited only once. In fact a full table scan would ensure that each block is read once and only once. So people, next time you are planning to index a field make sure to physically cluster the data in the table and find out the block selectivity for this field. For more information refer this link:

http://www.hotsos.com/e-library/abstract.php?id=5

P.S: You will have to register to read this article. Registration is very simple and will take only 1 min of your time.