Document using datatool is slow to compile

Question

The following document uses the datatool package, and is slow to compile, though the resulting PDF file is only 3 pages long. On my computer it takes of the order of 17 sec. I'm hoping for suggestions to speed things up.

Clearly most of the time is spent in datatool's database manipulations. The single line

\dtlsort{RowID}{docDB}{\dtlletterindexcompare}

currently takes approximately half the time of the compile, but it is not clear to me why.

UPDATE: Thus far there are two comments, basically saying - for the data processing steps (sorting and merging), use tools more suitable for the job. However, I'm unclear why using a fast sort algorithm (if that is part of the issue) is a problem. I found What are the Easiest/Cleanest way to create arrays for illustrating quicksort with tikz? which talks about quicksort in TeX.

Also, I'm automatically creating the table in question from the references in text based on @egreg's answer: Automatically creating a table from datatool using references in the text, so I can't easily separate the data processing step from the LaTeX file if I want to continue doing that. I suppose I could merge and sort the data before passing it to datatool...

I compile this with pdflatex filename.

######################
dto.tex
######################
\documentclass{letter}
\usepackage{datatool}
\usepackage{datagidx}
\usepackage{longtable}
\usepackage{lipsum}
\usepackage{array}
\usepackage{etoolbox}
\usepackage{url}
\setlength{\oddsidemargin}{-0.10in}
\setlength{\evensidemargin}{-0.10in}
\setlength{\topmargin}{-0.3in}
\setlength{\headsep}{0.2in}
\textheight=8.8in
\textwidth=6.7in
\newcounter{tabenum}\setcounter{tabenum}{0}
\newcommand{\colhead}[1]{\multicolumn{1}{>{\bfseries}l}{#1}}
\newcommand{\nextnuml}[1]{\refstepcounter{tabenum}\thetabenum.\label{#1}}
\makeatletter
\let\oldref\ref
\def\ref#1{%
  \immediate\write\@auxout{%
    \string\gappto\string\ReferencedIDs{#1,}%
  }%
  \oldref{#1}%
}
\def\ReferencedIDs{}
\makeatother

\usepackage{fouriernc}
\address{Some Address\\ Some Place\\Email: foo@bar.com}
\signature{(Somebody)}
\newcommand*{\checkmissing}[1]{\DTLifnull{#1}{}{#1}}

\newcommand{\PrintDocTableParekh}[3][]{%
 % #1 = list of rowIDs
 % #2 = database to search
 % #3 =caption
  \begin{longtable}{r l p{1.5in} c c p{2.5in}}
    \caption{#3}\\
   & \colhead{Date} & \colhead{Filename} & \colhead{From} & \colhead{To} & \colhead{Subject}\\\hline\endhead
    \DTLforeach
    [%
    \(%
    \equal{#1}{}\AND\DTLisSubString{\ReferencedIDs}{\RowID}%
    \)%
    \OR\(
    \DTLisSubString{#1}{\RowID}\AND\DTLisSubString{\ReferencedIDs}{\RowID}%
    \)%
    ]
    {#2}{%
      \RowID=RowID,%
      \Date=Date,%
      \Filename=Filename,%
      \From=From,%
      \To=To,%
      \Subject=Subject%
    }{%
      \nextnuml{\RowID} & \Date & {\bfseries\expandafter\url\expandafter{\Filename} } & \checkmissing{\From} & \checkmissing{\To} & \Subject \\
    }%
  \end{longtable}
}%

\makeatletter
\newcommand{\AddToTable}[2]{%
\DTLforeach*{#2}{\newDBRowID=RowID,\newDBDate=Date,\newDBFilename=Filename,\newDBFrom=From,\newDBTo=To,\newDBSubject=Subject}{
  \DTLnewrow{#1}
  {\let\DTLnewdbentry\relax % Avoid expansion of \DTLnewdbentry when using \protected@xdef below
   \protected@xdef\insertnewdbentry{%
     \DTLnewdbentry{#1}{RowID}{\newDBRowID}%
     \DTLnewdbentry{#1}{Date}{\newDBDate}%
     \DTLnewdbentry{#1}{Filename}{\newDBFilename}%
     \DTLnewdbentry{#1}{From}{\newDBFrom}%
     \DTLnewdbentry{#1}{To}{\newDBTo}%
     \DTLnewdbentry{#1}{Subject}{\newDBSubject}%
  }}\insertnewdbentry
}}
\makeatother

\begin{filecontents*}{documents.csv}
1952.02.19,19 Feb 1952,something.txt,subject
1994.03.26,26 Mar 1994,something.txt,subject
2010.11.04,04 Nov 2010,something.txt,subject
smyt.bs.ie,Mar 2004-2013 (incl.),something.txt,subject
ct.bs.ie,Mar 2004-2013 (incl.),something.txt,subject
cf.bs.ie,Mar 2004-2013 (incl.),something.txt,subject
ismail.bs.ie,Mar 2004-2013 (incl.),something.txt,subject
mh.bs.ie,Mar 2004-2013 (incl.),something.txt,subject
smyt.it,2007-2013,something.txt,subject
ismail.it,2008-2013,something.txt,subject
2013.10.05.powai,05 Oct 2013,something.txt,subject
2013.10.05.kanjur,05 Oct 2013,something.txt,subject
2013.10.28.zhm,28 Oct 2013,something.txt,subject
2014.02.26,26 Feb 2014,something.txt,subject
familytree,26 Feb 2014,something.txt,subject
trusts,26 Feb 2014,something.txt,subject
\end{filecontents*}

\begin{filecontents*}{correspondence.csv}
1998.09.14,14 Sep 1998,something.txt,FROM,TO,,subject
1998.09.16,16 Sep 1998,something.txt,FROM,TO,,subject
2001.05.23,23 May 2001,something.txt,FROM,TO,,subject
2007.06.10,10 Jun 2007,something.txt,FROM,TO,,subject
2011.05.09,09 May 2011,something.txt,FROM,TO,Y,subject
2011.09.09.slm,09 Sep 2011,something.txt,FROM,TO,Y,subject
2011.09.26.fm,26 Sep 2011,something.txt,FROM,TO,Y,subject
2011.09.26.slm,26 Sep 2011,something.txt,FROM,TO,Y,subject
2011.09.26.zhm,26 Sep 2011,something.txt,FROM,TO,,subject
2011.11.21.slm,21 Nov 2011,something.txt,FROM,TO,Y,subject
2011.11.21.fm,21 Nov 2011,something.txt,FROM,TO,Y,subject
2011.11.22,22 Nov 2011,something.txt,FROM,TO,Y,subject
2011.11.23,23 Nov 2011,something.txt,FROM,TO,Y,subject
2012.01.25,25 Jan 2012 (?),something.txt,FROM,TO,,subject
2012.12.07,07 Dec 2012,something.txt,FROM,TO,,subject
2013.01.14,14 Jan 2013,something.txt,FROM,TO,,subject
2013.08.29,29 Aug 2013,something.txt,FROM,TO,Y,subject
2013.09.09.fm,09 Sep 2013,something.txt,FROM,TO,Y,subject
2013.09.09.rm,09 Sep 2013,something.txt,FROM,TO,Y,subject
2013.09.10.slm,10 Sep 2013,something.txt,FROM,TO,Y,subject
2013.09.10.fm,10 Sep 2013,something.txt,FROM,TO,Y,subject
2013.09.10.slm2,10 Sep 2013,something.txt,FROM,TO,,subject
2013.09.11.slm1,11 Sep 2013,something.txt,FROM,TO,Y,subject
2013.09.11.fm,11 Sep 2013,something.txt,FROM,TO,Y,subject
2013.09.11.slm2,11 Sep 2013,something.txt,FROM,TO,Y,subject
2013.09.16,16 Sep 2013,something.txt,FROM,TO,,subject
2013.09.17,17 Sep 2013,something.txt,FROM,TO,,subject
2013.09.23,23 Sep 2013,something.txt,FROM,TO,,subject
2013.10.06,06 Oct 2013,something.txt,FROM,TO,,subject
2013.10.14.kma,14 Oct 2013,something.txt,FROM,TO,,subject
2013.10.14.ks,14 Oct 2013,something.txt,FROM,TO,,subject
2013.10.16,16 Oct 2013,something.txt,FROM,TO,,subject
2013.10.17,17 Oct 2013,something.txt,FROM,TO,,subject
2013.10.18,18 Oct 2013,something.txt,FROM,TO,,subject
2013.10.22,22 Oct 2013,something.txt,FROM,TO,,subject
2013.10.23,23 Oct 2013,something.txt,FROM,TO,,subject
2013.10.24,24 Oct 2013,something.txt,FROM,TO,,subject
2013.10.25.zhm,25 Oct 2013,something.txt,FROM,TO,,subject
2013.10.25.fm1,25 Oct 2013,something.txt,FROM,TO,Y,subject
2013.10.25.rm1,25 Oct 2013,something.txt,FROM,TO,Y,subject
2013.10.25.fm2,25 Oct 2013,something.txt,FROM,TO,Y,subject
2013.10.25.rm2,25 Oct 2013,something.txt,FROM,TO,Y,subject
2013.10.28,28 Oct 2013,something.txt,FROM,TO,,subject
2013.10.30,30 Oct 2013,something.txt,FROM,TO,,subject
2013.11.11,11 Nov 2013,something.txt,FROM,TO,,subject
2013.11.12,12 Nov 2013,something.txt,FROM,TO,,subject
2013.11.13,13 Nov 2013,something.txt,FROM,TO,,subject
2013.11.25,25 Nov 2013,something.txt,FROM,TO,,subject
2013.12.05.ta,05 Dec 2013,something.txt,FROM,TO,,subject
2013.12.05.slm,05 Dec 2013,something.txt,FROM,TO,,subject
2014.01.15,15 Jan 2014,something.txt,FROM,TO,,subject
2014.02.24,24 Feb 2014,something.txt,FROM,TO,,subject
2014.04.02,02 Apr 2014,something.txt,FROM,TO,,subject
2014.04.10,10 Apr 2014,something.txt,FROM,TO,,subject
2014.04.15,15 Apr 2014,something.txt,FROM,TO,,subject
2014.07.18.tm,18 Jul 2014,something.txt,FROM,TO,,subject
2014.07.18.ta,18 Jul 2014,something.txt,FROM,TO,,subject
2014.07.24,24 Jul 2014,something.txt,FROM,TO,,subject
2014.09.05.tm,05 Sep 2014,something.txt,FROM,TO,,subject
2014.09.05.ta,05 Sep 2014,something.txt,FROM,TO,,subject
2014.09.05.slm,05 Sep 2014,something.txt,FROM,TO,,subject
2014.10.17,17 Oct 2014,something.txt,FROM,TO,,subject
2014.11.12.tm,12 Nov 2014,something.txt,FROM,TO,,subject
2014.11.14,14 Nov 2014,something.txt,FROM,TO,,subject
2014.11.17,17 Nov 2014,something.txt,FROM,TO,,subject
2015.01.06,06 Jan 2015,something.txt,FROM,TO,,subject
\end{filecontents*}

\begin{document}

\def\today{9th January, 2014}
\begin{letter}{
    Someone\\
    Somewhere\\
    Subject: Some stuff
}

  \opening{Dear Someone}

  \lipsum[1]. Here is a ref - [\ref{2014.11.14}].

  \lipsum[2]. Here is a ref - [\ref{2014.11.14}].

  \lipsum[3] Here is a ref - [\ref{2014.11.17}].

  \lipsum[4]


  \lipsum[5] Here is a ref - [\ref{2014.11.14}].

  \lipsum[6] Here is a ref - [\ref{2014.07.18.tm}].

  \lipsum[7]

  \lipsum[8] Here is a ref - [\ref{2014.11.12.tm}].

  \lipsum[9]. See references
    ~[\ref{2013.10.05.kanjur}], [\ref{2013.10.05.powai}].
    [\ref{2013.10.06}], [\ref{2013.10.28.zhm}],
    [\ref{2013.10.17}], [\ref{2013.10.22}],

    \lipsum[10]. See references
    [\ref{2013.10.14.ks}], [\ref{2013.10.06}]
    [\ref{2013.10.17}], [\ref{2013.10.22}], [\ref{2013.10.24}],

    \lipsum[10]. See references
    [\ref{2013.10.28}], [\ref{2013.10.30}]

    \lipsum[10]. See references [\ref{2013.11.11}]

    \lipsum[11]. See references [\ref{2014.09.05.tm}]

    \lipsum[12]. See references
    [\ref{2014.07.18.tm}] [\ref{2014.11.12.tm}]

   \lipsum[13]. See references
    [\ref{2014.11.17}], [\ref{2015.01.06}], [\ref{2015.01.06}]

\closing{Yours Sincerely,}

\DTLloaddb[noheader,keys={RowID,Date,Filename,Subject}]{docDB}{documents.csv}
\newtermaddfield[docDB]{From}{From}{}
\newtermaddfield[docDB]{To}{To}{}
\DTLloaddb[noheader,keys={RowID,Date,Filename,From,To,Email,Subject}]{corrDB}{correspondence.csv}
\AddToTable{docDB}{corrDB}
\dtlsort{RowID}{docDB}{\dtlletterindexcompare}
\PrintDocTableParekh{docDB}{Documents}

\end{letter}
\end{document}

Answer 1

The datatool package uses an insertion sort algorithm. The gory details, for anyone who's interested, are described in section 4.10 of the datatool documented code. However, I agree with the comments. TeX is a typesetting tool (and a very good one) but there are a lot of things that it's not, which is why datatool has an accompanying helper application called datatooltk. It can load it's own native .dbtex format, which datatool can also load using \DTLloaddbtex (which loads far quicker than \DTLloaddb or \DTLloadrawdb). datatooltk can also load CSV, XLS, ODS and can fetch data from MySQL databases, and it can sort a database and merge two databases together. (It can also shuffle the database and filter out rows as well.)

For testing purposes I generated a CSV file containing a single column and 101 rows. The first row is the header row and the remaining 100 rows each contain a word or phrase randomly selected from a dictionary. The start of the CSV file (entries.csv) looks like:

Word
minnow
running board
dispirit
gravelly
sharp-tongued
penitentiary
vice
witness box
hydrochloric acid

Here's a test file (test-texsort.tex):

% arara: pdflatex
\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{datatool}

\DTLloaddb{test}{entries.csv}

\DTLsort{Word}{test}

\begin{document}

\DTLforeach*{test}{\Word=Word}{\Word. }

\end{document}

This just requires

pdflatex test-texsort

to compile. The next sample file (test-csv.tex) requires datatooltk to import and sort the data from the CSV file and convert it to entries.dbtex:

% arara: datatooltk: {csv: entries.csv, sort: Word, output: entries.dbtex}
% arara: pdflatex
\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{datatool}

\DTLloaddbtex{\testdb}{entries.dbtex}

\begin{document}

\DTLforeach*{\testdb}{\Word=Word}{\Word. }

\end{document}

This requires:

datatooltk --csv entries.csv --sort Word --output entries.dbtex
pdflatex test-csv

I converted the CSV file to XLS and ODS. The test files are exactly the same, although the datatooltk invocation requires different switches. Here's test-ods.tex (with modified arara directive):

% arara: datatooltk: {ods: entries.ods, sort: Word, output: entries.dbtex}
% arara: pdflatex
\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{datatool}

\DTLloaddbtex{\testdb}{entries.dbtex}

\begin{document}

\DTLforeach*{\testdb}{\Word=Word}{\Word. }

\end{document}

The command line invocations required to build the document are now:

datatooltk --ods entries.ods --sort Word --output entries.dbtex
pdflatex test-ods

Here's test-xls.tex:

% arara: datatooltk: {xls: entries.xls, sort: Word, output: entries.dbtex}
% arara: pdflatex
\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{datatool}

\DTLloaddbtex{\testdb}{entries.dbtex}

\begin{document}

\DTLforeach*{\testdb}{\Word=Word}{\Word. }

\end{document}

The command line invocations required to build the document are now:

datatooltk --xls entries.xls --sort Word --output entries.dbtex
pdflatex test-xls

I used arara version 4.0 to build all these documents, which gives the total time taken. Here are the results:

• test-texsort: 1.12 seconds
• test-csv: 0.42 seconds
• test-ods: 0.63 seconds
• test-xls: 0.57 seconds

I also converted the CSV file to a MySQL database. Here's test-sql.tex:

% arara: datatooltk: {sql: "SELECT * FROM words ORDER BY Word",
% arara: --> sqluser: sampleuser,
% arara: --> sqldb: samples, output: entries.dbtex}
% arara: pdflatex
\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{datatool}

\DTLloaddbtex{\testdb}{entries.dbtex}

\begin{document}

\DTLforeach*{\testdb}{\Word=Word}{\Word. }

\end{document}

The command line invocations are:

datatooltk --sql "SELECT * FROM words ORDER BY Word" --sqluser sampleuser --sqldb samples --output entries.dbtex
pdflatex test-sql

The total time was 4.23 seconds, which seems large, but most of that was caused by the time it took me to type the SQL password at the prompt. If I added the password to the command line invocation (which I don't recommend for obvious reasons) the time taken goes down to 0.58 seconds.

Merging another database can be performed using one of the --merge like switches, which are documented in the datatooltk user guide. The datatool package has a couple of commands that allow you to save a database in a .dbtex format: \DTLsaverawdb and \DTLprotectedsaverawdb. Rather than writing commands to the .aux file, you can create another database which you can use to store your references in and write out the database at the end of the document. Then use datatooltk to merge and filter.

For example:

% arara: datatooltk: {output: entries.dbtex, csv: entries.csv,
% arara: --> sort: Word, options: [--merge, Word, refs.dbtex],
% arara: --> filters: [[Used, eq, 1]] }
% arara: pdflatex
\documentclass{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage{datatool}

\DTLloaddbtex{\testdb}{entries.dbtex}

\DTLnewdb{refs}
\DTLaddcolumn{refs}{Word}
\DTLaddcolumn{refs}{Used}

\newcommand{\useword}[1]{% assumes no expansion required on #1
  \dtlgetrowindex{\myrowidx}{refs}{1}{#1}%
  \ifx\myrowidx\dtlnovalue
   \DTLnewrow{refs}%
   \DTLnewdbentry{refs}{Word}{#1}%
   \DTLnewdbentry{refs}{Used}{1}%
  \fi
}

\begin{document}

\DTLforeach*{\testdb}{\Word=Word}{\Word. }

Let's use the words  ``minnow''\useword{minnow}, 
``android''\useword{android} and ``felcity''\useword{felicity}.

\DTLsaverawdb{refs}{refs.dbtex}

\end{document}

The datatooltk invocation is now:

datatooltk --sort Word --filter Used eq 1 --csv entries.csv --merge Word refs.dbtex --output entries.dbtex

The first time I ran arara (when refs.dbtex doesn't exist) arara took 0.47 seconds and the resulting document looked like:

The second time I ran arara this took 0.45 seconds. The resulting document looks like:

The entries.dbtex file now only contains the three words that were used in the document on the previous run.

As for why I can't implement a more efficient sorting algorithm into datatool.sty, the answer to that is rather mundane: I run a business single-handed and I have a family to look after. I simply don't have all the time in the world to develop my LaTeX packages, and writing a TeX implementation of, say, the quick sort algorithm, would be extremely time-consuming, tiring and I don't see the point in it given that you can use datatooltk to sort instead.

Finally, a quick reminder of page i of the datatool user manual:

There's an old adage, "use the right tool for the right job." A carpenter's fine chisel is the right tool for delicate carving, but if you try to use it to hack off a tree branch it will take a long time. That doesn't mean there's something wrong with the chisel. It just means you're using the wrong tool for the job.

The datatool bundle is provided to help perform repetitive commands, such as mail merging, but since TeX is designed as a typesetting language, don't expect this bundle to perform as efficiently as custom database systems or a dedicated mathematical or scripting language. If the provided packages take a frustratingly long time to compile your document, use another language to perform your calculations or data manipulation and save the results in a file that can be input into your document. For large amounts of data that need to be sorted or filtered or joined, consider storing your data in an SQL database and use datatooltk to import the data, using SQL syntax to filter, sort and otherwise manipulate the values.