Database query processor
Disclosed is an associative content or memory processor for wirespeed query of routing, security string or multi-dimensional lookup tables or databases, which enables high utilization of memory resources and fast updates. The device can operate as binary or ternary CAM (content addressable memory). The device applies parallel processing with spatial and data based partitioning to store multi-dimensional databases with high utilization. One or more CAM blocks are coupled directly to leaf memory or indirectly through mapping stages. The contents of mapping memory are processed by the mapping logic block. The mapping logic processes the stored crossproduct bitmap information to traverse a path to one or more leaf memory storage blocks. The compare block compares the contents of the leaf memory with the search or query key. The output response includes match result, associated data address and associated data.
1 . An integrated circuit device comprising:
a plurality of mapping memory stages and an associated mapping path processing logic, the mapping path processing logic adapted to compare values stored in a trie structure with query key components and to generate pointers to a mapping memory stage of the plurality of mapping memory stages or to a leaf memory, the leaf memory storing records of information;
a content addressable memory (CAM) adapted to store a breadth first search component of the trie structure which generates an index to access a mapping memory stage of the plurality of mapping memory stages, the mapping memory adapted to store a plurality of values for the trie structure and a plurality of pointers; and
a result generator adapted to compare query key components with a record stored in the leaf memory and to generate a match result along with stored parameters.
2 . The integrated circuit device of claim 1 , wherein the information comprises one from a group consisting of state tables, grammar, statistical and compute instructions.
3 . The integrated circuit device of claim 1 , wherein the CAM array can store any part of a record.
4 . The integrated device of claim 1 , wherein a mapping memory stage of the plurality of mapping memory stages are accessed sequentially to retrieve one of an entry and a record.
5 . The integrated device of claim 1 , wherein the CAM is a ternary content addressable memory (TCAM).
6 . An integrated circuit device comprising:
a plurality of mapping memory stages and an associated mapping path processing logic, the mapping path processing logic adapted to compare values stored in a trie structure with query key components and to generate pointers to a mapping stage of the plurality of mapping memory stages or to a leaf memory, the leaf memory adapted to store information;
a plurality of content addressable memory (CAM) arrays adapted to store a breadth first search component of the trie structure, which generates an index to access a mapping memory, the mapping memory adapted to store a plurality of values for the trie structure and a plurality of pointers; and
a result generator adapted to compare query key components with record stored in the leaf memory and to generate match result along with stored parameters.
7 . The integrated circuit device of claim 6 , wherein each CAM array of the plurality of CAM arrays comprises a ternary CAM.
8 . The integrated circuit device of claim 6 , wherein the plurality of CAM arrays are combined to be a wider word width.
9 . The integrated circuit device of claim 8 , wherein the plurality of CAM arrays comprise a width.
10 . The integrated circuit device of claim 9 , wherein the width is one from a group consisting of 2 times width, 4 times width, 8 times width, 16 times width, 32 times width, 64 times width, and 128 times width.
11 . The integrated circuit device of claim 6 , further comprising an output generator adapted to combine results from the result generator and to output results in response to specific query type.
12 . A method to allocate a content addressable memory array for each dimension and various node lengths for optimal use of the resources, the method comprising:
comparing values stored in a trie structure with query key components;
generating pointers to a leaf memory, the leaf memory accessed by a pointer storing a plurality of records of information;
storing a breadth first search component of the trie structure;
generating an index to access a mapping memory;
storing in the mapping memory a plurality of values for the trie structure and a plurality of pointers;
comparing query key components with a record stored in the leaf memory; and
generating a match result along with stored parameters.
13 . The method of claim 12 , further comprising accessing sequentially the memory mapping to retrieve one of an entry and a record.
14 . The method of claim 12 , wherein the information comprises one from a group consisting of state tables, grammar, statistical and compute instructions.
15 . The method of claim 12 , further comprising identifying an update location for new records by using at least one of a CAM array, memory mapping stages, a logic function to associated memory, or an external memory.