Why is Query so much slower than Part?

Question

Time for another of these^(1),(2) as yet another new-in-10 function appears to have poor performance compared to older alternatives. This time: Query appears to be orders of magnitude slower than Part when used for simple extraction.

For example:

Needs["GeneralUtilities`"]

x = RandomInteger[99, 1*^6];
spans = Span @@@ Partition[Sort @ RandomInteger[{1, 1*^6}, 5000], 2, 1];

Do[x[[s]], {s, spans}]      // AccurateTiming
Do[Query[s][x], {s, spans}] // AccurateTiming

0.00447013

3.586205

Here Query is 800 times slower than Part. I know that Part is well optimized for packed arrays. Perhaps Query hasn't been similarly optimized yet. Let's try unpackable data:

x = "a" ~CharacterRange~ "z" ~RandomChoice~ 1*^6;

Do[x[[s]], {s, spans}]      // AccurateTiming
Do[Query[s][x], {s, spans}] // AccurateTiming

0.0106673

3.594706

Alright, that seems to account for some of the difference as Part is only 337 times faster than Query here, but that is still a huge difference. The reason I was interested in Query is that by default it will not fail on out-of-bounds span ranges as Part will:

a = Range[9];

a[[5 ;; 11]]

Query[5 ;; 11][a]

Part::take: Cannot take positions 5 through 11 in {1,2,3,4,5,6,7,8,9}. >>

{1, 2, 3, 4, 5, 6, 7, 8, 9}[[5 ;; 11]]

{5, 6, 7, 8, 9}

It also returns a Missing expression for a single part that is out-of-bounds:

Query[12][Range@9]

Missing["PartAbsent", 12]

This feature is controlled by PartBehavior. Perhaps its overhead is high so let's turn it off and try again:

SetOptions[Query, PartBehavior -> None];
Do[Query[s][x], {s, spans}] // AccurateTiming

3.568204

Well that doesn't seem to be the case. Thankfully Szabolcs's post in Why is Dataset upset by division by zero? made me take a look at the other options for Query. With MissingBehavior set to Automatic Query will apply special rules for certain operators when there are Missing[] expressions:

Query[Total] @ {1, 2, 3, Missing[]} 

6

This should have no role for Span however:

Query[2 ;; 4] @ {1, 2, 3, Missing[]}

{2, 3, Missing[]}

Let's turn it off and time again just to be sure:

SetOptions[Query, MissingBehavior -> None];
Do[Query[s][x], {s, spans}] // AccurateTiming

0.355520

It seems we have found the cause of most of the slow-down, yet it makes no sense to me for this to have any effect as there is no special behavior to apply for Missing elements in a Span operation.

With FailureAction -> None this comes down to 0.285016 second, or ~27 times slower than Part on unpacked data.

Questions

1. Why would MissingBehavior affect the speed of a Span operation?

2. Why is Query still many times slower than Part, even with all special handling turned off?

Answer 1

Let's start by taking a look at the compiled form of one of our queries:

Dataset`CompileQuery[Query @ First @ spans]

(* Dataset`WithOverrides@*Checked[Slice[205 ;; 313], Identity] *)

We can see that the operation is not implemented directly in terms of part. Indeed, there are three components: Dataset`WithOverrides, GeneralUtilities`Checked and GeneralUtilities`Slice.

Dataset`WithOverrides is an elaborate function that implements MissingBehaviour. A quick peek at the output of ??Dataset`WithOverrides shows that it scans its input ten times, each time looking for some kind of missing data. It handles all possible cases, whether they involve associations, lists, sequences, etc. There is some scope for improvement in this function. For example, it could check the cases in one pass instead of ten. However, there are a lot of rules to check and so long as they are expressed using pattern-matching, this function is going to remain costly. This function is responsible for all but a few percent of the total runtime. Fortunately, it can be disabled using MissingBehaviour -> None as observed in the question:

Dataset`CompileQuery[Query[First @ spans, MissingBehavior -> None]]

(* Checked[Slice[205 ;; 313], Identity] *)

This brings us to GeneralUtilities`Checked. Its role is to implement FailureAction. ?? shows us that this function is nowhere near as elaborate as Dataset`WithOverrides, but it still represents some overhead. Again, it can be turned off:

Dataset`CompileQuery[Query[First @ spans, MissingBehavior->None, FailureAction->None]]

(* Slice[205;;313] *)

Finally, we are left with GeneralUtilities`Slice. Presumably this function is being used instead of Part on account of part syntax within the context of Query being more general. More spelunking commands can give us some insight:

??GeneralUtilities`Slice

??GeneralUtilities`Slice`PackagePrivate`slice

??GeneralUtilities`Slice`PackagePrivate`part

Following the observed theme, we see that these functions are very elaborate and general. They need to handle any possible type of input, not just the lists that we feed them in this example.

Taking Stock

The recurring pattern we see in these query components is that they must deal with very general cases. As it stands, the query compiler has no idea what kind of operand is going to be passed to Query. It could receive any arbitrary nesting of datasets, associations, lists and general expressions. Therefore, the so-called "compiled" form is really an interpreter. To be truly compiled, there would need to be more type information available up front.

For example, if the TypeSystem` type were known ahead of time, our final compiled query expression could use Part directly (possibly with an optional light wrapper to verify that the passed operand conforms to the predeclared type).

A further complication for queries is that in general they have parameters other than the queried object. In our case, the slice specification is different for each query. Ideally, we would be able to describe the types of such parameters to the compiler rather than having to pass values explicitly. In the case at hand, this would mean that we would only have to incur the overhead of compiling the query once, instead of compiling it once per slice.

Perhaps we will see such enhanced query compilation capabilities in a future release if WL starts to drift towards being a hybrid early/late binding language like Lisp. But until then, we must "compile by hand" as necessary.

---

Update

The assertion above that Dataset`WithOverrides scans its input multiple times is incorrect. In fact, the scans are used to monkey-patch many system functions. These patches implement the MissingBehavior functionality, but they also have the potential to disturb the normal operation of those functions outside of the query machinery. For an example of such unexpected behaviour, see Possible Bug in ProbitModelFit when used in a Dataset.

Answer 2

This is not an answer. It is just a very long comment.

Both a simple manually operated drill press and a computer-controlled five-axis omni-mill can drill a hole through a piece of bar stock. And both will do the actual drilling in about the same amount of time. If one hole in one bar is all you want, then you will accomplish the job much faster with the old-fashioned drill press, because the set-up time on the omni-mill will totally overwhelm the actual drilling operation.

Is the foregoing analogy applicable to the matter brought up in this question? I don't know, but it might be. Could it be that before it can apply optimized, low-level code to actually do the job, Query has a lot of high-level (slow) code to run to figure out what it has been asked to do?

Query is a brand-new and very complex function. Perhaps we shouldn't be surprised that Query 1.0 is slow. I predict it will speed up in future releases as the developers refine it.

The documentation for Query is interesting in that it starts with only one usage message:

Query[operator-1, operator-2, ....] represents a query that can be applied to a Dataset object, in which the successive operator-i are applied at successively deeper levels.

It then, in a seeming contradiction, goes on to give many examples of Query applied to associations rather than to datasets. Still, I believe the initial usage message holds a real truth; WRI implemented Query as a five-axis omni-mill to do fancy machining on datasets.