原文地址https://db.cs.uni-tuebingen.de/theses/2025/ann-kathrin-claessens/claessens-2025.pdf2.6 性能评估运行第2.5节中提出的GIF解码器查询的DuckDB代码很快就会发现它相当慢。即使采用稍后讨论的CTE物化技术其速度也显著慢于原始的PostgreSQL查询。在本子章节中将比较不同版本查询运行EXPLAIN ANALYZE参见第1.4节所得的总时间。通过检查查询图识别出这些性能差异的可能原因以便创建一个针对性能优化的新实现。2.6.1 可读性优化和CTE物化的效果如第1.4节所述DuckDB仅在特殊情况下对CTE进行物化[3]而PostgreSQL在大多数情况下会自动将CTE仅计算一次即使它被同级CTE多次引用[7]。显式物化CTE以消除这种差异当应用于CTElzw_params及其源时会对整体执行时间产生影响。物化这个特定的CTE之所以影响巨大是因为它在解压缩算法CTEdecompression_steps的递归步骤中被引用。除了递归调用自身之外lzw_params是它引用的唯一CTE。由于它执行大量迭代这解释了为什么CTE物化仅对CTElzw_params及其源image_blocks如此有效因为这意味着它们只执行一次而不是每次迭代都执行。将PostgreSQL推理查询移植到DuckDB得到的初始DuckDB查询在其解压缩算法的递归步骤中嵌套了一个额外的WITH子句参见第2.3.3节。然而物化其CTE并未带来任何好处。外部WITH子句的所有CTE除了最后一个对输出行进行排序的CTE都可以被物化而不会对性能产生任何负面影响。在初始DuckDB版本和针对可读性优化的版本中都进行了这些物化后使用EXPLAIN ANALYZE来比较它们与原始PostgreSQL查询的性能见表11。版本时间PostgreSQL1.68秒DuckDB (初始)281.46秒DuckDB (CTE物化)150.30秒DuckDB (可读性优化)119.79秒表11不同版本的GIF解码器查询移植到DuckDB、CTE物化、以及可读性优化在92x92测试图像的GIF数据上的平均运行时间比较在没有任何CTE物化的情况下初始适应DuckDB的时间约为281秒。进行物化后总执行时间平均几乎减半。然而这仍然比原始查询慢89倍以上。针对可读性优化的物化版本性能没有比物化的初始查询适应版本明显更差这是意料之中的。除了几个查询简化和解压缩算法CTE中连接结构的不同之外它们之间的主要区别是宏的使用这不应造成显著的开销参见第1.4节。事实上根据查询图工具提供的分析见表12重构后的连接似乎导致了查询性能的改进。该分析包括了查询中递归CTE的运行时间这涵盖了表中显示的若干其他操作符的时间。阶段时间百分比总计时间154.36秒100.00%递归CTE153.44秒99.40%投影86.04秒55.74%哈希连接43.89秒28.43%哈希分组6.03秒3.90%右定界连接3.11秒2.02%阶段时间百分比总计时间123.14秒100.00%递归CTE122.34秒99.36%投影77.05秒62.57%哈希分组6.11秒4.96%右定界连接5.98秒4.86%哈希连接3.65秒2.96%表12DuckDB查询图工具为物化的初始查询左和可读性优化版本右提供的运行时分析两个查询版本之间的主要区别是物化的初始DuckDB查询的评估需要大量时间用于哈希连接操作。查看查询图递归CTEdecompression_steps中一个成本高昂的哈希连接似乎是导致此问题的主要原因。可读性优化包括将此CTE递归步骤的FROM从句从嵌套的WITH子句重构为LATERAL连接恰好极大地降低了这些成本。作为交换右定界连接操作符的时间略有增加。由于针对可读性优化的查询性能更好得多因此将其作为起点来讨论进一步的性能优化。2.6.2 性能优化到目前为止讨论的性能方面并未解决为什么该程序的原始PostgreSQL版本如此快的问题。查询图工具提供的分析表12显示针对可读性优化的查询版本超过99%的运行时间是由递归CTE引起的。此查询中有三个递归CTEblocks、image_data和decompression_steps。查看从DuckDB查询图工具获得的查询图CTEblocks的时间显示为小于0.0016秒image_data为0.04秒而decompression_steps大约需要122秒。因此以下讨论的性能优化主要集中在CTEdecompression_steps上。检查递归CTEdecompression_steps的子图很快发现单个投影操作占用了其运行时间的绝大部分。大约76秒这也代表了表12所示分析中投影所需77.05秒的主要原因。这个昂贵的投影与包含new_code_table列的子查询相关其中更新了码表表示。由于此子查询的其他部分并不突出为潜在的成本高昂操作很可能是在此CTE上下文中向字典添加新代码/模式对的方法成本高昂。如第2.3.2节所讨论的原始查询中用于表示码表的方法在DuckDB实现中不可用。可以想象所选的替代方案性能不如原始方案。因此下文探讨了一种实现码表更新的替代方法并进行了实验以验证其是否有潜力提高性能。检查码表中存储的键值发现它们是整数值。如代码清单25所示添加到表中的每个键的值是前一个键值加1。在这种情况下键值可以轻松转换为有序数据结构的位置索引设为解压缩算法期间添加到码表的第一个键的整数值。那么下一个键的值为1再下一个为2依此类推。对于按添加顺序存储条目的数据结构将每个键值减去−1可得到其位置索引其中添加到结构的第一个条目的索引为1。如第2.5.4节所讨论的键值范围从0到“信息结束代码”值eof_code的初始码表条目实际上并未存储在字典中。相反初始化或码表重置后添加的第一个键值是“信息结束代码”值加1见代码清单25。因此−1对应于“信息结束代码”的值。从任何键值中减去它即可得到条目的位置索引。有了这种计算索引的简便方法就不再需要存储键/值对。相反颜色模式可以存储在列表中。只要新模式被追加到列表的末尾使其按添加顺序出现就可以使用从LZW代码值计算出的索引来访问它们。通过比较两个递归查询代码清单29的性能测试了这是否会带来任何好处一个是将键/值对添加到类型为MAP(INT, INT[])的字典另一个是将值添加到类型为INTEGER[][]的列表。为了模拟GIF解码器查询执行码表更新的方式查询设计为从一个空的MAP或列表开始并在每个递归步骤中添加一个条目使其大小随着每次迭代而增加。为了更准确地表示码表更新添加的列表长度也应增加。为了简化起见查询的每次迭代将只添加一个长度为1的列表。-- 代码清单29添加个元素到MAP左或列表右的递归示例查询。-- 左MAPWITHRECURSIVE map_updateAS(SELECT0AScount,MAP()::MAP(INT,INT[])ASdictUNIONALLSELECTcount1,MAP_CONCAT(dict,MAP {count:[42]})FROMmap_updateWHEREcount⟨ N ⟩)SELECTdict,CARDINALITY(dict)AS# entriesFROMmap_updateWHEREcount⟨ N ⟩;-- 右列表WITHRECURSIVE map_updateAS(SELECT0AScount,[]::INT[][]ASdictUNIONALLSELECTcount1,dict||[[42]]FROMmap_updateWHEREcount⟨ N ⟩)SELECTdict,LEN(dict)AS# entriesFROMmap_updateWHEREcount⟨ N ⟩;码表最大增长到4095个条目除非清除代码导致提前重置。这对应于大小为4095 -eof_code的字典表示不包括初始表条目。然而在达到4000个条目之前很久就可以观察到两种存储表方法之间的性能差异。表13显示了为代码清单29中的两个查询对不同迭代次数运行EXPLAIN ANALYZE获得的运行时间。这些值是连续5次测量的平均值。 500 1000 1500 2000 2500 3000 3500 4000MAP0.32秒2.52秒6.65秒15.40秒28.62秒44.69秒61.26秒列表0.03秒0.05秒0.07秒0.09秒0.12秒0.15秒0.19秒表13递归添加个条目到MAP与添加到INTEGER[][]列表的平均运行时间表13中呈现的结果在两个查询之间存在巨大差异。对于向MAP添加条目的递归查询当迭代次数接近4000时运行时间急剧增加几乎达到一分半钟的标记。同时向列表添加条目的递归查询的运行时间仅接近0.25秒。由于这些运行时间之间存在巨大差异如图4所示很明显将码表表示更改为列表有很大的潜力来改善GIF解码器查询的性能。图4表13中值的散点图使用MAP用 x 表示使用列表用 o 表示将码表表示从MAP更改为类型INTEGER[][]相对容易因为涉及的代码行不多。表14展示了涉及码表的表达式在两种数据类型下的比较。操作MAP码表INTEGER[][]码表初始化表MAP()::MAP(INTEGER, INTEGER[])[]::INTEGER[][]添加新模式MAP_CONCAT(code_table, MAP {code: pattern})code_table检索模式code_table[code][1]code_table[table_index]表14使用MAP与列表涉及码表操作的SQL代码最显著的区别是从MAP中检索值使用提取的LZW代码值作为键而列表表示的条目则使用索引进行访问该索引必须首先从LZW代码计算得出。如前所述这是通过减去“信息结束代码”值eof_code来实现的。为了完全匹配从MAP检索数据的功能如表14所示从列表检索条目时当给定代码在码表表示中没有存储条目时必须返回NULL。在GIF解码器查询中所有长度为1的颜色模式的初始码表条目都会发生这种情况。由于它们没有存储在字典中因此使用COALESCE函数在尝试从MAP检索条目返回NULL时返回长度为1的列表。-- 代码清单30摘自代码清单24返回存储在MAP中或长度为1的颜色模式COALESCE(code_table[code][1],LIST_VALUE(code))但是如果代码小于“信息结束代码”的值则为表索引计算的值变为负数。小于0的索引不会导致列表访问返回NULL而是从列表末尾开始计数[3]。将负表索引的值设置为0反而会导致返回NULL的预期行为。这是使用GREATEST函数实现的如代码清单31所示。-- 代码清单31将LZW代码转换为不变成负数的位置列表索引SELECTGREATEST(0,code-eof_code)AStable_index完成这些更改后再次使用EXPLAIN ANALYZE观察查询的运行时间是否发生了变化。确实对于同一个测试图像时间已降至大约40秒的量级所有性能优化的效果见表17。虽然这快得多但仍然比原始的PostgreSQL查询慢很多。根据DuckDB查询图工具的新性能分析结果表15剩余时间的大部分仍然在递归解压缩CTE中。投影操作的时间已大幅下降现在不到1秒但右定界连接和哈希分组的成本仍然是整个PostgreSQL GIF解码器查询总运行时间的两倍多。阶段时间百分比总计时间38.61秒100%递归CTE38.01秒98.45%哈希分组5.62秒14.55%右定界连接5.43秒14.07%哈希连接2.76秒7.14%投影0.73秒1.88%表15码表使用INT[][]表示的运行时分析这些连接中成本最高的确实可以在解压缩CTE的递归步骤中找到其FROM从句被实现为一行的LATERAL连接参见第2.4.1节。DuckDB在解关联连接方面表现更好[20]这一事实支持了这不会导致最佳性能的观点。为了降低成本对其FROM从句进行了重构以减少LATERAL连接。将仅被引用一次的子查询中的代码移至该引用处。将不需要用于任何其他列的列定义向上移动到SELECT从句中。通过这些更改FROM从句可以减少为三个表的连接递归调用、包含算法参数的CTE以及一个嵌套的WITH子句如果不强制执行物化性能会更好。查询图工具提供的新分析表16显示这些措施实际上确实降低了哈希分组和右定界连接的时间。阶段时间百分比总计时间8.49秒100%递归CTE7.97秒93.91%哈希分组1.32秒15.52%右定界连接0.88秒10.35%哈希连接0.55秒6.53%投影0.47秒5.50%表16decompression_steps中减少LATERAL连接的运行时分析这些更改导致最终平均运行时间略低于9秒另见表17中的运行时间概览。根据表16所示的分析超过90%的时间仍然来自解压缩算法的递归CTE。仍有略多于1秒的时间是由decompression_steps中的哈希分组操作符引起的。但是即使此递归CTE子图中所有操作符的成本加起来也低于该CTE指示运行时间的一半。减少LATERAL连接使用的显著影响表明性能较差的连接似乎也对递归CTE的整体运行时间产生不成比例的负面影响。除了递归步骤中相当复杂的FROM从句外DuckDB实现仍然比PostgreSQL原始版本表现更差的另一个原因可能与以下事实有关此查询的结构方式不允许DuckDB应用其策略来快速评估递归CTE。尽管DuckDB支持递归CTE中的并行化[17]但解压缩算法的迭代不能并行执行。每次迭代不仅依赖于前一次迭代的LZW代码和颜色模式还依赖于码表的当前状态这是算法所有先前迭代的结果。版本时间可读性优化版119.79秒INT[][]码表版38.39秒INT[][]码表版 减少LATERAL连接版8.86秒表17不同版本DuckDB GIF解码器查询的平均运行时间2.6.3 结论使用DuckDB的字典类型MAP来弥补HSTORE类型的不可用性以及物化规则的不同导致了性能显著下降。根据实现方式的不同还观察到LATERAL连接阻碍了查询性能。这是因为它们影响了执行多次迭代的查询中最大CTE的递归步骤。由于无法对递归CTE的评估应用并行化DuckDB无法针对此GIF解码器查询发挥其快速查询执行的全部潜力。然而选择一种高效的方法来存储码表条目、根据DuckDB的优势设计连接模型以及显式物化CTE可以显著提高查询的性能。