<< Chapter_6_Search_Architecture

Index of HTML Docs

Chapter_8_Findings >>

 

 

Chapter 7.  Testing Procedures

 

Testing Philosophy

General Approach

Testing Architecture

XQuery Adaptations

Timing Issues

Test 1:  Storage Footprint

Test 2: Do We Get Out What We Put In?

Test 3: Storage Speed

Test 4: Queries for Accuracy

Test 5: Timed Benchmark Queries

Test 6: Working with Nearly Full Core Indices

Test 7: Extensibility Test

Test 9: Non-indexed Substring Searches

 

 

Testing Philosophy

 

(1). We are interested only in that testing which would shed light on the performance of the patented features described in Chapters 3 through 6 above. Specifically, we are not really interested in finding bugs or idiosyncracies which are likely to be fixed in future versions. And in particular we are not interested in testing the broader XMS which surrounds the NeoCore database. So, for example, we are not evaluating the performance or ease of use of the NeoCore XMS console; we are not interested in login/logout procedures; we are not interested in whether the NeoCore C++ API works efficiently; we are not interested in transaction management; we are not interested in locking/unlocking idiosyncracies; we are not interested in archiving or disaster recovery.

 

We are interested in the claimed small footprint, i.e., the amount of disk storage, that the patented features are supposed to allow. We are interested in whether XML documents retain their syntactical structure when they go through the flattening process and are later reconstructed. We are interested in the speed at which documents can be stored. We are interested in the claim that indexed searches of non-duplicate data items are near-equally rapid whether in an empty database or in a nearly full database. Given the amount of flattening, icon generation, map-file population, and indexing that has to take place on a store, we want to see how quickly stores can be done. We are especially interested in the key NeoCore claim:  that a whole series of documents can be stored and searched efficiently, even when there is no pre-determined DTD or external schema for the series of documents and even when the internal structures contained in the series of documents have nothing to do with each other. That is, we are especially interested in testing NeoCore’s ability to deal with the extensibility of XML—the principle feature where NeoCore claims superiority over its competitors.

 

(2). We are not going to evaluate the architecture’s ability to support large amounts of data—at least not for this current test. NeoCore states that the current version of the NeoCore XMS is not yet configured for huge databases. NeoCore claims that release 3.0 will support larger databases. For this reason, for each series of testing we perform, we will do so with documents whose size totals only about 100 megabytes. Note that this is our limitation, not NeoCore’s. We did initially verify that the XMS can be configured to store far more. But there ends up being nothing to gain by testing the larger sizes, given that NeoCore acknowledges that the currently version is not designed for huge databases and that this limitation will be dealt with in a future release.

 

(3). Because of NeoCore’s unique architecture, the performance of the database will be affected significantly by the type of data that is input. Text-heavy documents with few tags should show processing characteristics totally different than we would get from documents with large tag structures but little data. In general then, we will do our testing several times—each time with documents of a different sort. Here are the kinds of documents we will use:

 

Top of Chapter

 

 

General Approach

 

The testing tools described in this chapter were developed and themselves tested on a fairly typical Windows XP Home Edition platform. Once proven in that development environment, they were installed in the Computer Science laboratory at the University of Colorado, Colorado Springs, where all testing could be carried out in a more controlled environment on a more robust platform. Final testing in the UCCS laboratory was on a Windows XP Professional Edition platform with a Pentium 4, 3 GHz CPU and 1.50 GB of RAM.

 

Both client and server processes were run on the same single platform. This would not be considered a typical configuration. It was done in this way partly for our own convenience—we were taking only one and not two platforms away from other uses. In addition, and more significantly, by working on one platform we could minimize communication delays—as far as possible we wanted the times to reflect database performance rather than other functionality. There were sufficient CPU speeds and RAM so that we believed the client and server processes would not seriously impede one another. (Unfortunately, this belief was wrong—see our note on RAM usage in Chapter 8.)

 

Top of Chapter

 

 

Testing Architecture

 

There are several components to the testing architecture:

 

Here is how the testing structures are used:

 

Top of Chapter

 

 

XQuery Adaptations

 

None of the XOO7 queries worked in the NeoCore environment without modifications, in part because the XOO7 queries use an early version of XQuery and in part because NeoCore supports only a subset of the complete XQuery language. Appendix D shows the original and the modified versions. Of course, modifying the queries raises significant questions about whether we can legitimately compare our results with the results of the original benchmark testing. The following discussion explains the problems that were encountered, the solution we used, and a rationale for using that solution. It should be noted that XMS version 2.6, the version we are using in this test, was the first NeoCore release to support XQuery; previous releases supported XPath only. Not all XQuery functionality is supported in version 2.6; we assume that eventually, in future releases, the entire XQuery syntax will be supported.[2]

 

Lack of Support for Upper-Case FLWR Keywords. 

Problem:  XOO7 used as keywords “FOR”, “LET”, “IN”, “WHERE”, and “RETURN”. Current XQuery syntax requires these keywords be lower case.

Workaround: Change uppercase keywords to lower case.

Discussion:  This workaround should make no difference whatsoever in performance.

 

Extra “ND” tag for NeoCore XML Documents

Problem:  NeoCore inserts an <ND> tag at the beginning of every XML document. As a result, the document() function selects specified documents at the “/ND” level. This means that where the XOO7 benchmark calls for

for $d in document(“small31.xml”)/ComplexAssembly

NeoCore instead must use

for $d in document(“small31.xml”)/Module1/ComplexAssembly

Workaround:  Insert the required “/Module1” node designator in all queries.

Discussion:  Given the NeoCore architecture, this should make little difference, since both “ND>Module1>” and “Module1>” sequences are explicitly indexed. Whatever performance penalty might theoretically arise from having to parse and process the extra eight characters is in fact justified—it is one of the costs associated with using the NeoCore architecture.

 

NeoCore XMS, v. 2.6, does not support the obsolete XQuery “shallow()”function.

Problem: The XQuery “shallow()” function returns the target node but none of its children. Using NeoCore’s subset of current XQuery, there does not seem to be an alternate way of returning the identical result.

Workaround: Where “shallow($a)” might return

<Connection type=”type006” length=”10462”>

“$a/@*” will return

           <Connection type=”type006”>

           <Connection length=”10462”>

We used the notation given whenever XOO7 used “shallow()”.

Discussion: Whatever is gained by not having to process the extra function is offset by having to deal with the extra tag depth of the target, the wildcard, and the extra return characters. As far as the processing time is concerned, using the workaround should come close to not making appreciable difference, provided there is no large data item associated with the target—“shallow()” would return the data item, but the “@*” alternative would not. Fortunately, it turns out that in every case where the benchmark calls for “shallow()”, there is no associated data item.

 

NeoCore v. 2.6 does not support user-defined functions

Problem:  Query 14 of XOO7 contains a user-defined function which simply returns the current year.

Workaround: Where the XOO7 query calls the function, we simply inserted “2003”.

Discussion: We used the workaround; the primary thrust of Query 14 is to sort the query return. Including such a simple user-defined function seems somewhat gratuitous in XOO7; it evaluates the XQuery parser more than it evaluates database efficiency. In terms of process time, the sort operation required by Query 14 is what will be most demanding; not having to handle the simple user-defined function will admittedly generate some very minor advantage to NeoCore’s performance time.

 

NeoCore v. 2.6 does not support the inclusion of tags in the “RETURN” clause.

Problem: We cannot control the tag structure of the query return in the same way the original benchmark query calls for. This potentially affects queries #14, 18, 19, and 23.

Workaround: In queries 14 and18, we simply dropped the tags in the benchmark query’s “RETURN” clause. In queries 19 and 23, the problem was moot: we could not use the query anyway, because of other features that were not supported.

Discussion: Where we were able to use the workaround, it should provide some very minor advantage to NeoCore performance.

 

NeoCore v. 2.6 does not support “FILTER()”, “BEFORE”, and “AFTER”.

Problem:  We could not use queries 19, 22, or 23.

Workaround:  None.

Discussion: Once NeoCore supports user-defined functions and the “<<” and “>>” functions, we will be able to generate the result that was intended when the XOO7 Benchmark used these now-obsolete XQuery functions.

 

Top of Chapter

 

 

Timing Issues

 

In the Store Tool and the Query Tool we use the following technique to capture the time it takes to process a database command:

_ftime(&tstruct1);

      results = neosession.storeFileXML(new_file_name, NULL, NULL);

      _ftime(&tstruct2);

Then, obviously, we use the values within tstruct1 and tstruct2 to compute the time. This approach raises two issues.

 

The first issue is that the time information accessed by the ftime command is updated at 15 millisecond intervals. Some of the queries take less than 15 milliseconds, and so our statistics could well show that a query executed in “0” milliseconds. To alleviate the problem for those queries that are quick and simple, our Query Tool runs each query 10 times, times the entire loop, and computes the mean. The results will end up being affected slightly by the granularity of the timer: short queries will show as taking 1.5, 3.0, or 4.5 milliseconds each, with nothing in between those values. And in some cases, even with the extra loop control, the whole series of 10 queries would take less than 15 milliseconds, so that sometimes our statistics will show 10 queries taking zero seconds. As long as we understand what is happening and why, this does not really affect our testing: if our statistics show a given query taking zero milliseconds, just interpret that as 10 queries taking less than 15 milliseconds.  Either way, it is fast.

 

The second issue associated with our simple approach is that there is quite a bit of overhead activity occurring between the two time commands that have nothing to do with processing time within the core database. On the client side, the file has to be read, an HTTP command has to be created, the HTTP command with the appended file content has to be handed over to the socket management processes, everything has to be wrapped into the TCP structure, and only then can the client socket begin sending the package to the server. The socket management processes for both server and client and the communication between them (even when client and server sockets are on the same platform) will take some time—especially when our XOO7 Benchmark is typically using 4.5 meg files. Handoff from the server socket to the XMS will reverse the TCP and HTTP handling requirements. In the broader XMS there will be some session ID verification, group “write” verification, transaction management, transaction logging, and similar management functions. There will be the actual processing of the document within the core database. And then there will be all the processing of the HTTP “success” message from server to client and the time for the client to populate the “results” buffer.

 

Queries—especially those which generate lengthy reply strings—will have a similar problem, except (1) the larger communication delays will be on the return rather than on the initial command and (2) more client time will be spent populating the “results” buffer rather than accessing the document to be stored.

 

We can turn on XMS server logs which show the begin and end times for a given command within the XMS itself. The problem with this approach is twofold.  (1) The granularity on the displayed time is only seconds. Many of the commands are handled within the XMS in less than one second—there is no way of computing how much less. (I recommend that in a future build NeoCore add to the config files an option to provide a logging time in milliseconds—typically the option would be used for debugging and testing only.) (2) The figure would be misleading, since every user has to access the database through the XMS server and its HTTP ports one way or the other. The HTTP communications and the client-side API are part of the expense of using the NeoCore database. Input/output processes are part of the database expense. For all practical purposes, from the perspective of the using application, database storage time necessarily includes all the overhead time—even though in our particular test we are interested only in the performance of the core database.

 

We minimize the overhead time by putting the client and server on the same platform. This would not be a typical configuration for medium-sized databases and larger.

 

Bottom line:  there is no way (outside the NeoCore development/testing environment) we can measure precisely the performance of the core database only. All our time measurements embrace significant amounts of overhead functionality and are done with 15 millisecond granularity.

 

Top of Chapter

 

 

Test 1:  Storage Footprint

 

We generate a new database and calculate the storage footprint when it is empty. Then we fill up the database with documents whose sizes sum to about 100 megabytes. As we add each document, we compare the size of the document with the increased storage generated. We repeat this, each time using documents with varying XML characteristics.

 

All database storage is by default in the directory: C:\NeoCore\neoxml. There are 13 files in the “db” sub-directory (indexes, dictionaries, map files). The various utilities and executables are in the “bin” sub-directory. Configuration files are in the “config” sub-directory.

 

The only other directories one might count in the storage footprint are the two directories for various logs. The amount of logging, if any, is configurable, which causes a problem in determining the database footprint. If every logging option is used, performance degrades significantly and the logs become far larger than the entire database. We decided to turn off most logging and not include the logs in our calculation of database footprint.

 

The storage footprint, calculated as a percentage of the total size of the documents stored, is quite variable for the NeoCore XMS. If documents for the most part contain the tag structures and data items of previous documents, then the tag dictionary and data dictionary will remain relatively small—some quite large XML documents in some applications could end up being nothing more than relatively small entries in the duplicate indices and the map store—the database footprint theoretically could even be smaller than the sum of the size of the documents stored. This means that the storage footprint displayed in our testing should be interpreted as only an approximation of what might occur in real-life applications.

 

The database administrator would typically configure the system so that the dictionaries, indices, and map stores are large enough to handle expected storage needs, plus a very comfortable pad. (In version 2.6 it is a pain for the administrator to increase the storage sizes, particularly for the core indices. Starting with version 3.0, at one time planned for summer of 2003 but now delayed, NeoCore suggests the administrator will be able to “grow” the storage files relatively easily.) So there will typically be a larger database footprint than is actually needed at any particular time. The size of this “padded” footprint is totally configurable by the database administrator, and so we did not consider it in our “footprint” calculations. We set up our initial database so that the dictionaries were five times the NeoCore defaults; the indices and the Map Store were 25 times default sizes. Combined with the normal binaries and configuration files, our total initial footprint is:

 

FILE

KILOBYTES

Dictionaries

56,320

Core indices

278,528

Dupe indices

491,680

Map files

184,320

Admin

268

Binaries

2,704

Configs

18

TOTAL

1,013,838

 

Assuming we would not need to expand our capacities later, this would be our total footprint. Obviously this initial footprint in our testing has virtually nothing to do with the size of the footprint needed in any particular application. Studying the results of our testing, as reported in Chapter 8, will be far more useful in determining the expected footprint.

 

Our technique for calculating footprint is the following. Prior to each run and after storing each document, our Store Tool asks the XMS to return the current server statistics. From these statistics we can calculate the amount of each database file that is actually being used. Our tool parses the server statistics string and stores the needed information in the output data file.

 

Top of Chapter

 

 

Test 2: Do We Get Out What We Put In?

 

Because of the NeoCore architecture the XML document is not stored in its original structure. A “flattened” version is implicitly contained in the Map Store, as explained in Chapter 3. When the document or portions of the document are needed later, the system uses formatting codes contained in each line of the Map Store to reconstruct the document. As a result, we should question whether we will get out of the system what we initially stored there, when we query for the entire original document. (Database professionals sometimes refer to the ability to store and retrieve a document accurately as “round tripping”.)

 

At a very minimum, we would expect that the logical structure is reproduced faithfully, including the ordering of the various elements. We also want to see to what extent the actual physical structure is reproduced.

 

Test 2 amounts to nothing more than storing some XML documents with syntactically legitimate structures, then querying for the entire document and comparing what we put in with what we got out. Appendix F contains the XML documents used for this test.

 

We will be putting in documents with a variety of features.

 

Top of Chapter

 

 

Test 3: Storage Speed

 

For each variety of XML document we are using for the test, we will input the entire 100 meg set sequentially, as though they are being input by a single client application.

 

For the standard XOO7 Benchmark data only, we will run a separate test in which independent client processes all send documents to the database at more or less the same time.

 

For the standard XOO7 Benchmark data, we will have (1) a reference test, establishing the time to store a document in a near-empty database; (2) a capacity test, determining the the time to store a similar document in a near-full database; and (3) a load test, determining the average time to store documents when several store commands are being processed at the same time. We will also be able to compare the performance using Benchmark data with the performance using other kinds of data.

 

Top of Chapter

 

 

Test 4: Queries for Accuracy

 

Here we perform the Benchmark XOO7 queries manually, one at a time, from the Console, until we verify that the correct responses are received. This test is conducted in conjunction with figuring out what kinds of modifications have to be made to the original XOO7 queries in order to get them to work in the NeoCore environment.

 

Top of Chapter

 

 

Test 5: Timed Benchmark Queries

 

In this test we perform the Benchmark queries again. This time through we time them and compare performance with the findings initially reported by the designers of the XOO7 Benchmark. In a second pass, we simulate several users performing the same query at once, in order to provide a load test. The Benchmark XOO7 methodology calls for performing each query ten times and taking the average as the observed query time.

 

Top of Chapter

 

 

Test 6: Working with Nearly Full Core Indices

 

NeoCore claims that with their architecture the seek time for an item in the core index remains at an average of 1.5 look-ups even with a full index. We explained the theory behind this claim in Chapter 5. We want to verify this in operation. We will exaggerate the effect by searching for a non-existent item, so that we have to cycle through the complete relevant mini-chain, as explained in Chapter 5. By searching for a non-existent item, we will not be accessing any database functionality except the Icon Generator and the core indices.

 

The procedure is to first create a new database, configured so that the core indices will be almost full when we fill up the database with about 100 megs of “Extensibility” data. Then, with nothing stored in the database except initialization information such as user names and passwords, we will do several simple queries for non-existent items. We will establish a standard for these simple queries (which return null results) by performing the query a hundred times and taking the average time. Because we are querying for non-existent items and because there are virtually no items in the core index except the few bits of user and password data, there are not likely to be any collisions in the core indices. Then we will load a series of “Extensibility” documents until one of the core indices totally fills up and we can add nothing more to the database. Then we will perform the same timed queries we started with—for the same non-existent items. There should be an increase in query time, reflecting that in the core indices, we are encountering collisions and travelling through the whole relevant mini-chains, as explained in Chapter 5. Note that this should be such a small difference, we might not be able to notice it—we are challenging the granularity limits on our timing capability, and almost all the time we measure will be in client-side loop control, HTTP conversion, socket communication, and icon generation. Further, the times we measure might be more dependent on how many CPU cycles the host platform happens to be using to support background processes. But it is OK if we are unable to detect consistently measurable differences: we are interested not so much in the exact number of milliseconds but in verifying that the core indices work almost as efficiently when near-full as when near-empty. We primarily want to show that the NeoCore indices, even when full, do not show lengthy delays from numerous disk look-ups such as we would get when using traditional hash tables.

 

Top of Chapter

 

 

Test 7: Extensibility Test

 

Any thorough evaluation of a native XML database should determine what kind of times will be encountered when applications are taking advantage of the extensibility built into XML. While most applications today still display stable relational-like database structures even when XML is being used, a native XML database in principle needs to be able to respond to other applications where the data arrives with wildly disparate and unanticipated data structures. The XOO7 development team recognized the problem inherent in many XML-enabled RDBMS databases: you have to “prepare” a database structure to accept any document that contains a new schema. So their methodology reported how much time it took to “prepare” the database.

 

Nonetheless, their benchmark does not test how well a native XML database like NeoCore’s handles unpredictable structures, and it is our belief that any thorough test of a native XML database should include timed stores with unexpected structural input. Accordingly, we include as Appendix C a C++ program which generates a series of XML documents that can be used as a simple test of XML database extensibility. We would run the program so as to create XML documents that total 100 MB in size. We store them all, comparing their times to storing benchmark documents.

 

After storing the “Extensibility” documents, we then need to show that the NeoCore search architecture can effectively search the diverse tag structures without special preparation. The “Extensibility” documents contain numerous one-character to four-character tags, each character chosen randomly from {a . . z}. For the extensibility search, we will simply generate some arbitrary three-character or four-character strings, and search all documents in a near-empty database and a near-full database, counting all tags with that name. Given the thousands of these tags, we will rarely get a null reply in the full database. What we are looking for are search times that are approximately the same as search times for analogous queries performed on Benchmark data.

 

Theoretically, the NeoCore architecture handles XML documents with unpredictable structures as easily as it handles documents that reflect a stable, predictable structure. We will use our extensibility test to verify this. (The extensibility documents will have significantly more diverse tag structures, and the size of the Tag Dictionary will therefore be much larger. Also, the extensibility documents will challenge the core indices more—and the duplicate indices less—than the standard benchmark documents.) It is our belief that a native XML database should be able to smoothly and quickly deal with such an extensibility test. None of the current XML benchmarks provides a good test of extensibility; it is our belief that those benchmarks should be supplemented by a test such as this.

 

Top of Chapter

 

 

Test 8: Insertion Test

 

When insertions are made to the XMS database, it creates a “jump” in the Map Store. If the insertions create duplicates, they also cause insertions into the Duplicate Indices and a potentially time-consuming reordering of the duplicate elements. This raises two questions. First, are the insertions made efficiently? Second, do subsequent queries retrieve the inserted items as efficiently as if they had been installed in correct order from the start?

 

The test is done in four steps. (1) In step one, we query for the attributes of existing “<Document>” elements in an XOO7 Benchmark document already stored. We perform the query 10 times and compute the average. (2) At step two, we insert a second “<Document>” as a sibling of every already existing “<Document>”. The structure of these new documents will be the same as those that already exist, although the attribute values will not match the set of attribute values for any of the original <”Document”> elements. The step two insertion can be made at the Console with a single insert command. (3) At step three, we delete the original “<Document>” elements, again with a single manual command from the Console. This results in a document which is logically identical to the original document. However, the similarity between the original document and the resultant document does not reveal the significant differences that now exist within the structure of the database files. In the database, the original entries in the Duplicate Index and the Map Store will be marked for deletion, insertions will have been made into the Duplicate Index at several different locations, and in the Map Store, there will be numerous “jumps”. (4) At step four of this test, we repeat the same ten queries used at step one.

 

We expect the average time to perform the query in step one will not be significantly different from the average time to perform the query at step four. We also expect that the insertions performed at step two will take place reasonably quickly—even though the database is creating numerous “jumps” in the Map Store and allocating new quanta in the duplicate indices.

 

Top of Chapter

 

 

Test 9: Non-indexed Substring Searches

 

NeoCore anticipates that in a future release, they will include the patented non-indexed search routine, mentioned in Searching for Non-Indexed Strings Within Text” in Chapter 6 of this report. Recognizing the possibility that we will want to evaluate that feature when it is added to the product, we are going to do some testing now so that we have a baseline against which we can compare our future testing. The issue will be: to what extent does the new, patented algorithm improve performance when searching for multiple strings within text?

 

To do this test, we first load a number of various text-heavy XML documents into the database. The texts we are listed below. We prepended each document listed with, for example, “<text_document dir=”Plato” doc=”Apology”>” and, of course, appended “</text_document>”. The documents totaled 5,805,072 bytes. Then we created a series of XML documents consisting of nothing but nonsense text, so as to put a total of 100 megs into the database.

 

Then we will run several queries looking for multiple (3–10) substrings within specific documents and several looking for similar substrings within all documents. We will also search for combinations of substrings which exist in none of our documents—such searches typically take a long time. We will also run queries looking for only one or two substrings—the patented search technique is designed to make searches for multiple substrings more efficient, but we want to verify that it does not degrade performance on more trivial substring searches.

 

We expect only average performance when these queries are run, since NeoCore is currently using standard algorithms for such searches. But we will have this data available when it is time to test the new search algorithm.

 

Top of Chapter

 

<< Chapter_6_Search_Architecture

Index of HTML Docs

Chapter_8_Findings >>

 

 



[1] It is important to rename the file and not to build it or copy it with the “neoNNN.xml” name. Renaming a complete file is an instantaneous operation in the sense that if it has the new name, it is ready for the Store Tool. Building or copying a file is a process that takes some time. If you were to build a file or copy a file with the “neoNNN.xml” name, it is possible that the Store Tool would grab it before the building/copying were complete and send a partial file to the database.

[2] We note from the NeoCore website that version 2.7, recently released, includes additional XQuery capability. Version 2.7’s primary purpose was to correct some stability problems; we did not encounter those problems.