Hi all,
I'd like to open a discussion on whether index-only plans over a VTree (new
vector index) need the same protection against search in mid-writes (we've
been calling it the Halloween" problem here) that B-Tree index-only plans
have, and on the state of the code behind the original B-Tree mechanism.
Background: the B-Tree index-only plan
Given a secondary B-Tree index on a field that a query both filters on and
projects:
create index idx_review on ds(review);
FROM ds d
WHERE d.review<6
SELECT d.id, d.review
LIMIT 10;
so that the optimizer answers the query from the secondary index alone:
distribute result [$$32]
> -- DISTRIBUTE_RESULT |UNPARTITIONED|
> exchange
> -- ONE_TO_ONE_EXCHANGE |UNPARTITIONED|
> limit 10
> -- STREAM_LIMIT |UNPARTITIONED|
> project ([$$32])
> -- STREAM_PROJECT |PARTITIONED|
> exchange
> -- SORT_MERGE_EXCHANGE [$$34(ASC) ] |PARTITIONED|
> assign [$$32] <- [{"id": $$34, "review": $$33}] project:
> [$$34, $$32]
> -- ASSIGN |PARTITIONED|
> limit 10
> -- STREAM_LIMIT |PARTITIONED|
>
> * exchange*
> * -- ONE_TO_ONE_EXCHANGE |PARTITIONED|*
> * distinct ([$$34])*
> * -- PRE_SORTED_DISTINCT_BY |PARTITIONED|*
> * exchange*
> * -- ONE_TO_ONE_EXCHANGE |PARTITIONED|*
> order (ASC, $$34)
> -- STABLE_SORT [$$34(ASC)] |PARTITIONED|
> exchange
> -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
> select (lt($$33, 6))
> -- STREAM_SELECT |PARTITIONED|
> exchange
> -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
> unnest-map [$$33, $$34] <-
> index-search("idx_review", 0, "Default", "test", "ds", false, false, 0, 1,
> $$36, true, false, false)
> -- BTREE_SEARCH |PARTITIONED|
> exchange
> -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
> assign [$$36] <- [6]
> -- ASSIGN |PARTITIONED|
> empty-tuple-source
> -- EMPTY_TUPLE_SOURCE
> |PARTITIONED|
Note the sort on the primary key followed by DISTINCT above the secondary
search. That is the current answer to the 'halloween problem', which has
been handled in two ways over time:
1. The fork design (ASTERIXDB-1972
<https://issues.apache.org/jira/browse/ASTERIXDB-1972>, index-only plan,
2018-02-15). The secondary index-only search was given an instant-try-lock
callback. For each entry scanned, the cursor hashed the primary key and
tried an instant shared lock. Success meant no writer held the key, so the
entry could be emitted from the secondary index. Failure meant a write on
that key was in flight, so the entry had to be verified against the primary
index. (The optimizer built this fork up front: the unnest-map emitted an
extra boolean column with the try-lock result, a SPLIT routed each record
on that column so that records whose lock attempt failed went through a
primary BTREE_SEARCH, and a UNION_ALL merged the two branches).
2. The simplification (ASTERIXDB-3637
<https://issues.apache.org/jira/browse/ASTERIXDB-3637>, "[COMP] Simplify
Index-only plan", 2023-08-17). The lock is no longer acquired. In the words
of the commit message: "since no locks are acquired during the secondary
index scan, a sort on the PK is added after searching the secondary index,
followed by a DISTINCT operation to ensure result correctness. In the case
of an index nested loop join, a window function is used." The change
removes the SPLIT and UNION_ALL construction from the optimizer and adds
the DISTINCT and WINDOW operators instead.
Questions
1. Would a VTree index-only plan need to address the same problem? If so,
is the B Tree mechanism the pattern to follow for the vector
index-only plan?
2. Existing code in `SecondaryIndexInstantSearchOperationCallback`, is it
still active or used by other secondary indexes ?
public boolean proceed(ITupleReference tuple) throws HyracksDataException {
int pkHash = computePrimaryKeyHashValue(tuple, primaryKeyFields);
try {
return lockManager.instantTryLock(datasetId, pkHash,
LockMode.S, txnCtx);
} catch (ACIDException e) {
throw HyracksDataException.create(e);
}
}
[ai said " the code is present but inert ", which made sense here since the
patch 3637 disable the 'try-lock and fork' path for BTree index-only in the
optimizer code]. It's more of a code demystifying question.
see also JIRA issue here
<https://issues.apache.org/jira/browse/ASTERIXDB-3897>.
Thanks,
Hongyu
