Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I'm looking to crawl a lot of webpages (500,000,000,000) records and be able to store the linking structure for a later date. The way I planned on laying out the database was as follows:

2 Tables

Table: Pages

ID            URL - Max Length = 2048 chars
----------    -------------------------------
1             http://www.site1.com/page.php
2             http://www.site2.com/page-abc.php
3             http://www.site3.com/page-1.php
4             http://www.site4.com/page-cd.php
5             http://www.site5.com/page-nice.php
6             http://www.site6.com/page-some.php
7             http://www.site7.com/page-hrmm.php
8             http://www.site8.com/page-stack.php
9             http://www.site9.com/page-ex.php
10            http://www.site10.com/page-dba.php

Table: Links

Page          Links
----------    -------------------------------
2             1
3             1
4             1
5             1
6             1
7             1
8             1
8             9
9             1
10            1

Basically I'll be able to see what webpages link to where recurrently/several levels deep per website. I want to map a large network of websites and their linking patterns.

So I need to know if there is a better way of doing so, and maybe some suggestions on how to design the database structure/system. I was planning on PostgreSQL to start with since I've used it some, but with this amount of data I'm open to anything.

share|improve this question
2  
Not sure I'm tracking 1) what is the question and 2) What the tables are representative of. –  ETL Feb 26 '13 at 17:38
    
Added more detail. –  Jerry Tunin Feb 26 '13 at 17:41
3  
You should think really hard about data types and such for this as well. With 500b rows an extra byte per row is 465 GB. Your total data size is 19 TB just for 500b records in Table 1, assuming 32 characters average for your url (and not using unicode) –  JNK Feb 26 '13 at 18:01
    
500 billion rows? If you're trying to build a new Google, are you prepared to invest Google-like resources? Anyway, I agree with @ETL - what's the question? –  Aaron Bertrand Feb 26 '13 at 18:03
1  
It's not really a Google type project as there won't be any indexing or searching. But I would like to make the data freely available and accept donations for the project. –  Jerry Tunin Feb 26 '13 at 18:09
show 4 more comments

2 Answers 2

up vote 6 down vote accepted

To reduce space requirements you might consider a few things:

  1. Not bothering to store http:// or the leading www. - this is just wasted space (though in a few cases the www. is required because people don't know how to configure their web sites properly).
  2. Making sure you use data compression. Most systems are still I/O-bound, not CPU-bound.
  3. Only storing any domain name once, and storing the page URLs separately. Both may actually repeat and storing them multiple times is wasteful. So for example instead of:

    CREATE TABLE dbo.Pages
    (
      ID BIGINT IDENTITY(1,1) PRIMARY KEY, -- need BIGINT for 500 billion rows
      URL VARCHAR(2048) -- far too large to apply UNIQUE
    );
    
    CREATE TABLE dbo.PageLinks
    (
      PageID BIGINT NOT NULL FOREIGN KEY REFERENCES dbo.Pages(ID),
      LinkID BIGINT NOT NULL FOREIGN KEY REFERENCES dbo.Pages(ID),
      PRIMARY KEY (PageID, LinkID)
    );
    

    You could do something like this:

    CREATE TABLE dbo.Domains
    (
      DomainID INT IDENTITY(1,1) PRIMARY KEY, -- probably no more than 2BN domains
      DomainName VARCHAR(255) NOT NULL
    ) WITH (DATA_COMPRESSION = PAGE);
    
    CREATE UNIQUE INDEX dn ON dbo.Domains(DomainName)
      WITH (DATA_COMPRESSION = PAGE);
    
    CREATE TABLE dbo.URLs
    (
      URLID INT IDENTITY(1,1) PRIMARY KEY, -- maybe you need BIGINT here
      URL VARCHAR(2048) NOT NULL -- still can't apply UNIQUE here
      -- but you can have the same URL (e.g. /page.php) from two different 
      -- domains only listed once.
    );
    
    CREATE TABLE dbo.DomainURLs
    (
      DomainURLID INT IDENTITY(1,1) PRIMARY KEY, -- may also need BIGINT here
      DomainID INT NOT NULL FOREIGN KEY REFERENCES dbo.Domains(DomainID),
      URLID INT NOT NULL FOREIGN KEY REFERENCES dbo.URLs(URLID)
    ) WITH (DATA_COMPRESSION = PAGE);
    
    CREATE UNIQUE INDEX du ON dbo.DomainURLs(DomainID, URLID)
      WITH (DATA_COMPRESSION = PAGE);
    

    Yes, table design and query semantics will be much more complex, but it will scale much better once you index many pages on the same site (or many pages with the same URL across different sites).


Just to demonstrate the potential for space savings here. Taking just the storage of the URLs and ignoring the links between them, let's look at just the Pages, Domains and URLs tables (and to be fair, I'll even test your pages table with compression).

Note that we take advantage of the fact that you will probably index each site in turn, alphabetically, rather than hash and index random URLs each iteration. This allows compression to work as well as possible in this case.

For some sample data, on my system this generates about 121,000 rows, but that will vary depending on a lot of factors, such as how many databases are on your system, how many objects in your database, the design of any non-system objects (e.g. number of columns), and even @@VERSION:

;WITH x AS 
(
  SELECT 
    d = t.name + CONVERT(VARCHAR(5), d.database_id) + '.com', 
    p = '/' + c.name + '.php'
   FROM sys.all_objects AS t
   CROSS JOIN sys.databases AS d
   INNER JOIN sys.all_columns AS c
   ON t.[object_id] = c.[object_id]
 )
 SELECT d, p 
 FROM x
 ORDER BY d, p;

Sample results:

all_columns1.com    /collation_name.php
all_columns1.com    /column_id.php
all_columns1.com    /default_object_id.php
all_columns1.com    /is_ansi_padded.php
all_columns1.com    /is_column_set.php
...

Now let's use that to populate our four tables:

;WITH x AS 
(
  SELECT 
    d = t.name + CONVERT(VARCHAR(5), d.database_id) + '.com', 
    p = '/' + c.name + '.php'
   FROM sys.all_objects AS t
   CROSS JOIN sys.databases AS d
   INNER JOIN sys.all_columns AS c
   ON t.[object_id] = c.[object_id]
 )
 SELECT d, p 
 INTO #blat
 FROM x
 ORDER BY d, p;

 CREATE CLUSTERED INDEX x ON #blat(d, p);

 INSERT dbo.Pages(URL) SELECT 'http://www.' + d + p FROM #blat ORDER BY d, p;

 INSERT dbo.Pages_compressed(URL) SELECT 'http://www.' + d + p FROM #blat ORDER BY d, p;

 INSERT dbo.Domains(DomainName) SELECT DISTINCT d FROM #blat ORDER BY d;

 INSERT dbo.URLs(URL) SELECT DISTINCT p FROM #blat;

Now of course you would have to build the junction table here by cross-referencing the Domains and the URLs. But this will still show how much space you can save by not storing the same domain name or page name twice, even if it means more complicated logic to put these things together:

EXEC sp_spaceused 'dbo.Pages';            -- 8,904 KB
EXEC sp_spaceused 'dbo.Pages_compressed'; -- 4,552 KB
EXEC sp_spaceused 'dbo.Domains';          --   656 KB
EXEC sp_spaceused 'dbo.URLs';             --   136 KB

That's with 121,000 URLs. For 500 billion? Let's extrapolate. Per complete URL, without compression, you are storing about 73 bytes. With compression, 38 bytes per URL. My method: 6.5 bytes per URL. (Discard, for a moment, how unrealistic my sample data is. Let's pretend I've come somewhere close to the average URL length, and that both (a) you will be indexing many URLs on every domain and (b) you will get duplication of page paths across many domains.)

So ignoring those realities, simple math shows more than 90% reduction in storage space between your uncompressed method and my method:

Your method, uncompressed = 33.2 TB
Your method, compressed   = 17.1 TB
My method                 =  2.9 TB

And again, it's more complicated, so more work up front, but usually this is worth it. You only design the schema and write the code around it once; you'll be maintaining this for, well, how long do you expect the service to exist?

share|improve this answer
    
Well if it supports itself, indefinitely. After reading through what you've stated I got to thinking. You could use the same approach for directories as well. A lot of sites use the same permalink structure such as Wordpress: example.com/yyyy/mm/dd/post-name You could possibly just save the /yyyy/mm/dd/ if they are common. –  Jerry Tunin Feb 26 '13 at 21:36
    
@Jerry on an individual site, I doubt the whole pattern would be common (I don't ever write multiple posts on the same day, and I doubt very many do), but you could break it down by year or year and month and get some reuse. Depends on how many levels deep you want the reuse to go. I suppose across the entire Internet every valid y/m/d combination will be used at least twice (and possibly some invalid ones too). –  Aaron Bertrand Feb 26 '13 at 21:50
add comment

What you have seems fine. But maybe you want to look at existing solutions instead of rolling out your own (e.g. http://www.peachpit.com/articles/article.aspx?p=454165 - might not be suitable for the size but just saying).

Unless you want to do more than just that, I don't see anything wrong or other ways really of doing it.

share|improve this answer
2  
500b records in visio seems unlikely to me... –  JNK Feb 26 '13 at 18:04
    
@JNK: No? Can't Visio do that? That page promises it can do it in minutes. –  ypercube Feb 26 '13 at 18:21
    
@ypercube Oh it's Visio 2003 ;) –  JNK Feb 26 '13 at 18:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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