Field range with order by, filesort problem

Questions about the MySQL, PostgreSQL, and most other databases, as well as using it with PHP can be asked here.

Moderator: General Moderators

Post Reply
Geteburg
Forum Commoner
Posts: 25
Joined: Tue Aug 12, 2008 1:57 pm

Field range with order by, filesort problem

Post 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?
User avatar
ghurtado
Forum Contributor
Posts: 334
Joined: Wed Jul 23, 2008 12:19 pm

Re: Field range with order by, filesort problem

Post 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" :)
Geteburg
Forum Commoner
Posts: 25
Joined: Tue Aug 12, 2008 1:57 pm

Re: Field range with order by, filesort problem

Post 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..
User avatar
ghurtado
Forum Contributor
Posts: 334
Joined: Wed Jul 23, 2008 12:19 pm

Re: Field range with order by, filesort problem

Post 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.
Geteburg
Forum Commoner
Posts: 25
Joined: Tue Aug 12, 2008 1:57 pm

Re: Field range with order by, filesort problem

Post 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:
User avatar
onion2k
Jedi Mod
Posts: 5263
Joined: Tue Dec 21, 2004 5:03 pm
Location: usrlab.com

Re: Field range with order by, filesort problem

Post 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
User avatar
ghurtado
Forum Contributor
Posts: 334
Joined: Wed Jul 23, 2008 12:19 pm

Re: Field range with order by, filesort problem

Post by ghurtado »

Nice!

Does that mean that the order of the columns matters when you are defining a multi-column index in your table?
User avatar
onion2k
Jedi Mod
Posts: 5263
Joined: Tue Dec 21, 2004 5:03 pm
Location: usrlab.com

Re: Field range with order by, filesort problem

Post 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.)
Geteburg
Forum Commoner
Posts: 25
Joined: Tue Aug 12, 2008 1:57 pm

Re: Field range with order by, filesort problem

Post 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.. :)
User avatar
ghurtado
Forum Contributor
Posts: 334
Joined: Wed Jul 23, 2008 12:19 pm

Re: Field range with order by, filesort problem

Post 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 :)
Post Reply