Ayer jueves 5 de agosto, luego de una decepcionante charla que presenciamos junto a unos amigos (Leonardo Garcés y Luís Hereira), decidimos ir a pasar los malos ratos vividos al lugar tradicionalmente utilizado para celebrar, el ShopDog de Pedro de Valdivia con Providencia u 11 de septiembre.
La conversación derivó en variados temas, y después de algunas discusiones bizantinas, caímos en la eterna discusión sobre métodos de paginación. Yo presenté el esquema que actualmente utilizamos en IConstruye.
Nuestro sistema de paginación funciona de la siguiente forma. Es necesario tener un campo identity y utilizar cache. Una consulta a paginar típica tiene los siguientes elementos
Select
campos
From
tablas
Where
cláusulas
La idea consiste en dividir esta consulta en dos consultas, una que ejecute principalmente la parte del where y la segunda que ejecute principalmente la parte del select y los campos.
Con la primera consulta acotamos a una lista de ids (identitys) de los documentos que cumplen con la restricción where (por eso digo que principalmente ejecuta el where), y almacenamos nuestros N ids en un caché. Si consideramos que cada int pesa 4bytes y almacenamos 500 elementos, tenemos 2kilos (mas algunos bytes de estructura y otros) en un caché. No es mucho. Es mejor que almacenar todo en un caché.
Con la segunda consulta, le pedimos una página cualquiera de x registros. Con esto obtengo los x ids moviéndome sobre el arreglo de enteros almacenado en el cache. Con los ids, ejecuto la segunda consulta, que es mucho mas pesada en el select (y liviana en el where), pero como el resultado son sólo los documentos que quiero, se minimiza bastante el trafico de información que no va a ser considerada después. Traigo así SOLO los x registros de la página solicitada. Para cualquier otra página, ya tengo los ids almacenados en el cache así que no es necesario ejecutar la primera consulta.
Luís menciona que mi sistema está representado por la ecuación Y = m*X + b, es decir una recta con pendiente m y que parte en b. Pueden ver la discusión escrita en la servilleta en la imagen asociada. El costo b es el de la consulta 1 (la de los ids) y por cada pagina X se le pondera por un costo m. Yo argumento que m tiende a cero ya que no hay diferencia significante entre la primera y la última página.
Servilleta de la discusión
Cuando la discusión se torna inútil nuevamente, Luís propone su método de paginación, obtenido desde http://www.winnetmag.com/Article/ArticleID/40505/40505.html.
Este método se basa en dos consultas, una de ellas anidada en la otra. Un seudo SQL sería algo como
SELECT TOP page_size *
FROM table
WHERE primary_key NOT IN
(SELECT TOP page_size * (page_number - 1) primary_key FROM table WHERE filter_conditions ORDER BY sort_field)
AND filter_criteria
ORDER BY sort_field
El argumento mío no se deja esperar. Siempre haces dos consultas. Su respuesta, buena en todo caso, es que las primeras páginas son muy rápidas de cargar (por que el select anidado da Top 0 para el primer caso) y que el usuario nunca avanza muchas páginas. Es cierto, pero también ocurre a veces que usuarios llegan hasta altas páginas y ya deja de funcionar bien. En IConstruye utilizamos ese mismo sistema durante un tiempo y habían usuarios que llegaban hasta la página 27.
Cuando la página es muy alta, se pone cada vez mas lento. Este sistema es mas parecido a una exponencial. Verán en la imagen la exponencial y su ecuación ex. Interesante es encontrar el punto donde ex se junta con m*x+b.
¿Cual es mejor?. Dependerá de los requerimientos. Probablemente el sistema perfecto sea una mezcla de ambos, tal como existe el HybridDictionary, que tiene un comportamiento dual dependiendo de la cantidad de elementos. También recuerdo dentro de los algoritmos de ordenamiento, donde el QuickSort era muy rápido, pero para pocos elementos era muy lento. Si se hacia un algoritmo hibrido entre QuickSort y BubbleSort (creo que era el otro), para pocos elementos funcionaba bien el Bubble y para muchos, el Quick.