Why do lookup times in Dataset and Association differ by orders of magnitude?

Question

Consider the following three data structures: a list of rules, an association, and a dataset:

 n = 1000000;
 list = (ToString[#] -> #) & /@ Range[n];
 assoc = Association@list;
 dataset = Dataset@assoc;

When I try to look up an element "1000000", I get radically different run times:

 ns = ToString[n];
 {ns /. list // AbsoluteTiming, assoc[ns] // AbsoluteTiming, dataset[ns] // AbsoluteTiming}

The results are:

{{0.090609, 1000000}, {5.*10^-6, 1000000}, {0.000237, 1000000}}

Why is Dataset so much slower than Association?

Answer 1

As @Mr.Wizard notes in a comment, some discussion about the overheads associated with querying can be found in another question (56609).

This response will use Mathematica version 10.1.0 to examine the specific behaviour described in the present question. The general principles under discussion are the same for the various 10.0.x versions, but some details differ between releases.

I'll start by showing my timings of the original expressions and along with a few others that will be examined later:

Needs["GeneralUtilities`"]

Function[, {HoldForm[#], AccountingForm @ First @ RepeatedTiming[#;, 1]}, HoldAll] /@
  Unevaluated @
    { ns /. list
    , assoc[ns]
    , dataset[ns]
    , dataset[]
    , Slice[ns][assoc]
    , StrictSlice[ns][assoc]
    } // TableForm

(*
   ns /. list               0.191
   assoc[ns]                0.00000063
   dataset[ns]              0.000149
   dataset[]                0.0000479
   Identity                 0.00000018
   Slice[ns][assoc]         0.00000455
   StrictSlice[ns][assoc]   0.00000239
*)

The expression dataset[] evaluates an no-op query (Identity) upon the dataset. The runtime associated with an Identity operation is negligible, yet the time taken to execute dataset[] is almost a third of the time necessary to compute dataset[ns]. This time is consumed by various overheads associated with query execution, including such things as:

• query compilation
• data type deduction
• dataset validation
• dataset information caching
• operator interpretation and rewriting
• non-standard expression evaluation
• PartBehavior, MissingBehavior, FailureAction handling
• all of the myriad standard expression evaluations that occur while implementing these features

These overheads are absent when the operation is performed using a "bare" association.

If we compile the dataset query, we see that it resolves to an invocation of GeneralUtilities`Slice:

Query[ns] // Normal

(* GeneralUtilities`Slice *)

As the timings show, this function has more overhead than a direct application of an association. This is because it implements the default PartBehavior of queries.

We can eliminate that particular overhead by turning it off explicitly:

Query[ns, PartBehavior -> None] // Normal

(* GeneralUtilities`StrictSlice *)

The timings show that StrictSlice has less overhead than Slice, but it is still slower than a direct application of an association (which to all appearances seems to be a built-in kernel operation). If the query compilation process were sensitive to the exact data, it could replace StrictSlice with such a direct application, but the present implementation does not do that.

All of the queries considered in this question execute very quickly, and thus the overheads introduced by Dataset are proportionately very large. But if the queries were long-running (say, a second or more), then the overhead would be insignificant. However, this does mean that if one is going to run a large number of fast-running queries, it might make sense to avoid using Dataset or Query. Alternatively, we might seek ways to replace many small queries with one large query.

We are thus faced with a design decision whether to enjoy the notational convenience of Dataset in exchange for the runtime overhead. We can get closer to the best of both worlds if we precompile a query once using Query[...] // Normal, and then apply the resulting function many times to the data directly.

In closing, I will note that the Dataset / Query machinery gathers a lot of interesting metadata about the data and operations to be performed. The 10.0 and 10.1 implementations presently do not make much use of this metadata when compiling and executing queries. I (wishfully) expect some future release of Mathematica to put all of this metadata to better use. It could be used to make better operator selections, as mentioned with respect to StrictSlice earlier, or to store data within Dataset objects in high-performance data structures. When (if) that happens, then we will have the convenience of Dataset notation and the query execution overheads might not only pay for themselves but return dividends as well.