Inverted indexing

Disclosed herein are system, method, and computer program product embodiments for inverted indexing. An embodiment operates by receiving a request to add a new document identifier (doc ID) to an inverted index. A memory block corresponding to where the doc ID is to be added is determined or located, and the available space remaining in the memory block is determined. If the memory block has available space, the doc ID is added to the memory block.

BACKGROUND

Indexes are used in a database to track which documents of a database include a particular value. Indexes however can become problematic when they need to be resized, as the resizing process requires that the existing index is locked, a new index is created, the existing index is copied into the new index, and finally the new value added, before the new index is unlocked. This process of resizing an index consumes valuable system resources and can cause processing delays.

DETAILED DESCRIPTION

Provided herein are system, method and/or computer program product embodiments, and/or combinations and sub-combinations thereof, for inverted indexing.

FIG. 1is a system100for inverted indexing, according to an embodiment. Indexing system102maintains an inverted index (IX)104for documents106in a document store108.

Indexing system102indexes, tracks, or otherwise identifies which documents106contain a particular value110. Indexing system102stores the corresponding document identifiers (doc IDs)114in IX104. Then, for example, if a query is received from a user or system as to which documents106of doc store108contain a particular value110, indexing system102may quickly retrieve the corresponding doc IDs114from IX104rather than querying each document106of doe store108.

Querying each document106, without use of IX104, may be an expensive process that requires both extra time and resources. For example, the full text of each document106may need to be searched to determine which doc (s)106, if any, of doc store108contain value110. This problem becomes worse as the number of docs106stored increases.

In an embodiment, doc store108may be any memory or storage used to store data and/or files, including, but not limited to a database. In an embodiment, doc store108may include a large number of documents106. The docs106may include various fields112of data that are associated with particular values110. For example, field112may include a broad category or description of data. Example fields112may include account balance, interest rate, name, city, state, country, zip code, age, or any other field of data. Value110may be any number, string, text, or alpha-numeric and/or symbolic searchable combination of characters. In an embodiment, a particular field112may correspond to a particular data-type of value110(e.g., integer, string, real, Boolean, etc.). Value110may correspond to one or more fields112.

IX104may be used to track which documents106include particular values110corresponding to one or more fields112of the documents106. For example, IX104may be associated with a zip code field112. Then for example, IX104may track which documents106include zip codes of specified values110(e.g., 20005, 22015, 22079 . . . ).

As another example, IX104may correspond to an account balance field114. And value110smay correspond to ranges of account balances. For example, value A may include account balances of greater than one million dollars, value B may include account balances that are negative (less than 0), and value C (not shown) may include account balances between 0 and 1 million dollars.

In an example embodiment, different fields112may correspond to different IXs104. For example, a first IX104may be used for a name field112, while a second IX104may be used for a country field112.

Inverted indexes generally store any document identifiers that correspond to a particular value in an array. When a new document is added to a document storage area that includes the value corresponding to the array, a new document identifier needs to be added to the array (corresponding to the inverted index). To add the new document identifier to a general inverted index, the inverted index must first be locked (e.g., all reads/writes on the inverted indexed are paused/stopped), a new array is created of a greater size (i.e. one additional size than the previous array), the values of the old or original array are copied to the new array, and the new document identifier is added to the new array. The old array is discarded, and then the new array is unlocked.

This process of locking the array, causing pending operations to pause, stop or otherwise be blocked, generating a new array, and copying the old values to the new array, can be very costly in terms of time and computing resources, especially as the array and/or number of stored documents that include the value grow in size. For example, in a large document storage area may include a billion or more documents, which could yield arrays in excess of one million entries. To generate a new array and copy a million entries is very costly in terms of computing resources and time.

Unlike general inverted indexes that use arrays to store document identifiers, IX104uses memory blocks116to store doc IDs114. A memory block116is a contiguous portion or chunk of memory that is allocated to store one or more doe IDs114associated with a particular value110. For example, each value110may correspond to a particular memory block116. Then, when a document106is identified with a particular value110, the memory block116corresponding to that value110is identified. The identified memory block116is then checked to see if it has enough free memory to store the doc ID114corresponding to the document106. If the memory block116has enough memory, the new doc ID114is added to the memory block116.

In an embodiment, a primary vector132may track which values110are found amongst documents106. Primary vector132may be a storage area, such as a vector or array, that is used to store a limited amount of data. For example, primary vector132may store values110and a number of corresponding doc IDs114. When the number of doc IDs114corresponding to a particular value110exceeds a threshold (for example, two), primary vector132may include a pointer118A to a corresponding memory block110that includes the doc IDs114.

If the memory block116however does not have enough available memory to accommodate the storage of another doc ID114, a new memory block116is allocated to the value110. The new memory block116may be of the same size, or any different size than the original memory block116. The new doc ID114is then added to the newly allocated memory block116. Then for example, a pointer118may be added to the new memory block116(e.g., block2, val A) that points to the previous memory block116(e.g., block1, val A) corresponding to the value110. Similarly, a pointer118from the previous memory block116may be added that points to the newly allocated memory block116.

In an embodiment, each memory block116may include a block count132that tracks how many doc IDs114are stored in a particular memory block116, for a particular value110. For example, inFIG. 1, the respective block counts132for memory blocks1A,1B, and2A may be 3, 3, 1.

Also unlike general inverted indexes, IX104does not need to be locked to add new doc IDs104. Nor do the old/existing document identifiers need to be copied from one location to another (e.g., from one array into a new array). Instead, IX104uses fewer computing resources and saves time by allocating new memory blocks and adding one or more pointers118(if necessary) when new doc IDs114need to be added to IX104.

Indexing system102may include a document processor120that processes new documents106added to doc store108. For example, after one or more documents106are uploaded or otherwise added to document store108, document processor120scans or otherwise searches the added documents106for values110corresponding to one or more IXs104. Or for example, if a document106is modified, document processor120may scan or search the modified doc106. If a document106is identified that includes a value110, the doc ID114and corresponding value(s)110(and field(s)112, if necessary) may be provided to index processor122.

Index processor122may then identify the memory block116corresponding to the value(s)110and field(s)112. Upon identifying the memory block116, index processor122, may as discussed above, either add the doc ID114to the memory block or request/allocate a new memory block116to add the doc ID114.

In an embodiment, the doc IDs114may be sequential numbers generated by indexing system102. Doc count124may include the most recently created doc ID114. In another embodiment, if docs IDs114are not sequential numbers, then doc count124may include a count of how many documents106are included in doc store108.

In an embodiment, in addition to or in lieu of storing doc IDs114, a memory block110may include a bitmap130. Bitmap130may be used to save space in memory110. For example, in an embodiment, doc ID114may be 32 bits, and bitmap130may be 1 bit. Using a bitmap130may save resources, for example, by reducing memory accesses. Based on the bitmap130, indexing system102may determine which doc IDs114correspond to value110.

When a bitmap130is being created/allocated and populated (e.g., for example, if an existing bitmap130is full), the new bitmap130is not accessible to any readers that may be accessing IX104until the bitmap130is fully populated with whatever doe ID(s)114correspond to the associated value110. Once the bitmap130is populated, any subsequent read requests may be diverted to the new bitmap130, or the bitmap130is otherwise made live and accessible to readers.

System100includes an indexing system102that tracks which documents106of a database or other document storage108include particular value(s)110. Using memory blocks116, instead of a standard array, system100allows for the addition of new doc IDs114to the IX104without the need to lock/unlock the inverted index.

FIG. 2is a flowchart for a method200for inverted indexing, according to an embodiment. Method200can be performed by processing logic that can comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (e.g., instructions run on a processing device), or a combination thereof.

In step210, indexing system102receives a request to add a new document identifier (doc ID) to an inverted index. For example, a user or other system may upload or request to add a document106to doc store108. Document processor120may process the document106to determine if the document106includes any of values110associated with any of one or more IXs104. If document106includes a value110(e.g., in a particular field112or document text), then document processor120may send the doe ID114and value110(and field112or associated IX104, if necessary) to index processor104. Index processor122may receive this request to add the new doc ID114to IX104.

In step220, indexing system102determines which memory block, if any, includes a most recently added doc ID. For example, index processor122may request from or otherwise identify within IX104which memory block116includes the most recently added doe ID114corresponding to the value110.

In step230, indexing system102determines whether the memory block has available space for the doc ID. For example, index processor122may determine if memory block116has available memory to store a new or additional doc ID114. Index processor122may check the available space and/or used space of the memory block116to make this determination. In an embodiment, it may be known that a document ID114uses 32 bits of memory. Then for example, index processor122may determine if a memory block has more or less than 32 bits of memory.

If the memory block does not have available space for the doc ID, indexing system102allocates a new memory block into which to insert the new doc ID (Step240), generates a pointer from the memory block that includes the most recently added doe ID to the to the new memory block (242). For example, index processor122(or another processor) may request to allocate a new memory block116. One or more pointers118may be generated that link the previous memory block116to the new memory block116, and/or vice versa.

In an embodiment, if a bitmap130is being used to store doc IDs114, instead of checking memory bock116for available space, bitmap130may be checked for available space. If the bitmap130is full, a new bitmap130may be allocated. For example, the new bitmap130may be larger than the existing/full bitmap130, and may be populated with the existing values from the full bitmap130.

Or for example, IX104may include a list of doc IDs114that correspond to a value110of a particular field112. If a particular document includes a value110that does not correspond to an existing memory block116, a new memory block116may be allocated for the new value110(e.g., if there is not enough space in primary vector132).

In step250, indexing system102inserts the new doc ID into the memory block. For example, if there is available memory space available or if a new memory block116has been allocated, index processor122may add or request that doc ID114is added to the memory block116or bitmap130.

Various embodiments can be implemented, for example, using one or more well-known computer systems, such as computer system300shown inFIG. 3. Computer system300can be any well-known computer capable of performing the functions described herein.

Computer system300includes one or more processors (also called central processing units, or CPUs), such as a processor304. Processor304is connected to a communication infrastructure or bus306.

Computer system300also includes a main or primary memory308, such as random access memory (RAM). Main memory308may include one or more levels of cache. Main memory308has stored therein control logic (i.e., computer software) and/or data.

Computer system300may also include one or more secondary storage devices or memory310. Secondary memory310may include, for example, a hard disk drive312and/or a removable storage device or drive314. Removable storage drive314may be a floppy disk drive, a magnetic tape drive, a compact disk drive, an optical storage device, tape backup device, and/or any other storage device/drive.

Removable storage drive314may interact with a removable storage unit318. Removable storage unit318includes a computer usable or readable storage device having stored thereon computer software (control logic) and/or data. Removable storage unit318may be a floppy disk, magnetic tape, compact disk, DVD, optical storage disk, and/any other computer data storage device. Removable storage drive314reads from and/or writes to removable storage unit318in a well-known manner.

According to an exemplary embodiment, secondary memory310may include other means, instrumentalities or other approaches for allowing computer programs and/or other instructions and/or data to be accessed by computer system300. Such means, instrumentalities or other approaches may include, for example, a removable storage unit322and an interface320. Examples of the removable storage unit322and the interface320may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM or PROM) and associated socket, a memory stick and USB port, a memory card and associated memory card slot, and/or any other removable storage unit and associated interface.

Computer system300may further include a communication or network interface324. Communication interface324enables computer system300to communicate and interact with any combination of remote devices, remote networks, remote entities, etc. (individually and collectively referenced by reference number328). For example, communication interface324may allow computer system300to communicate with remote devices328over communications path326, which may be wired and/or wireless, and which may include any combination of LANs, WANs, the Internet, etc. Control logic and/or data may be transmitted to and from computer system300via communication path326.

In an embodiment, a tangible apparatus or article of manufacture comprising a tangible computer useable or readable medium having control logic (software) stored thereon is also referred to herein as a computer program product or program storage device. This includes, but is not limited to, computer system300, main memory308, secondary memory310, and removable storage units318and322, as well as tangible articles of manufacture embodying any combination of the foregoing. Such control logic, when executed by one or more data processing devices (such as computer system300), causes such data processing devices to operate as described herein.