Method and apparatus for searching metadata

• US 7,536,383 B2
• Filed: 08/04/2006
• Issued: 05/19/2009
• Est. Priority Date: 08/04/2006
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Colclasure, Kaelin Lee, Callaghan, Brent, Hörnkvist, John Martin, Suinn, Bradley Rm, Tucker, Ruxton J., Arrouye, Yan
• Primary Examiner(s): Lu; Kuen S
• Application Number:
  US11/499,267
• Publication Number:
  US 20080033920A1
• Time in Patent Office: 1,019 Days
• Field of Search: 707/4, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/14 Details of searching files based on file metadata
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

Methods and apparatuses for searching metadata are described herein. In one embodiment, an example of a process for search metadata includes, but is not limited to, in response to a search query for metadata stored in one or more of metadata stores, the search query is partitioned into multiple search query segments. Thereafter, searches corresponding to the search query segments are performed, where each search is performed independently within the one or more metadata stores. Other methods and apparatuses are also described.

Claims

1. A machine-implemented method, comprising:

in response to a search query for metadata stored in one or more of a plurality of metadata stores, partitioning the search query into a plurality of search query segments;

for each search query, allocating a system thread having a time slice with a predetermined time period; and

performing searches corresponding to the plurality of search query segments, each search being performed independently within the one or more metadata stores within a corresponding time slice of a corresponding system thread in a round-robin manner, including storing a search state and a partial search result in a queue at the end of the time slice if the respective search has not been finished, such that the respective search can be carried on in a subsequent time slice.

2. The method of claim 1, further comprising determining which of the metadata stores that need to be searched based on the search query, wherein the search query is partitioned based on a configuration of the metadata stores.

3. The method of claim 1, further comprising:

receiving a plurality of search results corresponding to the search query segments; and

integrating the search results associated with the search query segments into a final search result corresponding to the search query suitable to be returned to a client originating the search query.

4. The method of claim 1, further comprising scheduling a process for each search corresponding to a search query segment, wherein each search is performed independently within a scheduled process associated with each search.

5. The method of claim 4, further comprising allocating a system thread of an operating system for the search query, wherein processes for search query segments are scheduled within the system thread.

6. The method of claim 1, wherein the search query is a first search query partitioned into first search query segments, wherein the method further comprises:

in response to a second search query, partitioning the second search query into a plurality of second search query segments; and

grouping the first and second search query segments into a plurality of bundles, each bundle having at least one first search query segment and at least one second search query segment and each bundle having similar characteristics, wherein a search is performed on a per bundle basis.

7. The method of claim 6, further comprising scheduling a process for a search corresponding to each bundle, wherein each of search query segments within a bundle is searched during a respective process.

8. The method of claim 6, wherein search query segments within a bundle are searched within a predetermined proximity of a storage area of a metadata store.

9. A machine-readable storage medium having instructions, when executed by a machine, cause the machine to perform a method, the method comprising:

in response to a search query for metadata stored in one or more of a plurality of metadata stores, partitioning the search query into a plurality of search query segments;

for each search query, allocating a system thread having a time slice with a predetermined time period; and

performing searches corresponding to the plurality of search query segments, each search being performed independently within the one or more metadata stores within a corresponding time slice of a corresponding system thread in a round-robin manner, including storing a search state and a partial search result in a queue at the end of the time slice if the respective search has not been finished, such that the respective search can be carried on in a subsequent time slice.

10. The machine-readable storage medium of claim 9, wherein the method further comprises determining which of the metadata stores that need to be searched based on the search query, wherein the search query is partitioned based on a configuration of the metadata stores.

11. The machine-readable storage medium of claim 9, wherein the method further comprises:

receiving a plurality of search results corresponding to the search query segments; and

integrating the search results associated with the search query segments into a final search result corresponding to the search query suitable to be returned to a client originating the search query.

12. The machine-readable storage medium of claim 9, wherein the method further comprises scheduling a process for each search corresponding to a search query segment, wherein each search is performed independently within a scheduled process associated with each search.

13. The machine-readable storage medium of claim 12, wherein the method further comprises allocating a system thread of an operating system for the search query, wherein processes for search query segments are scheduled within the system thread.

14. The machine-readable storage medium of claim 9, wherein the search query is a first search query partitioned into first search query segments, wherein the method further comprises:

in response to a second search query, partitioning the second search query into a plurality of second search query segments; and

grouping the first and second search query segments into a plurality of bundles, each bundle having at least one first search query segment and at least one second search query segment and each bundle having similar characteristics, wherein a search is performed on a per bundle basis.

15. The machine-readable storage medium of claim 14, wherein the method further comprises scheduling a process for a search corresponding to each bundle, wherein each of search query segments within a bundle is searched during a respective process.

16. The machine-readable storage medium of claim 14, wherein search query segments within a bundle are searched within a predetermined proximity of a storage area of a metadata store.

17. An apparatus, comprising:

a task manager, in response to a search query for metadata stored in one or more of a plurality of metadata stores, configured to partition the search query into a plurality of search query segments and to allocate a system thread having a time slice with a predetermined time period; and

a search engine coupled to the task manager to perform searches corresponding to the plurality of search query segments, each search being performed independently within the one or more metadata stores within a corresponding time slice of a corresponding system thread in a round-robin manner, including storing a search state and a partial search result in a queue at the end of the time slice if the respective search has not been finished, such that the respective search can be carried on in a subsequent time slice, wherein the search engine includes a processor and a memory.

18. The apparatus of claim 17, further comprising a store manager coupled to the task manager to determine which of the metadata stores that need to be searched based on the search query, wherein the search query is partitioned based on a configuration of the metadata stores.

19. The apparatus of claim 18, further comprising a scheduler coupled to the task manager and the store manager to schedule a process for each search corresponding to a search query segment, wherein each search is performed independently within a scheduled process associated with each search.

20. The apparatus of claim 19, further comprising a plurality of queues coupled to the scheduler, each queue being associated with a search query segment to store a search status and a search result corresponding to the search query segment.

21. An apparatus, comprising:

in response to a search query for metadata stored in one or more of a plurality of metadata stores, means for partitioning the search query into a plurality of search query segments;

means for allocating a system thread having a time slice with a predetermined time period; and

means for performing searches corresponding to the plurality of search query segments, each search being performed independently within the one or more metadata stores within a corresponding time slice of a corresponding system thread in a round-robin manner, including storing a search state and a partial search result in a queue at the end of the time slice if the respective search has not been finished, such that the respective search can be carried on in a subsequent time slice, wherein means for performing searches includes a processor and a memory.