Echando código: ¿Como encontrar el mayor número en una tabla (usando SQL), sin usar funciones de agregación (max, min)?

Esta es otra de las preguntas con las cuales pueden tratar de matarlo en una entrevista:

¿Como encontrar el mayor número en una tabla (usando SQL), sin usar funciones de agregación (max, min)?

Hmmm. ¿Interesante, no es así?. La pregunta busca ver sus conocimientos básicos de SQL y como ataca problemas.

Primero, antes de empezar a resolver este problema, vamos a hacer un par de preparativos, ya que la idea es que usted lo haga frente a un computador; Así que si no tiene instalado PostgreSQL 7.4 y Java le recomiendo que lo haga, así como tambien debería crear una base de dados para pruebas la cual llamaremos ‘test’:
Ahora vamos a crear las tablas necesarias para resolver el problema y vamos a llenarlas con datos.

[root@localhost pgsql]# createdb –user=postgres test –host=localhost.localdomain
CREATE DATABASE
psql –user=postgres –host=localhost.localdomain test –file src/sql/create_tables.sql
CREATE TABLE

[josevnz@localhost SQLProblem]$ cat src/sql/create_tables.sql
/*
* Test table that will hold our numbers and names.
* Author: Jose V Nunez Z
* Blog: El Angel Negro – http://elangelnegro.blogspot.com
* License: GPL
*/
— Table with users
create table users (
ages int not null,
names varchar(15)
);

Y ahora vamos a llenarlas de datos, usando un programita en Java que genera números aleatorios, los cuales pueden estar repetidos:

   1:import java.sql.SQLException;
2:import java.sql.PreparedStatement;
3:import java.sql.Statement;
4:import java.sql.DriverManager;
5:import java.sql.ResultSet;
6:import java.sql.Connection;
7:
8:import java.util.Random;
9:
10:import java.util.ResourceBundle;
11:
12:/**
13: * This program generates a series of random numbers for our problem.
14: * @author Jose V Nunez Z
15: * @version 0.1 - 03/09/2005
16: * @see http://elangelnegro.blogspot.com
17: */
18:public final class GenerateNumbers {
19:
20: private static final ResourceBundle BUNDLE =
21: ResourceBundle.getBundle(GenerateNumbers.class.getName());
22:
23: /**
24: * Program entry routine
25: * @param args - Ignored for now
26: * @throws Exception
27: */
28: public static void main(String [] args) throws Exception {
29: Connection con = null;
30: Statement stat = null;
31: PreparedStatement prep = null;
32: Random rand = new Random();
33: int max = 0;
34: try {
35: max = Integer.parseInt(BUNDLE.getString("maxNumbers"));
36: Class.forName(BUNDLE.getString("driver"));
37: con = DriverManager.getConnection(
38: BUNDLE.getString("url"),
39: BUNDLE.getString("user"),
40: BUNDLE.getString("password")
41: );
42: stat = con.createStatement();
43: stat.executeUpdate("truncate table users");
44: stat.close();
45: prep = con.prepareStatement("INSERT INTO users(ages, names) VALUES(?, 'dumb')");
46: for (int i=0; i < max; i++) {
47: prep.setInt(1, rand.nextInt(i+1));
48: prep.executeUpdate();
49: prep.clearParameters();
50: }
51: prep.close();
52: } catch (SQLException sqlex) {
53: throw sqlex;
54: } catch (NumberFormatException nfexp) {
55: throw nfexp;
56: } finally {
57: if (stat != null) {
58: try {
59: stat.close();
60: } catch (SQLException ignore) {
61: // Empty
62: };
63: }
64: if (prep != null) {
65: try {
66: prep.close();
67: } catch (SQLException ignore) {
68: // Empty
69: };
70: }
71: if (con != null) {
72: try {
73: con.close();
74: } catch (SQLException ignore) {
75: // Empty
76: };
77: }
78:
79: }
80: }
81:}

En SQL normal, usted sólo tendría que hacer esto para hallar al número más grande:

select max(ages) from users

Eso nos dá el número 9872 (para mi corrida de ejemplo). Vamos a pensar un poco como hacerlo sin esta función.

Lo primero que se me ocurrió es limitar la cantidad de resultados que vienen desde la base de datos. Con Java es trivial pero si lo quiero hacer con SQL entonces puedo usar la sintaxis propia de PostgreSQL:

test=# select ages from users order by ages desc limit 1;
ages
——
9872
(1 row)

test=# explain select ages from users order by ages desc limit 1;
QUERY PLAN
———————————————————————
Limit (cost=69.83..69.83 rows=1 width=4)
-> Sort (cost=69.83..72.33 rows=1000 width=4)
Sort Key: ages
-> Seq Scan on users (cost=0.00..20.00 rows=1000 width=4)
(4 rows)

test=#

No está tan mal. Otra forma es iterar por todos los resultados, sin ordernarlos y a medida que vamos obteniendo los resultados guardamos el valor de el número sólo si es mayor que el anterior. Asi no ordenamos, pero quizas la sobrecarga de esta operación es muy grande; Lo único es que debemos cargar el lenguaje ‘pgsql’ en la nueva base de datos, de lo contrario no podremos crear stored procedures:

[josevnz@localhost lib]$ createlang plpgsql test –user=postgres –host localhost.localdomain

El código en plpgsql:

13:-- Another solution: Use a cursor and some programming
14:CREATE OR REPLACE FUNCTION getmax() RETURNS integer AS '
15:DECLARE
16: biggest integer := 0;
17: curr integer := 0;
18: curs CURSOR FOR SELECT ages FROM users;
19:BEGIN
20: OPEN curs;
21: FETCH curs INTO curr;
22: WHILE FOUND LOOP
23: IF curr > biggest THEN
24: biggest := curr;
25: END IF;
26: FETCH curs INTO curr;
27: END LOOP;
28: CLOSE curs;
29: return biggest;
30:END;
31:' LANGUAGE plpgsql;

Y la salida de ejemplo:
test=# select getmax();
getmax
——–
9872
(1 row)

En teoria el stored procedure debería ser más eficiente que la salida anterior, ya que no hay que ordenar toda la tabla para luego sacar el primero de ese resultado.

Finalmente, esta solución la conseguí en un libro:

— This answer doesn’t work at all…
SELECT
distinct ages
FROM
users
WHERE
ages NOT IN (
SELECT a.ages FROM users a, users b WHERE a.ages).

Según PostgreSQL esto es lo que el query va a hacer:

QUERY PLAN
——————————————————————————
Unique (cost=11712.41..11714.91 rows=100 width=4)
-> Sort (cost=11712.41..11713.66 rows=500 width=4)
Sort Key: ages
-> Seq Scan on users a (cost=0.00..11690.00 rows=500 width=4)
Filter: (NOT (subplan))
SubPlan
-> Seq Scan on users b (cost=0.00..22.50 rows=334 width=4)
Filter: ($0 < test="">.

El costo es altisimo, además de que el query nunca finaliza ya que la sección en rojo genera un número exagerado de combinaciones…

Por cierto, el costo de usar la función de agregación ‘max’ es el menor de todas las alternativas (la rutina está bien optimizada):

test=# explain select max(ages) from users;
QUERY PLAN
—————————————————————
Aggregate (cost=22.50..22.50 rows=1 width=4)
-> Seq Scan on users (cost=0.00..20.00 rows=1000 width=4)
(2 rows)

test=#

Si usted conoce otra solución a este problema, mucho se lo agradeceré. Estuve pensandolo por un tiempo pero sólo pude llegar a esto :D. También le dejo un enlace a un buen libro de PostgreSQL.

Se puede bajar todo el ćodigo desde aquí.

One thought on “Echando código: ¿Como encontrar el mayor número en una tabla (usando SQL), sin usar funciones de agregación (max, min)?

  1. El post es un tanto antiguo, pero me encontré con el mismo problema y he encontrado una solución alternativa usando consultas correlacionadas.
    El ejemplo sería algo asi:
    select * from tabla t
    where
    0=(select count(*) from tabla t2 where t2.campo>t.campo)–solo devolverá los que no tengan un elemento mayor que ellos

    en relación a los costos, estimo que sera mas costoso que un MAX puesto que por cada valor del select externo recorre la tabla interna, lo bueno es que si tenes multiples valores maximos los devuelve de manera que podes usarlos para encontrar los elementos maximos de la tabla.
    No se si me expliqué.
    Saludos!
    Martin

Los comentarios estan cerrados