P4 · Motor: consultas

Publicado: semana 12 · Entrega: semana 14 · En parejas

quipu ya guarda y encuentra filas; ahora va a responder consultas. Los operadores siguen la interfaz de iteradores de la sec. 15.7.2 de Silberschatz y de la nota 9 de CS186: cada uno tiene open(), next() (devuelve una fila o null cuando se acaba) y close(), y los operadores se encadenan en un árbol, como en el plan de ejecución de PostgreSQL. Cubre las semanas 11 a 13.

Los operadores trabajan sobre lo que dejó P3: leen los heap files con scan() y get(rid), y los índices con range(). Como en P3, todo es síncrono y el costo se mide en páginas leídas del disco (disk.stats).

Archivos

Esta carpeta trae el punto de partida. Se copia a la carpeta del proyecto, encima de lo de P3:

Ustedes agregan plans/plans.mjs y plans/README.md. Sus pruebas siguen en quipu/, con nombre *.test.mjs (por ejemplo, quipu/exec/sort.test.mjs). Nada de P3 cambia: p3.public.test.mjs, load.mjs y quipu/schemas.mjs se quedan como están y sus pruebas tienen que seguir pasando.

Reglas comunes

Las de P3 siguen valiendo: las pruebas usan exactamente los nombres de este enunciado, un RID es { pageId, slot }, una fila es un objeto con una propiedad por columna (NULL es null) y, cuando algo no se puede hacer, el método lanza un Error. Además:

• Interfaz de iteradores. Todos los operadores tienen open(), next() y close(), síncronos. next() devuelve la siguiente fila o null cuando ya no hay más, y sigue devolviendo null si se vuelve a llamar. open() después de close() vuelve a empezar desde el principio: así el block nested loop recorre el inner una vez por bloque. Un operador abre a sus hijos en su open() y los cierra en su close().
• Esquema. Todo operador tiene la propiedad schema, el esquema de las filas que devuelve (un arreglo de { name, type }, como en P3), lista desde el constructor. SeqScan e IndexScan lo toman del heap file: P4 usa la propiedad schema del HeapFile, el esquema con que se creó. Si su HeapFile lo guardó con otro nombre, agreguen esa propiedad; las pruebas de P3 no cambian por eso.
• Errores en el constructor. Una columna que no existe en el esquema del hijo, un nombre de columna repetido en la salida o un parámetro inválido (blockPages < 1, memPages < 3) hacen que el constructor lance un error.
• Filas. Un operador no modifica las filas que recibe. Project, los joins y HashAggregate devuelven objetos nuevos.
• Nada queda colgado. Después de close(), ningún operador deja páginas fijadas en ningún buffer pool ni archivos temporales en el disco, aunque se cierre antes de llegar al final (por ejemplo, debajo de un Limit).

Memoria y lecturas

En quipu cada archivo tiene su DiskManager y su BufferPool (P3); no hay un buffer pool global. Por eso:

• Los operadores reciben sus HeapFile y BPlusTree ya abiertos; no abren archivos de tablas por su cuenta. Quien arma el plan decide cuántos frames tiene cada archivo.
• Las páginas leídas de un plan son la suma de disk.stats.reads de todos los archivos de tablas e índices que abre, cada uno con un DiskManager recién abierto (contadores en cero, buffer pool vacío). Las páginas de los archivos temporales de ExternalSort se cuentan aparte, en sort.stats.
• La memoria propia de un operador (el bloque del block nested loop, las páginas del ordenamiento externo) es aparte de los buffer pools y se mide en páginas, con la regla que sigue.

Páginas de un operador

Las filas que pasan de un operador a otro no viven en páginas, pero el block nested loop y el ordenamiento externo tienen que contarlas en páginas. La regla es una sola, y las pruebas la calculan con su propio page.mjs y su propio record.mjs:

Un bloque de k páginas se llena con k SlottedPage en memoria (SlottedPage.init(Buffer.alloc(PAGE_SIZE))). Cada fila, en el orden en que llega, se codifica con encode(schema, fila) y se inserta en la última página; si insert devuelve −1, se abre una página nueva, y si ya había k, el bloque está lleno y esa fila es la primera del bloque siguiente.

Para un SeqScan sobre una tabla recién cargada, el número de páginas que llenan sus filas es, o casi, el número de páginas de su heap file.

Operadores (quipu/exec/)

Los operadores no saben qué consulta están ejecutando: reciben sus hijos ya construidos. Las pruebas arman árboles de operadores y comparan el resultado con la misma consulta en PostgreSQL; cuando la consulta no tiene ORDER BY, comparan sin importar el orden.

Scans

• SeqScan(heapFile) recorre heapFile.scan() y devuelve las filas (sin el RID). Lee cada página una vez: con un buffer pool frío, un recorrido completo lee numPages páginas, y un Limit arriba hace que lea solo las que necesita.
• IndexScan(btree, heapFile, lo, hi) recorre btree.range(lo, hi) y busca cada RID con heapFile.get(rid). Las filas salen en el orden de range: por clave y, si se repite, por RID. Sin lo ni hi, todo el índice; con lo > hi, nada. Cada página del heap que tiene filas del rango se pide una vez por fila; con un buffer pool que alcanza para todas, cada una se lee del disco una sola vez.

Filter, Project y Limit

• Filter(child, predicate): predicate es una función de JavaScript que recibe la fila. El esquema es el del hijo.
• Project(child, columns): columns es un arreglo de nombres de columna o de pares [columna, nuevoNombre], como columna AS nuevoNombre en SQL. Por ejemplo, new Project(scan, ['shipment_id', ['price', 'precio']]). El esquema tiene esas columnas, en ese orden, con el tipo que tenían. Es la forma de renombrar columnas antes de un join.
• Limit(child, n): después de n filas devuelve null sin pedirle más al hijo.

Joins

Los tres son inner joins. La fila de salida es una fila nueva con las columnas de los dos lados ({ ...izquierda, ...derecha }) y el esquema es el de la izquierda seguido del de la derecha; la izquierda es el outer (o el build en HashJoin). Si los dos lados tienen una columna con el mismo nombre (como trip_id en shipment y trip, o city en customer y agency), el constructor lanza un error: renombren antes con Project. El orden de las filas de salida no está definido.

BlockNestedLoopJoin(outer, inner, predicate, blockPages). predicate(o, i) recibe una fila del outer y una del inner y dice si van juntas; puede ser cualquier condición, no solo una igualdad. El algoritmo es el de la sec. 15.5.2:

1. Llenar un bloque de blockPages páginas con filas del outer (la regla de “Páginas de un operador”).
2. Si el bloque quedó vacío, terminar. Si no, abrir el inner, recorrerlo entero y, por cada fila del inner, devolver las combinaciones con las filas del bloque que cumplen el predicado; cerrar el inner y volver al paso 1.

El inner se abre una vez por bloque y nunca si el outer está vacío. Con blockPages páginas de bloque (en la notación de la semana 11, M = blockPages

• 2: una página para el inner y una para la salida), si el outer llena P_R páginas, las páginas leídas son

|R| + ⌈P_R / blockPages⌉ · |S|

cuando el buffer pool del inner es más chico que el inner (cada recorrido vuelve a leer todo) y |R| + |S| cuando el inner entra en su buffer pool. Las pruebas revisan las dos cosas, con el número de bloques que da la regla de páginas.

IndexNestedLoopJoin(outer, innerIndex, innerHeap, outerKey). Por cada fila del outer, toma su columna outerKey y busca en innerIndex todas las entradas con esa clave (range(k, k), porque la clave puede repetirse, como en shipment_sender); cada RID se trae con innerHeap.get(rid). El esquema es el del outer seguido de innerHeap.schema. Si outerKey es NULL, esa fila no se busca: NULL no está en ningún índice de quipu y en SQL no es igual a nada.

HashJoin(build, probe, buildKey, probeKey). open() lee todo build (y lo cierra) y arma un Map de la clave a sus filas; después, cada fila de probe se busca en el Map. Las claves son un nombre de columna o un arreglo de nombres del mismo largo (por ejemplo, ['origin_agency_id', 'dest_agency_id']); dos claves son iguales si lo son columna por columna. Una fila con NULL en alguna columna de la clave no coincide con nada, ni del lado del build ni del probe. Cada lado se lee una vez: |build| + |probe| páginas.

Bono: un hash join con particiones en disco (sec. 15.5.5) cuando el build no entra en memoria, con un quinto argumento { memPages, tmpDir } y las mismas reglas de archivos temporales que ExternalSort. Las pruebas públicas no lo revisan; si lo hacen, agreguen sus pruebas y cuéntenlo en su README.

ExternalSort

new ExternalSort(child, key, memPages, options) ordena las filas del hijo con memPages páginas de memoria (memPages ≥ 3), como en la sec. 15.4 y en la semana 11.

La clave. key es un nombre de columna, o un arreglo cuyos elementos son nombres de columna o { column, desc: true }. Por ejemplo, [{ column: 'price', desc: true }, 'shipment_id'] es ORDER BY price DESC, shipment_id. Como en PostgreSQL, NULL va después de todo en orden ascendente y antes de todo en descendente. Los números se comparan como números y los textos con < de JavaScript, que da el mismo orden que COLLATE "C" en PostgreSQL. Las filas con la misma clave pueden salir en cualquier orden.

El algoritmo.

1. Runs. open() llena un bloque de memPages páginas con filas del hijo, ordena sus filas en memoria y las escribe como un run; repite hasta que el hijo se acaba, y lo cierra. Si todas las filas entraron en el primer bloque, no se escribe nada: next() las entrega desde memoria.
2. Pasadas de fusión. Mientras haya más de memPages − 1 runs, una pasada los fusiona en grupos de memPages − 1 runs consecutivos, en orden (el último grupo puede ser más chico); un grupo de un solo run pasa tal cual a la siguiente pasada, sin copiarse. Un run se borra en cuanto se fusiona. Todas estas pasadas ocurren en open().
3. Última fusión. Cuando quedan a lo más memPages − 1 runs, next() los fusiona y entrega las filas una por una, sin escribirlas.

Con R runs iniciales, hay ⌈log_{memPages−1} R⌉ pasadas de fusión, contando la última; es la fórmula de la semana 11 con M = memPages.

Archivos temporales. Cada run es un archivo propio, con su DiskManager, en la carpeta options.tmpDir (por defecto, una carpeta nueva de mkdtemp en os.tmpdir(), que close() también borra). Los nombres los eligen ustedes, pero los runs van directamente en esa carpeta. Un run es una secuencia de páginas con slots (el formato de P3), escritas con allocatePage y writePage, sin buffer pool: el ordenamiento maneja sus memPages páginas por su cuenta. Al escribir, las filas ya ordenadas se empaquetan en una página de salida que se escribe cuando se llena; al fusionar, cada run de entrada se lee de a una página. Así, cada página temporal se escribe una vez y se lee una vez. Como las filas son de largo variable, un run puede ocupar alguna página más que memPages.

Lo que se observa. La propiedad stats es { runs, passes, reads, writes }: los runs iniciales (1 si todo entró en memoria, 0 si el hijo no devolvió filas), las pasadas de fusión, y las páginas leídas y escritas en los archivos temporales. runs y passes están listos al terminar open(); reads sigue creciendo durante la última fusión. Después de open(), en tmpDir quedan exactamente los runs de la última fusión; después de close(), nada. Las pruebas revisan que:

• runs es el número de bloques de memPages páginas que llenan las filas del hijo, y passes, el de la fórmula;
• la entrada se lee una vez y, al terminar, reads es igual a writes;
• si la entrada llena P páginas, writes es al menos (casi) P, lo que escribe la fase 1, y a lo más passes · (P + runs);
• el resultado es el de ORDER BY en PostgreSQL, también con NULL, con textos y con claves de varias columnas.

HashAggregate

new HashAggregate(child, groupBy, aggregates) agrupa con un Map, como la agregación con hash de la sec. 15.6.5. groupBy es un arreglo de nombres de columna (puede estar vacío) y aggregates un arreglo de objetos { fn, column, as }:

as es el nombre de la columna en la salida. La fila de salida tiene las columnas de groupBy y luego los agregados, en ese orden en schema. La semántica es la de SQL:

• Todos los NULL de una columna de groupBy van al mismo grupo.
• sum, avg, min y max de un grupo donde todos los valores son NULL dan null; count(columna) da 0.
• Sin groupBy, el resultado es siempre una fila, aunque el hijo no devuelva ninguna (count 0 y lo demás null). Con groupBy y sin filas, ninguna.
• El orden de los grupos no está definido.

Cargar Chasqui completo

Para los joins hacen falta más tablas que shipment. node load-all.mjs [carpeta] hace lo mismo que load.mjs para las cinco tablas de TABLES en quipu/schemas-p4.mjs y deja en la carpeta (por defecto, data/) once archivos:

con <tabla> en shipment, customer, agency, route y trip. Los tres archivos de shipment son los mismos que deja load.mjs. Las conversiones son las de P3 (numeric y timestamptz a float64) y, como en P3, cargar dos veces deja lo mismo que cargar una. Pueden reusar el código de load.mjs, pero load.mjs tiene que seguir haciendo lo que pide P3.

Tres consultas, tres planes

plans/ trae tres consultas sobre Chasqui: un join entre envíos y clientes con un filtro selectivo (q1.sql), un join de tres tablas con agregación (q2.sql) y un “top 20” que necesita ordenar (q3.sql). Para cada una:

1. Dos planes distintos armados con sus operadores en plans/plans.mjs. node plans/plans.mjs [carpeta] (o make plans, que antes corre load-all.mjs) abre los archivos de la carpeta con un buffer pool de 64 frames por archivo, ejecuta cada plan en frío, imprime las páginas leídas (la suma de disk.stats.reads de los archivos que abre el plan; las páginas temporales de ExternalSort, aparte) y comprueba que el resultado es el de PostgreSQL.
2. El costo que predicen las fórmulas de la semana 11 para esos dos planes y por qué difiere (o no) de lo medido. Una pista: el buffer pool de cada archivo tiene 64 frames y varias tablas de Chasqui caben enteras.
3. El plan de PostgreSQL, con EXPLAIN (ANALYZE, BUFFERS): sobre la base de pruebas (make psql, después de ANALYZE; son los mismos datos que cargó load-all.mjs) y sobre chasqui_big. Qué operadores de quipu corresponden a sus nodos, por qué sus números de páginas no coinciden con los de quipu, y qué índice o reescritura lo mejora. Lo que pongan en chasqui_big (un índice, ANALYZE) cambia esa base: háganlo en su propio contenedor.

Todo va en plans/README.md, con este formato, que las pruebas revisan:

## Consulta 1

### Plan A: <nombre corto>

```text
<el árbol de operadores, un operador por línea>
```

Páginas leídas: <número>

### Plan B: <nombre corto>

...

Páginas leídas: <número>

### Costo estimado

Costo estimado: <las fórmulas de los dos planes, con números>

<por qué difiere o no de lo medido>

### PostgreSQL

```text
<la salida de EXPLAIN (ANALYZE, BUFFERS) en la base de pruebas>
```

```text
<la salida en chasqui_big>
```

<la correspondencia con quipu y la mejora>

y lo mismo para ## Consulta 2 y ## Consulta 3. Las líneas Páginas leídas: y Costo estimado: empiezan así, al inicio de la línea. Las salidas de EXPLAIN se pegan tal como salen de psql, sin editar: los números que pongan tienen que salir de una corrida de verdad.

README

En el README de su proyecto, una sección de P4 corta: cómo vuelve a empezar cada operador en un segundo open(), qué guarda en memoria cada uno (y cuánto, en el peor caso) y cómo nombran y borran los archivos temporales. El análisis de los planes va en plans/README.md.

Pruebas

make test                  # carga Chasqui en chasqui_test y corre las pruebas de P3 y P4
QUIPU_SEED=7 make test     # lo mismo, con otras secuencias al azar

make test corre p3.public.test.mjs, p4.public.test.mjs y las pruebas de ustedes en quipu/. Antes de probar los operadores, p4.public.test.mjs carga las cinco tablas en una carpeta temporal con el HeapFile y el BPlusTree de ustedes, así que los operadores se pueden probar aunque load-all.mjs todavía no funcione; load-all.mjs tiene su propia sección.

Hay una sección por grupo de operadores (scans y operadores fila por fila, IndexScan, cada join, ExternalSort, HashAggregate), una para load-all.mjs y una para plans/, que solo revisa que estén los archivos y el formato de plans/README.md; el contenido del análisis se revisa a mano. Las pruebas comparan con PostgreSQL los resultados de árboles de operadores sobre las tablas de Chasqui y revisan las páginas leídas con las cotas de la sección “Memoria y lecturas”: exactas cuando la fórmula es exacta (un SeqScan, un HashJoin, un block nested loop con un inner que no entra en su buffer pool, los runs y las pasadas del ordenamiento) y con márgenes donde dependen del formato de sus páginas. Las pruebas privadas son las mismas con otras semillas y con los datos de Chasqui generados con otra semilla (SEED=123 make test). Todas las de P3 y P4 corren en menos de un minuto.