Technique to gather statistics on very large hierarchical collections in a scalable and efficient manner

摘要

Techniques are provided for efficiently collecting statistics for hierarchically-organized collections of data. A database system leverages container-level modification time stamps and stored subtree-level change information to gather statistical information from only those resources in a hierarchical collection for which the statistics have changed since the last time that statistics were gathered for the collection. A lockless data structure is also described for storing the subtree-level change information in which an identifier corresponding to each subtree in a collection containing a changed resource may be stored. This data structure may be a table that is distinct from one or more tables representing the collection. In one embodiment of the invention, the immediate parent resource of a particular modified resource may be omitted from the subtree table by leveraging modification time stamps while gathering statistics based on tracked subtree-level information.

主权项

1. A computer-executed method for gathering statistics from changed subtrees in a hierarchically-organized collection of resources comprising:
after traversing the collection of resources to gather statistics for the collection in connection with a first traversal of the collection that is performed previous to a second traversal of the collection:
in response to detecting a change to a particular resource in the hierarchically-organized collection of resources:
identifying a set of ancestor container resources of the particular resource, andadding, to a data structure, an identifier for each container resource of the set of ancestor container resources of the particular resource; while traversing the collection to gather statistics for the collection in connection with the second traversal of the collection:
determining whether an identifier for a first container resource in the collection of resources is stored in the data structure;wherein the set of ancestor container resources comprises the first container resource;in response to determining that an identifier for the first container resource is stored in the data structure, gathering statistics for one or more child resources of the first container resource to produce gathered statistics;determining whether an identifier for a second container resource in the collection of resources is stored in the data structure;in response to determining that an identifier for the second container resource is not stored in the data structure, skipping gathering statistics for immediate children of the second container resource; wherein the method is performed by one or more computing devices.