Thanks; I have seen this O(N) etc. explanations a lot, but not sure
what they exactly mean.
Does it in this case simply mean O * N and O * (m log N) ?
> and for each entry would perform a logN
Does the logN here mean m log N or something else?
> m==N/logN
Ditto, does this mean break even point roughly when m equals N / (m log N) ?
Sorry, these might be basic questions, but would like to get this clear.
RBS
-Original Message-
From: Igor Tandetnik [mailto:[EMAIL PROTECTED]
Sent: 04 August 2007 20:01
To: SQLite
Subject: [sqlite] Re: Re: Re: Re: How does SQLite choose the index?
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]
-
-
To unsubscribe, send email to [EMAIL PROTECTED]
-
