Indexes and Query Analysis

• PostgreSQL Indexes^🐘

Indexes

Advantages

• ensure referential integrity (PK, unique)

• speed up record (row) lookups for select update delete:
  clauses where and join

Disadvantages

overhead:

• additional data

• an index must be created and maintained

Speedup:

For example, selecting rows (select ... where ...) without indexes requires scanning the entire table (in O(n) time).

If, however, a suitable index exists for the fields used in the where ... clause, records can be found faster, typically using a search tree in O(log n) time.

Similar speedups happen when joining tables (join) and sorting results (order by).

Should an index be used?

Consider:

• the space/time trade-off

• whether to keep indexes, or create them temporarily and then drop them

Index types

default: B-tree^🌐

sqlcreate index name on table(column);

Suitable for:

• comparisons <, <=, =, >=, >, between, in, is (not) null, like 'xxx%'

• sorting with order by

Hash

Based on hash tables^🌐.

sqlcreate index name on table using hash (column);

• lower overhead than B-trees

• suitable only for =, in, is (not) null (no sorting, no range queries)

GIST, SP-GIST (Geographic Information Systems Technology)

• for spatial coordinates and nearest-neighbor searches

• use a quadtree^🌐 (2D) or an octree^🌐 (3D)

GIN (Generalized INverted index)

Full-text search, like, etc.

For the curious: more information

Multicolumn indexes

sqlcreate index name on table(col1, col2, ...);
create index name on table(col1 desc, col2 nulls first/last, ...);

The most selective column should be listed first from the left, followed by the second most selective, and so on.

Suitable for queries such as:

sql... where col1 op ... and col2 op ... and ...);

and

sql... order by col1, col2, ...);

(from left to right: col1, col2, …)

Combining indexes

If the conditions in the where clause are combined with and, the database may be able to use only one index.

sql... where ... and ...;

If they are combined with or, multiple indexes (or the same index more than once) are required.

sql... where ... or ...;

Unique indexes

sqlcreate unique index name on ... [ nulls [ not ] distinct ];

Expression indexes (computed indexes)

If a query uses a function, for example:

sql... where lower(col) = 'value';

then a corresponding index could be useful:

sqlcreate index name on table(lower(col));

Or, if the query is:

sqlselect * from people where (first_name || ' ' || last_name) = 'john smith';

the following index is useful:

sqlcreate index names on people ((first_name || ' ' || last_name));

Partial indexes

Partial indexes are a compromise between the overhead of preparing an index and faster query execution. They index only a specific range of values:

sqlcreate index name on table(col) where ... col ...

Index-only queries

If a query uses only columns that are present in the index, the table itself does not need to be read; the index alone is sufficient:

sqlcreate index name on table(col1, col2, ...)

sqlselect col1, col2 from name where ... col1 ... col2 ...

Query optimization

The query planner in a DBMS chooses the optimal way to execute a query. The (heuristic) choice is based on the size of:

• the tables being processed

• the temporary tables created during the execution of more complex queries.

The size of a table is mainly determined by the number of rows, because in practice, the number of columns being processed is usually limited:

Tables by size

• micro-tables = tables with only a few rows and columns, from tens to hundreds:
  optimization is counterproductive; use a sequential scan and, if needed, a hash join

• medium-sized (mezo-) tables = tens to thousands of rows (one or several disk blocks / memory pages)
  bitmap scan for multiple filters, hash join, merge join

• large (macro-) tables = hundreds of thousands of rows or more
  index scan, merge join, partitioning, helper tables, materialized views

Execution plan

The DBMS query planner prepares the query's execution plan: this is a critical operation.

The sizes of intermediate tables are often difficult to determine in advance, so they are usually estimated:

• from the sizes of physical tables

• from empirically observed probability distributions

• from the results of similar previous queries

Good estimates require ongoing data analysis and execution of queries that are actually used (so-called adaptive tuning).

Query analysis

To find out which plan was used:

sqlexplain [analyze] dotaz

explain displays a detailed plan showing the mechanisms used, the estimated cost, and the number of rows in the tables.

(analyze also executes the plan and adds actual execution statistics)

Practical example

Two versions of the tables (create in two different databases):

First, tables without indexes:

schema-noPK.sqlcreate database db1;
\c db1;

-- case insensitive text
create extension if not exists citext;

drop table if exists weather, place, country, continent;

-- validation functions

create or replace function is_name(val text)
returns boolean as $$ begin
  return val != '' and val !~ '^\s' and val !~ '\s$';
end; $$ language plpgsql;

-- custom domains

-- name, max. length 100 chars
drop domain if exists d_name;
create domain d_name as citext not null check (length(value) <= 100 and is_name(value));

-- temperature
drop domain if exists d_temp;
create domain d_temp as numeric(4,1) check (value between -90 and 90);

-- 8-region, continent-like world model, weather data

create table continent (
  id   integer  check (0 < id),
  name d_name
);

create table country (
  code         char(2)  check (code ~ '^[A-Z]{2}$'),
  id_continent integer  not null,
  name         d_name
);

create table place (
  id           serial,

  code_country char(2),
  name         d_name,

  -- Also domains?
  latitude     numeric(8,5) not null check (latitude  between  -90 and 90),
  longitude    numeric(8,5) not null check (longitude between -180 and 180),
  elevation    int          not null check (-430 <= elevation and elevation <= 8000) -- Dead Sea shore -430m
);

create table weather (
    id       serial,
    id_place int,
    date     date   not null,

    temp_lo  d_temp,
    temp_hi  d_temp,
    precip   decimal(6,2) check (precip is null or 0 <= precip and precip < 5000),

    check (temp_lo is null or temp_hi is null or temp_lo <= temp_hi)
);

Next, tables with PK/FK (implicit index on PK):

schema.sqlcreate database db2;
\c db2;

-- case insensitive text
create extension if not exists citext;

drop table if exists weather, place, country, continent;

-- validation functions

create or replace function is_name(val text)
returns boolean as $$ begin
  return val != '' and val !~ '^\s' and val !~ '\s$';
end; $$ language plpgsql;

-- custom domains

-- name, max. length 100 chars
drop domain if exists d_name;
create domain d_name as citext not null check (length(value) <= 100 and is_name(value));

-- temperature
drop domain if exists d_temp;
create domain d_temp as numeric(4,1) check (value between -90 and 90);

-- 8-region, continent-like world model, weather data

create table continent (
  id   integer  primary key check (0 < id),
  name d_name 	unique
);

create table country (
  code         char(2)  primary key check (code ~ '^[A-Z]{2}$'),
  id_continent integer  not null references continent(id),
  name         d_name 	unique
);

create table place (
  id           serial  primary key,

  code_country char(2) references country(code),
  name         d_name,
  unique(code_country, name),

  -- Also domains?
  latitude     numeric(8,5) not null check (latitude  between  -90 and 90),
  longitude    numeric(8,5) not null check (longitude between -180 and 180),
  elevation    int          not null check (-430 <= elevation and elevation <= 8000) -- Dead Sea shore -430m
);

create table weather (
    id       serial primary key,
    id_place int    references place(id),
    date     date   not null,

    temp_lo  d_temp,
    temp_hi  d_temp,
    precip   decimal(6,2) check (precip is null or 0 <= precip and precip < 5000),

    check (temp_lo is null or temp_hi is null or temp_lo <= temp_hi),
    unique(id_place, date)
);

Insert this data into both versions of the tables:

data.sql-- test data

insert into continent (id, name) values
  (1, 'Africa'),
  (2, 'Antarctica'),
  (3, 'Arctic'),
  (4, 'Asia'),
  (5, 'Europe'),
  (6, 'North America'),
  (7, 'South America'),
  (8, 'Oceania');

-- insert all two-letter uppercase codes (AA..ZZ) with generated names
-- assign continents in round-robin fashion

do $$
declare
  code char(2); c1 int; c2 int;
  continent_id int;
  name text;
  n int := 0;
begin
  for c1 in ascii('A')..ascii('Z') loop
    for c2 in ascii('A')..ascii('Z') loop
      code := chr(c1) || chr(c2);
      continent_id := (n % 8) + 1; n := n + 1;
      name := 'Country ' || code;

      insert into country (code, id_continent, name)
        values (code, continent_id, name);
    end loop;
  end loop;
end $$;

-- insert some places for each country (~ 16k rows)

do $$
declare
  row record;
  lati numeric(8,5);
  long numeric(8,5);
  elev int;
  name text;
begin
  for row in select code from country loop
    for i in 1..48 loop
      name := format('Place %s-%02s', row.code, i);
      lati := random() * 180 - 90;    -- [-90, 90)
      long := random() * 360 - 180;   -- [-180, 180)
      elev := -430 + (random() * 8430)::int; -- [-430, 8000]

      insert into place (code_country, name, latitude, longitude, elevation)
        values (row.code, name, lati, long, elev);
    end loop;
  end loop;
end $$;

-- insert some weather data for each place (~ a million rows)

with dates as (
  select
    (date_trunc('month', current_date))::date as start_date,
    (date_trunc('month', current_date) + interval '1 month - 1 day')::date as end_date
), days as (
  select
    generate_series(d.start_date, d.end_date, interval '1 day')::date as dt
  from dates d
)
insert into weather (id_place, date, temp_lo, temp_hi, precip)
select
  p.id, d.dt as date, random() * 30 as tl, 30 + random() * 5, random() * 10
from place p cross join days d;

-- show counts of inserted rows
do $$
declare
  cnt int;
begin
  select count(*) into cnt from continent;
  raise notice 'Inserted % continents', cnt;

  select count(*) into cnt from country;
  raise notice 'Inserted % countries', cnt;

  select count(*) into cnt from place;
  raise notice 'Inserted % places', cnt;

  select count(*) into cnt from weather;
  raise notice 'Inserted % weather reports', cnt;
end $$;

Explore:

sqlselect count(*) from country;
explain select count(*) from country;
explain analyze select count(*) from country;

sqlselect count(*) from country where code='OO';
explain select count(*) from country where code='OO';
explain analyze select count(*) from country where code='OO';

sqlselect count(*) from country cross join place;
explain select count(*) from country cross join place;
explain analyze select count(*) from country cross join place;

sqlselect count(*) from country join place on code=code_country;
explain select count(*) from country join place on code=code_country;
explain analyze select count(*) from country join place on code=code_country;

sqlselect count(*) from place join weather on place.id=weather.id_place;
explain select count(*) from place join weather on place.id=weather.id_place;
explain analyze select count(*) from place join weather on place.id=weather.id_place;

sqlselect count(*) from city join weather on city.id=weather.city_id where city.id='oo';
explain select count(*) from city join weather on city.id=weather.city_id where city.id='oo';
explain analyze select id from city join weather on city.id=weather.city_id where city.id='oo';
vacuum analyze;

sqldrop index if exists idx_temp_lo;
create index idx_temp_lo on weather(temp_lo);

explain analyze select avg(temp_lo) from weather where temp_lo < 20;

explain analyze select temp_hi from weather where temp_lo < 20;
explain analyze select temp_lo from weather where temp_hi < 20;

explain analyze select temp_hi from weather order by temp_lo;
explain analyze select temp_lo from weather order by temp_lo;
explain analyze select temp_lo from weather order by temp_hi;

continent → country → place → weather

• For each continent, what is the average daily maximum

• temperature and total precipitation over the last year, only

• for places above 1000 meters elevation, and show the top 5

• hottest continents?

sqlexplain analyze
select
  c.name                   as continent,
  round(avg(w.temp_hi), 1) as avg_temp_hi,
  round(sum(w.precip), 1)  as total_precip
from weather w
  join place     p on p.id   = w.id_place
  join country   y on y.code = p.code_country
  join continent c on c.id   = y.id_continent
where p.elevation > 1000
  and current_date - interval '1 year' <= w.date
group by c.name
order by avg_temp_hi desc
limit 5;

-- filters
create index idx_weather_date on weather(date);
create index idx_place_elevation on place(elevation);

-- joins
create index idx_weather_id_place on weather(id_place);
create index idx_place_code_country on place(code_country);
create index idx_country_id_continent on country(id_continent);

sqlcreate materialized view mv_weather_summary as
select
    w.id_place,
    date_trunc('month', w.date) as month,
    avg(w.temp_hi) as avg_hi,
    sum(w.precip) as total_precip
from weather w
group by w.id_place, date_trunc('month', w.date);

-- refresh materialized view mv_weather_summary;

select
    c.name as continent,
    round(avg(mv.avg_hi), 1)       as avg_temp_hi,
    round(sum(mv.total_precip), 1) as total_precip
from mv_weather_summary mv
join place     p on p.id   = mv.id_place
join country   y on y.code = p.code_country
join continent c on c.id   = y.id_continent
where p.elevation > 1000
  and date_trunc('month', current_date - interval '1 year') <= mv.month
group by c.name
order by avg_temp_hi desc
limit 5;