2 ms·

XML can do the same trick with indirect objects as COS, using ID and IDREF type attributes. A number of years ago I was dealing with the archival and retrieval/

XML can do the same trick with indirect objects as COS, using ID and IDREF type attributes. A number of years ago I was dealing with the archival and retrieval/display of enormous medical textbooks in XML, and I couldn't efficiently pull out arbitrary elements (chapters, sections, paragraphs, etc) because of the hierarchical nature of the XML document structure. I had to parse the whole thing to use an XPATH to get the element I needed, and that took too long. (My parser could handle 3MB/sec, and some of these books were over 100+MB.) The solution I came up with was a program that transformed the documents by flattening them into a relatively small hierarchical structure that represented the volume/chapter/section headings of the book, and a flat list of elements that were small enough to parse quickly. I inserted ID and IDREF elements to link these two parts together, and created an external index of the file offsets and lengths of each element in the flattened list. That let me use simple file I/O to access any element by ID, pull it out of the larger file, and only then start the parsing engine. It was like the article mentions: my XML file, together with the external index (in a simple Unix DBFile file) was a miniature NoSQL database of the textbook. BTW, this predated the "NoSQL" label, and was developed after testing of Oracle and the XML databases of the day completely failed to meet performance and scalability requirements. My solution has an infinite capacity to scale; its performance is not impacted by the number of books in the system nor their size. The retrieval and display time of a single chapter or any subelement is a constant proportional only to the size of that chapter, and is not affected by the overall size of the collection. All of the other solutions we looked at got slower as the number of books increased and as the size of the books increased. (I mention this only to head-off any comments about reinventing the wheel.)

thristian 14y ago
ID/IDREF isn't exactly the same as indirect objects in COS. When you're parsing an XML document, ID/IDREF are just attributes like any other that get added to the DOM, and then application code can dereference them later if it wants. In COS, indirect objects are part of the serialisation format and the parser needs to understand them and dereference them in order to be able to parse the file. For example, the COS "stream" object type is serialised as a settings dictionary, followed by the 'stream' keyword, the stream data, and the 'endstream' keyword. But what happens when the stream happens to contain the bytes 'endstream'? Well, the settings dictionary has a "Length" key that tells you how long the stream is, without you having to scan for the 'endstream' keyword. However, because most streams are compressed and compression makes it difficult to guess in advance exactly what the compressed size willl be, COS allows you to make the Length key an indirect reference to an integer defined later in the file. Like so: << % Here, the value associated with the Length key is % indirect object 42 revision 0. /Length 42 0 R /Filter /FlateDecode >> stream ...compressed data goes here... endstream % And now we define object 42 revision 0 42 0 obj 12345 endobj So, the parser needs to know the length of the compressed stream in order to parse it, but it needs to have parsed the compressed stream in order to get to the length data. The way out of this catch-22 is the object index at the end of the file, which gives you the index and location of each indirect object. A COS parser needs to start at the end of the file and load all the indirect objects, cache them, then go back to the beginning and stitch them into the deserialised object graph as they're referenced.

thristian 14y ago

ID/IDREF isn't exactly the same as indirect objects in COS. When you're parsing an XML document, ID/IDREF are just attributes like any other that get added to the DOM, and then application code can dereference them later if it wants. In COS, indirect objects are part of the serialisation format and the parser needs to understand them and dereference them in order to be able to parse the file. For example, the COS "stream" object type is serialised as a settings dictionary, followed by the 'stream' keyword, the stream data, and the 'endstream' keyword. But what happens when the stream happens to contain the bytes 'endstream'? Well, the settings dictionary has a "Length" key that tells you how long the stream is, without you having to scan for the 'endstream' keyword. However, because most streams are compressed and compression makes it difficult to guess in advance exactly what the compressed size willl be, COS allows you to make the Length key an indirect reference to an integer defined later in the file. Like so: << % Here, the value associated with the Length key is % indirect object 42 revision 0. /Length 42 0 R /Filter /FlateDecode >> stream ...compressed data goes here... endstream % And now we define object 42 revision 0 42 0 obj 12345 endobj So, the parser needs to know the length of the compressed stream in order to parse it, but it needs to have parsed the compressed stream in order to get to the length data. The way out of this catch-22 is the object index at the end of the file, which gives you the index and location of each indirect object. A COS parser needs to start at the end of the file and load all the indirect objects, cache them, then go back to the beginning and stitch them into the deserialised object graph as they're referenced.