Search across types in GraphQL - Time & Space Complexity

Time Complexity: Search across types

O(n)

Understanding Time Complexity

When searching across different types in a GraphQL schema, we want to know how the time to get results changes as the data grows.

We ask: How does the search time increase when there are more items in each type?

Scenario Under Consideration

Analyze the time complexity of the following GraphQL query that searches multiple types.

query SearchAcrossTypes($term: String!) {
  books(filter: { title_contains: $term }) {
    id
    title
  }
  authors(filter: { name_contains: $term }) {
    id
    name
  }
  publishers(filter: { name_contains: $term }) {
    id
    name
  }
}
    

This query searches for a term in three different types: books, authors, and publishers, returning matching items from each.

Identify Repeating Operations

Look for repeated work done during the search.

• Primary operation: Scanning each list of items in books, authors, and publishers to check if the term matches.
• How many times: Once for each item in each type's list.

How Execution Grows With Input

As the number of items in each type grows, the search work grows too.

Input Size (n)	Approx. Operations
10 items per type	About 30 checks (10 books + 10 authors + 10 publishers)
100 items per type	About 300 checks
1000 items per type	About 3000 checks

Pattern observation: The total work grows roughly in direct proportion to the total number of items across all types.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows linearly with the total number of items searched across all types.

Common Mistake

[X] Wrong: "Searching multiple types at once is faster because it's one query."

[OK] Correct: Even though it's one query, the server still checks each item in every type separately, so the total work adds up.

Interview Connect

Understanding how searching multiple types affects performance helps you explain real-world API behavior clearly and confidently.

Self-Check

What if we added pagination to each type's search? How would that change the time complexity?

Practice

1. What does the __typename field do in a GraphQL query when searching across types?

easy

A. It tells you the type of each returned object in the result.

B. It filters the results to only one type.

C. It sorts the results alphabetically.

D. It limits the number of results returned.

Solution

1. Step 1: Understand the role of __typename

   The __typename field returns the name of the type of each object in the query result.

2. Step 2: Differentiate from other options

   It does not filter, sort, or limit results; it only identifies the type.

3. Final Answer:

   It tells you the type of each returned object in the result. -> Option A

4. Quick Check:

   __typename shows object type [OK]

Hint: Remember: __typename reveals object type, not filters or limits [OK]

Common Mistakes:

• Thinking __typename filters results
• Assuming it sorts or limits data
• Confusing it with field selection

2. Which of the following is the correct syntax to query two different types, Book and Author, in one GraphQL query using fragments?

easy

A. query { search { ... on Book { title } ... on Author { name } } }

B. query { search { Book { title } Author { name } } }

C. query { search { title, name } }

D. query { search { ...Book { title } ...Author { name } } }

Solution

1. Step 1: Recognize fragment syntax for multiple types

   Fragments use ... on TypeName { fields } to specify fields for each type.

2. Step 2: Check each option's syntax

   query { search { ... on Book { title } ... on Author { name } } } correctly uses inline fragments for Book and Author. Options B, C, and D have invalid syntax.

3. Final Answer:

   query { search { ... on Book { title } ... on Author { name } } } -> Option A

4. Quick Check:

   Fragments use ... on Type [OK]

Hint: Use ... on Type for each type's fields [OK]

Common Mistakes:

• Using type names as fields directly
• Omitting 'on' keyword in fragments
• Trying to list fields without fragments

3. Given this GraphQL query:

query { search { __typename ... on Book { title author } ... on Author { name booksCount } } }

What will be the output if the search returns one Book and one Author?

medium

A. [{ "title": "1984", "author": "Orwell" }, { "name": "Orwell", "booksCount": 5 }]

B. [{ "__typename": "Book", "title": "1984", "author": "Orwell" }, { "__typename": "Author", "name": "Orwell", "booksCount": 5 }]

C. [{ "__typename": "Book", "name": "1984", "author": "Orwell" }, { "__typename": "Author", "title": "Orwell", "booksCount": 5 }]

D. Error: Cannot query field 'booksCount' on type 'Author'

Solution

1. Step 1: Understand the query structure

   The query requests __typename and fields specific to Book and Author types.

2. Step 2: Match output to query

   The output includes type names and requested fields correctly matched to each object.

3. Final Answer:

   [{ "__typename": "Book", "title": "1984", "author": "Orwell" }, { "__typename": "Author", "name": "Orwell", "booksCount": 5 }] -> Option B

4. Quick Check:

   Output matches requested fields and types [OK]

Hint: Look for __typename and matching fields in output [OK]

Common Mistakes:

• Ignoring __typename in output
• Mixing fields between types
• Assuming syntax errors without cause

4. Identify the error in this GraphQL query that searches across types:

query { search { ... on Book { title author } ... on Author { name booksCount } } }

Assuming booksCount is not a valid field on Author type.

medium

A. The query will ignore the Author fragment entirely.

B. The query will succeed but return null for booksCount.

C. The query will fail because booksCount is not a valid field on Author.

D. The query syntax is invalid due to missing commas.

Solution

1. Step 1: Check field validity on types

   Since booksCount is not defined on Author, the query is invalid.

2. Step 2: Understand GraphQL error handling

   GraphQL returns an error and fails the query if a requested field does not exist on the type.

3. Final Answer:

   The query will fail because booksCount is not a valid field on Author. -> Option C

4. Quick Check:

   Invalid field causes query failure [OK]

Hint: Check if all fields exist on their types before querying [OK]

Common Mistakes:

• Assuming invalid fields return null
• Ignoring GraphQL schema validation errors
• Thinking commas are required between fragments

5. You want to search across three types: Book, Author, and Publisher. Each type has a field name, but Book also has pages, Author has birthYear, and Publisher has location. Which query correctly fetches the name for all types and their specific fields?

hard

A. query { search { ...Book { name pages } ...Author { name birthYear } ...Publisher { name location } } }

B. query { search { name pages birthYear location } }

C. query { search { __typename { name } ... on Book { pages } ... on Author { birthYear } ... on Publisher { location } } }

D. query { search { __typename ... on Book { name pages } ... on Author { name birthYear } ... on Publisher { name location } } }

Solution

1. Step 1: Use __typename to identify each type

   This helps distinguish which object is which type in the results.

2. Step 2: Use inline fragments with ... on Type syntax

   Each fragment fetches the common name and the type-specific fields.

3. Step 3: Verify syntax correctness

   query { search { __typename ... on Book { name pages } ... on Author { name birthYear } ... on Publisher { name location } } } correctly uses fragments and includes __typename. Other options have syntax errors or missing fragments.

4. Final Answer:

   query { search { __typename ... on Book { name pages } ... on Author { name birthYear } ... on Publisher { name location } } } -> Option D

5. Quick Check:

   Fragments + __typename fetch all fields correctly [OK]

Hint: Use __typename and fragments for each type's fields [OK]

Common Mistakes:

• Listing all fields without fragments
• Omitting __typename for type identification
• Incorrect fragment syntax without 'on'