$query1="SELECT lat,lon from integer_test WHERE lat>$lat1 and lat<$lat2 and lon>$lon1 and lon<$lon2";

and lon>$lon1 and lon<$lon2";

Hello

I have been looking at planning the database strategy for openstreetmap (http://www.openstreetmap.org).

There are several data types stored in tables with longitude and latitude columns. Select statements work by selecting

where lat>$lat1 and lat<$lat2 and lon>$lon1 and lon<$lon2

I have made many empirical tests and have concluded:

1) I can improve performance by a factor of 2-2.5 by changing the double lat/lon to an integer then selecting on an integer.

2) I have concluded that for each 10 fold increase in the number of records, select queries take twice as long. For each doubling of the number of returned records, there is a sqrt(2) increase in select query time.

All this is assuming all relevant database information is in memory.

As the database grows, it would likely improve database performance by splitting an individual table into several thousand tables using the file system directory btree algorithm to effectively pre-select the data before the query is handled to the MySQL engine. This is not a neat solution. A much better way would be to improve the mysql index performance on very large numbers of records.

Given that there is such a strong relationship between the number of records returned, and query time, I conclude that the whole index tree is matched for every given number of root x records returned. If all records we are matching are under a single node or under a small number of nodes in the index tree, perhaps there is some way of telling the database engine to ignore the rest of the index tree.

Could this work, or am I misunderstanding how the index tree works? Are there existing optimisations which can de-couple the relationship between number of records and query time where the records I am selecting are within a small range?

Background information:

We can boil all this down to a mathematical relationship where query1 selects s number of records from r records dataset and query2 selects b number of records from c records dataset

Tquery1 is time to execue query 1 and Tquery2 is time to execute query2.

Tquery2=Tquery1 * sqrt(b/s) * (2^log(r/c)) + (b-s*CONST/15000)+CONST Where for my processor, CONST is 0.03

This can be simplified (loosing some accuracy) to:

Tquery2=Tquery1 * sqrt(b/s) * (2^log(r/c)

Raw data for selects: Creating a plan with 100000 points and averaging over 25 queries Points_per_tile Query_Time 25600 0.118 25600 0.119 25600 0.119 25600 0.119 12800 0.069 6400 0.042 3200 0.026 1600 0.017 800 0.011 400 0.008 200 0.005 100 0.004 50 0.003 Creating a plan with 1000000 points and averaging over 25 queries Points_per_tile Query_Time 25600 0.224 25600 0.223 25600 0.222 25600 0.223 12800 0.145 6400 0.093 3200 0.062 1600 0.043 800 0.029 400 0.020 200 0.015 100 0.011 50 0.008 Creating a plan with 10000000 points and averaging over 25 queries Points_per_tile Query_Time 25600 0.558 25600 0.548 25600 0.551 25600 0.551 12800 0.376 6400 0.257 3200 0.181 1600 0.125 800 0.087 400 0.062 200 0.044 100 0.031 Creating a plan with 100000000 points and averaging over 25 queries Points_per_tile Query_Time 25600 2.422 25600 2.332 25600 2.493 25600 2.446 12800 1.769 6400 1.295 3200 0.866 1600 0.657 800 0.456 400 0.328 200 0.233 100 0.159 50 0.118

Source code for the above test: #!/usr/bin/perl -w

#Program creates random point fields eqyuivalent to bitfieldtest.pl except the data is stored #as regular signed integers. To represent the globe as closely as possible, extents between #-180 and +179.999999 will be used. Therefore, adding 180 normalises for international date line 0. #Prime Meridian 180. 111111**0.000001

use DBI; use Time::HiRes qw( usleep ualarm gettimeofday tv_interval );

$DBHOST = "localhost"; $DBNAME = "nickh"; $DBUSER = "nickh"; $DBPASS = "xxxxxx";

#initialise database $driver = "mysql"; $dsn = "DBI:$driver:database=$DBNAME;host=$DBHOST"; $dbh = DBI->connect($dsn, $DBUSER, $DBPASS);

#@plane_densities=(100000000); @plane_densities=(100000,1000000,10000000,100000000); @tile_points=(25600,25600,25600,25600,12800,6400,3200,1600,800,400,200,100,50); $query_iterations=25; $debug=0;

sub create_bitfield; sub run_tests;

foreach $density(@plane_densities){ print "Creating a plan with $density points and averaging over $query_iterations queries\nPoints_per_tile Query_Time\n"; create_bitfield($density); foreach $tilepoints(@tile_points){ my $testtime=run_tests($density,$tilepoints); printf '%-14d %.3f',$tilepoints,$testtime; # prints "<1.0>"print "$density $testtime s\n"; print "\n"; } }

$dbh->disconnect; exit 0;

sub create_bitfield{ #takes number of points on the point field as argument. #We first create table without an index, as the indes slow populating table my $prep=q~ DROP TABLE IF EXISTS integer_test;

CREATE TABLE `integer_test` ( `lat` integer NOT NULL default '0', `lon` integer NOT NULL default '0' ) TYPE=MyISAM ~;

#drop/create tables without index foreach $aprepare(split(/;/,$prep)) { #print "preparing $preparation"; $dbh->do($aprepare); }

#populate table for ($i=0;$i<$_[0];$i+=100){ #create 100 element batched inserts (value,value),(value,value) etc my $insert=''; for ($j=0;$j<100;$j++){ if ($j>0) {$insert .= ','; } $lat=int(rand 3599999999)-1800000000; $lon=int(rand 3599999999)-1800000000; $insert .= "($lat,$lon)"; }

my $sql="INSERT INTO `integer_test` VALUES $insert;"; #print "SQL1 is $sql1\n\n"; $dbh->do($sql);

} #After populating table, we create indexes. #print "Creating index... This may take some time\n"; my $sql='CREATE INDEX index1 ON integer_test (lat,lon);'; $dbh->do($sql); }

sub run_tests{ #Parameters: Points in field; Size of tile in average number of points my $number_of_points=$_[0]; my $target_query_return=$_[1]; my $proportion_of_each_axis=1/(sqrt($number_of_points/$target_query_return)); my $max_extent=1-$proportion_of_each_axis; #Maximum extent for query without extending beyond bound my $returnedrows; $query1total=0;

for($i=0;$i<$query_iterations;$i++){ #$lat1=(0.4+(rand ($max_extent/10))); #$lon1=(0.4+(rand ($max_extent/10)));

$lat1=int(rand ($max_extent*3599999999))-1800000000; $lon1=int(rand ($max_extent*3599999999))-1800000000;

$lat2=int($lat1+($proportion_of_each_axis*3599999999)); $lon2=int($lon1+($proportion_of_each_axis*3599999999));

if ($debug){print "querying bounds $lat1 $lon1 $lat2 $lon2 with queries \n";}

$query1="SELECT lat,lon from integer_test WHERE lat>$lat1 and lat<$lat2 and lon>$lon1 and lon<$lon2";

#print "Query 1: $query1\n"; $t0 = Time::HiRes::time(); my $sth = $dbh->prepare($query1); $sth->execute(); $returnedrows+=$sth->rows(); #$sth->finish; $elapsed=Time::HiRes::time()-$t0; #print "Fetched $rows points in $elapsed \n"; $query1total+=$elapsed;

} #print $returnedrows; if ($debug){print "Each of the $query_iterations returned an average " . $returnedrows/$query_iterations . "records\n";} #print "unit test time is " . ($query1total/$query_iterations) . "seconds \n\n"; return ($query1total/$query_iterations); }