High value of Handler_read_rnd_next

[Yassine DAMERDJI]

Hi, I create a table containing 2 spatial coordinates (x,y). My table contain 500 million records. I make 512 partitions in it : partition by range of the new variable "box" which is the number of the box containing the coordinates (x,y).
The "box" is computed separatly with an easy and known algorithm based on power of 2. So it is an integer value (x,y are double values).
My table contain the columns :
id (int Primary), box (int index), x (double), y (double), other_columns

So when I have to find all records in a range (x1 < x < x2) AND (y1 < y < y2) I just must find all "box" in different ranges :
(box00 < box < box01) OR (box10 < box < box11) OR ... OR (boxn0 < box < boxn1)

When I run this kind of query, I have on my phpMyAdmin BAD VALUE of Handler_read_rnd_next and it says that may be my queries are not optimized !
My questions are :
1) Do someone have better idea to configure this kind or table (spatial coordinates). If yes, can you explain what partitions and what index can I use ?
2) I read in a paper that is better to use (box BETWEEN box00 AND box01) than
(box>box00 AND box < box01). Is it true ?
3) Is it better to convert my query to :
SELECT * FROM myTale WHERE (box>box00 AND box < box01) UNION SELECT * FROM myTale WHERE (box>box10 AND box < box11) UNION ... UNION SELECT * FROM myTale WHERE (box>boxn0 AND box < boxn1)
Thank you very much !