What is the most efficient way to store and query trees?

Question

I need to analyze 1 TB+ of web access logs, and in particular I need to analyze statistics relating to requested URLs and subsets of the URLs (child branches). If possible, I want the queries to be fast over small subsets of the data (e.g. 10 million requests).

For example, given an access log with the following URLs being requested:

/ocp/about_us.html
/ocp/security/ed-209/patches/urgent.html
/ocp/security/rc/
/ocp/food/
/weyland-yutani/products/

I want to do queries such as:

• Count the number of requests for everything 'below' /ocp.
• Same as above, but only count requests for child nodes under /ocp/security
• Return the top 5 most frequently requested URLs.
• Same as above, except group by an arbitrary depth,

e.g. For the last query above, depth 2 for the data would return:

2: /ocp/security/
1: /ocp/
1: /ocp/food/
1: /weyland-yutani/products/

I think the ideal approach would probably be to use a column DB and tokenize the URLs such that there is a column for each element in the URL. However, I would really like to find a way to do this with open source apps if possible. HBase is a possibility, but query performance seems too slow to be useful for real-time queries (also, I don't really want to be in the business of re-implementing SQL)

I'm aware there are commercial apps for doing this this type of analytics, but for various reasons I want to implement this myself.

Answer 1

Before investing too much time into designing a hierarchical data structure on top of a relational database, consider reading "Naive Trees" section (starting at slide 48) in the excellent presentation SQL Anti-Patterns Strike Back by Bill Karwin. Bill outlines the following methods for developing a hierarchy:

1. Path enumeration (slide 55)
2. Nested sets (slide 58)
3. Closure table (slide 68)

Answer 2

Trees are generally not very efficient in databases. I mean: if you'd design the tree to be truly recursive, with items pointing to their parents, you'll get lots of queries to find all sub-nodes.

But you can optimize the tree, according to your needs.

Put any part of the url into a column is not a bad idea. You need to limit the depth to a certain number of sub-nodes. You could have indexes on any column, which makes it very fast.

Queries on such a structure are very simple:

Select count(*) From Hits where node1 = 'ocp' AND node2 = 'security';

Make a access statistic:

SELECT node1, node2, count(*) as "number of hits"
FROM hits 
GROUP BY node1, node2
ORDER BY count(*) DESC

you'll get

node1            node2        number of hits
'ocp'                        23345
'ocp'            'security'   1020
'ocp'            'food'        234
'weyland-yutani' 'products'     22

You could also store the url as it is and filter using regex. This is more flexible, but slower, because you don't have indexes. You need only to limit the whole length of the url, not the number of sub-nodes.

I think you could do this with any database good enough to store large amount of data. For instance MySql.