Solution #2 - without the extra column, MySQL

Language: Layout:

DROP TABLE IF EXISTS bills;
    CREATE TABLE bills
    (
        id_interess     INT UNSIGNED    NOT 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) VALUES (1, '20160912-1');
    INSERT INTO bills (id_interess, id_bill) VALUES (2, '20161030-2');
    INSERT INTO bills (id_interess, id_bill) VALUES (6, '20161125-3');
    INSERT INTO bills (id_interess, id_bill) VALUES (10, '20161231-4');

INSERT INTO bills (id_interess, id_bill) VALUES (
        200,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        3,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        7,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        8,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        9,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        11,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        12,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        13,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        14,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        15,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

INSERT INTO bills (id_interess, id_bill) VALUES (
        16,
        CONCAT(DATE_FORMAT(CURDATE(),'%Y%m%d'),
               '-' ,
               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 SUBSTR(MAX(CONCAT(LEFT(id_bill, 8),
                                                       LPAD(SUBSTR(id_bill, 10), 10, 0))), 9) AS id_bill_tmp
                              FROM bills) b2),
                       0),
                   0)
                   + 1));

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


absolute service time: 0,37 sec