Method or system for spilling in query environments

• US 8,356,050 B1
• Filed: 11/21/2011
• Issued: 01/15/2013
• Est. Priority Date: 11/21/2011
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Olston, Chris, Reed, Benjamin, Elmeleegy, Khaled
• Primary Examiner(s): HO, BINH VAN
• Application Number:
  US13/301,242
• Time in Patent Office: 421 Days
• Field of Search: 707/769
• US Class Current: 707/769
• CPC Class Codes: G06F 16/986 Document structures and storage, e.g. HTML extensions

Abstract

Methods and systems are provided that may be utilized for spilling in query processing environments.

Claims

1. A system, comprising:

a first node including a primary memory and a secondary memory, said primary memory comprising a first memory sponge and one or more task processes having a memory capacity;

a second node comprising a second memory sponge;

a processor to execute a query process, wherein in response to memory usage of any of said one or more task processes reaching said memory capacity, said processor is capable of utilizing available memory space in said memory sponge to execute said query process, and said processor is capable of utilizing said second memory sponge of said second node in response to said available memory space of said first memory sponge being insufficient to complete execution of said query process; and

a memory manager to manage utilization of said available memory space of said nodes.

2. The system of claim 1, wherein said one or more task processes comprises a virtual machine with a map or reduce task.

3. The system of claim 1, wherein said processor comprises a shared-nothing processor.

4. The system of claim 3, wherein in response to said available memory space of said first memory sponge being insufficient to complete execution of said query process, said processor is capable of initiating a memory spilling process to said second node.

5. The system of claim 1, wherein said secondary memory comprises one or more hard disk drives.

6. The system of claim 1, wherein said query process comprises indexing of one or more web sites.

7. The system of claim 1, wherein said stored information is nested inside of a web site record.

8. A method, comprising:

executing a first query process via a first task process of a primary memory of a first node and a second query process via a second task process of said primary memory of said first node;

spilling state information associated with said first query process to a first memory sponge of said primary memory at least in part in response to said first task process reaching a first memory capacity;

spilling said state information to a second memory sponge of a second node in response to said available memory space of said first memory sponge being insufficient to complete execution of said first task process; and

managing utilization of available memory space of said nodes via a memory manager.

9. The method of claim 8, further comprising spilling state information associated with said second query process to said first memory sponge of said primary memory at least in part in response to said second task process reaching a second memory capacity.

10. The method of claim 8, further comprising executing a virtual machine with a map or reduce task via use of said first task process or said second task process.

11. The method of claim 8, further comprising writing said state information to one or more hard disks of said node in response to completing said query process.

12. An article, comprising:

a storage medium comprising machine-readable instructions executable by a special purpose machine to;

execute a first query process via a first portion of memory at a first data center node;

writing state information associated with said first query process to available memory space of a first memory sponge of said first data center node in response to memory usage of said first portion of memory reaching a size threshold, said first memory sponge being accessible to said first query process or to a second query process of said first data center node;

writing said state information to a second memory sponge of a second data center node in response to said available memory space of said first memory sponge being insufficient to complete execution of said first or second query processes; and

managing utilization of available memory space of said first and second data center nodes.

13. The article of claim 12, wherein said machine-readable instructions are further executable to perform a map or reduce task via use of said first memory portion or a second memory portion of said first data center node.

14. The article of claim 12, wherein said machine-readable instructions are further executable to index one or more web sites as part of a query process.

15. The article of claim 12, wherein said machine-readable instructions are further executable to write said state information to one or more hard disks of said first data center node in response to completing said first query process.