Производительность рекурсивного поиска индексов в больших наборах данных

Question

Сегодня я столкнулся с вопросом эффективности поиска для больших наборов, и я сделал все возможное, чтобы свести его к самому основному случаю.Я чувствую, что такого рода вещи, вероятно, относятся к какой-то классической проблеме или базовой концепции, которую я упускаю, поэтому указатель на это был бы великолепен.

Предположим, у меня есть определение таблицы, например

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

Заполняется n строками, где n / 2 - случайным образом назначенный тип = 1.Каждая строка ссылается на другой с тем же типом , за исключением первого, который имеет ссылку = null.

Теперь мы хотим напечатать все элементы с типом 1. Я предполагаю, что в какой-то момент этобудет быстрее рекурсивно вызывать что-то вроде

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]);
}

В отличие от

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?

Answer 1

Ваш пример немного сложен для разбора, но плохо начнем сверху:

Ваша первая функция не возвращает все элементы с типом = 1. Она возвращает все зависимые элементы (на основе ссылок) на элемент, который вы передаете. С точки зрения PHP, поскольку ссылка / дескриптор уже открыта, при каждом вызове функции возникают нетривиальные издержки при вызове каждой функции, не говоря уже о конкатенации строк, несущей затраты скаждое выполнение этой строки.

Как правило, лучше использовать стилизацию второй функции, поскольку она запрашивает базу данных только один раз и возвращает запрашиваемые элементы без дальнейшей работы.Конечно, все сводится к профилировщику, который определит, какой из них будет возвращаться быстрее, но из моих тестов второй - это лучший выбор:

Это было выполнено с n = 5000 элементов в БД (n / 2 = 2500 тип 1 и передача ссылки = наибольший идентификатор с типом = 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