Searching the internet: search engines and queries

Aysel is preparing a project about Caspian seals. When she types “Caspian” into a search engine, millions of pages are found — nobody can read them all. With “Caspian seal” there are far fewer results, and adding the word “protection” narrows them even more. A well-built query finds what you need in minutes instead of hours. DİM’s entrance exam tests this topic too: in three of the four exams of 2025–2026 there was a coded task in which a table lists some queries with the number of pages found, and you must find the result of another query.

How a search engine works

At the moment you send a query, the search engine does not scan the whole internet — that would take hours or even days. It looks in an index prepared in advance. The work goes like this:

1. 1
   The crawler visits pages

   A special program — the crawler (also called a spider or robot) — moves from page to page along links and downloads the text of each page.

2. 2
   Indexing

   For every word the engine builds a list of the pages where it occurs. It is like the index at the back of a book: “Nizami — pp. 12, 48, 95”.

3. 3
   Processing the query

   The keywords of the query are looked up in the index, and their page lists are intersected or joined according to the Boolean operators.

4. 4
   Ranking

   The pages found are ordered by how well they match: is the keyword in the title, how many sites link to the page, and so on. The results page also shows an approximate count, such as “about 120,000 results”.

So every keyword gives a set of pages: all the pages where the word occurs. The Boolean operators in a query are simply operations on these sets. The rest of the lesson is built on this simple idea.

The query language: AND, OR, NOT

Keywords can be combined with Boolean operators. DİM tasks write them in English — AND, OR, NOT; some books use the signs &, | and ~ instead. You know these operations from the lesson “Boolean logic and logic gates”: here they act on sets of pages instead of statements.

Without brackets NOT is done first, then AND, and OR last. For example, the query A OR B AND C means A OR (B AND C). If you need another order, write brackets: (A OR B) AND C. Real search engines also have their own rules: in Google, for example, words separated by spaces are joined with AND, OR is written in capital letters, a minus sign before a word (-advert) excludes it, and quotation marks search for an exact phrase.

Euler–Venn diagrams: two keywords

Draw the pages found for each keyword as a circle. The common part of the circles is the pages with both words (AND), the whole area covered by the two circles is the result of OR, and the part of a circle outside the other circle is obtained with NOT. Such a picture is called an Euler–Venn diagram.

When we add n(A) and n(B) to count the pages of A OR B, the common part is counted twice: it lies inside circle A and inside circle B. So we subtract it once:

Three keywords: DİM tasks

With three keywords the three circles split the diagram into 7 parts. Number the parts and write N₁, N₂, …, N₇ for the number of pages in each part. Every query is the sum of some of these parts — that is the whole secret of the task.

1. 1
   Draw the diagram

   Draw one circle per keyword and number the parts.

2. 2
   Rewrite the table in parts

   Write every row of the table as a sum of parts, e.g. n(B AND C) = N₆ + N₇.

3. 3
   Start from the centre

   Start with the narrowest query (usually the AND of all three words) and find the parts from the inside out.

4. 4
   Express the asked query

   Decide which parts make up the asked query and add them up.

5. 5
   Check

   No part may be negative; if possible, check the answer with the formula as well.

Query operations match Python’s set operations exactly: & is AND, | is OR, - is AND NOT. Check the formula yourself on a small example (pages are shown as numbers):

football = {1, 2, 3, 4, 5, 6, 7}
volleyball = {5, 6, 7, 8, 9}
basketball = {2, 7, 9, 10}

print('football AND volleyball:', sorted(football & volleyball))
print('football OR volleyball:', sorted(football | volleyball))
print('football AND NOT volleyball:', sorted(football - volleyball))
print('(football OR volleyball) AND basketball:',
      sorted((football | volleyball) & basketball))

# inclusion-exclusion: n(A OR B) = n(A) + n(B) - n(A AND B)
n_or = len(football) + len(volleyball) - len(football & volleyball)
print(n_or, len(football | volleyball))

football AND volleyball: [5, 6, 7]
football OR volleyball: [1, 2, 3, 4, 5, 6, 7, 8, 9]
football AND NOT volleyball: [1, 2, 3, 4]
(football OR volleyball) AND basketball: [2, 7, 9]
9 9