MySQL Forums
Forum List  »  Optimizer & Parser

Re: ORDER BY + LIMIT
Posted by: Toa Sty
Date: November 13, 2006 04:40AM

Quote

That means, every row needs a pre-calculated "sort-id"?

Hi again Markus,

I've only really done this when the data allows me to do it 'naturally'. Fortunately I've not had to worry about adding an artificial 'sort_id'.

BTW there's some discussion on the general wider subject here which might be of interest: http://www.mysqlperformanceblog.com/2006/09/01/order-by-limit-performance-optimization/ (see the section "Beware of large LIMIT", but note that it's a different (and much worse) case when you can't use an index and have to filesort)



Anyway, the artificial sort_id isn't really very nice, but it could work in some limited cases. Actually to be honest it's pretty horrible in most cases, because if you need to insert/delete a row 'in the middle' of your table you have a nasty job of renumbering the sort_id for each row that comes after it. Rather you than me!

Imagine a table:
name	value	sort_id
a	10	1
b	20	2
d	40	3
e	50	4
f	60	5

If you need to insert (c,30) you need to update the sort_id for d, e and f. Urgh.

I think most people tend just to change their app to disallow such large limits. Typically these seem to occur when you have 'results 500000-500009' from a search or list of items on a website etc. - In this case you 'fix' it by allowing users to only search back (say) 1000 results.


It's a shame that there's not a way of saying 'jump to position 500000 in the index' but (not having thought about it too much) I don't know if there's a way to do that in a B-tree easily. (You'd have to traverse the tree and keep a counter I think?) I suppose if it were simple to do it'd be used by MySQL already. :)

Does your app allow you to do any sneaky workarounds to help a little? eg:

* Say you have a 600K row table, and you want rows 500000->500009 in order of 'created asc', then can you do something like
select * from mytable order by created DESC limit 99991,10 
and so search through 'only' 100K rows backwards in the index rather than 500K rows forwards? You'd have to re-sort them in your app or in a union/outer select - here's an example (which is hacky because I seem to need the union to force the query to run as expected in 5.0.20a):
  (select * from mytable order by created DESC limit 99991,10) union (select null limit 0) order by created ASC;

(You'd first need to do a count(*) query to get the number of rows so that you can calculate the limit, but count(*)s are fast if you're on MyISAM)


* If you're in the fairly typical scenario for this kind of query and are running a web app and supporting pages like 'results 500000-500009' then if you can remember the order column value (in your case: 'created') from the previous page you can then add 'where created>374564 limit 10' to your query instead of using a large limit. It'll be much faster.


It's a tricky one if you can't do any of these workarounds though.
Maybe someone else here has a smarter way of doing it? :)

HTH,
Toasty

-----------------------------------------
email: 'toasty'*3 at gmail

Options: ReplyQuote


Subject
Views
Written By
Posted
4677
November 12, 2006 04:45AM
3285
November 12, 2006 08:27AM
3100
November 12, 2006 12:09PM
Re: ORDER BY + LIMIT
30535
November 13, 2006 04:40AM
3630
January 30, 2007 12:06PM


Sorry, you can't reply to this topic. It has been closed.

Content reproduced on this site is the property of the respective copyright holders. It is not reviewed in advance by Oracle and does not necessarily represent the opinion of Oracle or any other party.