Inside OcientAIQ™: Modeling array queries

By Jason Arnold, Co-Founder, Director and Distinguished Engineer at Ocient

Welcome back. Over this series we have looked at casting and timestamps, arrays, tuples, the surface of the Earth, graph analytics, the Spark connector, and Dataflows. The previous array post was about syntax: how to declare an array column, how to index into it, and which operators OcientAIQ gives you. Today I want to come back to arrays from a completely different angle, and ask a question that syntax does not answer: How long is that query going to take?

Not “is it fast,” which is a marketing answer. I mean an actual number, in seconds, before you run it, for a table size and an array width and a predicate size you have not tried yet, on a cluster of whatever size you happen to have. That is a different kind of question, and answering it turned into one of the more interesting pieces of work I have been involved in lately.

Why this query shape is worth the trouble

The pattern I care about is deceptively simple. You have a table where each row carries a set of things, and you want the rows whose set touches some other set.

That && is the overlap operator: give me the rows where the array shares at least one element with the list. Its sibling @> is contains: give me the rows whose array holds all of the listed elements.

Once you start looking for this shape you find it everywhere:

• Ad tech: Each user profile carries a list of segment IDs. A campaign targets a list of segments. Which users match?

• Security: Each event carries a list of observed indicators. A threat feed publishes a list of bad indicators. Which events match?

• Telco: Each subscriber record carries a list of device or service codes, and you want everyone touching some set of them.

• Retail and recommendations: Each basket carries a list of product IDs, and you want the baskets containing a particular combination.

• Access control and entitlements: Each row carries a list of tags, and the caller carries a list of grants.

Every one of those is the same query, and in production none of them has three literals in the predicate. They have thousands. Sometimes hundreds of thousands, and the list of values usually is not typed by a human at all. It lives in another table.

That is the workload we wanted to characterize. Not “does it work,” but “here is the shape of the cost surface, so you can plan against it.”

Six models

We settled on six models because there are genuinely six different things people write. They split along two axes.

The first axis is where the values you are matching against come from. You can write them into the query text as literals, or you can read them out of a second table. That sounds like a trivial distinction and it absolutely is not, which I will get to.

The second axis is what you want back. Just the matching keys? The keys plus which elements actually matched? Or the rows that contain all of the values rather than any of them?

Here are all six, written out in full. t is the table being searched, with a key column and an INT[] column called attributes. needles is a single-column table holding the values to match against.

The symmetry is the point. Models 4 through 6 are models 1 through 3 with the literal array swapped for a subquery that collects the values out of a table. Same operators, same output, same three shapes. The only thing that changes is where the values came from, which is exactly the variable we wanted to isolate.

Five variables drive all six models. N is the number of rows in the table, A is the number of elements in each row’s array, L is the number of values you are matching against, M is the number of rows that come back, and F is the number of foundation nodes in your cluster.

How to read these exponents

Those formulas are compact, so let me unpack what each piece is actually telling you. Every model has the same skeleton.

The constant is the price of admission. 0.17 seconds for the inline forms, 0.40 for the table-sourced ones. It is planning, dispatch, and coordination, and you pay it if the table is empty. That 0.40 against 0.17 is the cost of involving a second table at all, and it is the entire reason the table-sourced forms lose at small value counts.

The L term is linear, but it is not the same work in every model. This is worth being precise about, because the coefficient means something different depending on where the values came from.

In models 1, 2 and 3 they are query text, so the L term is dominated by tokenizing and parsing them. That is why those coefficients are the largest of the six. A hundred thousand literals times 18.78 microseconds is 1.9 seconds of parsing before any data is touched.

In models 4, 5 and 6 they arrive as rows from another table, so nothing is parsed. But there is still work proportional to L: the engine has to read those rows and build the lookup structure the predicate tests against. That work is real, it just costs far less per value, which is why those coefficients are 3.56, 1.57 and 2.78 microseconds. Roughly a fifth of the inline cost, doing the useful half of the job and skipping the parsing.

The N^x * A^y product is the data work, and the exponents are the interesting part. An exponent of 1.0 would mean strictly proportional: twice the rows, twice the time. Every exponent in these models is well below 1.0, which means the engine gets more efficient per row as the table grows. Concretely, for model 1’s N^0.625:

Going from a million rows to a billion, a thousand times the data, costs 75 times the time rather than 1000. That gap is parallelism and per-row fixed costs being amortized across more work.

The same reading applies to A. Model 1’s A^0.475 means widening arrays from 10 to 1000 elements, a hundredfold, costs about 8.9x. The exponents on A differ noticeably between models, from 0.40 to 0.75, and the practical consequence is what matters: a query shape that looks cheap on narrow arrays does not necessarily stay cheap as arrays widen, and the model tells you which shape you are in. Compare the exponent on the shape you plan to run rather than assuming array width costs the same everywhere.

And (8/F) is the hardware term. Every model was fitted on an eight foundation node cluster, so at F = 8 the correction is exactly 1 and you recover the numbers we measured. At F = 16 the data term drops to 0.66x, and at F = 4 it rises to 1.52x. The next section explains where that came from, and why it multiplies only the data term.

One comparison across those coefficients is worth pulling out on its own, because it drives the main recommendation later in this post. Model 1 pays 18.8 microseconds per value and model 4 pays 3.6, and the two queries return the same answer. The difference is almost entirely that model 1’s values have to be tokenized as query text while model 4’s arrive as data.

The node count term

A model with no hardware term in it describes exactly one cluster, which is not much use to anyone who does not own that cluster. So we ran a separate scaling study on dynamically provisioned systems at several different foundation node counts, running an identical harness at every one: same queries, same repetitions, and value files generated from a fixed seed so the runs compare exactly.

One design decision in that study is worth explaining, because it is what makes the result trustworthy. We used only the ratios, never the absolute timings. The provisioned systems are slower per node than the cluster the models were fitted on. Mixing their raw numbers into the fit would have corrupted it. So the models stay fitted to the eight node cluster, and the scaling study contributes exactly one thing: the exponent.

Fitting T proportional to F^-k gives k = 0.59 on average, and 0.82 on the compute-heavy cases, with the single heaviest workload reaching 1.01. That heaviest case is the interesting one: an exponent of 1.0 is linear scaling, so four times the nodes made it four times faster.

I published 0.6 rather than the 0.82 the heaviest cases support, because it is the conservative number. To be explicit about what that means, since it is easy to misread: an exponent of 0.6 is sublinear, so it does promise less than proportional benefit.

So at 0.6, doubling your cluster does take more than half the original time. That is deliberate. The measured exponent reached 1.0 on the heaviest workload but fell to 0.27 on the lightest, and publishing the optimistic end of that range would leave someone short when they sized hardware against it. Under-promising is the right direction for a planning number.

The lighter workloads scale worse, and that is not a defect. When a query’s compute is only a few seconds, fixed costs are a meaningful fraction of it and there is not enough work to spread across additional machines. Extra nodes help in proportion to how much real work there is to divide. That is true of every distributed system, and the models now say so out loud.

The other half of the measurement is the part that confirms the formula’s shape. Holding the queries fixed and varying only the node count, the parse and fixed cost stayed flat, fitting an exponent of 0.03 at a hundred thousand values, while the data work on those same queries fitted 1.01. Across every workload measured, the parse term’s scaling exponent averaged 0.17 against the data term’s 0.59.

The parse cost does not care how many nodes you own, because tokenizing a hundred thousand literals happens once, on one node, before any data is touched. That is exactly why (8/F) multiplies only the data term in those six formulas and not the whole expression. If you throw hardware at a query whose cost is dominated by parsing a giant literal list, you will be disappointed, and the model will correctly predict your disappointment.

Where is the selectivity term?

If you have been reading closely, something should be bothering you. Only one of those six models mentions M, the number of rows that come back. Every database person’s instinct says selectivity is a first-order driver of query cost, so a model that ignores it looks broken.

It is a fair challenge and we spent real effort on it. The short answer is that we tested an output term in every model, and kept it only in the one where it earned its place. The longer answer is more interesting, and it comes in three parts.

First, selectivity was originally not free to vary at all. The measurement grid drew both the array elements and the match values uniformly from all positive 32-bit integers. That pins the value universe, call it D, and once D is fixed the number of matches is not an independent variable, it is a consequence:

Matched rows are a deterministic function of N, A, and L. Adding M as a separate parameter to a model fitted on that grid does not add information, it adds a term that is collinear with terms already present. Worse, with a universe of two billion values almost nothing matched, often under a tenth of a percent, so the output term had almost nothing to act on. The models were being fitted in one corner of the space.

Second, we broke that dependency on purpose and measured what happened. By shrinking the value universe while holding N, A, and L fixed, M moves on its own and its effect can be isolated. The result genuinely surprised me:

A thirteen-thousand-fold change in the number of matching rows moved a keys-only query by ten to twenty percent. Fitted as a free coefficient, model 1’s per-row output cost came out at 0.27 nanoseconds, which is indistinguishable from zero, and held-out accuracy was identical whether the term was included or not.

That is not a fitting artifact, it is mechanical. In a scan-based overlap, every row pays the array comparison whether or not it matches. Selectivity does not change how much work the engine does; it only changes how many keys survive. Emitting one more BIGINT is nothing next to the comparison that row already paid for. Selectivity determines how much output you carry, and for a keys-only query the output is tiny by construction.

Third, and this is where the asymmetry you can see in the formulas comes from, we fitted every model three ways and let held-out accuracy decide: no output term, a term proportional to M, and a term proportional to M times A for output volume rather than row count. Across 95 overlap points with M spanning one to ten million rows, only model 5 improved enough to justify the term. That is why model 5, and only model 5, carries + 43.82ns*M.

Model 2 is the case worth explaining, because the table above shows it is genuinely selectivity-sensitive and yet it has no M term. Both things are true. Its sensitivity is real, but on this grid it is already captured by its other terms: model 2 carries the steepest array exponent of the inline models at A^0.60 against model 1’s A^0.475, and nearly double the per-value coefficient. Adding an explicit M term on top moved the median only slightly and made the tail worse, which is the classic sign of a term the fit does not need. The output cost is in the model. It is just not wearing a label that says M.

So the honest summary is that the asymmetry is a finding, not an omission. Selectivity is first-order when the query returns payload and third-order when it returns keys, and where it does bite, it is not always best expressed as a row count.

Splitting the table from the array

An early version of these models used a single combined term of the form (N*A)^p, on the theory that what matters is the total number of elements the engine has to look at. It is a reasonable theory and it was wrong.

Splitting N and A into separate exponents improved every single model, and every held-out 90th percentile figure improved as well.

In hindsight it is obvious. Adding rows and widening rows are not the same operation. More rows means more of everything: more index work, more scheduling, more scan. Wider arrays means the same number of rows each carrying more payload, which stresses a different part of the engine. Forcing them to share an exponent was always a compromise, and the data said so as soon as we let them separate.

Do the models actually work?

This is the part that matters, because it is easy to fit a curve to data you already have and much harder to predict data you do not.

First, accuracy on the fitted data, plus a held-out test. The held-out numbers are leave-one-cell-out: we pull an entire configuration out of the data, refit the model without it, and then ask the model to predict the thing it never saw.

Median held-out error between 4% and 11%. That is good, but it only proves interpolation, because the removed cell still sits inside the range of everything else.

So we did the harder test. We picked points well outside the fitted ranges, printed the predictions before running the measurements, and then ran them.

Everything lands within 25%, at three times the largest value count any model was fitted on. Model 1 was also tested against arrays ten times wider than it was fitted on, and came in between 1.21x and 1.31x.

Predicting a billion-row query to within 13% from a formula with three terms is, I think, a genuinely useful result. It means capacity planning for this workload is arithmetic rather than a benchmark campaign.

It is also worth noticing the direction of the error, not just the size. Models 1 and 2 under-predict when you push far past a hundred thousand values, and under-prediction is the dangerous direction for capacity planning, so treat those as a floor rather than an estimate out there. Model 3 over-predicts, which is the safe direction.

The result that should change how you write these queries

Now for the practical payoff, and it is the one I would actually put on a slide.

If you have a large list of values to match against, keep it in the database. Do not pull it into your application.

The comparison here is against what people actually do when a database makes this awkward: run one query to fetch the values, build a giant literal list in the client, then run a second query with that list pasted in.

The in-database form carries about half a second of fixed cost for involving the second table, which is why it only reaches parity at a hundred values. Above a thousand it wins, and the margin keeps growing, because the inline form pays roughly 19 microseconds per value in parsing that the table-sourced form never pays at all.

Look at the in-database column again. It is essentially flat: 0.44, 0.35, 0.42, 0.40 seconds while the value count goes up by a factor of a thousand. The workaround column grows by more than 5x over the same range. That flat line is the whole argument.

There is a second reason to prefer it that the node-scaling numbers make concrete. Parsing does not parallelize, so the per-value parse term is the one part of these queries that adding hardware cannot touch. Every value you move out of the query text and into a table is cost moved from the term that ignores your cluster into the term that scales with it.

And the best part is that the fast way is the obvious way:

Point the predicate at a subquery over the table that holds your values, and let the engine handle the rest. That is model 4, and models 5 and 6 are the same move applied to the matched-elements and contains shapes.

Here is the thing about building a model: it forces you to look at a whole grid of configurations rather than the handful you would normally test, and then it tells you when a measurement does not fit the curve.

That turned out to be a remarkably good bug detector. Over the course of this work we found and fixed five separate issues in the engine, and I want to be clear that we found them because we were modeling, not because anything was visibly broken.

I am not going to walk through the internals, but the flavor is worth sharing:

• Two of the fixes were the same shape in two different places: work that logically only needed to happen once per query was being redone for every row. In the worse of the two, the subquery spelling above was re-reading and rebuilding its lookup set for every single row it tested. Fixing it took that query from 563 seconds to 0.4 seconds at a hundred thousand values, which is what makes the in-database column above flat.

• One was a plan-choice rule for the array index that counted values where it should have been comparing the cost of probing against the cost of scanning. The next section is about that decision.

• One was not in the array code at all. It was in a path that runs on every statement, and it only became visible because very large queries made it big enough to see.

All five are merged or in review. Every number in this post was measured on a single build containing all of them.

I want to be careful here, because the easy version of this section would be “we scan,” and that is not true. OcientAIQ has had a secondary index that serves array predicates for a long time. The honest statement is that whether it helps depends on where you are in the parameter space, and the boundary is sharper than most people expect.

The existing index probes one cursor per value, and each cursor costs a b-tree descent per segment whether or not it matches anything. So the two alternatives scale in opposite directions:

That single pair of lines explains the whole picture. Probing wins when there are few values and the arrays are wide, because you avoid streaming a lot of bytes. Scanning wins when there are many values or the arrays are narrow, because a scan does not care how long your list is.

Measured across several regimes, each against an identical unindexed twin table so the scan alternative was measured rather than assumed: