Geek asks and answers

Recursive index search performance in large datasets

Today I was faced with the issue of search efficiency for large sets, and I did everything possible to reduce it to the most basic business. I feel that things like this are probably related to some kind of classic problem or basic concept that I am missing, so a pointer to that would be great.

Suppose I have a table definition like

CREATE TABLE foo(
    id int,
    type bool,
    reference int,
    PRIMARY KEY(id),
    FOREIGN KEY(reference) REFERENCES foo(id),
    UNIQUE KEY(reference)
) Engine=InnoDB;

It is filled with n lines, where n / 2 is randomly assigned type = 1. Each line refers to another with the same type , with the exception of the first, which has a link = null.

Now we want to print all elements with type 1. I assume that at some point it will recursively call something like

function printFoo1($ref){
    if($ref==null)
        return;
    $q = 'SELECT id, reference FROM foo WHERE id='.$ref;
    $arr = mysql_fetch_array( mysql_query($q) );
    echo $arr[0];
    printFoo1($arr[1]);
}

Unlike

function printFoo2($ref){
    $q = 'SELECT id FROM foo WHERE type=1';
    $res = mysql_query($q);
    while( $id = mysql_fetch_array($res) ){
        echo $id[0];
    }
}

, 1 "id", , 2 n/2 , , , SELECT.

? , , 1 2?

+3
1

, :

= 1. , ( ) , . PHP, / , , .

, , , , . , , , , - :

n = 5000 db (n/2 = 2500 1 reference = id = 1 db).

printFoo1: 3.591840 seconds
printFoo2: 0.010340 seconds

, . , , JOIN .

$res = mysql_query('SELECT MAX( id ) as `MAX_ID` FROM `foo` WHERE `type` = 1', $link);
$res2 = mysql_fetch_assoc($res);

$id = $res2['MAX_ID'];

// cleanup result and free resources here

echo "printFoo1: ";
$start = microtime(true);
printFoo1($id);
echo microtime(true) - $start;

echo '<br />';

echo "printFoo2: ";
$start = microtime(true);
printFoo2();
echo microtime(true) - $start;

mysql_close($link);

PHP 5.2.17, Linux

0

More articles:


All Articles