`/api/search/random` results are biased by asset UUID

[aazuspan]

I have searched the existing issues, both open and closed, to make sure this is not a duplicate report.

• Yes

The bug

When you query random assets with /api/search/random, the assets returned are strongly biased towards lower UUIDs. The figure below was generated by sampling 100k assets (100 queries of size 1000) from a library of 3.5k images and plotting the relative sample rate of each asset compared to the lexicographic order of its UUID within the database.

Assets with low UUIDs (e.g. 00012fdc-95e5-412f-b8aa-65807961c489) are being sampled ~16x more frequently than assets with high UUIDs (e.g. ffdbd0d4-891a-49cb-a296-2d2ef7311768). The result is that any "random" sample, like a randomized slideshow, returns some assets much more frequently than others.

The OS that Immich Server is running on

Unraid 7.2.2

Version of Immich Server

v2.5.2

Version of Immich Mobile App

N/A

Platform with the issue

• Server
• Web
• Mobile

Device make and model

No response

Your docker-compose.yml content

name: immich

services:
  immich-server:
    container_name: immich_server
    image: ghcr.io/immich-app/immich-server:${IMMICH_VERSION:-release}
    # extends:
    #   file: hwaccel.transcoding.yml
    #   service: cpu # set to one of [nvenc, quicksync, rkmpp, vaapi, vaapi-wsl] for accelerated transcoding
    volumes:
      # Do not edit the next line. If you want to change the media storage location on your system, edit the value of UPLOAD_LOCATION in the .env file
      - ${UPLOAD_LOCATION}:/usr/src/app/upload
      - /etc/localtime:/etc/localtime:ro
    env_file:
      - .env
    ports:
      - '2283:2283'
    depends_on:
      - redis
      - database
    restart: always
    healthcheck:
      disable: false

  immich-machine-learning:
    container_name: immich_machine_learning
    # For hardware acceleration, add one of -[armnn, cuda, rocm, openvino, rknn] to the image tag.
    # Example tag: ${IMMICH_VERSION:-release}-cuda
    image: ghcr.io/immich-app/immich-machine-learning:${IMMICH_VERSION:-release}
    # extends: # uncomment this section for hardware acceleration - see https://immich.app/docs/features/ml-hardware-acceleration
    #   file: hwaccel.ml.yml
    #   service: cpu # set to one of [armnn, cuda, rocm, openvino, openvino-wsl, rknn] for accelerated inference - use the `-wsl` version for WSL2 where applicable
    volumes:
      - model-cache:/cache
    env_file:
      - .env
    restart: always
    healthcheck:
      disable: false

  redis:
    container_name: immich_redis
    image: docker.io/valkey/valkey:8-bookworm@sha256:ff21bc0f8194dc9c105b769aeabf9585fea6a8ed649c0781caeac5cb3c247884
    healthcheck:
      test: redis-cli ping || exit 1
    restart: always

  database:
    container_name: immich_postgres
    image: ghcr.io/immich-app/postgres:14-vectorchord0.3.0-pgvectors0.2.0@sha256:fa4f6e0971f454cd95fec5a9aaed2ed93d8f46725cc6bc61e0698e97dba96da1
    environment:
      POSTGRES_PASSWORD: ${DB_PASSWORD}
      POSTGRES_USER: ${DB_USERNAME}
      POSTGRES_DB: ${DB_DATABASE_NAME}
      POSTGRES_INITDB_ARGS: '--data-checksums'
      # Uncomment the DB_STORAGE_TYPE: 'HDD' var if your database isn't stored on SSDs
      # DB_STORAGE_TYPE: 'HDD'
    volumes:
      # Do not edit the next line. If you want to change the database storage location on your system, edit the value of DB_DATA_LOCATION in the .env file
      - ${DB_DATA_LOCATION}:/var/lib/postgresql/data
    restart: always

volumes:
  model-cache:

Your .env content

# You can find documentation for all the supported env variables at https://immich.app/docs/install/environment-variables

# The location where your uploaded files are stored
UPLOAD_LOCATION=/mnt/user/Media/Immich

# The location where your database files are stored. Network shares are not supported for the database
DB_DATA_LOCATION=/mnt/user/appdata/postgresql/data

# To set a timezone, uncomment the next line and change Etc/UTC to a TZ identifier from this list: https://en.wikipedia.org/wiki/List_of_tz_database_time_zones#List
# TZ=Etc/UTC

# The Immich version to use. You can pin this to a specific version like "v1.71.0"
IMMICH_VERSION=release

# Connection secret for postgres. You should change it to a random password
# Please use only the characters `A-Za-z0-9`, without special characters or spaces
DB_PASSWORD=redacted

# The values below this line do not need to be changed
###################################################################################
DB_USERNAME=postgres
DB_DATABASE_NAME=immich

Reproduction steps

1. Make multiple POST requests to the search/random endpoint.
2. Compare the frequency that each asset is returned to the lexicographic order of its UUID.

This can be done with the following Python script and a running Immich server:

import requests
import pandas as pd

KEY = "API_KEY_HERE"
BASE_URL = "IMMICH_URL_HERE"

# Query 100k random assets in batches of 1k
assets = []
for _ in range(100):
    assets += requests.request(
        "POST", 
        BASE_URL + "/api/search/random", 
        headers={"x-api-key": KEY}, 
        json={"size": 1000},
    ).json()

# Compare asset UUIDs to their sampling frequency
df = pd.DataFrame(assets)
sorted_ids = df["id"].sort_values().unique().tolist()
(
    df["id"].value_counts()
    .reset_index(name="count")
    .assign(lex_order=lambda x: x["id"].apply(lambda id: sorted_ids.index(id)))
    .sort_values("lex_order")
).plot(x="lex_order", y="count")

Relevant log output

Additional information

The root cause seems to be the sampling algorithm used in SearchRepository.searchRandom, which queries assets below and above a random cutoff UUID, unions them, and returns a subset of the union.

I tested that SQL query in a dummy Postgres database and found that on average, the final subset is sampled much more heavily (~90%) from the left side of the union (lower UUIDs) than the right side of the union (higher UUIDs).

[mertalev]

That algorithm was assuming uuidv4, which doesn’t really work since we use uuidv7 now. In any case, the point of it was to avoid the super inefficient order by random(), which was added there later anyway… It’d be nice to randomize in a way that doesn’t scan and sort the entire table, but in the meantime the uuid + union check isn’t doing anything beneficial at this point.

[mmomjian]

Is there any reason we would expect our own randomizer to be more efficient than Postgres, even though it is pretty slow?

[mertalev]

The problem is that Postgres doesn't have a randomizer (well it does with TABLESAMPLE, but that doesn't help us). Everyone is left to figure out efficient randomization in their own DDL-specific way.

[mmomjian]

Yeah, that makes sense. We could potentially add a column populated with random(), index it, and use that for asset selection? I know that's a common approach while keeping things in the DB.

[mertalev]

Oh yeah, that seems like a reasonable solution!

[mbuzina]

Yeah, that makes sense. We could potentially add a column populated with random(), index it, and use that for asset selection? I know that's a common approach while keeping things in the DB.

So you will generate a random order, but you always have the same random order (new assets are inserted at a random place). To avoid that you may generate a random number N for which (total # assets in slideshow) mod N = 1 and skip N assets instead of moving to the next. This way you get a more random show each time.

[mrmkrs]

I dont have anything technical to say (yet), but i'll be watching this issue because it seem like the cause of what i experience with my DYI digital photoframe; I use the /api/search/random endpoint to fetch 10 random images, show them one by one and then call the endpoint again etc.. This is working a couple of weeks now in the living room so it's pretty visible. We noticed some images are displayed way more often than others. Some never even seem to make the cut (about 500 images). Went to github and found this issue :)

[Phlogi]

Oh yeah, that seems like a reasonable solution!

I was working on a PR for that already and will open it soon after some testing.

[StevenMassaro]

I believe a simpler solution here would be to divide size by 2 for each half of the union, so the code would look something like this (kind of psuedocode):

  async searchRandom(size: number, options: AssetSearchOptions) {
    const uuid = randomUUID();
    const builder = searchAssetBuilder(this.db, options);
    const lessThan = builder
      .selectAll('asset')
      .where('asset.id', '<', uuid)
      .orderBy(sql`random()`)
      .limit(size/2);
    const greaterThan = builder
      .selectAll('asset')
      .where('asset.id', '>', uuid)
      .orderBy(sql`random()`)
      .limit(size/2);
    const { rows } = await sql<MapAsset>`${lessThan} union all ${greaterThan} limit ${size}`.execute(this.db);
    return rows;
  }

This would guarantee an equal distribution of pictures from either side of the union. This code is not complete because it does not guarantee that the number of rows returned will actually be equivalent to the size requested, it could be one or two less.

[StevenMassaro]

The approach that I described above actually does not work. Interestingly it changes the distribution of randomness to prefer both low and high UUIDs but ignores the middle. I did not explore any further why this was the case because I think that the solution for this problem is actually significantly simpler (see my PR). Note that my PR is more of a bandaid type fix of the existing logic, rather than the addition of a new column and more robust random that was being proposed earlier.