서브 폴더에있는 누적 파일 수

Question

파일 목록이있는 테이블이 있습니다.

이

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

내가 알고 싶습니다

, 많은 파일이 각 폴더 (현재 폴더 포함)의 모든 하위 폴더에 얼마나 (wigh 주어진 폴더를 시작) : id_folder, id_parrent_folder, 크기 (파일 크기)이 있습니다. 데이터

id_folder  files 
100623   35 
100624   14 

샘플 : 나는 PostgreSQL을 (postgresql docs)에서 예제를 사용하려고했습니다

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); 

있지만 (명백하게)는 할 수없는 나는 다음과 같은 출력을 기대할 아래 samle 데이터를 게시 감안할 때 이런 식으로 일하십시오. 어떤 도움을 주셔서 감사합니다.

- 편집 나는 다음과 같은 쿼리를 시도했습니다

:

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

매우 좋은 문제에 대해 생각하고, 나는 upvoted!

1. 다단계 경로 및
2. 멀티 자식 노드 :

   내가보기로

   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 스크립팅에 능숙).

다음 표가 생성되었다 :

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 항목이 있습니다. 업로드 후, 다음을 실행 한 :이 데이터를 처음으로 쿼리를 실행하려고하고 aprx 1 시간 후 죽일 했어

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; 

. 개선 된 방법은 파일 시스템에서 작업을 수행하기 위해 2 분 (MBP에서) 걸립니다. 여기에 온다 :

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; 

쿼리 내 테이블 이름을 사용하지만이를 변경 어렵지 않을 것이다. fs_tree에있는 file_id에 대한 그룹 집합을 만듭니다.

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

일부 노트 : 원하는 출력을 얻으려면, 당신은 뭔가를 할 수있는 중복 거기없는 경우

1. 쿼리 만을 작동합니다. 나는 그것이 옳은 길이라고 생각한다. 왜냐하면 하나의 디렉토리에 똑같이 2 개의 엔트리를 갖는 것은 불가능하기 때문이다.
2. 쿼리는 성능에 영향을 미치지 만 트리의 깊이 또는 형제 수를 고려하지 않습니다.
3. 제게는 비슷한 기능이 작업 계획 시스템에도 필요하기 때문에 좋은 경험이었습니다.
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; 

, 당신은 Materialized Views 및 사전 계산을 구현할 수 있습니다 일부 측정 항목.나는 약간 문을 만들 업데이트했는지,

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); 

주 :

---

샘플 데이터

다음은 테이블 내부의 데이터를 표시하는 작은 덤프입니다.

#!/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() 

이 스크립트는 파이썬 3.2과 official python documentation의 예를 기반으로합니다

는 그리고 이것은 내가 파일 시스템을 검사하는 데 사용 한 스크립트입니다.

희망 사항은 다음 사항을 설명합니다.

Answer 2

샘플 데이터를 사용하면 원하는 결과를 얻을 수 있습니다. 이 내용은 (때문에 id_parent_folder = 100623의하지만 하나의 계층 구조를 포함 http://sqlfiddle.com/#!12/bb942/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 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 데모입니다 : 나는 당신의 트리에서 가능한 모든 이상을 충당 할 수 있지만 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_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; 

.