sql - サブフォルダー内の累積ファイル数

Question

ファイルのリストを含むテーブルがあります。id_folder、id_parrent_folder、size（ファイルサイズ）があります：

create table sample_data (
    id_folder bigint ,
    id_parrent_folder bigint,
    size bigint
);

各フォルダー（特定のフォルダーから始まる）のすべてのサブフォルダー（現在のフォルダーを含む）にいくつのファイルがあるかを知りたいです。以下に投稿されたサンプルデータを考えると、次の出力が期待されます。

id_folder     files
100623           35
100624           14

サンプルデータ：

insert into sample_data values (100623,58091,60928);
insert into sample_data values (100623,58091,59904);
insert into sample_data values (100623,58091,54784);
insert into sample_data values (100623,58091,65024);
insert into sample_data values (100623,58091,25600);
insert into sample_data values (100623,58091,31744);
insert into sample_data values (100623,58091,27648);
insert into sample_data values (100623,58091,39424);
insert into sample_data values (100623,58091,30720);
insert into sample_data values (100623,58091,71168);
insert into sample_data values (100623,58091,68608);
insert into sample_data values (100623,58091,34304);
insert into sample_data values (100623,58091,46592);
insert into sample_data values (100623,58091,35328);
insert into sample_data values (100623,58091,29184);
insert into sample_data values (100623,58091,38912);
insert into sample_data values (100623,58091,38400);
insert into sample_data values (100623,58091,49152);
insert into sample_data values (100623,58091,14444);
insert into sample_data values (100623,58091,33792);
insert into sample_data values (100623,58091,14789);
insert into sample_data values (100624,100623,16873);
insert into sample_data values (100624,100623,32768);
insert into sample_data values (100624,100623,104920);
insert into sample_data values (100624,100623,105648);
insert into sample_data values (100624,100623,31744);
insert into sample_data values (100624,100623,16431);
insert into sample_data values (100624,100623,46592);
insert into sample_data values (100624,100623,28160);
insert into sample_data values (100624,100623,58650);
insert into sample_data values (100624,100623,162);
insert into sample_data values (100624,100623,162);
insert into sample_data values (100624,100623,162);
insert into sample_data values (100624,100623,162);
insert into sample_data values (100624,100623,162);

postgresql ( postgresql docs ) の例を使用しようとしましたが、(明らかに) この方法では機能しません。どんな助けでも感謝します。

- 編集

次のクエリを試しました。

WITH RECURSIVE included_files(id_folder, parrent_folder, dist_last_change) AS (
SELECT 
    id_folder, 
    id_parrent_folder, 
    size
FROM 
    sample_data p 
WHERE 
    id_folder = 100623
UNION ALL
SELECT 
    p.id_folder, 
    p.id_parrent_folder, 
    p.size
FROM 
    included_files if, 
    sample_data p
WHERE 
    p.id_parrent_folder = if.id_folder
)
select * from included_files

すべての子には多くの親があり、その結果、子フォルダーの行が乗算されるため、これは機能しません。

Answer 1

サンプルデータを使用すると、必要なものが返されます。ただし、ツリー内のすべての可能な異常をカバーするかどうかは 100% わかりません。

with recursive folder_sizes as (
   select id_folder, id_parent_folder, count(*) as num_files
   from sample_data
   group by id_folder, id_parent_folder
), 
folder_tree as (

   select id_folder, id_parent_folder, num_files as total_files
   from folder_sizes
   where id_parent_folder = 100623

   union all 

   select c.id_folder, c.id_parent_folder, c.num_files + p.total_files as total_files
   from folder_sizes c
     join folder_tree p on p.id_parent_folder = c.id_folder

)
select id_folder, id_parent_folder, total_files
from folder_tree;

ここに SQLFiddle のデモがあります: http://sqlfiddle.com/#!12/bb942/2

ただし、これは単一レベルの階層のみをカバーします (id_parent_folder = 100623条件のため)。任意の数のレベルをカバーするには、最初にすべてのサブフォルダーを収集し、次にそのツリーを再度上に移動して、ファイルの総数を計算する 2 段階のアプローチしか考えられません。

このようなもの：

with recursive folder_sizes as (
   select id_folder, id_parent_folder, count(*) as num_files
   from sample_data
   group by id_folder, id_parent_folder
), 
folder_tree_down as (
   select id_folder, id_parent_folder, num_files, id_folder as root_folder, 1 as level
   from folder_sizes

   union all 

   select c.id_folder, c.id_parent_folder, c.num_files, p.root_folder, p.level + 1 as level
   from folder_sizes c
     join folder_tree_down p on p.id_folder = c.id_parent_folder
), 
folder_tree_up as (

   select id_folder, id_parent_folder, num_files as total_files, level
   from folder_tree_down
   where root_folder = 100623

   union all 

   select c.id_folder, c.id_parent_folder, c.num_files + p.total_files as total_files, p.level
   from folder_tree_down c
     join folder_tree_up p on p.id_parent_folder = c.id_folder

)
select id_folder, id_parent_folder, total_files
from folder_tree_up
where level > 1;

これにより、最初のステートメントと同じ出力が生成されますが、無制限の数のレベルで機能するはずです。

Answer 2

考えるのにとてもいい問題です、私は賛成しました！

私が見ているように、考えるべき2つのケース：

1. マルチレベルのパスと
2. 複数の子ノード。

これまでのところ、次のクエリを思いつきました。

WITH RECURSIVE tree AS (
    SELECT id_folder id, array[id_folder] arr
      FROM sample_data sd
     WHERE NOT EXISTS (SELECT 1 FROM sample_data s
                        WHERE s.id_parrent_folder=sd.id_folder)
    UNION ALL
    SELECT sd.id_folder,t.arr||sd.id_folder
      FROM tree t
      JOIN sample_data sd ON sd.id_folder IN (
        SELECT id_parrent_folder FROM sample_data WHERE id_folder=t.id))
,ids AS (SELECT DISTINCT id, unnest(arr) ua FROM tree)
,agg AS (SELECT id_folder id,count(*) cnt FROM sample_data GROUP BY 1)
SELECT ids.id, sum(agg.cnt)
  FROM ids JOIN agg ON ids.ua=agg.id
 GROUP BY 1
 ORDER BY 1;

に次の行を追加しましたsample_data。

INSERT INTO sample_data VALUES (100625,100623,123);
INSERT INTO sample_data VALUES (100625,100623,456);
INSERT INTO sample_data VALUES (100625,100623,789);
INSERT INTO sample_data VALUES (100626,100625,1);

ただし、このクエリは最適ではなく、行数が増えるにつれて速度が低下します。

---

本格試験

元の状況をシミュレートするために、ファイルシステムをスキャンしてデータベースに保存する小さな python スクリプトを作成しました (したがって、遅延が発生しました。python スクリプトはまだ得意ではありません)。

次のテーブルが作成されました。

CREATE TABLE fs_file(file_id bigserial, name text, type char(1), level int4);
CREATE TABLE fs_tree(file_id int8, parent_id int8, size int8);

MBP のファイルシステム全体をスキャンするには 7.5 分かかり、fs_treeテーブルには 870k のエントリがあり、元のタスクと非常によく似ています。アップロード後、以下が実行されました。

CREATE INDEX i_fs_tree_1 ON fs_tree(file_id);
CREATE INDEX i_fs_tree_2 ON fs_tree(parent_id);
VACUUM ANALYZE fs_file;
VACUUM ANALYZE fs_tree;

このデータに対して最初のクエリを実行しようとしましたが、約 1 時間後に強制終了する必要がありました。改善されたものは、ファイルシステム全体でジョブを実行するのに (私の MBP で) 約 2 分かかります。ここに来ます：

WITH RECURSIVE descent AS (
    SELECT fs.file_id grp, fs.file_id, fs.size, 1 k, 0 AS lvl
      FROM fs_tree fs
     WHERE fs.parent_id = (SELECT file_id FROM fs_file WHERE name = '/')
    UNION ALL
    SELECT DISTINCT CASE WHEN k.k=0 THEN d.grp ELSE fs.file_id END AS grp,
           fs.file_id, fs.size, k.k, d.lvl+1
      FROM descent d
      JOIN fs_tree fs ON d.file_id=fs.parent_id
      CROSS JOIN generate_series(0,1) k(k))
/* the query */
SELECT grp, file_id, size, k, lvl
  FROM descent
 ORDER BY 1,2,3;

クエリはテーブル名を使用しますが、変更するのは難しくありません。file_idで見つかった各グループのセットを作成しfs_treeます。目的の出力を得るには、次のようにします。

SELECT grp AS file_id, count(*), sum(size)
  FROM descent GROUP BY 1;

いくつかのメモ:

1. クエリは、重複がない場合にのみ機能します。1 つのディレクトリに同じ名前のエントリを 2 つ持つことは不可能だからです。
2. クエリはツリーの深さや兄弟数を気にしませんが、これはパフォーマンスに影響を与えます。
3. タスク計画システムにも同様の機能が必要なので、私にとっては良い経験でした (私は現在 1 つを使用しています)。
4. タスクが考慮されるため、単一のエントリは複数の親を持つことができ (ただし、そうでない場合は不可)、クエリは引き続き機能します。
5. この問題は、ツリーを昇順にトラバースしたり、事前に計算された値を使用して最終的なグループ化ステップを回避したりするなど、他の方法でも解決できますが、これは単純な質問よりも少し大きくなっているので、演習として生きますあなたのために。

推奨事項

このクエリを機能させるには、データを集計して準備する必要があります。

WITH RECURSIVE
fs_tree AS (
    SELECT id_folder file_id, id_parrent_folder parent_id,
           sum(size) AS size, count(*) AS cnt
      FROM sample_data GROUP BY 1,2)
,descent AS (
    SELECT fs.file_id grp, fs.file_id, fs.size, fs.cnt, 1 k, 0 AS lvl
      FROM fs_tree fs
     WHERE fs.parent_id = 58091
    UNION ALL
    SELECT DISTINCT CASE WHEN k.k=0 THEN d.grp ELSE fs.file_id END AS grp,
           fs.file_id, fs.size, fs.cnt, k.k, d.lvl+1
      FROM descent d
      JOIN fs_tree fs ON d.file_id=fs.parent_id
      CROSS JOIN generate_series(0,1) k(k))
/* the query */
SELECT grp file_id, sum(size) size, sum(cnt) cnt
  FROM descent
 GROUP BY 1
 ORDER BY 1,2,3;

スピードアップするために、具体化されたビューを実装し、いくつかのメトリックを事前に計算できます。

---

サンプルデータ

テーブル内のデータを表示する小さなダンプを次に示します。

INSERT INTO fs_file VALUES (1, '/Users/viy/prj/logs', 'D', 0),
    (2, 'jobs', 'D', 1),
    (3, 'pg_csv_load', 'F', 2),
    (4, 'pg_logs', 'F', 2),
    (5, 'logs.sql', 'F', 1),
    (6, 'logs.sql~', 'F', 1),
    (7, 'pgfouine-1.2.tar.gz', 'F', 1),
    (8, 'u.sql', 'F', 1),
    (9, 'u.sql~', 'F', 1);

INSERT INTO fs_tree VALUES (1, NULL, 0),
    (2, 1, 0),
    (3, 2, 936),
    (4, 2, 706),
    (5, 1, 4261),
    (6, 1, 4261),
    (7, 1, 793004),
    (8, 1, 491),
    (9, 1, 491);

create ステートメントを少し更新したことに注意してください。

ファイルシステムのスキャンに使用したスクリプトは次のとおりです。

#!/usr/bin/python

import os
import psycopg2
import sys
from stat import *

def walk_tree(full, parent, level, call_back):
    '''recursively descend the directory tree rooted at top,
       calling the callback function for each regular file'''

    if not os.access(full, os.R_OK):
        return

    for f in os.listdir(full):
        path = os.path.join(full, f)
        if os.path.islink(path):
            # It's a link, register and continue
            e = entry(f, "L", level)
            call_back(parent, e, 0)
            continue

        mode = os.stat(path).st_mode
        if S_ISDIR(mode):
            e = entry(f, "D", level)
            call_back(parent, e, 0)
            # It's a directory, recurse into it
            try:
                walk_tree(path, e, level+1, call_back)
            except OSError:
                pass

        elif S_ISREG(mode):
            # It's a file, call the callback function
            call_back(parent, entry(f, "F", level), os.stat(path).st_size)
        else:
            # It's unknown, just register
            e = entry(f, "U", level)
            call_back(parent, e, 0)

def register(parent, entry, size):
    db_cur.execute("INSERT INTO fs_tree VALUES (%s,%s,%s)",
                   (entry, parent, size))

def entry(name, type, level):
    db_cur.execute("""INSERT INTO fs_file(name,type, level)
                   VALUES (%s, %s, %s) RETURNING file_id""",
                   (name, type, level))
    return db_cur.fetchone()[0]

db_con=psycopg2.connect("dbname=postgres")
db_cur=db_con.cursor()

if len(sys.argv) != 2:
    raise SyntaxError("Root directory expected!")

if not S_ISDIR(os.stat(sys.argv[1]).st_mode):
    raise SyntaxError("A directory is wanted!")

e=entry(sys.argv[1], "D", 0)
register(None, e, 0)
walk_tree(sys.argv[1], e, 1, register)

db_con.commit()

db_cur.close()
db_con.close()

このスクリプトは Python 3.2 用であり、公式の python ドキュメントの例に基づいています。

これがあなたのために物事を明確にすることを願っています.