时间戳

首页 > 解决方案 > 树搜索的数据类型或结构

postgresql - 树搜索的数据类型或结构

问题描述

我正在使用一个大数据结构，它通过字符串标签描述项目树，例如文件系统中的路径字符串。有 ~198,000 个树元素和 ~9,100,000 个叶元素。

实施选项：

我想，在实施后，我可以比较两者EXPLAIN ANALYZE。但是，在实施之前，是否可以预测差异或估计（速度和额外磁盘消耗）性能？

笔记和测试

关于查询（要求），它是开放的：当您通过“字符串路径”表示分层信息时，“分层搜索引擎”必须具有表现力，ltree、正则表达式和有时 LIKE 运算符都具有表现力。

用于测试CREATE TABLE test (path ltree)与 ~198,000 个树元素相似的指南：

    CREATE INDEX path_gist_idx ON test USING GIST (path)
    ; -- consumes ~3G
    SELECT count(*) n 
    FROM test WHERE path ~ 'first.second.*.etc_etc_etc.*'
    ; -- n= 149068
    EXPLAIN ANALYSE 
      SELECT count(*) n 
      FROM test WHERE path ~ 'first.second.*.etc_etc_etc.*'
    ;  -- Planning Time: 0.075 ms
       -- Execution Time: 1317.443 ms

标签： postgresqlperformance

解决方案

正如这个问题/解决方案所推荐的，规范化表的最佳解决方案似乎是“闭包表” 。

在其他索引策略上，我们可以使用这个问题/答案的线索，建议尝试pg_trgm模块。另见https://www.postgresql.org/docs/current/pgtrgm.html

让我们检查所有解决方案。

蛮力（索引）

“蛮力”的优点是不需要改变数据结构，只添加一个索引，在大数据上下文中我们有一些额外的磁盘空间。所以，只测试了索引，没有拆分成真正的树和指针。

测试ltree搜索

请参阅问题主体的测试。执行时间：~1300 毫秒。

良好的层次搜索运算符。唯一的问题是索引需要一个新列，当字符串必须保留以供其他用途时，或者不是ltree-ingestion 格式。我使用了转换

trim(
  replace( 
   regexp_replace(text_path,'[^A-Z0-9_/]+','_','ig'), -- clean
   '/',  -- the path separator at text_path
   '.'   -- the ltree separator
  ),
  '.'  -- clean
)::ltree

因此，当您转换其他问题时，它不能 100% 可逆地被 cast 重用ltree2text()。

使用 LIKE 运算符测试pg_trgm搜索

这是更快的方法：~200 ms

CREATE EXTENSION pg_trgm;
CREATE INDEX textpath_gist_idx  ON t2_text USING gin (txt_path gin_trgm_ops);
EXPLAIN ANALYSE 
   SELECT count(*) n
   FROM   t2_text  
   WHERE  txt_path LIKE 'first/second/%/etc_etc_etc/%'
; --  Planning Time: 0.133 ms
  --  Execution Time: 195.524 ms
  -- ... BUT, returns zero on COUNT result!

索引USING gin (colName gin_trgm_ops)使用较少的磁盘空间，~2G。

这里的问题不是性能而是它不起作用（！），并且不是“两个%”的问题，因为对于类似的查询工作正常，所以它不可靠：

  • 计数WHERE txt_path LIKE 'first/second/%/etc_etc_etc/%'为零。
  • 计数WHERE txt_path LIKE '%etc_etc_etc%'是正确的。

似乎是 PostgreSQL v12 错误（其他版本相同？）。

pg_trgm使用正则表达式测试搜索

执行时间约为 1000 毫秒，它比最可靠的ltree LIKE运算符快一点（并且磁盘消耗更少）。

EXPLAIN ANALYSE 
   SELECT count(*) n
   FROM   t2_text  
   WHERE  txt_path ~ '^first/second/.+/etc_etc_etc/'
--  Timing: Generation 2.312 ms, ..., Total 27.853 ms
--  Execution Time: 1017.293 ms

封闭表

需要添加一个id bigserialif not exists 和一个新表，其祖先和后代指向原始表。它会消耗更多的磁盘空间，而且...我可以用这个模型做所有的查询吗？

它还消耗更多的程序员时间（！），没有自动化的方式（它是一个模板表，但 PostgreSQL 不提供“标准解决方案”）来创建额外的表。对于查询，没有简单的 operator。

...所以我没有添加测试，它是一个 Wiki：如果您在此处编辑某些内容，我可以添加测试以显示差异。

CREATE TABLE t2_treeclosure (
   ancestor bigint NOT NULL,
   descendant bigint NOT NULL,
   PRIMARY KEY (ancestor,descendant),
   FOREIGN KEY (ancestor) REFERENCES t2_text(id),
   FOREIGN KEY (descendant) REFERENCES t2_text(id)
 );

...有时可以减少原始t2_text表减少文本的磁盘消耗，在滑倒它之后。需要一个函数来重建路径等，但如果“表关闭”比“蛮力”方法更快，则可以更快。

推荐阅读