English
Keyset paging
Step 1. Offset or keyset
Why. A chat may have 100 000 messages; the client shows the newest 50 and loads older ones as the user scrolls up. The textbook way to page is offset paging:
sql
SELECT ... FROM messages WHERE chat_id = @chat ORDER BY id DESC LIMIT 50 OFFSET 5000It has two problems in a messenger:
- It gets slower with every page.
OFFSET 5000makes PostgreSQL read and throw away 5000 rows before it returns 50. - It is wrong when data changes. If three new messages arrive while the user is scrolling, every message moves three places down; the next page starts three messages too early and the user sees duplicates. Deleted messages make the page skip some instead.
Keyset paging (also called cursor paging) remembers where the previous page ended instead of how many rows to skip:
sql
SELECT ... FROM messages WHERE chat_id = @chat AND id < @last_id_of_previous_page ORDER BY id DESC LIMIT 51With the index (chat_id, id DESC) of topic 4 every page costs the same, and new messages above the cursor do not shift anything below it. This is where the UUIDv7 ids of topic 3 pay off: because ids sort by creation time, the id of a message is its cursor.
Why LIMIT 51 for a page of 50? The extra row answers "is there another page?" without a second COUNT query.
Step 2. A helper for pages
Do.
cs
using Chatex.Data.Models;
namespace Chatex.Data.Repositories;
internal static class Paging
{
/// <summary>
/// Turns <paramref name="items"/>, fetched with <c>Take(limit + 1)</c>, into a page.
/// The extra row only tells whether another page exists; it is not returned.
/// </summary>
public static CursorPage<TItem, TCursor> ToPage<TItem, TCursor>(
List<TItem> items, int limit, Func<TItem, TCursor> cursorOf)
where TCursor : struct
{
if (items.Count <= limit)
{
return new CursorPage<TItem, TCursor>(items, null);
}
items.RemoveAt(limit);
return new CursorPage<TItem, TCursor>(items, cursorOf(items[^1]));
}
}The method receives the list fetched with Take(limit + 1) and a function that extracts the cursor from an item. If at most limit items came back, this is the last page and the cursor is null. Otherwise the extra item is removed and the cursor of the last returned item becomes NextCursor. items[^1] is the index from end operator: the last element.
Step 3. The message history
Why. The history is read in three ways:
- No cursor — the newest page, when a chat is opened;
before— older messages, newest first, while the user scrolls up;after— newer messages, oldest first, after the browser was offline for a while and must fill the gap without reloading everything (topic 20).
Do.
cs
using Chatex.Data.Abstractions;
using Chatex.Data.Entities;
using Chatex.Data.Models;
using Microsoft.EntityFrameworkCore;
namespace Chatex.Data.Repositories;
internal sealed class MessageRepository(ChatexDbContext db) : IMessageRepository
{
public void Add(Message message) => db.Messages.Add(message);
public Task<Message?> GetByIdAsync(Guid id, CancellationToken cancellationToken = default) =>
db.Messages.Include(m => m.Attachments).FirstOrDefaultAsync(m => m.Id == id, cancellationToken);
public Task<Message?> GetDetailsAsync(Guid id, CancellationToken cancellationToken = default) =>
db.Messages
.AsNoTracking()
.Include(m => m.Sender).ThenInclude(u => u.Profile)
.Include(m => m.Attachments)
.AsSplitQuery()
.FirstOrDefaultAsync(m => m.Id == id, cancellationToken);
public Task<bool> ExistsInChatAsync(Guid chatId, Guid messageId, CancellationToken cancellationToken = default) =>
db.Messages.AnyAsync(m => m.Id == messageId && m.ChatId == chatId && m.DeletedAt == null, cancellationToken);
public async Task<CursorPage<Message, Guid>> GetPageAsync(
Guid chatId, Guid? before, Guid? after, int limit, CancellationToken cancellationToken = default)
{
if (before is not null && after is not null)
{
throw new ArgumentException($"Pass either {nameof(before)} or {nameof(after)}, not both.");
}
var query = db.Messages
.AsNoTracking()
.Include(m => m.Sender).ThenInclude(u => u.Profile)
.Include(m => m.Attachments)
.Where(m => m.ChatId == chatId);
// UUIDv7 ids sort by creation time, so the id alone is the cursor.
if (after is { } newerThan)
{
query = query.Where(m => m.Id.CompareTo(newerThan) > 0).OrderBy(m => m.Id);
}
else
{
if (before is { } olderThan)
{
query = query.Where(m => m.Id.CompareTo(olderThan) < 0);
}
query = query.OrderByDescending(m => m.Id);
}
var items = await query.Take(limit + 1).AsSplitQuery().ToListAsync(cancellationToken);
return Paging.ToPage(items, limit, m => m.Id);
}
}m.Id.CompareTo(olderThan) < 0is how we write "id < @cursor" in LINQ: C# has no<operator forGuid, but Npgsql translatesCompareTointo the SQL comparison of twouuidvalues.- The pattern
after is { } newerThanchecks that the nullableGuid?has a value and copies it into a non-nullable variable in one step. - Both cursors at once make no sense, so the method rejects them with an
ArgumentException: that is a bug of the caller, not an expected situation. AsSplitQuery()loads the messages, their senders' profiles and their attachments with separate SQL queries instead of one bigJOIN. A single join would repeat every message once per attachment; split queries avoid this "cartesian explosion".GetByIdAsyncis tracked andGetDetailsAsyncis not: the first serves editing and deleting, the second returns a message for display.
Step 4. Members and read positions
Do.
cs
using Chatex.Data.Abstractions;
using Chatex.Data.Entities;
using Chatex.Data.Models;
using Microsoft.EntityFrameworkCore;
namespace Chatex.Data.Repositories;
internal sealed class ChatMemberRepository(ChatexDbContext db) : IChatMemberRepository
{
public void Add(ChatMember member) => db.ChatMembers.Add(member);
public void Remove(ChatMember member) => db.ChatMembers.Remove(member);
public Task<ChatMember?> GetAsync(Guid chatId, Guid userId, CancellationToken cancellationToken = default) =>
db.ChatMembers.FirstOrDefaultAsync(m => m.ChatId == chatId && m.UserId == userId, cancellationToken);
public Task<bool> IsMemberAsync(Guid chatId, Guid userId, CancellationToken cancellationToken = default) =>
db.ChatMembers.AnyAsync(m => m.ChatId == chatId && m.UserId == userId, cancellationToken);
public Task<int> CountAsync(Guid chatId, CancellationToken cancellationToken = default) =>
db.ChatMembers.CountAsync(m => m.ChatId == chatId, cancellationToken);
public async Task<IReadOnlyList<Guid>> GetExistingUserIdsAsync(
Guid chatId, IReadOnlyCollection<Guid> userIds, CancellationToken cancellationToken = default) =>
await db.ChatMembers
.Where(m => m.ChatId == chatId && userIds.Contains(m.UserId))
.Select(m => m.UserId)
.ToListAsync(cancellationToken);
public async Task<CursorPage<ChatMember, Guid>> GetMembersAsync(
Guid chatId, Guid? afterUserId, int limit, CancellationToken cancellationToken = default)
{
var query = db.ChatMembers
.AsNoTracking()
.Include(m => m.User).ThenInclude(u => u.Profile)
.Where(m => m.ChatId == chatId);
if (afterUserId is { } cursor)
{
query = query.Where(m => m.UserId.CompareTo(cursor) > 0);
}
var items = await query.OrderBy(m => m.UserId).Take(limit + 1).ToListAsync(cancellationToken);
return Paging.ToPage(items, limit, m => m.UserId);
}
public async Task<IReadOnlyList<Guid>> GetChatIdsForUserAsync(Guid userId, CancellationToken cancellationToken = default) =>
await db.ChatMembers
.Where(m => m.UserId == userId && m.Chat.DeletedAt == null)
.Select(m => m.ChatId)
.ToListAsync(cancellationToken);
public async Task<bool> MarkReadAsync(Guid chatId, Guid userId, Guid messageId, CancellationToken cancellationToken = default)
{
var updated = await db.ChatMembers
.Where(m => m.ChatId == chatId
&& m.UserId == userId
&& (m.LastReadMessageId == null || m.LastReadMessageId.Value.CompareTo(messageId) < 0))
.ExecuteUpdateAsync(s => s.SetProperty(m => m.LastReadMessageId, messageId), cancellationToken);
return updated > 0;
}
}GetMembersAsyncpages through a channel that may have thousands of subscribers. The cursor is the user id; the order by user id is not meaningful to people, but it is stable and unique, which is all keyset paging needs.MarkReadAsyncimplements the rule "the read position only moves forward" (topic 3) in the database itself: theUPDATEchanges the row only if the stored position isNULLor older than the new one. Two browser tabs that report "read up to X" and "read up to an older Y" in any order end with X. The method returns whether a row changed, so the service of topic 10 notifies the other members only when something actually changed.GetChatIdsForUserAsyncfilters bym.Chat.DeletedAt— a navigation property inside the query, which EF Core turns into aJOIN.
Check
dotnet build succeeds. The paging is tested in topic 6 with 120 messages and pages of 50: 50, 50 and 20 messages, no duplicates, NextCursor null on the last page.