Modify toQueryString to prevent SQLite expression tree from exceeding depth of 1000 #2565

LZRS · 2024-06-08T23:46:01Z

IMPORTANT: All PRs must be linked to an issue (except for extremely trivial and straightforward changes).

Description
Recursively bifurcates the conditional params expressions to prevent occurences of SQLite expression tree exceeding depth of 1000, as suggested in this comment

Alternative(s) considered
Chunking large expression list to limit 50 within parantheses to avoid crashing with Expression tree is too large (maximum depth 1000), as described here

Type
Enhancement Feature

Screenshots (if applicable)

Checklist

I have read and acknowledged the Code of conduct.
I have read the Contributing page.
I have signed the Google Individual CLA, or I am covered by my company's Corporate CLA.
I have discussed my proposed solution with code owners in the linked issue(s) and we have agreed upon the general approach.
I have run ./gradlew spotlessApply and ./gradlew spotlessCheck to check my code follows the style guide of this project.
I have run ./gradlew check and ./gradlew connectedCheck to test my changes locally.
I have built and run the demo app(s) to verify my change fixes the issue and/or does not break the demo app(s).

https://stackoverflow.com/a/17032196

engine/src/main/java/com/google/android/fhir/search/filter/FilterCriterion.kt

…rash

engine/src/main/java/com/google/android/fhir/search/filter/FilterCriterion.kt

…rash

jingtang10 · 2024-07-22T18:45:45Z

judging purely by the error message, my hypothesis is that the expression tree depth is O(n) for nested OR operators because the expression tree is constructed naively by parsing the OR operators sequentially. For example, for this expression

a OR b OR c OR d OR e OR f OR g OR h

if the expression tree is constructed naively you'd get:

where each o stands for an OR operator. This has depth 8.

But what you really want is actually this:

        o
      /   \
    o       o
   / \     / \
  o   o   o   o
 / \ / \ / \ / \
 a b c d e f g h

where the tree is more "balanced" and this has depth 4. In other words, this is O(log(n)).

If my hypothesis of what causes the problem is correct above, instead of trying to break the OR statements into chunks (and having to come up with a value), all you actually have to do is keep the tree balanced by splitting the top level OR statment at the middle of the list of params.

Does this make sense?

LZRS · 2024-07-23T07:59:00Z

judging purely by the error message, my hypothesis is that the expression tree depth is O(n) for nested OR operators because the expression tree is constructed naively by parsing the OR operators sequentially. For example, for this expression
a OR b OR c OR d OR e OR f OR g OR h
if the expression tree is constructed naively you'd get:
  o
 / \
a   o
   / \
  b   o
     / \
    c   o
       / \
      d   o
         / \
        e   o
           / \
          f   o
             / \
            g   h
where each o stands for an OR operator. This has depth 8.

But what you really want is actually this:
        o
      /   \
    o       o
   / \     / \
  o   o   o   o
 / \ / \ / \ / \
 a b c d e f g h
where the tree is more "balanced" and this has depth 4. In other words, this is O(log(n)).

If my hypothesis of what causes the problem is correct above, instead of trying to break the OR statements into chunks (and having to come up with a value), all you actually have to do is keep the tree balanced by splitting the top level OR statment at the middle of the list of params.

Does this make sense?

Yeah, it makes sense.

jingtang10 · 2024-07-23T09:56:16Z

there's no guarantee what i said is true @LZRS - i've done no testing or verification and depending on sqlite's implementation what i said could be complete garbage... so pls test and see if this is true :) (for example you could try to see if you'll hit the depth limit a bit later to bifurcate the tree instead of chunking the parameters)

LZRS · 2024-07-23T11:13:58Z

Alright, no problem. I'll test it out and get back

…rash

LZRS · 2024-08-22T01:02:14Z

there's no guarantee what i said is true @LZRS - i've done no testing or verification and depending on sqlite's implementation what i said could be complete garbage... so pls test and see if this is true :) (for example you could try to see if you'll hit the depth limit a bit later to bifurcate the tree instead of chunking the parameters)

@jingtang10 I tested this out for 1000, 2000 and upto 5000 parameters, and it worked perfectly. I also went ahead a drafted an implementation in the PR

engine/src/main/java/com/google/android/fhir/search/filter/FilterCriterion.kt

engine/src/test/java/com/google/android/fhir/search/SearchTest.kt

aditya-07

Can we add a DatabaseImplTest with

engine/src/test/java/com/google/android/fhir/search/SearchTest.kt

FORK - With unmerged PR #9 - WUP #13 SDK - WUP google#2178 - WUP google#2650 - WUP google#2663 PERF - WUP google#2669 - WUP google#2565 - WUP google#2561 - WUP google#2535

…rash

engine/src/main/java/com/google/android/fhir/search/filter/FilterCriterion.kt

engine/src/test/java/com/google/android/fhir/search/SearchTest.kt

FORK - With unmerged PR #9 - WUP #13 SDK - WUP google#2178 - WUP google#2650 - WUP google#2663 PERF - WUP google#2669 - WUP google#2565 - WUP google#2561 - WUP google#2535

…rash

jingtang10 · 2024-10-08T10:24:53Z

engine/src/androidTest/java/com/google/android/fhir/db/impl/DatabaseImplTest.kt

@@ -5169,6 +5170,29 @@ class DatabaseImplTest {
      assertThat(localChangeResourceReferences.size).isEqualTo(locallyCreatedPatients.size)
    }

+  @Test
+  fun searchTasksForManyPatientsReturnCorrectly() = runBlocking {
+    val patients = (0..5001).map { Patient().apply { id = "task-patient-index-$it" } }


There are 5002 patients and 5001 tasks. Is this test case deliberately checking this? I feel like if you really want to test the filter clause, it's better to query tasks linked to patient 0-4999 so at least you're filtering out 1 patient to know that the filter clause works.

jingtang10 · 2024-10-08T10:26:33Z

engine/src/androidTest/java/com/google/android/fhir/db/impl/DatabaseImplTest.kt

+      }
+    database.insert(*tasks.toTypedArray())
+
+    val patientsSearchIdList =


you can also limit this list to 2000 or 3000.

you can also limit this list to 2000 or 3000.

I couldn't set limit the test to either 3000 or 2000, ran to another sqlite error on android

android.database.sqlite.SQLiteException: too many SQL variables (code 1)

It's related to https://issuetracker.google.com/issues/73634057

For now, I just used a limit of 990

but 5000 worked? this is odd...

can you please do some more testing to see what's goign on here?

this is not blocking the pr though.

Initially the way they'd passed for the 5000, I had generated the bifurcated queries and ran them in separate sqlite db browser. That might be the difference, assuming the sqlite version for Android may be limited

engine/src/main/java/com/google/android/fhir/search/filter/FilterCriterion.kt

engine/src/test/java/com/google/android/fhir/impl/FhirEngineImplTest.kt

engine/src/test/java/com/google/android/fhir/search/SearchTest.kt

…rash

jingtang10 · 2024-10-15T10:09:18Z

engine/src/androidTest/java/com/google/android/fhir/db/impl/DatabaseImplTest.kt

+      }
+    database.insert(*tasks.toTypedArray())
+
+    val patientsSearchIdList =


but 5000 worked? this is odd...

can you please do some more testing to see what's goign on here?

this is not blocking the pr though.

jingtang10 · 2024-10-15T10:16:31Z

engine/src/androidTest/java/com/google/android/fhir/db/impl/DatabaseImplTest.kt

+      }
+    val searchQuery =
+      Search(ResourceType.Task)
+        .apply { filter(Task.SUBJECT, *patientsSearchIdList.toTypedArray()) }


this filter is checking that tasks are referencing patients 0-990 (inclusive) so that's 991 patients.

but you only have tasks for patients 0-989 (990 in total).

so the filter criteria is not really being tests because the filter criteria is broader than what you have in the database.

if you want to test it, make the filter more strict. for example, create N patients, and in the filter list N-1 IDs. and check that you only get N-1 results.

Modify toQueryString to chunk large list of ConditionParam

6b3d4c4

https://stackoverflow.com/a/17032196

LZRS force-pushed the 2561-fix-sqlite-crash branch from ae8187f to 6b3d4c4 Compare June 12, 2024 15:11

pld reviewed Jun 14, 2024

View reviewed changes

engine/src/main/java/com/google/android/fhir/search/filter/FilterCriterion.kt Outdated Show resolved Hide resolved

Merge remote-tracking branch 'upstream/master' into 2561-fix-sqlite-c…

8c720e2

…rash

LZRS marked this pull request as ready for review June 21, 2024 17:52

LZRS requested review from aditya-07, jingtang10 and MJ1998 as code owners June 21, 2024 17:52

pld reviewed Jun 21, 2024

View reviewed changes

engine/src/main/java/com/google/android/fhir/search/filter/FilterCriterion.kt Outdated Show resolved Hide resolved

LZRS added 2 commits June 24, 2024 14:15

Add test for condition params chunking and wrapping in brackets

c73037d

Merge remote-tracking branch 'upstream/master' into 2561-fix-sqlite-c…

0264816

…rash

LZRS force-pushed the 2561-fix-sqlite-crash branch from 80c50de to 0264816 Compare June 24, 2024 11:17

Merge remote-tracking branch 'upstream/master' into 2561-fix-sqlite-c…

6a45013

…rash

LZRS requested a review from santosh-pingle as a code owner June 26, 2024 14:16

Add support for chunkSize param in SearchDsl filters

d764115

LZRS force-pushed the 2561-fix-sqlite-crash branch from d9e6d03 to d764115 Compare June 26, 2024 22:21

LZRS added 2 commits June 27, 2024 11:57

Update workflow engine dependency to use latest

d509f53

Merge branch 'master' into 2561-fix-sqlite-crash

ab9a4a6

LZRS added 3 commits August 22, 2024 03:12

Merge remote-tracking branch 'upstream/master' into 2561-fix-sqlite-c…

432f7af

…rash

Refactor remove chunkSize parameter

b5e67df

Recursively bifurcate expression tree to reduce depth

b9708a6

LZRS requested a review from a team as a code owner August 22, 2024 00:57

Revert touched files not relevant for the PR

821feab

LZRS force-pushed the 2561-fix-sqlite-crash branch from af4d912 to 821feab Compare August 22, 2024 13:03

LZRS changed the title ~~Modify toQueryString to chunk large list of ConditionParam~~ Modify toQueryString to prevent SQLite expression tree from exceeding depth of 1000 Aug 22, 2024

jingtang10 requested changes Sep 10, 2024

View reviewed changes

aditya-07 requested changes Sep 10, 2024

View reviewed changes

engine/src/test/java/com/google/android/fhir/search/SearchTest.kt Show resolved Hide resolved

FikriMilano suggested changes Sep 10, 2024

View reviewed changes

engine/src/test/java/com/google/android/fhir/search/SearchTest.kt Show resolved Hide resolved

LZRS added 2 commits September 11, 2024 13:33

Merge remote-tracking branch 'upstream/master' into 2561-fix-sqlite-c…

a304c19

…rash

Refactor toQueryString

112344f

jingtang10 reviewed Sep 11, 2024

View reviewed changes

LZRS added 2 commits October 8, 2024 12:36

Update tests to include base cases for toQueryString

ed8d74b

Merge remote-tracking branch 'upstream/master' into 2561-fix-sqlite-c…

999fe93

…rash

LZRS requested a review from jingtang10 October 8, 2024 09:37

jingtang10 requested changes Oct 8, 2024

View reviewed changes

LZRS added 3 commits October 9, 2024 17:20

Refactor and update related test cases

5a96ef8

Merge remote-tracking branch 'upstream/master' into 2561-fix-sqlite-c…

7aacdde

…rash

Merge branch 'master' into 2561-fix-sqlite-crash

d83e139

jingtang10 approved these changes Oct 15, 2024

View reviewed changes

jingtang10 requested changes Oct 15, 2024

View reviewed changes

Refactor test to make filter strict

e7dde67

LZRS requested review from pld and jingtang10 October 16, 2024 10:11

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Modify toQueryString to prevent SQLite expression tree from exceeding depth of 1000 #2565

Modify toQueryString to prevent SQLite expression tree from exceeding depth of 1000 #2565

LZRS commented Jun 8, 2024 •

edited

Loading

jingtang10 commented Jul 22, 2024 •

edited

Loading

LZRS commented Jul 23, 2024

jingtang10 commented Jul 23, 2024

LZRS commented Jul 23, 2024

LZRS commented Aug 22, 2024

aditya-07 left a comment

jingtang10 Oct 8, 2024

jingtang10 Oct 8, 2024

LZRS Oct 15, 2024

jingtang10 Oct 15, 2024

LZRS Oct 16, 2024 •

edited

Loading

jingtang10 Oct 15, 2024

jingtang10 Oct 15, 2024

Modify toQueryString to prevent SQLite expression tree from exceeding depth of 1000 #2565

Are you sure you want to change the base?

Modify toQueryString to prevent SQLite expression tree from exceeding depth of 1000 #2565

Conversation

LZRS commented Jun 8, 2024 • edited Loading

jingtang10 commented Jul 22, 2024 • edited Loading

LZRS commented Jul 23, 2024

jingtang10 commented Jul 23, 2024

LZRS commented Jul 23, 2024

LZRS commented Aug 22, 2024

aditya-07 left a comment

Choose a reason for hiding this comment

jingtang10 Oct 8, 2024

Choose a reason for hiding this comment

jingtang10 Oct 8, 2024

Choose a reason for hiding this comment

LZRS Oct 15, 2024

Choose a reason for hiding this comment

jingtang10 Oct 15, 2024

Choose a reason for hiding this comment

LZRS Oct 16, 2024 • edited Loading

Choose a reason for hiding this comment

jingtang10 Oct 15, 2024

Choose a reason for hiding this comment

jingtang10 Oct 15, 2024

Choose a reason for hiding this comment

LZRS commented Jun 8, 2024 •

edited

Loading

jingtang10 commented Jul 22, 2024 •

edited

Loading

LZRS Oct 16, 2024 •

edited

Loading