在大型数据集中递归搜索索引的性能

今天我遇到了一个关于大型数据集的搜索效率的问题，我已经完成了将它归结为最基本的案例。我觉得这种事情可能涉及一些经典问题或者我缺少的基本概念，所以指向这个的指针会很棒。在大型数据集中递归搜索索引的性能

假设我有像

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

与其中n/2是随机分配的类型= 1 n行填充的表定义。每行都引用另一个及其相同类型，除了第一个引用= 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之前，我们需要多大的数据集？

来源

2011-06-06 Matt

我认为甲骨文基于成本的优化器至少将占到其更好地根据当前的表统计... – Randy 2011-06-06 21:16:25

@Randy谢谢，我对此并不熟悉。我会看看。 – Matt 2011-06-06 21:31:07

这段代码是一个SQL注入漏洞：''SELECT id，引用FROM foo WHERE id ='。$ ref;'，将其改为'“SELECT id，引用FROM foo WHERE id ='$ ref';”'请注意使用单引号。没有那些你的'mysql_real_escape_string（）'将不起作用。 – Johan 2011-06-06 21:35:28

你的例子是有点难以解析，但生病开始在顶部：

你的第一个函数不返回所有类型= 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上

来源

2011-06-06 21:57:38

这是我的预期，但我没有'意识到这种差距会非常大，或者查询的开销太大。我仍然很好奇，看看时代是否相交;我将在下次访问我的机器时对其进行测试。感谢您提供非常深入的答案。 – Matt 2011-06-06 23:27:26

在大型数据集中递归搜索索引的性能

回答

相关问题