RB Smissaert <[EMAIL PROTECTED]> wrote:
One thing I am not sure about yet is when an index would be helpful in the first place in relation to the data in the field. I understand an index is going to help little if the values in a particular field can only for example be 1 or 0, but roughly when does it become useful to add an index?
Suppose you have a table with N records. You run a query like "select * from t where f='x'; " which selects m records. Without an index on t(f), the query would run in O(N) time. With the index, it would be O(m log N) (it will scan m entries in the index, and for each entry would perform a logN lookup in the main table, by rowid).
Thus, when m is close to N (that is, the query selects almost all records), an index actually performs worse than a linear scan. The break-even point is somewhere on the order m==N/logN.
Igor Tandetnik
----------------------------------------------------------------------------- To unsubscribe, send email to [EMAIL PROTECTED] -----------------------------------------------------------------------------