The Wayback Machine - https://web.archive.org/web/20220110180026/https://github.com/github/codeql/pull/7475
Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JS: Improve performance of ATM queries on large databases #7475

Draft
wants to merge 8 commits into
base: main
Choose a base branch
from

Conversation

@adityasharad
Copy link
Collaborator

@adityasharad adityasharad commented Dec 22, 2021

Work in progress.

One of the heuristics for test files looks for source files
of the form `base.ext`, then looks for sibling test files
of the form `base.test.ext` or `base.spec.ext`.

On large databases, the result join order computed all source files,
the containers of those files, then all other files within those
containers, before computing the test file names and filtering using
those names.

The product of all files with all other files in the same containers
is of the same order of magnitude as the product of the `files`
table with itself, which on large DBs like Node can be 12M+ tuples.

As a performance optimisation, factor out a helper predicate that
computes the likely test file names for each source file, so these
can be determined with a single join against the files table.
This results in much better join orders, such as computing the set
of files and their containers, then the test file names, then the
sibling files with those names.

This loses some flexibility because the set of 'test' extension names
is hardcoded in the library rather than provided by the caller predicate.
The original predicate remains to avoid breaking other callers, but could
eventually be deprecated.
When join-ordering and evaluating this conjunction,
it is preferable to start with the relatively small set of
`sanitizer` calls, then compute the set of SSA variables accessed
as the arguments of those sanitizer calls, then reason about how
those variables are used in phi nodes.

Use directional binding pragmas to encourage this join order
by picking `sanitizer` first, and discourage picking the
opposite join order starting with `phi`.

This impacts performance of the ATM XSS queries on large databases like Node,
where computing all variable accesses from phi nodes leads to 435M+ tuples.
@adityasharad adityasharad force-pushed the atm/perf-debugging-node branch from d4bb4c8 to 6da4aa0 Dec 22, 2021
On databases with a large number of Exprs, it can be better
to start with the set of route handlers, then find their
response headers, then find the expression values set in
those headers.
@adityasharad adityasharad force-pushed the atm/perf-debugging-node branch from 6da4aa0 to eb66af3 Dec 23, 2021
Factor the regex-independent logic of `isReadFrom` into its own predicate.

Call this predicate directly from `isNumeric`, which doesn't have much
restrictive context on the set of starting nodes.
Use a binding hint to discourage starting with all expr nodes in this case.

Other callers may have more restrictive context on the set of nodes,
so they are not changed.
Should most likely refer to `AccessPathWrite` and look for write nodes.
This also improves the performance of `rankedAccessPath`, since the
set of candidate blocks is now limited to blocks with both a read and a write.
We have to look up the  node index within the block anyway,
so include it as an aggregation variable.
Check that the read node is in a *reachable* basic block
before looking for a dominating write block.
@adityasharad adityasharad force-pushed the atm/perf-debugging-node branch from eb66af3 to b43891a Dec 23, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Linked issues

Successfully merging this pull request may close these issues.

None yet

1 participant
Morty Proxy This is a proxified and sanitized view of the page, visit original site.