优化大(宽)树的单向同步 -- postgresql 领域 和 optimization 领域 和 tree 领域 和 postgresql-11 领域 dba 相关 的问题

Optimizing one-way syncing of large (wide) tree


0
vote

问题

中文

我处理几棵树的大小(它们都有〜8-10的深度),但它们不是不寻常的组成〜50-100K节点。

此刻,树木使用简单的parent_id fks存储。

在程序中创建/生成树,然后需要保存在数据库中。捕获是我们无法擦除前一棵树(如果存在相同类型,如果存在),我们需要更新它以反映新(已更改)的树。偶尔这意味着交换整个树(如果根本改变),而且很多时候它只是意味着这里和那里的微小变化(例如,添加一些孩子/子树,退休)。我们也不会删除旧孩子(及他们的孩子),他们只是被标记为旧的。

完成更新/验证的方式是通过树(深度首先)并逐一检查每个节点。

一个性能问题是它可能需要几乎2分钟才能验证DB中的树(〜50k节点)与程序中的树相同(因为它涉及n选择n的数字总节点)。

在利用Ltree结构的同时可以在读取方面有益,我认为它不会解决这个问题(插入/更新/验证树)。

我不确定优化这一点的最佳方式是什么。我有一个想法是计算和存储每个子树的哈希,这可能在大多数情况下可能速度加速,因为它会知道不需要触摸的树的哪些部分。哈希计算应相当快,可以在程序中并行化,其中工作量更易于管理。但是,也许还有一些我缺少的其他方式?

散装刀片等是不可能的,因为树依赖于递归关系。

此外,数据库自然地在云中,这意味着逐渐执行的数千个查询可能在延迟(程序和DB上都是在AWS上的情况下毫不犹豫地引起的延迟很小,但当然仍然存在)。我的一部分想要批量将新生成的树插入一些临时表,然后写入将其同步到实际表中的DB函数。

树的一般结构/架构:

  • 每个节点都有一个id和一个parent_id列(可为nullable fk到ID)
  • 根节点具有parent_id = null
  • 是什么让每个节点唯一的是(parent_id,attrs ...)
    • 意味着在树中的多个位置中可以存在重复的节点
  • 节点仅添加或标记为过时

任何建议都非常感谢!

英文原文

I deal with several trees that can vary in size (they all have depths of ~8-10) but it's not unusual for them to consist of ~50-100k nodes.

At the moment, the trees are stored using simple parent_id FKs.

A tree is created/generated in a program, and then it needs to be saved in the database. The catch is that we cannot just wipe the previous tree (of the same type, if one exists), we need to update it to reflect the new (changed) tree. Occasionally this means swapping the entire tree (if the root changed), but a lot of the time it just means minor changes here and there (e.g. add some children/sub-trees, retire others). We also do not delete old children (and their children), they just get marked as old.

The way updates/verifications are done is by traversing through the tree (depth-first) and checking each node one-by-one.

One of the performance issues is that it can take almost 2 minutes to just verify that a tree (~50k nodes) in the db is the same as the one in the program (since it involves n selects where n is the number of total nodes).

While utilizing an ltree structure could be beneficial in terms of reads, I don't think it would solve this issue (inserting/updating/verifying a tree).

I'm not sure what the best way to optimize this is. One idea I had was to calculate and store a hash of every sub-tree, and that way it could potentially speed things up in most cases since it would know what parts of the tree that doesn't need touching. The hash calculation should be pretty fast and can be parallelized in the program, where the workload is easier to manage. However, perhaps there is some other way that I'm missing?

Bulk inserts etc. are impossible since the tree relies on recursive relationships.

Furthermore, the database is naturally in the cloud, which means that these thousands of queries being executed one-by-one probably incur quite a bit of time just in terms of latency (both the program and the db are on AWS so the latency is small, but still exists of course). A part of me wants to bulk insert the newly generated tree into some temporary table and then write a DB function that syncs it into the actual table.

General structure/schema of a tree:

  • Each node has an id and a parent_id column (nullable FK to id)
  • The root node has parent_id=NULL
  • What makes each node unique is (parent_id, attrs...)
    • Meaning that duplicate nodes can exist in multiple places in the tree
  • Nodes are only added or marked as obsolete

Any advice is much appreciated!

           

回答列表

0
 
vote

看起来更有效地将树的新状态与旧状态一起转移到基座中,然后将它们与单个CTE进行比较。

这是一种我在 varchar8 中使用的方法,但我希望 varchar9 允许与次要更改相同:

  enum0  

结果,您将获得这样的表:

  enum1  

使用的最终选择可用于仅滤除更改/添加/删除的节点。然后,您可以修改旧树结构或记录更改或其他。

 

It's look like that is more efficient to dump the new state of the tree into the base along with the old state and then compare them with a single CTE.

Here is an approach I've used in the MariaDB but I hope PostgreSQL allows the same with minor changes:

WITH RECURSIVE     old_tree (dpth, id, parent_id, attr1, attr2 ...) AS (       SELECT 1, t.*, a.*                          -- initial portion         FROM trees  AS t                          -- the table containing all the trees         JOIN attrs  AS a ON a.node_id = t.id      -- attributes for node        WHERE t.id = 1234                          -- root node for the old tree       UNION ALL       SELECT o.dpth+1, t.*, a.*                   -- recurrent portion         FROM old_tree AS o                        -- this is recursive CTE         JOIN trees    AS t ON t.parent_id = o.id  -- childs of the nodes already fetched          JOIN attrs    AS a ON a.node_id = t.id    -- attributes for node(s)       ),      new_tree (dpth, id, parent_id, attr1, attr2 ...) AS (       SELECT 1, t.*, a.*                          -- all the same for the new_tree         FROM trees  AS t                                   JOIN attrs  AS a ON a.node_id = t.id              WHERE t.id = 4567                          -- root node for the new tree       UNION ALL       SELECT n.dpth+1, t.*, a.*                                             FROM new_tree AS n                        -- this is recursive CTE too         JOIN trees    AS t ON t.parent_id = n.id           JOIN attrs    AS a ON a.node_id = t.id           ) SELECT ot.*, nt.*                     -- should be aliased to avoid ambiguity   FROM            old_tree AS ot    /* there is no FOJ in mysql/mariadb but I've used it to be more clear */   FULL OUTER JOIN new_tree AS nt  ON nt.attr1 = ot.attr1 -- or any other node identifier(s)                                  AND nt.dpth = ot.dpth   -- and by same depth of recursion ; 

As a result you'll get the table like that:

+------+------+------+------+------+------+------+------+ |  oid | opid | oat1 | oat2 |  nid | npid | nat1 | nat2 | +------+------+------+------+------+------+------+------+ | 1234 | NULL |    X |    x | 4567 | NULL |    X |    x | -- unchanged | 1235 | 1234 |    Y |    y | NULL | NULL | NULL | NULL | -- deleted | NULL | NULL | NULL | NULL | 4568 | 4567 |    A |    B | -- added | 1357 | 1234 |    Q |    a | 9876 | 4567 |    Q |    z | -- modified | .... | .... | .... | .... | .... | .... | .... | .... | 

The final SELECT of the WITH can be used to filter out only changed/added/deleted nodes. Then you can modify the old tree structure or log the changes or else.

 
 
         
         

相关问题

4  在Postgres触发器中分配给新键  ( Assign to new by key in a postgres trigger ) 
在触发器体中,如何将值分配给 NEW 的字段名称? 这就是我想做的: some_key = "some_column"; NEW[some_key] = 5; ...

0  PostgreSQL使用从SELECT开始或使用中选择的数据?  ( Postgresql utilize data from select in begin or use with ) 
我通过了文档为9.3 ,没有查找任何建议我可以或不能在 BEGIN 查询中使用来自 SELECT 查询的数据。是否可能或者我必须求助于 WITH 查询某种类型? 我正在尝试将两个查询合并到单个 BEGIN 查询中,以弄清楚如何在向数据库执行查询时更高效。我有另一个项目这个兔子落后于我建立了一个快速重复表的工具的工具(...

0  大中查询所需的性能改进  ( Performance improvement needed for query with large in ) 
我有一个相对简单的表: CREATE TABLE t_balances ( f_index BIGINT NOT NULL ,f_epoch BIGINT NOT NULL ,f_balance BIGINT NOT NULL ); CREATE UNIQU...

2  在一个字段中显示带有非唯一值的行  ( Show rows with non unique value in one field ) 
我熟悉如何聚合行,如此答案所示: 仅显示重复值 我也熟悉如何使用具有vall子句过滤聚合结果。 我似乎无法掌握(以至于它粘)是如何基于值或比较其他行的行,没有聚合它们。 我知道答案涉及关于窗口函数或窗口条款的东西,实际上我之前已经成功完成了。但似乎并不粘在我的脑海中如何工作;我觉得我错过了一些根本的东西。 给...

2  每项值的重复[复制]  ( Numerate duplicate of every value ) 
这个问题已经在这里有答案: 用升值列更新列 (2个答案) 关闭 20天前。...

1  在PostgreSQL中优化查询,它试图匹配字符串并匹配时间戳范围  ( Optimizing query in postgresql that tries to match a string and matches a timest ) 
我在PostgreSQL中构建了一个数据库,用于财务数据,表格如下所示: create table fin_data( brokerid text, stock int, holding bigint, stake float, value bigint, ...

3  更改默认权限中的错误  ( Error in alter default privileges ) 
我正在尝试在aws aurora postgres db中创建一个新用户。 创建用户工作正常,我可以使用该帐户登录DB。 授予它的权限不是。 首先: GRANT ALL on ALL tables in schema public to username 返回: ERROR: permission d...

16  PostgreSQL中的(x不为null)vs(不是x为null)  ( X is not null vs not x is null in postgresql ) 
为什么 information_schema3 不等于 information_schema4 ? 本代码: information_schema5 给出以下输出: information_schema6 虽然我希望得到这个输出: information_schema7 ...

0  由于SQL_IDENTIFIER数据类型,无法升级到v12  ( Cannot upgrade to v12 due to sql identifier data type ) 
我试图在AWS RDS实例上升级Postgres 11.8至12.3。升级失败了以下错误: 您的安装包含用户表中的"SQL_IDENTIFIER" 数据类型 和/或索引。此数据类型的磁盘格式已更改,因此此 群集当前不能升级。您可以删除问题表或 将数据类型更改为"名称" 并重新启动升级。 问题列列表位于文件中: ta...

1  postgres row_to_json数字类型的精度  ( Postgres row to json precision for numeric type ) 
我正在使用row_to_json函数将表行转换为JSON对象。 表中有几列是 numeric 的类型为 abcdefghijklmn0 。 当Row_to_json返回JSON时,如9.98变为9.98000000000000043或6.30在这些数字列中变为6.2999999999999982。 是否有一种方法可...

1  搜索阵列性能?  ( Searching in array performance ) 
我们有一个的表 id|school_id|parent_ids 其中 parent_ids 是一个ID数组。 如果我们没有 school_id 并且只有 parent_id 来搜索,那么查询将通过 parent_ids 数组,可能存在数千行,而 parent_id 实际上可能在其中的少数内。 在此情况下,阵...

6  Postgres程序的测试驱动设计  ( Test driven design for postgres procedures ) 
我正在寻求介绍一个测试驱动设计样式,用于编写我的存储过程的POSTGRESQL数据库实现。 我已经看到 pgtap 是postgres的流行单元测试工具,正确允许测试用sql写成,而不是外部建造和运行。 为了走到全距离我还希望能够使用测试双打(存根,模拟,假,假),也许甚至可以支持运行和重构的IDE支持(像 tsql...

0  Windows的任何PostgreSQL版本是否支持自动更新?  ( Do any of the postgresql releases for windows support automatic updates ) 
postgreSQL有两个用于Windows的分布, Enterprisedb Bigsql 这些Windows发行版中的任何一个支持支持支持的自动更新?寻找在线更新的东西,下载它们,并安装它们。 ...

-3  隐藏维护用户的业务数据  ( Hide business data from maintenance user ) 
我是新手的postgres,有一个问题: 我们有一些关于postgres上超级安全敏感数据的客户,他们不想向任何人展示。但有时,应用程序的统计或其他原因不太新的应用程序。 问题:如何在没有实际业务数据访问的情况下维护性能?我的意思是特定的功能: 如何运行"分析" , 在另一个用户的表中'解释分析' 没有超级用户权...

1  用postgres_fdw(外国数据包装器)分析PostgreSQL  ( Sharding postgresql with postgres fdw foreign data wrapper ) 
我们希望通过租户(客户端ID)将单个PostgreSQL 10.2数据库分离给多个服务器。最简单的方法之一是使用外国数据包装器(Postgres_fdw扩展)。 它看起来像: 我们有一个"主机" 和具有相同架构的几个数据节点。主节点具有日志表,替换为视图。视图由外国表格的工会组成。查看要对特定服务器的转发操作进行插入...




© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有


Licensed under cc by-sa 3.0 with attribution required.