Would you mind writing a design one-pager to track this once you've got a more solid idea of what you're building? This will be useful for the style team to understand what's changing.

Here's a prototype approach I tried a long time ago:
https://codereview.chromium.org/1496533003

It was years ago, but as I recall the virtual calls made the micro benchmarks regress some, but I don't know how bad that'd be in realistic usage. I also didn't correctly implement the traverse scope optimization where if you write ".a div" we first scan the document with a fast path looking for ".a", and then fall back to running the real SelectorChecker since that's more expensive.

I also learned quite a bit in the process of that patch:

- The bloom filter (SelectorFilter) is really expensive when you're matching a single selector across the tree, instead of many selectors like inside recalcStyle. It doesn't seem to make sense to use it here, the overhead easily defeats the win.

- The SelectorCheckingContext, SelectorChecker and Init objects are never reused inside selectorMatches whic adds up in the micro benchmarks initializing the same 20 struct fields repeatedly for simple selectors. This is also true inside recalcStyle, but making the internals of SelectorChecker avoid copies of SelectorCheckingContext proved difficult with how that code works. I don't have good ideas how to fix the copy cost yet or how much we should care, but it's definitely there.

I'll write a doc once I'm done experimenting. Right now I'm leaning towards a design where we build a sequence of operations (QueryPlan) that we then execute. Much like CSSSelector is a list of operations executed inside SelectorChecker, we'd have a list of operations in the QueryPlan like:

.a div => [FindByClass(.a), FindByTag(div)]

Today the code is very confusing trying to handle all these cases manually and the operations are not composable, ex.
https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/dom/SelectorQuery.cpp?q=selectorquery.cpp+package:%5Echromium$&l=263

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/2ea907e4d0ea17ae9bc9293694db1128f2237ddc

commit 2ea907e4d0ea17ae9bc9293694db1128f2237ddc
Author: esprehn <esprehn@chromium.org>
Date: Wed Mar 22 08:04:01 2017

Merge SelectorDataList into SelectorQuery.

Having a separate class doesn't really do anything here except mean we
need proxy methods to call through to it. This patch merges the two
classes and removes those proxy methods. I also made some methods into
file level functions since they didn't use any instance data.

Finally I added comments linking to the specs for each of the four
query methods.

This patch should have no behavioral changes.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2765993003
Cr-Commit-Position: refs/heads/master@{#458680}

[modify] https://crrev.com/2ea907e4d0ea17ae9bc9293694db1128f2237ddc/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/2ea907e4d0ea17ae9bc9293694db1128f2237ddc/third_party/WebKit/Source/core/dom/SelectorQuery.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/146a91c44120872cb59aba6078b7cb40e4e8f4f6

commit 146a91c44120872cb59aba6078b7cb40e4e8f4f6
Author: esprehn <esprehn@chromium.org>
Date: Thu Mar 23 00:09:36 2017

Centralize more querySelector logic behind QuerySelectorCache.

We make the types to the functions more clear, move the empty selector
check inside, and handle the NthIndexCache automatically instead of
expecting the callers to do the setup.

This also unifies the exception messages for matches(), closest(),
querySelector(), and querySelectorAll() when an empty string is passed.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2769783002
Cr-Commit-Position: refs/heads/master@{#458942}

[modify] https://crrev.com/146a91c44120872cb59aba6078b7cb40e4e8f4f6/third_party/WebKit/LayoutTests/fast/dom/Element/matches-expected.txt
[modify] https://crrev.com/146a91c44120872cb59aba6078b7cb40e4e8f4f6/third_party/WebKit/LayoutTests/fast/selectors/element-closest-general-expected.txt
[modify] https://crrev.com/146a91c44120872cb59aba6078b7cb40e4e8f4f6/third_party/WebKit/Source/core/dom/ContainerNode.cpp
[modify] https://crrev.com/146a91c44120872cb59aba6078b7cb40e4e8f4f6/third_party/WebKit/Source/core/dom/Element.cpp
[modify] https://crrev.com/146a91c44120872cb59aba6078b7cb40e4e8f4f6/third_party/WebKit/Source/core/dom/Element.h
[modify] https://crrev.com/146a91c44120872cb59aba6078b7cb40e4e8f4f6/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/146a91c44120872cb59aba6078b7cb40e4e8f4f6/third_party/WebKit/Source/core/inspector/InspectorCSSAgent.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/26d67176f9cf8b10fd2a378cb83492e432af23ba

commit 26d67176f9cf8b10fd2a378cb83492e432af23ba
Author: esprehn <esprehn@chromium.org>
Date: Thu Mar 23 06:37:42 2017

Simplify some arguments inside SelectorQuery.

We can hoist some code and remove some arguments since we always pass the same
thing.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2767113003
Cr-Commit-Position: refs/heads/master@{#459011}

[modify] https://crrev.com/26d67176f9cf8b10fd2a378cb83492e432af23ba/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/26d67176f9cf8b10fd2a378cb83492e432af23ba/third_party/WebKit/Source/core/dom/SelectorQuery.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/eec8e66dfa3536d3ab04a497434490ace4ae75cf

commit eec8e66dfa3536d3ab04a497434490ace4ae75cf
Author: esprehn <esprehn@chromium.org>
Date: Thu Mar 23 23:31:50 2017

Simplify the SelectorQuery constructor and reuse CSSSelectorList::length().

Instead of reimplementing length(), lets just give it a name that makes
it clear it's actually doing work and isn't free so folks don't use it
in for loops.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2774663003
Cr-Commit-Position: refs/heads/master@{#459279}

[modify] https://crrev.com/eec8e66dfa3536d3ab04a497434490ace4ae75cf/third_party/WebKit/Source/core/css/CSSSelectorList.cpp
[modify] https://crrev.com/eec8e66dfa3536d3ab04a497434490ace4ae75cf/third_party/WebKit/Source/core/css/CSSSelectorList.h
[modify] https://crrev.com/eec8e66dfa3536d3ab04a497434490ace4ae75cf/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/eec8e66dfa3536d3ab04a497434490ace4ae75cf/third_party/WebKit/Source/core/dom/SelectorQuery.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/7166178c862576e32636718ec0ec5ab29eb9a453

commit 7166178c862576e32636718ec0ec5ab29eb9a453
Author: esprehn <esprehn@chromium.org>
Date: Mon Mar 27 09:39:20 2017

Remove isTreeScopeRoot and just rely on isDescendantOf instead.

Today the SelectorQuery code does:
isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)

after getting an element from the rootNode's treeScope id map as a way to
check if the element is inside the rootNode, but if isTreeScopeRoot was
true then isDescendantOf must also be true, so all this was doing was saving
a function call and a few branches for the elements with the matching id. This
doesn't seem worth the added complexity, so lets just rely on isDescendantOf.

This also lets us remove isTreeScopeRoot function, which is semantically
equivalent to Node::isTreeScope() anyway.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2768263006
Cr-Commit-Position: refs/heads/master@{#459734}

[modify] https://crrev.com/7166178c862576e32636718ec0ec5ab29eb9a453/third_party/WebKit/Source/core/dom/Node.h
[modify] https://crrev.com/7166178c862576e32636718ec0ec5ab29eb9a453/third_party/WebKit/Source/core/dom/SelectorQuery.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/7283eda4c582d4aa64838377970466ae6a4d2f2e

commit 7283eda4c582d4aa64838377970466ae6a4d2f2e
Author: esprehn <esprehn@chromium.org>
Date: Wed Mar 29 17:50:44 2017

Inline SelectorQuery::executeForTraverseRoots into findTraverseRootsAndExecute.

This function is just a glorified if statement over the enum value we pass
into it. Inline the two loops into the call sites. We can also remove the
check against SelectorQueryTrait::shouldOnlyMatchFirstElement inside the loops
since the outer check ensures it's always false.

This lets us remove the MatchTraverseRootState enum. It does make the
findTraverseRootsAndExecute function bigger, but it removes a bunch of
checks in the process. Future patches will simplify further and hopefully
shrink the function.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2786493003
Cr-Commit-Position: refs/heads/master@{#460448}

[modify] https://crrev.com/7283eda4c582d4aa64838377970466ae6a4d2f2e/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/7283eda4c582d4aa64838377970466ae6a4d2f2e/third_party/WebKit/Source/core/dom/SelectorQuery.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/ab0448c6ce0471b98a8a7538a1a07377e41ff0bd

commit ab0448c6ce0471b98a8a7538a1a07377e41ff0bd
Author: esprehn <esprehn@chromium.org>
Date: Wed Mar 29 21:49:14 2017

Simplify some shadow crossing logic in SelectorQuery.cpp

ElementTraversal::firstWithin is the same as doing
::next(rootNode, &rootNode) we can just do that here. We can also use
isOpenOrV0() to remove some verbose checks, and finally we don't need to
check isShadowHost (which contains a bunch of duplciate checks) and can
just null check ::shadow() which is equivalent.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2782483004
Cr-Commit-Position: refs/heads/master@{#460544}

[modify] https://crrev.com/ab0448c6ce0471b98a8a7538a1a07377e41ff0bd/third_party/WebKit/Source/core/dom/SelectorQuery.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/d3b15e0c4bb54971c3d689537a2b08c91a89238b

commit d3b15e0c4bb54971c3d689537a2b08c91a89238b
Author: esprehn <esprehn@chromium.org>
Date: Wed Mar 29 23:22:45 2017

Simplify the id fast path for non-right most selectors in querySelector.

The id path inside SelectorQuery::findTraverseRootsAndExecute is not actually
reachable for the right most selector since we handle that separately inside
the top level ::execute() call. We also only ever take the fast path when
rootNode.isConnected() (as checked by canUseFastPath) so we can use that too.

By using these two truths inside this code we can simplify what it was doing
and delete a bunch of the code.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2786763002
Cr-Commit-Position: refs/heads/master@{#460572}

[modify] https://crrev.com/d3b15e0c4bb54971c3d689537a2b08c91a89238b/third_party/WebKit/Source/core/dom/SelectorQuery.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/9a91d5107bc7f45f238c52466449a9cea12e8493

commit 9a91d5107bc7f45f238c52466449a9cea12e8493
Author: esprehn <esprehn@chromium.org>
Date: Thu Mar 30 21:18:29 2017

Reuse executeForTraverseRoot to avoid a manual loop in SelectorQuery::findTraverseRootsAndExecute.

This lets us remove a for loop inside SelectorQuery::findTraverseRootsAndExecute,
we can also make executeForTraverseRoot take a reference since only one caller
could have passed null before.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2785253002
Cr-Commit-Position: refs/heads/master@{#460880}

[modify] https://crrev.com/9a91d5107bc7f45f238c52466449a9cea12e8493/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/9a91d5107bc7f45f238c52466449a9cea12e8493/third_party/WebKit/Source/core/dom/SelectorQuery.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/3d7c1de5f24317f05204476c657ff93d088aa514

commit 3d7c1de5f24317f05204476c657ff93d088aa514
Author: esprehn <esprehn@chromium.org>
Date: Fri Mar 31 00:22:01 2017

Reuse selectorListMatches for all loops over the selectors in SelectorQuery.

This means we need to repeat the SelectorQueryTrait::appendElement +
SelectorQueryTrait::shouldOnlyMatchFirstElement dance in two places, but it
removes two for loops as a trade and lets us untemplatize the
selectorListMatches function which is nice.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2791473002
Cr-Commit-Position: refs/heads/master@{#460949}

[modify] https://crrev.com/3d7c1de5f24317f05204476c657ff93d088aa514/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/3d7c1de5f24317f05204476c657ff93d088aa514/third_party/WebKit/Source/core/dom/SelectorQuery.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/00b1fe65b09e25713e2ebb7c0e940be33cdfb7c7

commit 00b1fe65b09e25713e2ebb7c0e940be33cdfb7c7
Author: esprehn <esprehn@chromium.org>
Date: Sat Apr 01 05:35:56 2017

Remove ClassElementList and reuse collectElementsByClassName in SelectorQuery.

We can add a check to collectElementsByClassName to match a full
selector once we find an element with a matching class name and remove
the AllElements mode of the ClassElementList.

This does mean we do one extra branch per element in the cases of
selectors like '.a' for each element that does actually have this class
name, but that seems fine given the cost of allocating wrappers and
everything else that's going to happen after returning the matches.

After removing the AllElements mode we can inline the loop for
ClassElementList into the caller and remove this iterator abstraction
entirely.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2788953003
Cr-Commit-Position: refs/heads/master@{#461316}

[modify] https://crrev.com/00b1fe65b09e25713e2ebb7c0e940be33cdfb7c7/third_party/WebKit/Source/core/dom/SelectorQuery.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/c00d9dec2a75f7ab0ca2220066c93f7749b797f2

commit c00d9dec2a75f7ab0ca2220066c93f7749b797f2
Author: esprehn <esprehn@chromium.org>
Date: Thu Apr 06 17:22:52 2017

Test cases for querySelector fast paths.

Historically we only had perf tests for the various fast paths
but that makes it hard to know what's really happening and if a
change in the SelectorQuery code changed behavior (ex.
Searching too many elements but still finding the right answer).

This patch introduces a system that tracks counters inside
SelectorQuery (only enabled with dchecks) that let us
write tests to verify the fast paths.

I then wrote a bunch of tests and added comments about edge
cases that are handled poorly by the fast paths today.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2797083002
Cr-Commit-Position: refs/heads/master@{#462526}

[modify] https://crrev.com/c00d9dec2a75f7ab0ca2220066c93f7749b797f2/third_party/WebKit/Source/core/dom/ContainerNode.h
[modify] https://crrev.com/c00d9dec2a75f7ab0ca2220066c93f7749b797f2/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/c00d9dec2a75f7ab0ca2220066c93f7749b797f2/third_party/WebKit/Source/core/dom/SelectorQuery.h
[modify] https://crrev.com/c00d9dec2a75f7ab0ca2220066c93f7749b797f2/third_party/WebKit/Source/core/dom/SelectorQueryTest.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/a9061e850f97072fd4c6baa802a5b46105e7b99d

commit a9061e850f97072fd4c6baa802a5b46105e7b99d
Author: esprehn <esprehn@chromium.org>
Date: Tue Apr 11 00:55:23 2017

Add lots more tests for SelectorQuery fast paths.

This adds tests for things inside ShadowRoots, disconnected subtrees, and
sibling selectors.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2803103002
Cr-Commit-Position: refs/heads/master@{#463477}

[modify] https://crrev.com/a9061e850f97072fd4c6baa802a5b46105e7b99d/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/a9061e850f97072fd4c6baa802a5b46105e7b99d/third_party/WebKit/Source/core/dom/SelectorQueryTest.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/8f55866589a385c959b0e9f0a3bd1f70e4139a66

commit 8f55866589a385c959b0e9f0a3bd1f70e4139a66
Author: esprehn <esprehn@chromium.org>
Date: Sat Apr 15 08:56:57 2017

Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in *All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex.
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks .mw-normal-catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues.

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

Note: These numbers were all taken on a 2013 Mac Pro trashcan.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2820013002
Cr-Commit-Position: refs/heads/master@{#464861}

[modify] https://crrev.com/8f55866589a385c959b0e9f0a3bd1f70e4139a66/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/8f55866589a385c959b0e9f0a3bd1f70e4139a66/third_party/WebKit/Source/core/dom/SelectorQuery.h
[modify] https://crrev.com/8f55866589a385c959b0e9f0a3bd1f70e4139a66/third_party/WebKit/Source/core/dom/SelectorQueryTest.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/ad2bef1e6dd219c8b8e1fbe58b86a896550634c9

commit ad2bef1e6dd219c8b8e1fbe58b86a896550634c9
Author: esprehn <esprehn@chromium.org>
Date: Fri May 12 18:45:11 2017

Allow using SelectorQuery fast paths in quirks mode and disconnected subtrees.

Previously there was a single global switch in the form of
SelectorQuery::CanUseFastQuery which controlled if we use any fast path
at all in querySelector. It was trying to enforce the rules for the
original id fast path though, and meant we were disabling all the other
fast paths (class, tagName) in quirks documents even though there's no
need to do that. It also meant we wouldn't use the id fast path inside
disconnected ShadowRoots.

This patch removes CanUseFastQuery() and replaces it with specific
checks for the id fast path, and stores the now static checks for the
other fast paths in a member variable use_slow_scan_.

This means shadowRoot or element.querySelector("#a") for an element in
a ShadowRoot is now O(1) even when the ShadowRoot is not connected to
the document. It also means we'll use the class and id fast paths in
quirks mode and also disconnected subtrees.

BUG= 703900 

Review-Url: https://codereview.chromium.org/2875673006
Cr-Commit-Position: refs/heads/master@{#471384}

[modify] https://crrev.com/ad2bef1e6dd219c8b8e1fbe58b86a896550634c9/third_party/WebKit/Source/core/dom/SelectorQuery.cpp
[modify] https://crrev.com/ad2bef1e6dd219c8b8e1fbe58b86a896550634c9/third_party/WebKit/Source/core/dom/SelectorQuery.h
[modify] https://crrev.com/ad2bef1e6dd219c8b8e1fbe58b86a896550634c9/third_party/WebKit/Source/core/dom/SelectorQueryTest.cpp

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/d40c7d7a91939001b1b6a9f7399257403c3b15d6

commit d40c7d7a91939001b1b6a9f7399257403c3b15d6
Author: Zhuoyu Qian <zhuoyu.qian@samsung.com>
Date: Wed Jan 10 01:19:00 2018

Move HasClassName() to |Element| class.

As the TODO in SelectorQuery.cpp by esprehn@, move the function
HasClassName() to |Element| class.

BUG= 703900 

Signed-off-by: Zhuoyu Qian <zhuoyu.qian@samsung.com>
Change-Id: I31a6c3bd1de48d2982da6fff1e9ff56e8367508a
Reviewed-on: https://chromium-review.googlesource.com/856381
Reviewed-by: meade_UTC10 <meade@chromium.org>
Cr-Commit-Position: refs/heads/master@{#528194}
[modify] https://crrev.com/d40c7d7a91939001b1b6a9f7399257403c3b15d6/third_party/WebKit/Source/core/css/SelectorQuery.cpp
[modify] https://crrev.com/d40c7d7a91939001b1b6a9f7399257403c3b15d6/third_party/WebKit/Source/core/dom/Element.h

This issue has been Available for over a year. If it's no longer important or seems unlikely to be fixed, please consider closing it out. If it is important, please re-triage the issue.

Sorry for the inconvenience if the bug really should have been left as Available.

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot