Page 1 of 1

Field range with order by, filesort problem

Posted: Tue Aug 12, 2008 2:02 pm
by Geteburg
Hey!

Got a bit of a problem that i cannot solve.

I've got a table, and i need to get some results from it. The problem is of course filesort.
I know why filesort is in use but cannot get rid of it.

Important fields:
- active
- points
- date_added

Index's are set..

Code: Select all

SELECT ... WHERE active = '1' AND points <= '2' ORDER BY date_added DESC

Code: Select all

CREATE TABLE IF NOT EXISTS `entries` (
  `id` int(11) NOT NULL auto_increment,
  `user_id` int(11) NOT NULL default '0',
  `date_added` datetime NOT NULL default '0000-00-00 00:00:00',
  `source_url` varchar(200) collate utf8_unicode_ci NOT NULL,
  `views` int(11) NOT NULL default '0',
  `text` text collate utf8_unicode_ci NOT NULL,
  `active` tinyint(1) NOT NULL default '0',
  `points` int(11) NOT NULL default '0',
  `approved_by` int(11) NOT NULL,
  `approve_date` datetime NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `user_id` (`user_id`),
  KEY `points` (`points`),
  KEY `ind_active_points_date` (`active`,`points`,`date_added`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci AUTO_INCREMENT=2065 ;

Code: Select all

mysql> explain SELECT * FROM entries FORCE INDEX (ind_active_points_date) WHERE active = 1 AND points <= 2 ORDER BY date_added DESC;
+----+-------------+------------+-------+------------------------+------------------------+---------+------+------+-----------------------------+
| id | select_type | table      | type  | possible_keys          | key                    | key_len | ref  | rows | Extra                       |
+----+-------------+------------+-------+------------------------+------------------------+---------+------+------+-----------------------------+
|  1 | SIMPLE      | entries    | range | ind_active_points_date | ind_active_points_date | 4       | NULL |    1 | Using where; Using filesort |
+----+-------------+------------+-------+------------------------+------------------------+---------+------+------+-----------------------------+
1 row in set (0.01 sec)
Of course the problem is that i want results that have 2 or less in points field, and use ORDER BY on different field.

I'm stuck here.. I even tried with ALTER table to first change the order of the table, and then use the above query without ORDER BY. Since right now table is at 2000 rows only, ALTER table worked quite fast. I'm not too sure about it when it comes to 2M+ rows.

I know why the problem is there, but since i'm not too advance with sql i can't solve it really.

Any suggestions how to solve this?

Re: Field range with order by, filesort problem

Posted: Tue Aug 12, 2008 2:26 pm
by ghurtado
I made a table from your DDL and did some experiments without much success. I think you have the right idea: the problem could be related to the column you are using "order by" on, but I dont really know why you cant use the index on the date column. I even tried changing it to a timestamp column, and removed all your indexes, to no avail. You probably already know this, but mySQL is defaulting to filesort because it can't find an adequate index to use.

As an aside, this post is a wonderful example of the perfect way to ask a question: you simplified the problem, stated the expected and actual results, and gave us a very easy way to reproduce a pretty complex problem. If you hadn't done that, chances are I wouldn't have taken the trouble to look into it.

I wish there was a way to highlight your thread as a model of "how to ask for help" :)

Re: Field range with order by, filesort problem

Posted: Tue Aug 12, 2008 2:47 pm
by Geteburg
Hey!

Yeah, i know exactly where the problem is! Like you said the problem lies in ORDER BY with a range field..
You probably already know this, but mySQL is defaulting to filesort because it can't find an adequate index to use.
Yeah, and the reason for mysql not using index is in this range/order part:

Code: Select all

SELECT ... points <= 2 ORDER BY date_added DESC
This part is the reason for filesort. You cannot do range on 1 field and ORDER BY on a different field.

For example, a query without range will work just fine:

Code: Select all

SELECT ... points = 2 ORDER BY date_added DESC
Query that has "points" field in ORDER BY will also work without filesort:

Code: Select all

SELECT ... points <= 2 ORDER BY points DESC, date_added DESC
But of course in both solutions that work, the results are not what i want :)

Actually, i'm not asking how to fix this query itself cause i'm thinking its impossible.

The question should be: How to get results back in the order that i want them with the smallest number of queries. Cause i don't think this will be possible with one query. Something along those lines :D

Basically the results should be:
- records that have points <= 2
- ordered by date DESC

I have no idea why, but i simply cannot figure it out..

So any ideas, whatever, i'm open to them..

Re: Field range with order by, filesort problem

Posted: Tue Aug 12, 2008 6:21 pm
by ghurtado
Yeah, I dunno, I tried it from home too and I wasn't able to get it to use an index either.

I think using more than one query the biggest problem you are gonna face is the fact that the ordering of records matters if you are using LIMIT, which, with 2M+ rows, you probably would be.

Re: Field range with order by, filesort problem

Posted: Wed Aug 13, 2008 11:10 am
by Geteburg
I made a nice mess for myself :D
There's got to be a solution for this!

Of course i'm using LIMIT.

The only solution i came up so far was this:

1. Get 100 records ordered by date
2. Put this 100 records to TEMP table
3. Pull out records from TEMP table that have points <= 2
4. IF i do not get 10 records with points <= 2 from those 100, repeat from step 1 until i hit the required 10 records. The records that were found would be added each to time array so that when 10 records are found, we go to next step.
5. Loop over array, and do query each time (10 queries required)

Code: Select all

SELECT ... WHERE id = N ...
The only order that is important is for field "date_added".
I don't care if records are mixed when it comes to "points" field as long as they are within the required range.

Way too much queries!
If only i could put TEXT data to temp table then the last point could be ignored, but since i would use memory type i can't.

:banghead:

Re: Field range with order by, filesort problem

Posted: Wed Aug 13, 2008 11:26 am
by onion2k

Code: Select all

ALTER TABLE `entries` DROP INDEX `ind_active_points_date`;
ALTER TABLE `entries` ADD INDEX `ind_date_points_active` ( `date_added` , `points` , `active` );
 
EXPLAIN SELECT * FROM entries FORCE INDEX (ind_date_points_active) WHERE active = 1 AND points <= 2 ORDER BY date_added DESC;
Results in

Code: Select all

id  select_type     table   type    possible_keys   key     key_len     ref     rows    Extra
1   SIMPLE  entries     index   NULL    ind_date_points_active  13  NULL    11  Using where

Re: Field range with order by, filesort problem

Posted: Wed Aug 13, 2008 11:37 am
by ghurtado
Nice!

Does that mean that the order of the columns matters when you are defining a multi-column index in your table?

Re: Field range with order by, filesort problem

Posted: Wed Aug 13, 2008 1:42 pm
by onion2k
Yes, sort of. Essentially the index is sorted by whichever column is first. The order of any subsequent columns doesn't matter. In this case because you're ordering by the same order that the index is stored in MySQL doesn't need to use filesort.

To quote the manual ( http://dev.mysql.com/doc/refman/5.0/en/ ... dexes.html ):
To sort or group a table if the sorting or grouping is done on a leftmost prefix of a usable key (for example, ORDER BY key_part1, key_part2). If all key parts are followed by DESC, the key is read in reverse order.
(I think that's how it works. I'm not really an expert in these things.)

Re: Field range with order by, filesort problem

Posted: Wed Aug 13, 2008 3:43 pm
by Geteburg
Holly crap!
That works even better then a naked chick on a bike! :lol:

Did not know that about indexes! Thanks for the info!
Each day we learn something new.. :)

Re: Field range with order by, filesort problem

Posted: Wed Aug 13, 2008 8:17 pm
by ghurtado
onion2k wrote:...I'm not really an expert in these things.

Certainly enough of an expert to have taught us all something today :)