Script to test three algorithms for SQL-based area search

testscript_locations.js

var mysql = require('mysql'),
	assert = require('assert'),
	util = require('util'),
	sys = require('sys');

var client = mysql.createClient({
	user: 'root',
	password: null,
	database: 'tests'
});

/* ===== test configuration ===== */

var test = {
	locations: 200,
	limits: [1, 5, 10, 20, 50, 100, 150, 200]
	//limits: [1, 5]
};
var testrange = {
	lat: [47.4, 55.0],
	lon: [5.9, 15.0]	
};
var highestLimit = test.limits.slice(-1)[0];

/* ===== create tests ===== */

diffLat = testrange.lat[1]-testrange.lat[0];
diffLon = testrange.lon[1]-testrange.lon[0];

testcases = [];
for (var i = 0; i < test.locations; i++) {
	testcases.push({
		lat: testrange.lat[0] + Math.random()*diffLat,
		lon: testrange.lon[0] + Math.random()*diffLon
	});
}

/* ===== helper functions ===== */

function allIn(array, testArray) {
	for (var i = 0; i < array.length; i++) {
		if (testArray.indexOf(array[i]) === -1)
			return false;	
	}
	return true;
}

function exactQuery(coords, limit, cb) {
	var start = (new Date()).getTime();
	client.query('SELECT id, (acos(sin('+coords.lat+'*Pi()/180)*sin(lat*Pi()/180)+cos('+coords.lat+'*Pi()/180)*cos(lat*Pi()/180)*cos(('+coords.lon+'-lon)*Pi()/180))) as distance FROM coords ORDER BY distance ASC LIMIT '+limit,
	function(err, results, fields) {
		assert.ifError(err);
		cb(Math.round(((new Date()).getTime()-start)/1));
	});	
}
function pythagoras(coords, exact, limit, cb) {
	var start = (new Date()).getTime();
	client.query('SELECT id FROM coords ORDER BY SQRT(POW(('+coords.lat+'-lat), 2)+POW(('+coords.lon+'-lon), 2)) ASC LIMIT '+limit, function(err, results) {
		assert.ifError(err);
		var r = [];
		for (var i = 0; i < results.length; i++) {
			r.push(results[i].id);	
		}
		
		if (allIn(exact, r)) {
			var timeDiff = Math.round(((new Date()).getTime()-start)/1);
			cb(limit, timeDiff);
		} else {
			pythagoras(coords, exact, limit+1, cb);	
		}
	});
}
function advancedPythagoras(coords, exact, limit, cb) {
	var start = (new Date()).getTime();
	client.query('SELECT id FROM coords ORDER BY SQRT(POW(('+coords.lat+'-lat)/70, 2)+POW(('+coords.lon+'-lon)/110, 2)) ASC LIMIT '+limit, function(err, results) {
		assert.ifError(err);
		var r = [];
		for (var i = 0; i < results.length; i++) {
			r.push(results[i].id);	
		}
		
		if (allIn(exact, r)) {
			var timeDiff = Math.round(((new Date()).getTime()-start)/1);
			cb(limit, timeDiff);
		} else {
			advancedPythagoras(coords, exact, limit+1, cb);	
		}
	});
}

var testResults = {};
function doEnd() {
	/* Output as CSV */
	console.log('Testcase; Lon; Lat; Limit; Exact:Time; Pythagoras:Limit; Pythagoras:Time; AdvancedPythagoras:Limit; AdvancedPythagoras:Time');
	for (var testcase in testResults) {
		for (var i = 0; i < test.limits.length; i++) {
			console.log(''+testcase+';'+testcases[testcase].lon+';'+testcases[testcase].lat+';'+test.limits[i]+';'+testResults[testcase]['exact'][test.limits[i]]['time']+';'+testResults[testcase]['pythagoras'][test.limits[i]]['end']+';'+testResults[testcase]['pythagoras'][test.limits[i]]['time']+';'+testResults[testcase]['advancedPythagoras'][test.limits[i]]['end']+';'+testResults[testcase]['advancedPythagoras'][test.limits[i]]['time']);
		}	
	}
	
	setTimeout(function() {
		process.exit(0);
	}, 2000);
}

function runExact(testcases, ix, limits, ixl, cb) {
	if (ixl >= limits.length) {
		cb();
		return;	
	}
	
	exactQuery(testcases[ix], limits[ixl], function(time) {
		testResults[ix]['exact'][limits[ixl]] = { time: time };
		
		runExact(testcases, ix, limits, ixl+1, cb);
	});					
}
function runPythagoras(testcases, ix, exact, limits, ixl, cb) {
	if (ixl >= limits.length) {
		cb();
		return;	
	}
	
	pythagoras(testcases[ix], exact.slice(0, limits[ixl]), limits[ixl], function(l, time) {
		testResults[ix]['pythagoras'][limits[ixl]] = { end: l, time: time };
		
		runPythagoras(testcases, ix, exact, limits, ixl+1, cb);	
	});
}
function runAdvancedPythagoras(testcases, ix, exact, limits, ixl, cb) {
	if (ixl >= limits.length) {
		cb();
		return;	
	}
	
	advancedPythagoras(testcases[ix], exact.slice(0, limits[ixl]), limits[ixl], function(l, time) {
		testResults[ix]['advancedPythagoras'][limits[ixl]] = { end: l, time: time };
		
		runAdvancedPythagoras(testcases, ix, exact, limits, ixl+1, cb);
	});
}

function runTestcase(testcases, ix, cb) {
	if (ix >= testcases.length) {
		cb();
		return;	
	}
	
	testResults[ix] = {
		pythagoras: {},
		advancedPythagoras: {},
		exact: {}
	};
	
	// get exact results
	var exact = [];	
	client.query('SELECT id, (acos(sin('+testcases[ix].lat+'*Pi()/180)*sin(lat*Pi()/180)+cos('+testcases[ix].lat+'*Pi()/180)*cos(lat*Pi()/180)*cos(('+testcases[ix].lon+'-lon)*Pi()/180))) as distance FROM coords ORDER BY distance ASC LIMIT '+highestLimit,
	function(err, results, fields) {
		assert.ifError(err);
		
		for (var i = 0; i < results.length; i++) {
			exact.push(results[i].id);	
		}
		
		runExact(testcases, ix, test.limits, 0, function() {
			runPythagoras(testcases, ix, exact, test.limits, 0, function() {
				runAdvancedPythagoras(testcases, ix, exact, test.limits, 0, function() {
					runTestcase(testcases, ix+1, cb);
				});
			});
		});
	});	
}

/* ===== perform tests ===== */

//util.log("Start tests");

runTestcase(testcases, 0, function() {
	doEnd();
});