Is bookmark in a nonclustered index ordered?

When a nonunique nonclustered index is built on top of a clustered
index, is it guaranteed that the bookmark in the nonclustered index
will be kept in the same order as the clustered index?

Here's an example to demonstrate my question:

CREATE TABLE indextest (col1 int NOT NULL,col2 int NOT NULL,col3
int,col4 int)
ALTER TABLE indextest ADD PRIMARY KEY CLUSTERED (col1,col2)
CREATE INDEX ix_indextest ON indextest (col1,col3)
GO
INSERT indextest VALUES (1,2,1,1)
INSERT indextest VALUES (1,3,2,1)
INSERT indextest VALUES (1,4,2,1)
INSERT indextest VALUES (2,1,1,1)
INSERT indextest VALUES (1,1,1,1)
SELECT col1,col2 FROM indextest WHERE col1=1 AND col3=1
DROP TABLE indextest

The select statement above is covered by the nonclustered index, so
that index is used. However, the nonclustered index is defined only to
ensure the ordering of col1 and col3 within the index; col1 and col2
follow within the index as the bookmark to the clustered index. When I
run this query, my desired result is to have the records appear in the
order supported by the clustered index:
1,1
1,2
As it happens, the result I got was indeed in that order, but I don't
know if it was mere coincidence, or if the bookmark in the nonclustered
index is maintained in the same order as the clustered index. If I
want to ensure the above order, is it sufficient to have the
nonclustered index defined as above, or do I need to define it as:
create index ix_indextest on indextest (col1,col3,col2)
just to be sure that the results are returned in ascending order for
col1,col2? If the two-column index is sufficient, is it guaranteed to
still be sufficient in SQL2005 and future versions of SQL Server, or am
I better off adding the third column just to be safe?

Thank you,
--Dennis CulleyAn index (clustered or non-clustered) shouldn't be relied upon to fix the
order in which rows are returned. There are no guarantees unless you use
ORDER BY in your query. Use ORDER BY and let the server decide which index
is most appropriate.

--
David Portas
SQL Server MVP
--|||Here's an example of why you cannot rely on the order of rows returned
unless you specifically use an ORDER BY. We have a concept of merry-go-round
scans. If two queries need to perform a range scan over an index, they can
share the same scan. Now, if query one starts before query two, we still
recognize that the scan we need for query two is already under way and we
piggy-back on it until it completes. However, because we hopped on it after
it had started, we need to go back to the start of the scan to read the rows
we missed. (e.g. query one scans and returns rows 1 to 100. Query two starts
when query one's scan is at row 46. Query two thus returns rows 46 to 100
plus 1 to 45)

Regards.

--
Paul Randal
Dev Lead, Microsoft SQL Server Storage Engine

This posting is provided "AS IS" with no warranties, and confers no rights.

"David Portas" <REMOVE_BEFORE_REPLYING_dportas@.acm.org> wrote in message
news:WvidncyWk-E2CZnfRVn-hg@.giganews.com...
> An index (clustered or non-clustered) shouldn't be relied upon to fix the
> order in which rows are returned. There are no guarantees unless you use
> ORDER BY in your query. Use ORDER BY and let the server decide which index
> is most appropriate.
> --
> David Portas
> SQL Server MVP
> --|||Okay, good point. So if I include ORDER BY col1,col2 in the query, the
query plan I get back does not show an additional sorting operation.
Does that imply that SQL Server has ensured that the bookmarks will be
maintained in this order, because they're ordered that way in the
clustered index?

--Dennis Culley|||DC (cactuswren1@.hotmail.com) writes:
> Okay, good point. So if I include ORDER BY col1,col2 in the query, the
> query plan I get back does not show an additional sorting operation.
> Does that imply that SQL Server has ensured that the bookmarks will be
> maintained in this order, because they're ordered that way in the
> clustered index?

Yup. If you run the query with and without ORDER BY and compare the
popups, you will see that the one with ORDER BY includes a ORDERED FORWARD,
while the one without ORDER BY does not.

--
Erland Sommarskog, SQL Server MVP, esquel@.sommarskog.se

Books Online for SQL Server SP3 at
http://www.microsoft.com/sql/techin.../2000/books.asp