Benchmarking in BaseX: how to set up

Question

Currently I am an intern at a research group that makes large sets of texts (corpora) searchable. Not only can one search for literal strings, but more importantly it is also possible to look for similar syntactical dependency structures as the given input, without the need of being proficient in any programming language or corpus annotation style. It may be clear that this tool is intended for linguists.

At the start of the project - before I was engaged in the project - the tool was limited to rather small corpora (up to 9 million words). The goal is to make large sets of texts searchable as well. We are talking about +- 500 millions words. Attempts have been made that in theory ought to improve speed by reducing the search space (see this paper) but this has not been tested yet. The results of this attempt is a new file structure. Let's call this structure B, compared to a non-processed structure A. We expect B to provide faster results when queried with BaseX.

My question is: what is the best way to test and compare both approaches with a Perl script? Below you find my current script to query BaseX locally. It takes two arguments. A directory that stores different files. These files each individually store XPaths. Those XPaths are the ones that I have selected to benchmark with. A second argument is the limit of results to return. When set to zero, no limit is set.

Because some parts of the dataset are so incredibly huge, we have divided them in different, equally sized files as well, called treebankparts. They are stored in <tb> tags inside treebankparts.lst.

#!/usr/bin/perl

use warnings;

$| = 1;    # flush every print

# Directory where XPaths are stored
my $directory = shift(@ARGV);

# Set limit. If set to zero all results will be returned
my $limit = shift(@ARGV);

# Create session, connect to BaseX
my $session = Session->new([INFORMATION WITHHELD]);

# List all files in directory
@xpathfiles = <$directory/*.txt>;

# Read lines of treebank parts into variable
open( my $tfh, "treebankparts.lst" ) or die "cannot open file treebankparts.lst";
chomp( my @tlines = <$tfh> );
close $tfh;

# Loop through all XPaths in $directory
foreach my $xpathfile (@xpathfiles) {
    open( my $xfh, $xpathfile ) or die "cannot open file $xpathfile";
    chomp( my @xlines = <$xfh> );
    close $xfh;

    print STDOUT "File = $xpathfile\n";

    # Loop through lines from XPath file (= XPath query)
    foreach my $xline (@xlines) {
        # Loop through the lines of treebank file
        foreach my $tline (@tlines) {
            my ($treebank) = $tline =~ /<tb>(.+)<\/tb>/;
            QuerySonar( $xline, $treebank );
        }
    }
}
$session->close();

sub QuerySonar {
    my ( $xpath, $db ) = @_;

    print STDOUT "Querying $db for $xpath\n";
    print STDOUT "Limit = $limit\n";
    my $x_limit;
    my $x_resultsofxp = 'declare variable $results := db:open("' . $db . '")/treebank/alpino_ds'
      . $xpath . ';';
    my $x_open       = '<results>';
    my $x_totalcount = '<total>{count($results)}</total>';
    my $x_loopinit   = '{for $node at $limitresults in $results';

    # Spaces are important!
    if ( $limit > 0 ) {
        $x_limit = ' where $limitresults <= ' . $limit . ' ';
    }
    # Comment needed to prevent `Incomplete FLWOR expression`
    else { $x_limit = '(: No limit set :)'; }

    my $x_sentenceinfo = 'let $sentid := ($node/ancestor::alpino_ds/@id)
        let $sentence := ($node/ancestor::alpino_ds/sentence)
        let $begin := ($node//@begin)
        let $idlist := ($node//@id)
        let $beginlist := (distinct-values($begin))';

    # Separate sentence info by tab
    my $x_loopexit = 'return <match>{data($sentid)}&#09;
        {string-join($idlist, "-")}&#09;
        {string-join($beginlist, "-")}&#09;
        {data($sentence)}</match>}';
    my $x_close = '</results>';

    # Concatenate all XQuery parts
    my $x_concatquery =
        $x_resultsofxp
      . $x_open
      . $x_totalcount
      . $x_loopinit
      . $x_limit
      . $x_sentenceinfo
      . $x_loopexit
      . $x_close;

    my $querysent = $session->query($x_concatquery);

    my $basexoutput = $querysent->execute();
    print $basexoutput. "\n\n";

    $querysent->close();
}

(Note that this is a stripped down version and that it may not work as-is. This snippet does not use structure B!)

What happens is: loop through all XPath files, loop through each line in an XPath file, loop through all treebankparts and then execute the sub. The sub then queries BaseX. This comes down to sending a new XQuery to BaseX, and returning the total hits and the results (possibly limited by an argument in the Perl script). So I got that going, but now the question is: how can I improve this script so I can get some benchmarking results out of it.

First of all, I'd start with adding a profiler to this script. I guess that bit is obvious. However, I am not sure how I should start comparing structure A with B. Would I put both queries (to different databases) in separate scripts, then call a profiler on both, and run both scripts a number of times and get a mean value and compare? Or would I run each query by both databases in the same script, almost at the same time?

It is important to consider caching that is happening. Therefore I am not entirely sure what build-up for benchmarking of a database this huge is appropriate. First one script, then the other. Both at the same time. Alternating queries between the two. And so on. There are so many possibilities, but I wonder which would provide the best results. Also, I would repeat the process a couple of times. Would I repeat each query and then continue to the next, or finish all XPath files, and then repeat the whole process again?

(Reading the description of the benchmark-tag I am confident that this - albeit elaborate - post is suited for SO.)

Answer 1

One possible improvement: minimize the number of times you transfer control from Perl to the database -- just as you have minimized the number of database connections. (Or at least set yourself up to measure the cost of the transfer of control.) I suspect you will get significantly better results if you move your loop into XQuery rather than running the loop in Perl.

A single call to a database management system asking it to perform 1000 searches is likely to be somewhat faster than 1000 calls to the DBMS each requesting a single search. The first involves two context switches: one from your script or bash to the dbms, and one back; the second involves 2000. The last time I measured something like this carefully, each context switch cost something like 500 ms; it mounted up fast. (That said, this was a long time ago, with a different database. But it was surprising [and sobering] to learn than the difference between the two query formulations I was trying to compare was dwarfed by the difference between running the test loop in a script or inside the dbms.)

A second suggestion: From what you say, the size of the database and the result sets seem likely to ensure that caching between runs doesn't have a big effect on the results. But this seems to be a testable assertion, and one worth testing. So set up your A and B scripts, and then do a trial run: does for runcount in 1 2 3 4 5; do perl A.pl; perl B.pl; done produce results comparable to for runcount in 1 2 3 4 5; do perl A.pl; done; for runcount in 1 2 3 4 5; do perl B.pl; done? If they are comparable, then you have reason to believe it doesn't matter if you run A and B separately or in alternation. If they are not comparable, then you know it does matter, which would be very valuable information. Other things being equal, I would expect caching to produce lower times when running one query several times before moving on to the next query, and cache misses to produce higher times if running each query just once. Probably worth measuring.

In the same spirit, I would recommend that you run tests both with the loop in the Perl script and with the loop in an XQuery query.

A third suggestion: in practice, a query at the corpus query interface will involve several stages, each with measurable time: transmission of the query from the user's browser (assuming it's a Web interface) to the server, translation of the request into a form suitable for transmission to the back end dbms (here BaseX), context switch to BaseX, processing within BaseX, context switch back, handling by web server, transmission to user. It would be useful to have at least rough estimates of the times involved in each of these steps, or at least of the time taken for everything-but-BaseX.

So if it were me running the tests, I think I'd also prepare a set of vacuous XQuery tests, along the lines of

2 + 3

or just

42

to push the BaseX time as close to zero as possible; the measured time between user initiation of the query and display of response is the per-query overhead. (Interesting question: should one use many different trivial expressions to prevent caching of results, or should one use the same expression over and over, to encourage caching of the result? How can we try to ensure that BaseX will cache the result, but the Web server won't? ...)

A final suggestion: remember that other people who need to do benchmarking will often have the same questions as you do. This means that you can reformulate every question of the form "Should I do X or Y?" into the form "What measurable effect does the difference between X and Y have on the results of a benchmarking test?" Run some tests to try to measure that effect, and write them up. (I always find it makes it more interesting if I force myself to make a prediction after formulating the question but before measuring the difference.)

Answer 2

There are several things we have to separate here: The first issue is that BaseX performance should not be confused with your perl script as your perl script seems to simply construct an XQuery (and not XPath as you suggested in your question and tags). So for testing I would suggest to use some already pre-fined XQueries suitable to your real-world scenarios, as your XQuery construction should be negligible. How you pass your query to BaseX, so via the Perl API or via any other means should not be relevant. Even if your perl performance is relevant, you should test the performance separately.

Hence, your original question whether you should put test both scenarios in the same script or not is not relevant anymore. Instead you simply execute the two separate XQueries for the scenario A and B by themself without the perl script.

You are partly correct to worry about caching, however it is the Java JIT compiler which most likely will be relevant here (as BaseX is written in java, JIT and use caching, not BaseX itself. You should therefore use the Client/Server infrastructure and have a long-running server and warm it up before running performance measurements.

Regarding performance: The BaseX GUI and also the command line already have an included measurement (using command line you can set -V to get run times for parsing, compiling, evaluating and printing). Also, using the -r parameter you can execute a query multiple times and it will give you the average execution times.

In general, if you want to improve the performance of your script you should take a look at the query plan and the optimized query and check whether the appropriate indexes are used. Also, our new Selective Indexing might be very useful to you. If the index isn't used, your query will definitely not perform well for 500 million words.

Full Disclosure: I am with the BaseX team and you might get better help at the BaseX mailing list or might want to reference this questions as our head architect isn't watching SO as regularly as the ML.