5

I have a table which contains folders' paths. This table contains four columns:

  • DirID - The folder's ID.
  • BaseDirID - The ID of the first folder in the hierarchy. So all the folders (paths) from the same hierarchy share the same value in this column.
  • DirLevel - The depth of the folder.
  • DisplayPath - The folder's path.

I need to find all the "gaps" between those folders in the hierarchy.

Sample data for example:

DirID BaseDirID DirLevel DisplayPath
1         1        1     'A'
2         1        3     'A\B\C'
3         1        5     'A\B\C\D\E'
4         1        3     'A\B\F'
5         1        5     'A\B\F\G\H'
6         2        1     'U'
7         2        3     'U\V\W'
8         2        5     'U\V\W\X\Y'
9         2        3     'U\V\M'
10        2        5     'U\V\M\L\O'

So we need to find the following data:

BaseDirID   DisplayPath
1           'A\B'
1           'A\B\C\D'
1           'A\B\F\G'
2           'U\V'
2           'U\V\W\X'
2           'U\V\M\L'

Comments:

  1. This table contains more than 250,000 records of folders, so we seek for the most efficient way to do so, otherwise, the script will be stuck for a long time, the time we don't have.
  2. I don't have the list of all folders. What I have are the "root" folders and the "leafs" folders which I need to find the "gaps" between them in the hierarchy.
  3. The table can contain more than one hierarchy and we need to find the "gaps" in all of the hierarchies.
  4. Each of the hierarchies can split, as you can see in the sample data the first hierarchy splits to two folders paths from the 'A\B' folder: 'A\B\C' and 'A\B\F'. And the second hierarchy splits to two folders paths from the 'U\V' folder: 'U\V\W' and 'U\V\M'. And we need to find all the "gaps" even in such cases when the hierarchies split.
  5. We can make any changes to the table - add pk, indexes etc...
  6. The SQL Server version is 2012 SP3.
  7. The real folder names could be anything - one character or more.
  8. The results must only contain the "gaps".
  9. All missing intermediate folders are required.

Extended sample data and expected results in this dbfiddle.

This question is a continuation of the Stack Overflow question Find missing hierarchy Folders (Paths) in a table. Our question includes also the 4th comment which appears in bold.

I saw that there is a new type called hierarchyid (starting from SQL Server 2008), which I thought might help us. What do you think?

0
5

I'd try something like this:

  • First, create a new table and copy the existing data there.
  • Then iterate, and in each iteration, remove the last node of each filepath (e.g.: 'A\B\C\D\E' becoming 'A\B\C\D') and add these new filepaths in the table, if they aren't already there.
  • Stop when an iteration doesn't produce new rows.

The initialization:

-- step 0
CREATE TABLE filepaths
  ( BaseDirID int NOT NULL,
    DirLevel int NOT NULL,
    DisplayPath varchar(1000) NOT NULL,   -- adjust the size according to your data,
    ReverseDisplayPath varchar(1000) NOT NULL,
    Iteration int NOT NULL,
    PRIMARY KEY (Iteration, ReverseDisplayPath),
    UNIQUE (ReverseDisplayPath)
  ) ;

INSERT INTO filepaths
  ( BaseDirID, DirLevel, DisplayPath, ReverseDisplayPath, Iteration )
SELECT
    BaseDirID, DirLevel, DisplayPath, reverse(DisplayPath), 0
FROM 
    existing_table ;

And the iterations:

DECLARE @new_items bigint ;
DECLARE @iter int ;
SET @iter = 0 ;

-- repeat
repeat:     
    INSERT INTO filepaths
        (BaseDirID, DirLevel, DisplayPath, ReverseDisplayPath, Iteration)
    SELECT DISTINCT
        f.BaseDirID, f.DirLevel - 1, reverse(r.rdp), r.rdp, @iter + 1
    FROM 
        filepaths AS f
      CROSS APPLY
        ( SELECT substring(f.ReverseDisplayPath, 
                           1 + charindex('\', f.ReverseDisplayPath), 
                           1000) AS rdp
        ) AS r
    WHERE 
          f.Iteration = @iter
      AND f.DirLevel > 1 
      AND NOT EXISTS
          ( SELECT *
            FROM filepaths AS ex
            WHERE ex.ReverseDisplayPath = r.rdp
          ) ;
    SET @new_items = @@ROWCOUNT ;

    SET @iter = @iter + 1 ;
    -- until new_items = 0
    IF (@new_items > 0) GOTO repeat; 

After the process is finished, you can get only the missing filepaths with a simple query:

SELECT DisplayPath FROM filepaths 
WHERE Iteration > 0 
ORDER BY DisplayPath ;

Tested in dbfiddle.uk.

The reverse strings are not strictly needed but they simplify the splitting of the strings. You could go without them (and a bit more complex code). You could also have only the reverse paths stored in the new filepaths table and when the iterations are complete, reverse them again into the target table (the existing one I guess or wherever you want them to go).

The whole thing could also be done with a single pass - using a recursive CTE - but I don't know if that would be more or less efficient.

5
  • The results must only contain the "gaps" and not the entire folders (existing folders and missing folders combined). – Nuriel Zrubavely May 18 '17 at 7:24
  • The DisplayPath (and 'ReverseDisplayPath' column) is of type 'nvarchar(608)' - we support multiple languages. is it a problem? Since when creating the table I got warnings: 'Warning! The maximum key length is 900 bytes. The index 'PK__FilePath__1FB056E71650D123' has maximum length of 1220 bytes. For some combination of large values, the insert/update operation will fail.' 'Warning! The maximum key length is 900 bytes. The index 'UQ__FilePath__4CE3FD7BF7C51663' has maximum length of 1216 bytes. For some combination of large values, the insert/update operation will fail.' – Nuriel Zrubavely May 21 '17 at 10:20
  • You could run it without any indexes on the varchar columns - only on (iteration) - but it would probably hurt performance. – ypercubeᵀᴹ May 21 '17 at 10:24
  • And anyway, I don't know if performance is something you worry about too much. Isn't this something that you only need to do once? – ypercubeᵀᴹ May 21 '17 at 10:27
  • Its runs like 100 times a day :) – Nuriel Zrubavely May 21 '17 at 11:58
3

As far as you need all intermediate folders, I'd suggest a CURSOR solution.

CREATE TABLE #Gaps (BaseDirID int, Path VARCHAR(2048));

DECLARE @BaseDir int, @LastPath VARCHAR(2048), @DisplayPath VARCHAR(2048);
DECLARE @p1 VARCHAR(2048), @p2 VARCHAR(2048);

DECLARE curG CURSOR FAST_FORWARD FOR
    SELECT BaseDirID, DisplayPath
           , LAG(DisplayPath) 
                   OVER (PARTITION BY BaseDirID ORDER BY BaseDirId, DirId) LastPath
    FROM   paths;

OPEN curG;

FETCH NEXT FROM curG INTO @BaseDir, @DisplayPath, @LastPath

WHILE @@FETCH_STATUS = 0
BEGIN

    IF LEFT(@DisplayPath, LEN(@LastPath)) =  @LastPath
    BEGIN
        SET @p1 = @LastPath;
        SET @P2 = @DisplayPath
        WHILE CHARINDEX('\', @p2, LEN(@p1)+2) > 0
        BEGIN
            SET @p1 = SUBSTRING(@p2, 0, CHARINDEX('\', @p2, LEN(@p1)+2))
            INSERT INTO #Gaps VALUES (@BaseDir, @p1);
        END
    END

    FETCH NEXT FROM curG INTO @BaseDir, @DisplayPath, @LastPath

END

CLOSE curG;
DEALLOCATE curG;

SELECT * FROM #Gaps;
GO
BaseDirID | Path                                                                                   
--------: | :--------------------------------------------------------------------------------------
        1 | A\B                                                                                    
        1 | A\B\C\D                                                                                
        1 | A\B\F\G                                                                                
        2 | U\V                                                                                    
        2 | U\V\W\X                                                                                
        2 | U\V\M\L                                                                                
        3 | 35C9CA71\6D28                                                                          
        3 | 35C9CA71\6D28\4A42                                                                     
        3 | 35C9CA71\6D28\4A42\9F45\34EC6EACAB08                                                   
        3 | 35C9CA71\6D28\4A42\9F45\34EC6EACAB08\488CEA3F                                          
        3 | 35C9CA71\6D28\4A42\9F45\34EC6EACAB08\488CEA3F\003E\4C2A                                
        3 | 35C9CA71\6D28\4A42\9F45\34EC6EACAB08\488CEA3F\003E\4C2A\BE20                           
        3 | 35C9CA71\6D28\4A42\9F45\34EC6EACAB08\488CEA3F\003E\4C2A\BE20\B7F1A36A6895\67A89AC5     
        3 | 35C9CA71\6D28\4A42\9F45\34EC6EACAB08\488CEA3F\003E\4C2A\BE20\B7F1A36A6895\67A89AC5\2C83

dbfiddle here

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.