Two-dimensional indexes for quick multiple attribute search in a catalog system

• US 8,219,564 B1
• Filed: 04/29/2008
• Issued: 07/10/2012
• Est. Priority Date: 04/29/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Shao, Minglong, Pasupathy, Shankar, Leung, Andrew, Bisson, Timothy Clayton
• Primary Examiner(s): Lovel, Kimberly
• Assistant Examiner(s): REYES, MARIELA D
• Application Number:
  US12/111,530
• Time in Patent Office: 1,533 Days
• Field of Search: 707/741, 707/743
• US Class Current: 707/743
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951

Abstract

Embodiments of the present invention provide mechanisms that overcome limitations of existing indexes by creating two-dimensional (2D) spatial indexes to quickly locate data containers that match two or more predicates. This is accomplished by representing metadata attributes describing a data container as dimensions in a 2D space so that a data container can be expressed as a point or a cell in a 2D space with coordinates being a pair of values of the selected attributes. A space filling curve is used to traverse the 2D space and convert each pair of the 2D coordinates to a single space filling curve value. A 2D spatial index is then created based on the computed space filling curve values so that one value can be associated with one or more points (data containers) in the index. Advantageously, the created spatial index provides for searching and processing fewer metadata entries, thereby decreasing the time typically used to search for data.

Claims

1. A method for generating an index for searching data containers in a storage system, comprising a processor and a memory, based on selected metadata attributes, the method comprising:

mapping, for a given data container of a plurality of data containers, a pair of values corresponding to a pair of attributes associated with metadata describing the given data container that stores data, wherein the pair of values represent coordinates for the given data container in a two-dimensional (2D) space;

imposing a grid comprising a plurality of cells on the 2D space so that each cell in the grid represents coordinates of a single data container of the plurality of data containers in the 2D space;

computing a space filling curve value for each cell in the grid;

generating a searching index wherein each computed space filling curve value is used as a key in the searching index to search for the plurality of data containers in the storage system;

receiving a query to search for one or more particular data containers based on ranges of metadata values of selected attributes;

computing particular space-filling curve values based on the ranges of metadata values of selected attributes associated with the query; and

searching the searching index to identify the one or more particular data containers based on the particular space-filling curve values.

2. The method of claim 1, further comprising:

receiving the selected attributes; and

searching data structures storing metadata for the one or more particular data containers associated with the values corresponding to the selected attributes.

3. The method of claim 1, further comprising:

determining whether an attribute value has an integer value; and

responsive to the attribute value not being a discrete integer, converting the attribute value to the integer value.

4. The method of claim 1, wherein the space filling curve is at least one of a Hilbert Curve, a Peano Curve, a Z-order Curve, and a Gray-code Curve.

5. The method of claim 1,

wherein the ranges represent a region having four coordinates in the 2D space, one or more perfect squares within the region are identified, and a highest value and a lowest value among the computed particular space-filling curve values for corner cells in each of the one or more perfect squares are identified to search the generated index to identify the one or more particular data containers.

6. The method of claim 5, wherein identifying one or more perfect squares further comprising identifying an area having a lower left coordinate (X_—

0, Y_—

0) and an upper right coordinate (X_—

1, Y_—

1), which meet the following criteria;

highest bits of X_—

0 and X_—

1 being a same and remaining bits of X_—

0 being all 0 and remaining bits of X_—

1 being 1;

highest bits of Y_—

0 and Y_—

1 being a same and remaining bits of Y_—

0 being all 0 and remaining bits of Y_—

1 being 1; and

length of a matched highest bits of X and Y are equal.

7. The method of claim 1, further comprising using the searching index to identify the one or more particular data containers corresponding to keys in the index.

8. The method of claim 1, further comprising:

receiving the query to search for the one or more data containers based on N number of attributes, where N is an even number;

responsive to finding searching indexes for any pair of attributes of the N number of attributes in the query, using each of the searching indexes to identify the one or more particular data containers matching the query; and

applying a logical function to the one or more particular data containers to identify one or more data containers that match all attributes in the query.

9. The method of claim 8, wherein the logical function is an intersection function.

10. The method of claim 1, further comprising:

receiving the query to search for the one or more particular data containers based on N number of attributes, where N is an odd number;

responsive to identifying searching indexes for any pair of attributes of the N number of attributes in the query, using each of the searching indexes to identify the one or more particular data containers corresponding to the query;

applying a logical function to the one or more particular data containers to identify selected data containers that match an even number of attributes in the query; and

using remaining attribute as a filter to identify one or more data containers that match all the attributes in the query.

11. A method for computerized searching of data containers on a storage system having a processor and a memory, comprising:

maintaining metadata describing a plurality of attributes associated with each data container of the data containers that stores information, wherein each attribute has an associated value;

representing a pair of values corresponding to a pair of attributes of the plurality of attributes associated with a given data container as dimensions in a two-dimensional (2D) space so that the pair of the selected values corresponding to the pair of attributes represents coordinates for a given data container in the 2D space;

imposing a grid comprising a plurality of cells on the 2D space so that each cell in the grid represents coordinates of a single data container in the 2D space;

computing a space filling curve value for each cell in the grid;

generating a searching index wherein each computed space filling curve value is used as a key in the searching index;

receiving a query to search for one or more data containers based on ranges of metadata values of selected attributes; and

searching the searching index for the one or more data containers based on a match between particular space-filling curve values associated with the range of metadata values of selected attributes and one or more keys in the searching index.

12. A catalog system for generating an index for searching data containers stored in a computerized system, comprising a processor and a memory, the method comprising:

an attribute collecting module configured to collect values associated with selected metadata attributes from a data structure storing metadata for a plurality of data containers;

an index generation module configured to represent the selected attributes as dimensions in a two-dimensional (2D)space so that a pair of values corresponding to a pair of selected metadata attributes represent coordinates of a given data container in the (2D) (2D) space having a plurality of cells where each cell represents a single data container in the 2D space, to compute a space filling curve value for each cell; and

to generate a searching index wherein each computed space filling curve value is used as a key in the searching index, wherein a match between one or more keys in the searching index and particular space-filling curve values associated with a range of metadata values of selected attributes identifies one or more particular data containers.

13. The catalog system of claim 12, further comprising a mapping table stored in the memory of the computerized system and configured to map values of non-integer attributes to integer values.

14. The catalog system of claim 12, wherein the index generation module is further configured to use the searching index to identify selected data containers corresponding to the searching index.

15. A non-transitory computer-readable medium containing executable program instructions executed by a processor, comprising:

program instructions that map, for a given data container of the plurality of data containers, a pair of values corresponding to a pair of attributes associated with metadata describing the given data container that stores data, wherein the pair of values represent coordinates for the given data container in a two-dimensional (2D) space;

program instructions that impose a grid comprising a plurality of cells on the 2D space so that each cell in the grid represents coordinates of a single data container in the 2D space;

program instructions that compute a space filling curve value for each cell in the grid;

program instructions that generate a searching index wherein each computed space filling curve value is used as key in the searching index to search for one or more data containers;

program instructions that receive a query to search for the one or more data containers based on ranges of metadata values of selected attributes;

program instructions that compute particular space-filling curve values based on the ranges of metadata values of selected attributes associated with the query; and

searching the searching index to identify the one or more data containers based on the particular space-filling curve values.

16. The non-transitory computer-readable medium of claim 15,

wherein the ranges represent a region having four coordinates in the 2D space, and further of comprising:

program instructions that identify one or more perfect squares within the region, and a highest value and a lowest value among the computed particular space-filling curve values for corner cells in each of the one or more perfect squares are to search the generated index to identify the one or more data containers.

17. The non-transitory computer-readable medium of claim 15, further comprising program instructions that collect values of selected metadata attributes from a data structure storing metadata for the one or more data containers.

18. The non-transitory computer-readable medium of claim 15, wherein an identifier associated with a particular key in the searching index is an inode number of a particular data container.

19. The non-transitory computer-readable medium of claim 15, wherein the generated searching index is a tree-like data structure.

20. The non-transitory computer-readable medium of claim 15, wherein a particular key in the generated searching index is associated with one or more selected data containers.