Estoy leyendo Hadoop: la guía definitiva de Tom White. En el capítulo 13.6 "HBase vs RDMS", dijo que si tiene una gran cantidad de datos, incluso consultas simples como obtener 10 artículos recientes son extremadamente caros y tuvieron que reescribirlos usando Python y PL/SQL.Son RDBMS tan malos como se describen en Hadoop: ¿La guía definitiva?
Se da la siguiente consulta de ejemplo:
SELECT id, stamp, type FROM streams
WHERE type IN ('type1','type2','type3','type4',...,'typeN')
ORDER BY stamp DESC LIMIT 10 OFFSET 0;
Y dice: "Una consulta de RDBMS planificador trata esta consulta como sigue:
MERGE (
SELECT id, stamp, type FROM streams
WHERE type = 'type1' ORDER BY stamp DESC,
...,
SELECT id, stamp, type FROM streams
WHERE type = 'typeK' ORDER BY stamp DESC
) ORDER BY stamp DESC LIMIT 10 OFFSET 0;
El problema aquí es que estamos después de solo los 10 principales identificadores, pero la consulta planificador realmente materializa una fusión completa y luego limita al final .... Fuimos tan lejos como para escribir un guión PL/Python personalizado que realizó un heapsort. ... En casi todos los casos, este superó la implementación de SQL nativo y la estrategia del planificador consulta ...
perforamnce esperado y los resultados expermiental
no podía imaginar el conjunto de datos eso causará tales problemas que tienes que escribir pl/python para hacer una consulta tan simple a la derecha. Así que he jugado durante un tiempo sobre este problema y se produjeron las siguientes observaciones:
El rendimiento de dicha consulta está limitado por O (KlogN). Debido a que puede ser traducido a lo que algo de la siguiente manera:
SELECT * FROM (
SELECT id, stamp, type FROM streams
WHERE type = 'type1' ORDER BY stamp DESC LIMIT 10,
UNION
...,
SELECT id, stamp, type FROM streams
WHERE type = 'typeK' ORDER BY stamp DESC LIMIT 10
) t ORDER BY stamp DESC LIMIT 10;
(Nota de la LÍMITE 10 'a cada consulta BTW Yo sé que no puedo limitar y uniones de orden pero yo he despojado a cabo envolviendo a las selecciones. en aras de la legibilidad)
Cada sub consulta debe ejecutarse tan rápido como encontrar la posición correcta en un índice O (logN) y devolver 10 elementos. Si repetimos esa K veces obtenemos O (KlogN).
Y aunque el planificador de consultas es tan malo que no puede optimizar la primera consulta siempre podemos traducirlo a la consulta con uniones y obtener el rendimiento deseado sin escribir nada en pl/python.
Para verificar mis cálculos, he realizado las consultas sobre un postgresql lleno con 9,000,000 de registros de prueba. Los resultados confirmaron mis expectativas de que ambas consultas fueron bastante rápidas, 100 ms para la primera consulta y 300 ms para la segunda (la que tenía los sindicatos).
Así que si la consulta se ejecuta en 100ms para 9,000,000 (logn = 23) de registros, entonces para 9,000,000,000 (logn = 33) de registros debe ejecutarse en 140ms.
Preguntas
- , ¿existen otras fallas en el razonamiento anterior?
- ¿Se imagina un conjunto de datos en el que necesitaría volver a escribir la consulta anterior en pl/python?
- ¿Ve alguna situación en la que dicha consulta no funcionaría en O (K log n)?
No, no lo son. ¿Qué base de datos consulta una tabla completa una vez para cada elemento en un filtro de un campo, fusiona todos los registros, los ordena y luego limita al final? – MkV