## 3 Use Cases of Graphs
### The Naive Algorithm  
Without graphs, the naive algorithm answers _on-demand size_ queries by running SQL queries against the database containing deduplication metadata. In a deduplicated storage system, there is one table that comprises the deduplication metadata: the chunk information table (denoted as \(ChunkTable\)). Among other fields, the query-related fields in \(ChunkTable\) are \(\langle FileID,ChunkLength,ChunkHash\rangle\), where \(FileID\) is the unique file identifier, \(ChunkLength\) is the length of the chunk, and \(ChunkHash\) is the hash value of the chunk for deduplication (e.g., 20-byte MD5 hash value). The naive algorithm, denoted as _Naive_, takes 4 steps to answer _on-demand size_ queries. In the first step, _Naive_ initializes the list of files that meet the filtering criteria as a file table called \(SelectedFiles\). In the second step, it does an SQL JOIN operation on \(SelectedFiles\) and \(ChunkTable\) to select all \(\langle FileID,ChunkLength,ChunkHash\rangle\) tuples for files in \(SelectedFiles\), which results in a table  
\(SelectedChunks\). In the third step, unique chunks in \(SelectedChunks\) are found by an SQL GROUP BY operation. In the final step, the total size of unique chunks are computed by an SQL SUM operation. All queries in these 4 steps are optimized properly. For example, in step 2, the \(SelectedFiles\) table has a cluster index on the \(FileID\) field so that the SQL JOIN operation is efficient. The SQL query for these 4 steps are shown in Figure 12.  
Figure 12: The SQL query of _Naive_ for _on-demand size_ queries. If we assume the number of \(\langle FileID,ChunkLength,ChunkHash\rangle\) tuples is \(N\), the number of selected files is \(S\), the number of chunks in these selected files is \(C\), and the number of unique chunks is \(U\), then the complexity of the _Naive_ algorithm in asymptotic notation is \(O(S+N+C+U)\) given that all involved SQL queries are optimized properly. In particular, step 1 has the complexity of \(O(S)\), step 2 has the complexity of \(O(N)\), step 3 has the complexity of \(O(C)\), and step 4 has the complexity of \(O(U)\). Because the _Naive_ algorithm has to scan all chunk tuples in step 2, it is not scalable to the number of chunks. One has to use alternative methods to avoid scanning all chunk tuples. The proposed graph-based algorithm is such an alternative method, and we will describe the details of the algorithm below. The Graph Algorithm  
As described in Section 2.2, a _DCSG_ graph is created from the deduplication metadata. We use adjacency list to represent edges in the _DCSG_ graph. Each _file_ vertex is assigned a file identifier \(FID\), and each unique _chunk_ vertex is assigned a chunk identifier \(CID\). Note that after deduplication, multiple duplicate chunks map to the same chunk identifier, and we can use the unique chunk identifier to replace the chunk hash value in the algorithm. The _DCSG_ graph consists of 2 parts: the first part is an indexed and ordered list of \(\langle FID,FileSize\rangle\) pairs, and the second part is a per-vertex adjacency list consisting of \(\langle CID,ChunkSize\rangle\) pairs, where \(FileSize\) and \(ChunkSize\) represents file size and chunk size, respectively. We modify the original _DCSG_ graph in two aspects: first, we remove the vertex list of \(CID\)s; second, we add \(ChunkSize\) as one attribute of each edge. On one hand, by removing the \(CID\) list, we do not need to query the per-\(CID\) size from the potentially large \(CID\) list, which can become the performance bottleneck for large number of \(CID\)s. On the other hand, by adding chunk size to each edge, the size of the adjacency lists can double from their original form with only \(CID\)s. Given that we can sequentially load the per-file adjacency list into RAM and the average size of per-file adjacency list is considerably small (_i.e._, \(<\)1 MB), the IO overhead in terms of elapsed time is reasonable (\(<\)\(10\) ms for hard drives). Based on the graph representation, the _Graph_ algorithm proceeds with two steps.