Solution #1 - with the extra column, MySQL

Language: Layout:

DROP TABLE IF EXISTS bills;
    CREATE TABLE bills
    (
        id_interess     INT UNSIGNED    NOT NULL,   
        id_bill_tmp     INT UNSIGNED    NULL,
        id_bill         VARCHAR(30)     NULL,
        PRIMARY KEY (id_interess)
    ) ENGINE=InnoDB;

-- For testing purposes, populate sample data for a previous year so the first inserted value should be counted as a new year.
    INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (1, 1, '20160912-1');
    INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (2, 2, '20161030-2');
    INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (6, 3, '20161125-3');
    INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (10, 4, '20161231-4');

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        200,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        3,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        7,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        8,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        9,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        11,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        12,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        13,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        14,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        15,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
            IFNULL(
                (SELECT id_bill_tmp
                 FROM (SELECT id_bill_tmp
                       FROM bills
                       WHERE CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                             (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                                LPAD(SUBSTR(id_bill, 10), 10, 0)))
                              FROM bills)) b2),
                0),
            0)
            + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

INSERT INTO bills (id_interess, id_bill_tmp, id_bill) VALUES (
        16,
        IF(LEFT((SELECT id_bill FROM 
                 (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                    LPAD(SUBSTR(id_bill, 10), 10, 0))) AS id_bill
                  FROM bills) b1), 4) = DATE_FORMAT(CURDATE(),'%Y'), 
           IFNULL(
               (SELECT id_bill_tmp
                FROM (SELECT id_bill_tmp
                      FROM bills
                      WHERE CONCAT(LEFT(id_bill, 8),
                                   LPAD(SUBSTR(id_bill, 10), 10, 0)) =
                            (SELECT MAX(CONCAT(LEFT(id_bill, 8),
                                               LPAD(SUBSTR(id_bill, 10), 10, 0)))
                             FROM bills)) b2),
               0),
           0)
           + 1,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'), '-' , id_bill_tmp));

SELECT *
    FROM bills
    ORDER BY CONCAT(LEFT(id_bill, 8),
                    LPAD(SUBSTR(id_bill, 10), 10, 0));


absolute service time: 0,37 sec