Weee... check this out:

A full scan of a table containing ten million items requires up to ten 
million operations. (On average, half that.) Using binary chop, it takes 
only the binary logarithm of that - about 25 operations.

If a computer can process 1,000 operations per second (bearing in mind, 
comparing a record to the target being looked up is a far few machine 
instructions), we achieve the following times:

   Full scan:   2.777 hours
   Binary chop: 0.025 seconds

So one way takes almost three hours to do a single lookup, while the 
other can do 40 lookups per second. O(log N) FTW!

But wait, check this out. Perhaps you are somehow unimpressed with 
taking a 3-hour operation and completing it in 1/40th of a second. Well 
try this for size:

Assume there are 10^80 atoms in the observable universe. If you 
sequentially full scan then all, one by one, at 1,000 atoms per second, 
it'll take you 10^77 seconds.

This is longer than the universe has existed (10^11 seconds). 
Hypothetically, it's longer than it will take for all the energy in the 
universe to be exhausted. By the time 10^77 seconds is up, the universe 
will have died a cold, dark, silent death of total equilibrium a very 
long time ago.

In short, this procedure is so slow that there isn't enough time or 
energy in the whole of the known universe to actually complete it. (But 
then, who's going to pin a unique record to every atom in the universe 
anyway?)

On the other hand, according to my sums 10^80 is roughly 2^266. Thus, 
the binary chop algorithm requires only 266 operations, and can easily 
complete the entire process in well under a second. [If we assume 
completely random access to any atom in the universe, which completely 
defies several known physical laws...]

Like, wow man!

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> On the other hand, according to my sums 10^80 is roughly 2^266. Thus, 
> the binary chop algorithm requires only 266 operations, and can easily 
> complete the entire process in well under a second. [If we assume 
> completely random access to any atom in the universe, which completely 
> defies several known physical laws...]

  It would require for the atoms to be sorted in a specific order.
How would you sort them?

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> On the other hand, according to my sums 10^80 is roughly 2^266. Thus, 
>> the binary chop algorithm requires only 266 operations, and can easily 
>> complete the entire process in well under a second. [If we assume 
>> completely random access to any atom in the universe, which completely 
>> defies several known physical laws...]
> 
>   It would require for the atoms to be sorted in a specific order.
> How would you sort them?

Clearly by the value of the time component of the space-time event where 
the atom currently exists. ;-)

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

"Invisible" <voi### [at] devnull> wrote in message
news:48908346@news.povray.org...

> So one way takes almost three hours to do a single lookup, while the
> other can do 40 lookups per second. O(log N) FTW!

Which is why we really, really like indexes on database tables.

Post a reply to this message

>> So one way takes almost three hours to do a single lookup, while the
>> other can do 40 lookups per second. O(log N) FTW!
> 
> Which is why we really, really like indexes on database tables.

To quote Team America, "**** YEAH!"

Although - and not many people seem to understand this part - indexes 
make looking up *one* element much faster (if you index the right 
thing). However, if you're doing to end up needing to process a large 
percentage of the table anyway, it's actually faster to *not use* any 
indexes there might be.

This is why we have complex database engines with sophisticated 
algorithms which attempt to pick the best method for performing each 
query. Yet still it seems that certain people think that the task of 
"tuning" an SQL query means working out which combination of optimiser 
hints cause the database to always use indexes for that query. *sigh*

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

> This is longer than the universe has existed (10^11 seconds). 

Some of the guys mentioned here might have disagreed with you on that one:

http://en.wikipedia.org/wiki/12th_century_BC

Post a reply to this message

"Invisible" <voi### [at] devnull> wrote in message
news:48917361$1@news.povray.org...

> Although - and not many people seem to understand this part - indexes
> make looking up *one* element much faster (if you index the right
> thing). However, if you're doing to end up needing to process a large
> percentage of the table anyway, it's actually faster to *not use* any
> indexes there might be.

Really? I'll go and discard everything I know about using indexes right
away....

If you're processing a portion of a table and you have an index that covers
the required columns and finds you the portion of the table you want, it's
much, much better to use the index than to scan the table. Think about it
this way. If you need all the entries in the phone book where the first
letter of the surname in between N and T, would you prefer the phone book
ordered by surname or would you prefer an unorganised heap of phone book
entries?

Post a reply to this message

>> Although - and not many people seem to understand this part - indexes
>> make looking up *one* element much faster (if you index the right
>> thing). However, if you're doing to end up needing to process a large
>> percentage of the table anyway, it's actually faster to *not use* any
>> indexes there might be.
> 
> Really? I'll go and discard everything I know about using indexes right
> away....
> 
> If you're processing a portion of a table and you have an index that covers
> the required columns and finds you the portion of the table you want, it's
> much, much better to use the index than to scan the table. Think about it
> this way. If you need all the entries in the phone book where the first
> letter of the surname in between N and T, would you prefer the phone book
> ordered by surname or would you prefer an unorganised heap of phone book
> entries?

My point is that if you need to process 75% of the rows of the table, 
it's probably faster to do a sequential full scan than to use an index 
and do lots of random I/O. Obviously if you only need to process, say, 
5% of the table, you'd be mad to not use an index...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

"Gail Shaw" <initialsurname@sentech sa dot com> wrote in message
news:48919ec6@news.povray.org...
>
> "Invisible" <voi### [at] devnull> wrote in message
> news:48917361$1@news.povray.org...
>
> > Although - and not many people seem to understand this part - indexes
> > make looking up *one* element much faster (if you index the right
> > thing). However, if you're doing to end up needing to process a large
> > percentage of the table anyway, it's actually faster to *not use* any
> > indexes there might be.
>
> Really? I'll go and discard everything I know about using indexes right
> away....

Sorry, that cam out a little snarkier than I intended.

Taking SQL Server as an example (so I can give specific numbers), if an
index does not contain all the columns required, the break point for use the
index or scan the table is around 1% of the table. If the index does contain
all the columns, then the index will be used whether 1 row is required or
the entire table.

It's not hard to demonstrate.

Post a reply to this message

"Invisible" <voi### [at] devnull> wrote in message
news:4891a10d$1@news.povray.org...

> My point is that if you need to process 75% of the rows of the table,
> it's probably faster to do a sequential full scan than to use an index
> and do lots of random I/O. Obviously if you only need to process, say,
> 5% of the table, you'd be mad to not use an index...

I'm talking about range queries (all values between 1 and 100, all surnames
with first letters between N and Z). In that case you;'re not going to be
doing random IOs. One seek to find the start of the range (3 -5 random IOs),
then scan along the index leaf pages (sequential IOs). Provided all the data
required is included in the leaf pages, that is going to be faster than a
scan of the entire table.

Firstly because in general indexes are smaller than the entire table so
fewer IOs are required, second because the inapplicable 25% can be ignored
and doesn't have to be read and examined.

Of course, if you're looking for a random 75% of the table, then it's a
table scan.

Post a reply to this message

Gail Shaw wrote:

> Sorry, that cam out a little snarkier than I intended.
> 
> Taking SQL Server as an example (so I can give specific numbers), if an
> index does not contain all the columns required, the break point for use the
> index or scan the table is around 1% of the table. If the index does contain
> all the columns, then the index will be used whether 1 row is required or
> the entire table.
> 
> It's not hard to demonstrate.

Ah, right.

I was thinking of something like "you have a bunch of invoices, indexed 
by invoice number. You want to do something to all the invoices who's 
numbers are less than 999,999,999". In which case, after you've found 
the index nodes that tell you where those table rows are, you still need 
to seek to them and load them. If you're processing a high enough 
percentage of the rows in the table, just sequentially scanning the 
table is going to wind up faster because sequential I/O is faster, and 
reading only the table rather than table + index is less data to 
transfer too.

I hadn't considered the possibility of the entire table data being in 
the index itself. That would move the tipping point somewhat...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

"Invisible" <voi### [at] devnull> wrote in message
news:4891a551$1@news.povray.org...

> I hadn't considered the possibility of the entire table data being in
> the index itself. That would move the tipping point somewhat...
>

Not the entire table, just the columns required by the query in question.
Say the index table has 15 columns and the query that is looking for all
invoice numbers <  999,999,999 needs to return the date, the address and the
customer name, then an index on InvoiceNumber, Date, Address, CustName is
called a covering index, as it covers this particular query.

If an index is not covering, then, as I mentioned before, the tipping point
isn't most of the table (at least for SQL Server), it's somewhere around 1%

Post a reply to this message

>> I hadn't considered the possibility of the entire table data being in
>> the index itself. That would move the tipping point somewhat...
> 
> Not the entire table, just the columns required by the query in question.

Right, that's the other point I overlooked - you might not actually want 
every single column in the table for a given query.

So, now that we've got all that out of the way, I'm sure you'll agree 
with me that there are times when you do *not* want to use an index, 
even if there is one. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

"Invisible" <voi### [at] devnull> wrote in message
news:4891aca4@news.povray.org...
>
> So, now that we've got all that out of the way, I'm sure you'll agree
> with me that there are times when you do *not* want to use an index,
> even if there is one. ;-)

<g> No.

Dunno about Oracle, but in SQL Server it's possible (and recommended) to
make the table into an index that contains, at the leaf levels, all of the
data in the table. It's called the clustered index.

I will agree that there are times when you want to scan an index, rather
than doing a seek on it.

Post a reply to this message

>> So, now that we've got all that out of the way, I'm sure you'll agree
>> with me that there are times when you do *not* want to use an index,
>> even if there is one. ;-)
> 
> <g> No.
> 
> Dunno about Oracle, but in SQL Server it's possible (and recommended) to
> make the table into an index that contains, at the leaf levels, all of the
> data in the table. It's called the clustered index.

Oracle provides an "index-organised table" which sounds like it's 
similar. I don't know about "recommended" though - it seems to be more 
for special situations.

I still think if you have a huge table with an index in just one field, 
full-scanning the table would be faster than an index scan if you're 
processing a very large percentage of the table's rows. But apparently 
that's just me. :-}

BTW, what does "<g>" mean? I always thought it was short for "Gail" or 
something, but that doesn't make much sense...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

"Invisible" <voi### [at] devnull> wrote in message
news:4891b12a$1@news.povray.org...
> I still think if you have a huge table with an index in just one field,
> full-scanning the table would be faster than an index scan if you're
> processing a very large percentage of the table's rows. But apparently
> that's just me. :-}

Ah, but read again. The clustered inde (or index-organised table) is an
index that has ALL of the data at the leaf level of the index. In essence,
it is the table.
So, if the index is the table, and you scan all the leaf pages of the index
.......

> BTW, what does "<g>" mean? I always thought it was short for "Gail" or
> something, but that doesn't make much sense...

Short hand for <grin>

Post a reply to this message

Gail Shaw wrote:
> It's called the clustered index.

That's funky. Every time I ask an expert what a "clustered index" is, I 
get a different definition. And I don't think they're compatible but 
differing descriptions of the same concept.

I'd been told a clustered index is one in which the rows in the table 
date are in physically the same order as the rows in the index. And that 
that's why you can only have one clustered index for a table.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

"Darren New" <dne### [at] sanrrcom> wrote in message
news:4891d67e$1@news.povray.org...
> Gail Shaw wrote:
> > It's called the clustered index.
>
> I'd been told a clustered index is one in which the rows in the table
> date are in physically the same order as the rows in the index. And that
> that's why you can only have one clustered index for a table.

Mostly correct.

The clustered index is the table. The leaf levels of the cluster are the
actual data pages and they are stored physically in the order of the
clustering key. The index's b-tree is built above those pages.
A scan of the clustered index is a scan of the data pages of the table.

With a clustered index, the clustering key is the row's 'address' and is
used in all other indexes to indicate the row's location if a lookup is
necessary (to retrieve additional columns)

There's a fairly decent diagram here - :
http://msdn.microsoft.com/en-us/library/ms177443.aspx

Does thet help at all, or have I just muddied the water more?

Bear in mind, I'm talking specifically for MS SQL Server. If other database
products have something with the same name, the physical implementation may
be different

Post a reply to this message

Gail Shaw wrote:
> The clustered index is the table. The leaf levels of the cluster are the
> actual data pages and they are stored physically in the order of the
> clustering key.

Oh, OK. I guess that makes sense, once I realize that there *is* no 
"table data" outside the index.

> There's a fairly decent diagram here - :
> http://msdn.microsoft.com/en-us/library/ms177443.aspx

That's a fairly good picture of a B-tree. :-)

> Does thet help at all, or have I just muddied the water more?

It helps. I guess I just wasn't thinking it through. Thanks for 
clarifying that.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

"Darren New" <dne### [at] sanrrcom> wrote in message
news:4891e365$1@news.povray.org...
>
> > There's a fairly decent diagram here - :
> > http://msdn.microsoft.com/en-us/library/ms177443.aspx
>
> That's a fairly good picture of a B-tree. :-)

Yup. Look at that and the one for the nonclustered indexes (link's at the
bottom of the page) and compare what's at the leaf level

> > Does thet help at all, or have I just muddied the water more?
>
> It helps. I guess I just wasn't thinking it through. Thanks for
> clarifying that.

Pleasure. There are a lot  of full time SQL Server people who have little to
no clue what a clustered index is.

Post a reply to this message