In a query such as:

SELECT id FROM foo WHERE status = 'NORMAL' ORDER BY id LIMIT k

(status is an enum, with an index)

Does MySQL select all the rows which meet the WHERE condition, sort them
all, then pick the top k? Or is it smart enough to optimize the
combined ORDER & LIMIT operations into a single partial sort which runs
in O(n log k), as opposed to O(n log n)?

On Oct 22, 1:31*pm, Roy Smith <r... (AT) panix (DOT) com> wrote:
If the index was status + id, then it could do it without needing to
sort at all.

Captain Paralytic:

How would MySql, using that index, know what the greatest or smallest
10 id's are without sorting them? Is an index always already sorted?

[I'm not saying it isn't...I just don't know and would like to
hear some more]


--
Erick

That is the whole purpose of an index. It speeds up searching
tremendously, as you can do a binary search.

(See http://www.topcoder.com/tc?module=St...2=binarySearch )

Best regards,
--
Willem Bogaerts

Application smith
Kratz B.V.
http://www.kratz.nl/

Erick T. Barkhuis wrote:

On 10/22/2010 11:55 AM, The Natural Philosopher wrote:
You don't have "sort of sorted" - it's either sorted or not sorted.
Indexes are ALWAYS sorted - that's their purpose.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex (AT) attglobal (DOT) net
==================

Willem Bogaerts:


Please allow me to ask a bit further. I'm still not quite sure how it
works. I thought that the purpose of indexes was to enable the database
software to directly find a record in the disk structure.

Suppose we have these records (never mind the symantics):

id date city
-------------------------
12 2009-08-12 London
14 2009-07-16 Athens
15 2010-01-10 Paris


Now, if I have an index on 'city', what do I actually have?
- just an array [0=>Athens, 1=>London, 2=>Paris] ?
- an array [Athens=>???, London=>???, Paris=>???] ?
- the full table ordered by 'city'?
- something else?

If it's the first mentioned structure, what good would that do to
direct searches as in:
SELECT date FROM mytable WHERE city="London"
?
Just the first array wouldn't speed up the search, so I suppose there's
more in the index than just the values in a proper order.



--
Erick

On 2010-10-22 18:53, Erick T. Barkhuis wrote:
[...]
Think of the index as a sorted tree where the leaf nodes point to a page
in the data. You will typically find the row that match your predicate
with log(n) i/o operations, and then fetch any columns not part of the
index. For a large table this will save a lot of time, for a small table
the optimizer would probably choose to ignore the index and scan the
table instead.

/Lennart

[...]

On 10/22/2010 2:10 PM, Lennart Jonsson wrote:
Erick, an index isn't an array at all (an array is a programming
concept, not a file concept). If anything, an index would be closer to
rows in a database or spreadsheet. And while the exact implementation
details may vary from one database manufacturer to another, the concept
is the same.

Each index entry is directly related to a single row of data. The entry
has two parts: the data in the columns used to create the index, and a
pointer to the row's physical location in the database.

Entries in the index are sorted by the indexed columns. This allows very
fast access to the a matching index entry via a binary sort. And once
the index entry is found, there is a direct pointer to the data.

Now, when a new row is added to the table, it can be places anywhere
there is space in the table. The database then builds an index entry
and adds it in the appropriate place. As this is almost never at the
end of the index, any entries following the location of the new index
entry may have to be read in and rewritten (it depends on the exact
implementation details - but some entries always need to be rewritten).
The same is true of an UPDATE which affects the index column(s) or a
DELETE. This is why you don't index everything - while retrieval may be
faster, other operations more time for each index you have.

So let's take an example - for simplicity, assume rows of a fixed size
of 50 bytes (variable row size makes no difference):

Offset id
0 114
50 23
100 free space
150 88
200 free space
250 42

An index on the id would have:

id offset
23 50
42 250
88 150
114 0

Now obviously there isn't a lot of advantage to an index on a table with
only 4 rows, but assume there were 4,000,000 rows.

To get to id 42 (because it happens to be the last) without an index, we
would have to read 6 rows (table scan). id 88 would require 4 rows, etc.

But doing a binary search on the index, we need a maximum of 3 reads to
get to any id, then we can directly access the data via the offset.

If we had 1M rows, we would have a maximum of 1M rows to read to get the
data we want, with an average of 500K rows. But with a binary search of
the index, we only need a maximum of 21 reads to get to the appropriate
index entry, then one read for the data itself.

Does this help?

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex (AT) attglobal (DOT) net
==================

In article <8idk6iFb6pU1 (AT) mid (DOT) individual.net>, "Erick T. Barkhuis" <erick.use-net (AT) ardane (DOT) c.o.m> wrote:

An index wouldn't be much use if it weren't sorted. Same concept exactly as
the index in a book.