MySQL - How to index this query?

Question

I have trouble with indexing this query :

SELECT  *,
        (ROUND(SQRT(
           POW(LEAST(ABS(-12 - wdata.x),
           ABS(401 - ABS(-12 - wdata.x))), 2) +
            POW(LEAST(ABS(45 - wdata.y),
            ABS(401 - ABS(45 - wdata.y))), 2)),3)
         ) AS distance
    FROM  odata
    LEFT JOIN  wdata ON wdata.id=odata.vref
    WHERE  TRUE
    HAVING  distance<4.9497474683058326708059105347339
    ORDER BY  distance
    LIMIT  30

and the result is :

+----+-------------+-------+--------+---------------+---------+---------+-----------------------------+-------+---------------------------------+
| id | select_type | table | type   | possible_keys | key     | key_len | ref                         | rows  | Extra                           |
+----+-------------+-------+--------+---------------+---------+---------+-----------------------------+-------+---------------------------------+
|  1 | SIMPLE      | odata | ALL    | NULL          | NULL    | NULL    | NULL                        | 19118 | Using temporary; Using filesort |
|  1 | SIMPLE      | wdata | eq_ref | PRIMARY       | PRIMARY | 4       | mytravia_1000-14.odata.vref |     1 | NULL                            |
+----+-------------+-------+--------+---------------+---------+---------+-----------------------------+-------+---------------------------------+
2 rows in set (0.00 sec)

i know it shows 0.00 sec is execution time but this query will run many many times and it shows its will slow my database i dont know why !

every time i see row examined is 459448 for this query so its quite bad for my work in some reasons .

can anyone give a suggestion ? how can i make a proper index for odata table? or can i use sub querys to fix it ?

the tables are :

explain odata:

vref    int(10) unsigned    NO  PRI     NULL    
type    tinyint(4)  NO      NULL    
conqured    mediumint(8) unsigned   NO      NULL    
wood    float(12,2) NO      NULL    
iron    float(12,2) NO      NULL    
clay    float(12,2) NO      NULL    
woodp   float(12,2) NO      NULL    
ironp   float(12,2) NO      NULL    
clayp   float(12,2) NO      NULL    
maxstore    mediumint(8) unsigned   NO      NULL    
crop    float(12,2) NO      NULL    
cropp   float(12,2) NO      NULL    
maxcrop     mediumint(8) unsigned   NO      NULL    
lasttrain   int(10) unsigned    NO      NULL    
lastfarmed  int(10) unsigned    NO      NULL    
lastupdated     int(10) unsigned    NO      NULL    
loyalty     tinyint(4)  NO      100 
owner   smallint(5) unsigned    NO      2   
name    char(45)    NO      Oasis   

and explain wdata:

id  int(10) unsigned    NO  PRI     NULL    auto_increment
fieldtype   tinyint(3)  NO      NULL    
oasistype   tinyint(3)  NO      NULL    
x   smallint(5) NO  MUL     NULL    
y   smallint(5) NO  MUL     NULL    
occupied    tinyint(4)  NO      NULL    
image   char(12)    NO  MUL     NULL    
pos     tinyint(3)  NO  MUL     NULL    

i have to say wdata.id and odata.vref is indexed already !

tables structure ->

CREATE TABLE IF NOT EXISTS `odata` (
  `vref` int(10) unsigned NOT NULL,
  `type` tinyint(4) NOT NULL,
  `conqured` mediumint(8) unsigned NOT NULL,
  `wood` float(12,2) NOT NULL,
  `iron` float(12,2) NOT NULL,
  `clay` float(12,2) NOT NULL,
  `woodp` float(12,2) NOT NULL,
  `ironp` float(12,2) NOT NULL,
  `clayp` float(12,2) NOT NULL,
  `maxstore` mediumint(8) unsigned NOT NULL,
  `crop` float(12,2) NOT NULL,
  `cropp` float(12,2) NOT NULL,
  `maxcrop` mediumint(8) unsigned NOT NULL,
  `lasttrain` int(10) unsigned NOT NULL,
  `lastfarmed` int(10) unsigned NOT NULL,
  `lastupdated` int(10) unsigned NOT NULL,
  `loyalty` tinyint(4) NOT NULL DEFAULT '100',
  `owner` smallint(5) unsigned NOT NULL DEFAULT '2',
  `name` char(45) NOT NULL DEFAULT 'Unoccupied Oasis',
  PRIMARY KEY (`vref`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

And for wdata is ->

CREATE TABLE IF NOT EXISTS `wdata` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `fieldtype` tinyint(3) NOT NULL,
  `oasistype` tinyint(3) NOT NULL,
  `x` smallint(5) NOT NULL,
  `y` smallint(5) NOT NULL,
  `occupied` tinyint(4) NOT NULL,
  `image` char(12) NOT NULL,
  `pos` tinyint(3) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `x` (`x`),
  KEY `y` (`y`),
  KEY `image` (`image`),
  KEY `pos` (`pos`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=160802 ;

best regards.

Answer 1

There is no index what will speed up that query as it stands. It currently must evaluate that SQRT for every row in the result of JOINing the two tables.

You will get some improvement by finding the closes 30 before doing any JOINing:

SELECT  *, distance
  FROM  ( SELECT id,
    (ROUND(SQRT(
       POW(LEAST(ABS(-12 - wdata.x),
       ABS(401 - ABS(-12 - wdata.x))), 2) +
        POW(LEAST(ABS(45 - wdata.y),
        ABS(401 - ABS(45 - wdata.y))), 2)),3)
     ) AS distance
    FROM  wdata
    HAVING  distance<4.9497474683058326708059105347339
    ORDER BY  distance
    LIMIT 30
      ) w
  JOIN odata ON w.id=odata.vref
  ORDER BY  w.distance

That will need id and vref indexed.

The next improvement is to bound the search in at least one direction:

AND x >= -12 - 4.94...
AND x <= -12 + 4.94...

and have the composite index INDEX(x, id) in wdata. (Sorry, I don't know where "401" fits into the formula.)

If that is not fast enough, the solution gets more complicated.

Answer 2

Like Rick James says, you cannot index distance because it is being dynamically calculated.

this gives you two problems: 1, it is slow, as you know. And 2, you're doing logical calculations at the data tier, which I just am not fond of.

I think the best solution here is to not calculate the distance on-the-fly as you're doing. Why not just store the distance in wdata at the same time that you insert/update x and/or y? Put it in a column named distance. Then you can index that column and everything will be very fast. Also, you wont be redoing the calculation over-and-over again, making things more efficient. And lastly, you'll be able to remove the calculation for the data tier and put into a more appropriate place at the application level.

CREATE TABLE IF NOT EXISTS `wdata` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `fieldtype` tinyint(3) NOT NULL,
  `oasistype` tinyint(3) NOT NULL,
  `x` smallint(5) NOT NULL,
  `y` smallint(5) NOT NULL,
  `distance` decimal(32, 24) NOT NULL,
  `occupied` tinyint(4) NOT NULL,
  `image` char(12) NOT NULL,
  `pos` tinyint(3) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `x` (`x`),
  KEY `y` (`y`),
  KEY `distance` (`distance`),
  KEY `image` (`image`),
  KEY `pos` (`pos`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 AUTO_INCREMENT=160802;

(The data type for distance can be whatever you think is appropriate. I used decimal(32, 24) which will store numbers with up to 24 places to the right of the decimal and up to 12 to the left. Adjust as needed.)

Then you would change your inserts to be something like this:

(sample data:

• fieldtype=1
• oasistype=1
• x=10
• y=11
• occupied=1
• image='abcdefghijkl'
• pos=1

)

insert into wdata (fieldtype,oasistype,x,y,distance,occupied, image, pos)
values (1, 1, 10, 11, (ROUND(SQRT(
           POW(LEAST(ABS(-12 - 10),
           ABS(401 - ABS(-12 - 10))), 2) +
            POW(LEAST(ABS(45 - 11),
            ABS(401 - ABS(45 - 11))), 2)),3)
         ), 1, 'abcdefghijkl', 1)

and your select statement would be:

SELECT  * FROM  odata
    LEFT JOIN  wdata ON wdata.id=odata.vref
    where wdata.distance<4.9497474683058326708059105347339
    ORDER BY  wdata.distance
    LIMIT  30

If you already have a bunch of data in the wdata table and you cannot insert it freshly, you can do this to update all the rows at one time (after you add the new column for distance):

update wdata set distance = 
   (ROUND(SQRT(
    POW(LEAST(ABS(-12 - x),
    ABS(401 - ABS(-12 - x))), 2) +
    POW(LEAST(ABS(45 - y),
    ABS(401 - ABS(45 - y))), 2)),3))

Also it is worth noting that I would remove the math from MySQL and let your application do it.

For example, in PHP:

$distance = (round(sqrt(pow(min(abs(-12 - 10), abs(401 - abs(-12 - 10))), 2) + pow(min(abs(45 - 11), abs(401 - abs(45 - 11))), 2)),3));

$sql = "insert into wdata (fieldtype, oasistype, x, y, distance, occupied, image, pos)
        values (1, 1, 10, 11, $distance, 1, 'abcdefghijkl', 1)";