为什么在排序后查询 table 会慢很多？

Question

我有一个 Python 程序，它使用 Pytables 并以这种简单的方式查询 table：

def get_element(table, somevar):
    rows = table.where("colname == somevar")
    row = next(rows, None)
    if row:
        return elem_from_row(row)

为了减少查询时间，我决定尝试用table.copy(sortby='colname'). This indeed improved the query time (spent in where), but it increased the time spent in the next()内置函数对table排序几个数量级！可能是什么原因？

只有当 table 中有另一列时才会出现这种减慢，并且减慢会随着另一列的元素大小而增加。

为了帮助我理解问题并确保这与我程序中的其他内容无关，我做了这个重现问题的最小工作示例：

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import tables
import time
import sys


def create_set(sort, withdata):
    #Table description with or without data
    tabledesc = {
        'id': tables.UIntCol()
    }
    if withdata:
        tabledesc['data'] = tables.Float32Col(2000)

    #Create table with CSI'ed id
    fp = tables.open_file('tmp.h5', mode='w')
    table = fp.create_table('/', 'myset', tabledesc)
    table.cols.id.create_csindex()

    #Fill the table with sorted ids
    row = table.row
    for i in xrange(500):
        row['id'] = i
        row.append()

    #Force a sort if asked for
    if sort:
        newtable = table.copy(newname='sortedset', sortby='id')
        table.remove()
        newtable.rename('myset')
    fp.flush()
    return fp


def get_element(table, i):
    #By construction, i always exists in the table
    rows = table.where('id == i')
    row = next(rows, None)
    if row:
        return {'id': row['id']}
    return None


sort = sys.argv[1] == 'sort'
withdata = sys.argv[2] == 'withdata'
fp = create_set(sort, withdata)

start_time = time.time()
table = fp.root.myset
for i in xrange(500):
    get_element(table, i)
print("Queried the set in %.3fs" % (time.time() - start_time))
fp.close()

这里是一些显示数字的控制台输出：

$ ./timedset.py nosort nodata
Queried the set in 0.718s

$ ./timedset.py sort nodata
Queried the set in 0.003s

$ ./timedset.py nosort withdata
Queried the set in 0.597s

$ ./timedset.py sort withdata
Queried the set in 5.846s

一些注意事项：

行实际上在所有情况下都已排序，因此它似乎与 table 了解排序有关，而不仅仅是数据被排序。
如果我没有创建文件，而是从磁盘读取它，结果相同。
仅当数据列存在时才会出现此问题，即使我从未写入或读取过它。我注意到当列的大小（浮点数）增加时，时间差增加 "in stages"。减速必须与内部数据移动或 I/O 相关联：
如果我不使用 next 函数，而是使用 for row in rows 并相信只有一个结果，速度仍然会变慢。

通过某种 id（排序或未排序）访问 table 中的元素听起来像是一项基本功能，我一定是错过了使用 pytables 执行此操作的典型方法。它是什么？为什么会出现如此可怕的放缓？这是我应该报告的错误吗？

Answer 1

终于明白是怎么回事了

长话短说

根本原因是一个错误，它在我这边：我在制作副本之前没有刷新数据以防排序。结果，副本基于不完整的数据，新排序的数据也是如此 table。这就是导致速度变慢的原因，并且在适当的时候进行刷新导致了一个不那么令人惊讶的结果：

...
#Fill the table with sorted ids
row = table.row
for i in xrange(500):
    row['id'] = i
    row.append()
fp.flush()  # <--

#Force a sort if asked for
if sort:
    newtable = table.copy(newname='sortedset', sortby='id')
    table.remove()
    newtable.rename('myset')
    fp.flush()  # <--

return fp
...

但是为什么呢？

当我决定检查和比较 table "not sorted" 与 "sorted" 的结构和数据时，我意识到了我的错误。我注意到在排序的情况下，table 的行数较少。根据数据列的大小，该数字看似随机变化，从 0 到大约 450。此外，在排序的table中，所有行的id都设置为0。我猜想在创建table时，pytables会初始化列，可能会也可能不会预先- 创建一些具有初始值的行。这 "may or may not" 可能取决于行的大小和计算的 chunksize.

因此，在查询已排序的table时，除了id == 0以外的所有查询都没有结果。我最初认为 raising and catching the StopIteration error 是导致速度下降的原因，但这并不能解释为什么速度下降取决于数据列的大小。

在阅读了 pytables 的一些代码后（特别是 table.py and tableextension.pyx），我认为会发生以下情况：当列被索引时，pytables 将首先尝试使用此索引来加快搜索。如果找到一些匹配的行，将只读取这些行。但是，如果索引指示没有行与查询匹配，则出于某种原因 pytables 回退到 "in kernel" 搜索，该搜索遍历并读取所有行。这需要在多个 I/Os 中从磁盘读取完整行，这就是数据列的大小很重要的原因。同样在该列的特定大小下，pytables 没有 "pre-create" 磁盘上的某些行，导致排序后的 table 根本没有行。这就是为什么在图表上当列大小小于 525 时搜索非常快的原因：迭代 0 行不会花费太多时间。

~~我不清楚为什么迭代器回退到 "in kernel" 搜索。如果搜索到的 id 明显超出了索引范围，我看不出有任何理由去搜索它...~~ 编辑： 仔细查看代码后，原来这是因为一个bug。它存在于我使用的版本 (3.1.1) 中，但已 fixed in 3.2.0.

讽刺

真正让我哭笑不得的是，只在题例中复制前忘记flush了。在我的实际程序中，这个错误是不存在的！我也不知道但在调查问题时发现的是默认情况下 pytables 不传播索引。这必须通过 propindexes=True 明确要求。这就是为什么在我的应用程序中排序后搜索变慢的原因...

故事的寓意：

索引很好：使用它
但是在排序 table
确保你的数据在读取之前在磁盘上...

为什么在排序后查询 table 会慢很多？

Why is querying a table so much slower after sorting it?

python

optimization

iterator

pytables

长话短说

但是为什么呢？

讽刺